Cím: A szerkesztő megjegyzése (1987. március)
Szerző(k):  Csirmaz László 
Füzet: 1987/március, 104. oldal  PDF  |  MathML 
Témakör(ök): Egyéb írások

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 cn elemszámú valamilyen c>1, n-től független konstanssal) szénakazalban keres egy tűt : egy helyes (vagy a helyes) megoldást. Ilyen jellegű algoritmusok nagyobb n-ekre (n=10 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):

 

n    1    2    3    4    5    6    7    8    9  a csomópontok száma    1    2    10    48    212    1018    6546    47 973  379 777  a megoldások száma    1    -    -    8    21    -    -    3 040    20 505  

 

Így például n=9-re tetszőleges csomópontot választva 5%-nál nagyobb valószínűséggel egy megoldást találunk el!
Szóval az, hogy a 3. program n64-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 n-et akár eggyel is növelni tudjuk. Az, hogy a 3. program nagy n-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.