A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. A számítógépek másképpen és másra is használhatók, mint ahogyan az a köztudatban általánosan elterjedt. Kós Géza cikke egy ilyen számítógépes (el)kalandozást ír le: egy érdekes matematikai probléma tisztázásához számítógépet használ kísérleti eszközként. Matematikai kísérleteket végez, hogy az eredményt megsejtse, és a kísérletek mutathatják, hogy a megsejtett állítás bizonyítását milyen úton, merrefelé érdemes keresni. A cikkben megfogalmazott sejtést az elvégzett kísérletek igazolták, azonban nem vezettek annak bizonyításához. (A sejtésről egyébként nem tudjuk, hogy igaz-e vagy sem; lehet hogy bevonul a "nagy'' megoldatlan feladatok közé?) A cikkben megfogalmazott eljárás az úgynevezett "kereső algoritmusok'' közé tartozik. Ennek általános jellemzője, hogy egy exponenciális méretű (azaz legalább elemszámú valamilyen , -től független konstanssal) szénakazalban keres egy tűt : egy helyes (vagy a helyes) megoldást. Ilyen jellegű algoritmusok nagyobb -ekre ( rendszerint már nagynak számít!) általában kivárhatatlanul sokáig futnak. Két kivétel van: a szalmakazalban olyan sok tű van, hogy akárhol túrunk bele, kezünkbe szúr egy, vagy pedig ott keressük a tűt, ahol van. A cikkben leírt három program egyre jobb helyen kereste a "tűt''; ezt mutatja a futási idők csökkenése. Ugyanakkor rengeteg "tű'' is van a kazalban (már ahol van egyáltalán):
Így például -re tetszőleges csomópontot választva -nál nagyobb valószínűséggel egy megoldást találunk el! Szóval az, hogy a 3. program -re ellenőrizni tudta a sejtés helyességét, sokkal inkább a szerencsének, a feladat speciális tulajdonságainak, semmint az algoritmus gyorsaságának, általános voltának tulajdonítható. Sok más kereső feladat azt a tapasztalati tényt támasztja alá, hogy a cikkben leírt típusú javítgatások nem segítenek, nem csökkentik a keresés idejét annyira, hogy -et akár eggyel is növelni tudjuk. Az, hogy a 3. program nagy -ekre is gyorsan fut, azt mutatja, hogy
a) valószínűleg rengeteg megoldás van; b) a megoldások arrafelé vannak, ahol a 3. program keresi őket. Ezek egyúttal azzal is biztatnak, hogy a sejtést mégiscsak be lehet bizonyítani ‐ bár útmutatást ehhez nem adnak. Mindezzel mindössze arra szerettem volna felhívni a figyelmet, hogy a kereső algoritmus "apró'', nem lényegi javításai általában semmit nem használnak ‐ ámbár akadnak kivételek. Ez semmit nem von le Kós Géza érdemeiből: a fociban is csak jó kapusnak van szerencséje.
|