Sok olyan feladat van, amelyet a matematikusok is csak nehezen, minden trükköt bevetve tudnak megoldani, majd egy-két évre rá az újabb, sokkal gyorsabb, nagyobb kapacitású gépek játszva elvégzik. Úgy tűnhet hát, hogy kár erőltetni a bonyolult matematikai módszereket. Ám ha jobban belegondolunk, ennek az ellenkezője igaz: a technikai fejlődés olyan feladatokat állít elénk, amelyeket csak vérbeli matematikai módszerekkel lehet megoldani. Mert megérthető-e egzakt matematikai gondolkodás nélkül az internet, amely több százmillió számítógépet köt össze egymással? Tervezhető-e egzakt matematikai módszerek nélkül modern integrált áramkör, amelyben 50 millió számítási alapegység van egy négyzetcentiméteren összezsúfolva? Lehet-e pontos matematikai modellezés nélkül gondolkodni olyan rendszer biztonságáról, amelyet milliárdnyi ember használ, akiket nem ismerünk – de tudjuk, hogy vannak köztük bűnözők és terroristák is?
Nyilvánvalóan nem. A matematika tehát nagyon is sokat nyújt a számítástechnikának. De mit kap cserében? Nagyon sok mindent: izgalmas, új fogalmakat, problémákat és módszereket, új kísérletezési lehetőségeket. Ezek közül nézzünk meg néhányat.
A XIX. századi matematika nagy sikere a végtelen fogalmának megragadása volt. Ennek bűvölete olyan erős, hogy hajlamosak vagyunk mindenre, ami véges, rálegyinteni: „véges sok eset van, amit egyenként végig lehet nézni!” A számítógépek megjelenése eredményezte, hogy rájöttünk: a véges is lehet olyan nagy, hogy gyakorlatilag már kezelhetetlen. E felismerésből nőtt ki a bonyolultság új, matematikailag pontosan meghatározható fogalma.
A klasszikus történet szerint az unalma elűzéséért hálás király a sakkjáték feltalálójának felajánlotta, hogy azt kívánhat jutalmul, amit akar. A feltaláló azt kérte, hogy a sakktábla első mezejére tegyenek egy búzaszemet, a másodikra kettőt, a harmadikra négyet, a negyedikre nyolcat, és így tovább, minden mezőre kétszer annyit, mint az előzőre. A király nagyon megörült, hogy ilyen olcsón megúszta, de aztán rá kellett jönnie, hogy nemcsak a 10–12. mezőtől nem férnek el a búzaszemek, de a tábla közepe táján már birodalmának teljes búzatermése sem lenne elegendő ígéretének betartásához.
Ezt a jelenséget, hogy egy mennyiség az ismételt duplázással igen gyorsan növekszik, exponenciális robbanásnak hívjuk. A számítástudományban az exponenciális robbanással a leggyakrabban akkor találkozunk, ha azt a kijelentést, hogy „véges sok eset van, amit végig lehet nézni!”, megpróbáljuk közelebbről megvizsgálni. Mondjuk az esetek megkülönböztetéséhez először két alapesetet kell megkülönböztetni, aztán ezek mindegyikén belül két újabb eset van, azokon belül ismét kettő, és így tovább. Ezt a logikai helyzetet egy szerteágazó hálózattal, úgynevezett bináris fával ábrázolhatjuk, amelyben az „ágak” száma szintenként megduplázódik. Látható, hogy már néhány elágazás után is a végignézendő esetek száma ugrásszerűen nő, és bekövetkezik az exponenciális robbanás. Ha algoritmusunk egy ilyen fát vizsgál, akkor ezt a modern számítógépek mondjuk 30 szintig bírják. S ezen még a számítógépek rohamos fejlődése sem segít: ha tíz évig várunk, akkor talán öt szinttel tudunk továbbmenni.
Ezért a számítástudományban elég hamar megfogalmazódott, hogy olyan algoritmusokra kell törekedni, amelyek lépésszáma a feladat méretével csak mérsékelten, a méret valamilyen hatványával nő, nem pedig exponenciálisan. Tehát ha a feladat mérete n, akkor a lépésszám lehet n2 vagy n3 (polinomiális algoritmus), de nem lehet 2n. A kétfajta növekedés közötti különbséget legjobban azon mérhetjük le, hogy mennyit lehet várni a technológia fejlődésétől. Tegyük fel, hogy ma mind az A, mind a B algoritmus 50 bemenő adattal tud egy adott problémát megoldani. Az A algoritmus lépésszáma úgy nő a bemenő adatok számával, mint n3, a B algoritmusé pedig mint 2n. Ha várunk tíz évet, és eközben a számítógépek teljesítménye a mainak 32-szeresére nő, akkor az A algoritmus már 150 bemenő adattal birkózik meg, míg a B algoritmus teljesítőképessége csak 55-re emelkedik.
A matematikai feladatokat megoldó algoritmusok lépésszámigényét (gépi futásidejét) ma már a matematika új ága, az úgynevezett bonyolultságelmélet vizsgálja. E látszólag igen elvont kérdések sokszor nagyon gyakorlatias célokat szolgálnak.
Hadd mutassam be ezt egy fontos példán! Egy pozitív egész számot prímszámnak nevezünk, ha 1-en és önmagán kívül más egész számmal nem osztható. Az 1-et nem tekintjük prímnek, de utána sok szám sorjázik: 2, 3, 5, 7, 11, 13 stb. Azok a természetes számok pedig, amelyek nem prímek, felbonthatók prímszámok szorzatára, például: 6 = 2 l 3, 40 = 2 l 2 l 2 l 5 stb.
A prímszámokkal kapcsolatban két fontos algoritmikus problémát fogalmazhatunk meg: ha adott egy k jegyű szám, hogyan tudjuk eldönteni róla, hogy prímszám-e; illetve ha nem prímszám, hogyan tudjuk megtalálni a prímtényezőit?
Mindkét kérdésre könnyű „véges” választ adni: csak ki kell próbálni, hogy osztható-e a szám kettővel, hárommal, öttel stb. Ha találunk olyan számot, amelyik osztója, akkor tudjuk, hogy nem prímszám, és a felbontást is könnyű megcsinálni. A baj az, hogy iszonyú sok számot kell kipróbálni: ahhoz, hogy egy 100 jegyű számról eldöntsük, prím-e, 10 100 számot kell kipróbálni, ami nagyobb, mint a világegyetem bármely paramétere. Kis ravaszsággal rájöhetünk, hogy elegendő a szám négyzetgyökéig kipróbálni a számokat. De ez sem segít eleget: egy 100 jegyű szám négyzetgyöke 50 jegyű, és 1050 is messze túl van lehetőségeink határán.
Tovább vizsgálódva kiderül, hogy az első kérdés sokkal kevésbé „bonyolult”, mint a második: vannak olyan hatékony (polinomiális) algoritmusok, amelyek akár 1000 jegyű számról is könnyedén eldöntik, hogy prím-e. A tényezőkre bontás viszont csak olyan algoritmust ismer, amely lényegében exponenciális: 100-nál több jegy esetén már csak nagy üggyel-bajjal működik, 150 jegy fölött pedig egyáltalában nem. Később még látni fogjuk, hogy ennek az egyszerű ténynek rendkívül fontos gyakorlati következményei vannak.
Másik fontos terület, ahol az informatika egy új fogalomhoz vezetett, a matematikai bizonyításoké, ahol megjelent az interaktív bizonyítás.
Alan Turing angol matematikus, a számítógép-tudomány egyik megalkotója azon töprengett, vajon hogyan lehet megkülönböztetni az embertől egy nagyon fejlett számítógépet. Azt a kísérletet javasolta, hogy egy szobába ültessünk be valakit egy képernyővel és billentyűzettel, míg a másik szobába másik embert ültessünk hasonló képernyővel és billentyűzettel, vagy párbeszédre képes interaktív számítógépet tegyünk. Az első ember kérdéseket tehet fel, vagy bármi egyéb módon társaloghat a másik szobában lévő „lénnyel”, és ennek alapján el kell döntenie, hogy emberrel vagy géppel áll-e szemben. Ezt a kísérletet nevezik Turing-tesztnek.
Hinnénk-e, hogy ezt a nyilvánvalóan csak gondolatkísérletnek szánt tesztet naponta sok ezerszer végzik el? Ha valaki új e-mail számlát akar nyitni, ilyen kéréssel találkozik: „Kérjük, gépelje be az alábbi betűket”, és alatta kicsit piszkos alapon néhány kissé elmosódó, kuszán odavetett betűt lát. Ha nem érti, mire való ez, rákattinthat a „Miért?” szövegre, és megtudja, hogy azért van rá szükség, mert sok program van, amely automatizálja a levelezőszámlák nyitását (hogy aztán hirdetéseket küldjön szét róluk, vagy ami rosszabb, levelek tömeges küldésével megbénítson valakit). A képernyőn az emberi szem könnyedén felismeri a betűket, de (legalábbis ma) egy számítógépet a betűk torzulásai és a kusza vonalak megtévesztenek, így az a teszten megbukik, és a programozott számlanyitások kiszűrhetők.
Ez az eljárás az interaktív bizonyítás szép példája: két résztvevő van, és ez esetben a bizonyító azt a „tételt” akarja bebizonyítani, hogy ő ember. A hagyományos matematikában a tételhez hozzá lehet csatolni a bizonyítást – itt azonban van egy ellenőr, aki egy vagy több kérdést tesz föl, és a „bizonyítás” a kérdéstől függ. A séma sokkal erősebb – gondoljunk csak bele, hogyan tudnánk kérdés nélkül bebizonyítani, hogy emberek vagyunk.
Hasonló interaktív bizonyítások lépten-nyomon használatban vannak: jelszavak, „okos kártyák” stb. Számítógépes hálózataink biztonsága nagyrészt ilyeneken múlik. Hadd mutassak be egy nagyon leegyszerűsített példát. Tegyük fel, hogy Aliz és Béla interneten keresztül sakkozik. Beesteledett, és meg kell szakítani a mérkőzést. Hagyományos sakkversenyen ilyenkor az történik, hogy mondjuk Aliz eldönti az utolsó lépést, de nem teszi meg a táblán, hanem borítékolja, és odaadja a bírónak. A borítékot Béla csak másnap nyithatja ki. Így egyikük sem ismeri a másik utolsó lépését, ezért nincs meg az az előnye, hogy egész éjjel gondolkodhat a következő lépésen.
De most nincs bíró és nincs boríték. Aliz üzenhet valamit Bélának este, és megmondhatja a lépését másnap reggel, de mit üzenjen este? Ha már esti üzenetével elkötelezi magát, akkor Béla előnyben lesz; ha nem, akkor Aliz lesz előnyben, mert megváltoztathatja a lépést az éjszaka folyamán. A hagyományos információelmélet szerint a „borítékolás” lehetetlen.
A bonyolultságelmélet azonban megoldást kínál erre. Előre megállapodnak abban, hogy a lépéseket egy-egy négyjegyű számmal írják le: Kf3 helyett mondjuk azt mondják, hogy 9083. Ezek után Aliz választ magának két 100 jegyű prímszámot, amelyek közül a kisebbik úgy kezdődik, hogy 9083… (Számítógéppel nem nehéz ellenőrizni, hogy egy szám prímszám-e; be lehet bizonyítani a klasszikus matematika eszközeit felhasználva, hogy ha néhány száz 100 jegyű számot találomra kipróbál, ezek között lesz prím.) Legyen ez a két szám p és q, ahol p < q. Este Aliz elküldi a pq szorzatot Bélának, reggel pedig elküldi a két tényezőt (ami annak felel meg, hogy felbontja a borítékot).
Láthatjuk, hogy Béla már előző este megkapta a teljes információt: egy kb. 200 jegyű természetes számot; a kisebbik prímtényezőjének első négy jegye megadja Aliz lépését. De mivel a számot nem tudja hatékonyan tényezőire bontani, a lépést másnap reggelig (vagy akár évekig) nem tudja ebből kiolvasni. Ezt a „titkot” hét pecsétként őrzi a számítás bonyolultsága!
Ennél sokkal bonyolultabb módon, de azért hasonló gondolatokat használva valósíthatók meg digitálisan a társadalmi érintkezés olyan fontos elemei, mint a mások által felbonthatatlan boríték (titkosírás), elismervény, számla, aláírás és annak hitelesítése, vízjel stb.
A klasszikus matematikát sokan elefántcsonttoronyként kezelik. Godfrey Hardy, aki a prímszámok elméletének egyik legkiemelkedőbb kutatója volt a XX. század első felében (tehát még a számítógépek korszakát megelőzően), ezt írja Egy matematikus védekezése című könyvében:
„Soha nem tettem semmi »hasznosat«. Semelyik felfedezésem sem volt, és nem valószínű, hogy valaha is legyen, közvetlenül vagy közvetve, jó vagy rossz hatással a világ folyására…
Az »igazi« matematikusok »igazi« matematikája, Fermat és Euler és Gauss és Abel és Riemann matematikája csaknem teljesen »haszontalan«”.
A számítógépek megjelenése és elterjedése azonban alaposan rácáfolt erre. Ma, amikor az interneten vásárolunk, vagy bankügyeket intézünk, számítógépünknek több száz jegyű számokról kell eldöntenie tizedmásodpercek alatt, hogy prímek-e. Ehhez Fermat tételét használja. A különböző számítógépes protokollok, biztonsági módszerek a Hardy által felsorolt nagyságok szinte mindegyikének a munkájára építenek.
Pedig ha e nagyságokat csak kutatásuk közvetlen haszna motiválta volna, és nem a matematikai kérdések szépsége, a megismerés vágya, akkor ma nem lennének eszközeink a számítógéprendszerek biztonságvédelmére!
www.mindentudas.hu
Szóljon hozzá!
Jelenleg csak a hozzászólások egy kis részét látja. Hozzászóláshoz és a további kommentek megtekintéséhez lépjen be, vagy regisztráljon!