Új Szó, 2003. július (56. évfolyam, 150-175. szám)

2003-07-07 / 154. szám, hétfő

ÚJ SZÓ 2003. JÚLIUS 7.

Mindentudás egyeteme

Új fogalmak, problémák, módszerek és paradigmák - Kutatások az elektronikus boríték, elismervény, számla és aláírás biztonságáért - A titokzatos prímszámok világa

Feleslegessé teszik-e a számítógépek a matematikát?

A számítógépek a 20. század igazi forradalmát jelentik.

Az elmúlt század második felét szokás „atomkorszak”- ként emlegetni, pedig a „számítógépek korszaka” pontosabb leírás volna. Lovász László a Mindentudás Egyetemén tartott előadásában kizárólag a matematika szempontjából vette szemügyre a számítógépeket.

LOVÁSZ LÁSZLÓ ELŐADÁSA

Minden nagy fejlődés sok olyan dolgot tesz fölöslegessé, mely korábban fontos, sőt alapvető volt. Vajon odakerül a matematika is a logarléc és a gőzmozdony mellé? Vagy éppen ellenkezőleg, a számítógépek igénye a matematika új fejezeteit hívja létre és a régi fejezeteket egészen új megvilágításba helyezi?

A felvetett probléma gyakran konkrétabb formában is megfogalmazódik: Nem teszi-e feleslegessé a hardver fejlődése a matematikai módszereket a programozásban? A hardver hihetetlen fejlődését a Moore törvényével lehet leírni. Az Intel egyik alapítója 1965-ben azt a megfigyelést tette, hogy az egy-egy integrált áramkörben használt tranzisztorok száma mintegy 2 évenként megduplázódik. Ez a gyors fejlődés azóta is tart. Egykor rádiócsöves gépeken gyűjthettek tapasztalatokat a matematikusok; minden ilyen cső egy-egy számítási alapegységet, „kaput” valósított meg. Ma a számítógépek egy négyzetcentiméterén 50 millió ilyen kapu van! És vajon meg lehet-e térMINDENTUDÁS

EGYETEME

robbanásnak hívjuk. Moore említett törvényében az a meglepő, hogy az informatikában bekövetkezett exponenciális robbanás ilyen sokáig tud tartani. Az 1960-as évek környezetvédelmi forradalma mögött az áll, hogy egyre többen értették meg, hogy az exponenciális növekedés nem tarthat örökké, sem a népesség, sem a termelés, sem a fogyasztás területén.

A számítástudományban az exponenciális robbanás leggyakrabban akkor lép fel, ha azt a kijelentést, hogy „Véges sok eset van, amit végig lehet nézni!”, megpróbáljuk közelebbről vizsgálni. Mondjuk, az esetek megkülönböztetéséhez először is két alapesetet kell megkülönböztetni; aztán ezek mindegyikén belül két újabb eset van és így tovább. A végignézendő esetek száma már néhány elágazás után is ugrásszerűen nő, és bekövetkezik az exponenciális robbanás. Ha algoritmusunknak egy ilyen bináris fát kell végigvizsgálnia, akkor a modern számítógépek nagyjából 30 szint mélységig még bírják, de minden egyes újabb szint megdupvezni egzakt matematikai módszerek nélkül egy modern integrált áramkört, ahol 50 millió számítási alapegység van egy négyzetcentiméteren összezsúfolva?

Vagy továbblépve: meg lehet-e érteni egzakt matematikai gondolkodás nélkül az Internetet, ami több százmillió számítógépet köt össze egymással? Lehet-e pontos matematikai modellezés nélkül gondolkodni egy 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?

A BONYOLULTSÁG ÚJ FOGALMÁRÓL - EGYSZERŰEN

lázza az esetek számát. Itt még Moore törvénye sem segít: ha 10 évig várunk, akkor is csak 5 szinttel tudunk továbbmenni.

Ezért aztán a számítástudományban elég hamar megfogalmazódott, hogy olyan algoritmusok tervezésére kell törekedni, melyek lépésszáma a feladat méretével csak mérsékelten nő, úgy, mint a méret egy hatványa, nem pedig exponenciálisan. Tehát ha a feladat mérete n, akkor a lépésszám lehet n2 vagy n3, de nem lehet 2n. Az ilyen algoritmust polinomiálisnak szokás nevezni. A probléma jelentőségét jól szemlélteti a prímszámok tesztelésének példája.

A TITOKZATOS PRÍMEK

A sakkjáték feltalálójáról szóló klasszikus történet szerint az unalma elűzéséért hálás király felajánlotta neki, 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, hogy a 10-12-ik mezőtől már 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 lett volna elegendő, hogy ígéretét betartsa.

Ezt a jelenséget, hogy ha egy mennyiséget ismételten duplázunk (vagy bármilyen egynél nagyobb számmal szorzunk), akkor igen gyorsan növekszik, exponenciális

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 aztán sok példát látunk: 2, 3, 5, 7, 11, 13 stb. Azokat a természetes számokat, melyek nem prímek, fel lehet bontani prímszámok szorzatára, például 6=2*3, 40=2*2*2*5 stb. - ezt a felbontást nevezzük prímfaktorizá- ciónak.

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; és 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 2-vel, 3- mal, 4-gyel, 5-tel. Ha találunk

Godfrey Harold Hardy

0877-194?)

LOVÁSZ LÁSZLÓ matematikus

Lovász László Budapesten született 1948-ban. A Fazekas Mihály Gyakorló Gimnázium első matematika tagozatos osztályába járt. Szinte minden matematika versenyt megnyert (Ki miben tudós?, KöMaL, OKTV, Nemzetközi Matematikai Diákolimpia, Schweitzer- verseny stb.). Az ELTE matematikus szakán végzett 1971-ben. Negyedéves egyetemistaként megvédte a gráfok faktorairól írt kandidátusi disszertációját. Világhírű eredménye a perfekt gráfsejtés bizonyítása volt. 1979-ben megoldotta az információelmélet egyik legnevezetesebb problémáját, a Shannon-problémát. Cikke az év

publikációja lett az IEEE Transaction Information Theory c. folyóiratban. 31 éves korában lett akadémikus. Az algoritmikus gondolkodásmód elterjesztésének úttörője, az elméleti számítógép-tudomány egyik vezéralakja. 1999- ben megkapta a matematikusok Nobel-díjának tartott Wolf-díjat.

MINDENNAPOS INTERAKTÍV BIZONYÍTÁS TURING-TESZTTEL

A bizonyítás a matematika lelke, a görög tudomány talán legfontosabb alkotása. Mégis, az iskolai matematikatanításból sokszor kimarad. Gyakran még egyetemi hallgatók sem értik, miért van rá szükség: „Elhisszük mi a tanár úrnak, minek azt bizonygatni.” A Pi- tagorasz-tételre már nagyon-na- gyon sok bizonyítást talált az emberiség, és világos, hogy a bizonyításon nem azért kell végigmenni, hogy a tétel helyességéről még jobban meg legyünk győzve, hanem azért, hogy a bizonyításban szereplő matematikai módszereket elsajátítsuk. A programok helyessége, a kommunikációs protokollok biztonsága nap mint nap bizonyítást igényel (ne).

Alan Turing angol matematikus, a számítógép-tudomány egyik megalkotója azon gondolkodott, hogy vajon hogyan lehet megkülönböztetni egy nagyon fejlett számítógépet egy embertől. Azt a kísérletet javasolta, hogy egy szobába ültessünk be egy embert egy képernyővel és billentyűzettel, míg a másik szobába vagy egy másik embert ültessünk hasonló képernyővel és billentyűzettel, vagy egy 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 levő lénnyel, és el kell döntenie ennek alapján, 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

olyan számot, amelyik osztója, akkor tudjuk, hogy nem prímszám, és a felbontást is könnyű megcsinálni. Csakhogy ehhez iszonyú sok számot kell kipróbálni: ahhoz, hogy egy 100 jegyű számról eldöntsük, hogy prím-e, 10 100 számot kell kipróbálni, ami nagyobb, mint a világegyetem bármilyen paramétere. Az első kérdés mai ismereteink számára sokkal könnyebb, mint a második: olyan hatékony (polino- miális) algoritmusok vannak, amelyek akár 1000 jegyű számról is könnyedén eldöntik, hogy prím-e. A tényezőkre bontásra azonban csak olyan algoritmus ismert, amely lényegében exponenciális: 100-nál több jegy esetén már csak nagy üggyel-bajjal működnek, 150 jegy fölött pedig egyáltalában nem. Ennek az egyszerű ténynek hallatlan gyakorlati következményei vannak.

Azt gondolnánk, hogy a teszteléshez és a faktorizációhoz is végig kell próbálni az adott számnál kisebb számokat, hogy nem osztha- tó-e velük az adott szám. Ez azonban nagyon hosszadalmas lenne, valahogy másképp kell tehát eljárnunk. A hatékony prímtesztelő algoritmusok az ún. „kis” Fermat-té- telen alapulnak (a „kis” jelző nem a tétel fontosságára utal, csak így különböztetjük meg a csak nemrégen bebizonyított „nagy” Fermat- tételtől. Fermat, a nagy 17. századi francia matematikus ugyanis csak az előbbinek a bizonyítását adta meg.)

Fermat tétele szerint, ha p prímszám, és a tetszőleges egész szám, akkor p/ap-a, vagyis p osztója az ap-a számnak. Ha egy p számról el akarjuk dönteni, hogy prímszám-e, akkor megnézzük, hogy 2p-2, 3p-3 stb. oszthatók-e p-vel. És ezt nem kell nagyon sok számra kipróbálni, elegendő csak néhányra, vagyis sikerült kikerülnünk az exponenciális robbanás csapdáját.

MITŐL VÉLETLEN A VÉLETLEN?

csit piszkos alapon néhány kuszán odaírt betűt lát. Erre azért van szükség, mert sok program van, amely automatizálja a címek létrehozá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épen az emberi szem könnyedén felismeri a betűket, de egy számítógépet (ma még legalábbis) a betűk torzulásai és a kusza vonalak megtévesztenek, így a programozott címgenerálást ki lehet szűrni. A mai számítógépek még nagyon gyorsan megbuknak a Turing-teszten, bár érdemes azt is megemlíteni, hogy itt a tesztet magát nem ember, hanem egy számítógép hajtja végre.

A fenti eljárás az interaktív bizonyítás szép példája: két résztvevő van, és ebben az 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. Ez a séma sokkal erősebb a hagyományos bizonyítási formáknál - gondoljunk csak bele, hogyan tudnánk kérdés nélkül bebizonyítani, hogy emberek vagyunk?

A KÖZHASZNÚ ELEFÁNTCSONTTORONY

Godfrey Hardy, a prímszámok elméletének egyik legkiemelkedőbb

közvetve jó vagy rossz hatással a világ folyására, és nem valószínű, hogy valaha is hatással lesz... Az. „igazi” matematikusok „igazi” matematikája, Fermat és Euler és Gauss és Abel és Riemann matematikája csaknem teljesen „haszontalan”.

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, hogy prímek-e - tizedmásodpercek alatt. 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. Napjaink legnagyobb jelentőségű megoldatlan matematikai problémája pedig minden bizonnyal így fogalmazható meg: Prímtényezőire lehet-e bontani egy 1000 jegyű számot hatékonyan (nem-csillagászati idő alatt)?

E tények Hardy kutatási elveit legalább annyira alátámasztják, mint amennyire az állításait cáfolják. Ha a felsorolt tudósokat 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ép-rendszerek biztonságának védelmére.

Készítette az M&H Communications szabad felhasználásra, a szerzői jogok korlátozása nélkül.

Véletlen-e az, hogy egy földobott pénz fejre vagy írásra esik? A valóságban (talán a kvantumfizikát leszámítva) csupa olyan „véletlen” jelenséggel találkozunk, melyek igazából nem véletlenek, csak megjóslásukhoz nem áll rendelkezésre elegendő adat és idő. Képzeljük el a pénzfeldobások olyan sorozatát, amelyet nem tudnánk egyszerűen leírni, definiálni: semmi más értelmes módon nem volna leírható, mint azzal, hogy felsoroljuk az elemeit. Pontosan ezzel definiálhatjuk a véletlen sorozatot: egy sorozat akkor véletlen, ha nem írható le rövidebben, mint a saját hossza. Általánosabban megfogalmazva azt nevezzük egy sorozat vagy bármilyen más struktúra, kép információtartalmának (információs bonyolultságának), hogy milyen hosszú a lehető legrövidebb leírása, mennyire lehet tömöríteni a sorozatot a lehető leghatékonyabb kódolást használva.

Egy sorozat információtartalmának a definíciója rengeteg izgalmas és máig megoldatlan kérdéshez vezet: Mekkora a genetikus kód, például egy emberi kromoszóma információtartalma? Mekkora az agy bonyolultsága? Milyen nagyságrendű az egész világegyetem bonyolultsága?

tesztet naponta sok ezerszer végzik el? Ha valaki például új e-mail címet akar csinálni magának, ilyesféle kérdéssel találkozhat: „Kérjük, gépelje be az alábbi betűket”, és ki20. századi, ezt írta Egy matematikus védekezése című könyvében: Soha nem tettem semmi „hasznosat”. Semelyik felfedezésem sem volt közvetlenül vagy