Lovász László

Napjainkban teljesen magától értetődőnek tűnik, hogy munkánk során számítógépet használunk, internetezünk, bankkártyával fizetünk vagy meghallgatunk egy CD-lemezt. Ilyenkor talán végig sem gondoljuk, hogy ezek egyikét sem tehetnénk meg, ha nem jöttek volna létre a matematika új ágai: az algoritmuselmélet, a kriptográfia vagy a bonyolultságelmélet. Gondolnánk-e, hogy adatvédelmünk, a katonai létesítmények, a bankrendszer, s így a gazdaság biztonsága azon is múlik, hogy egy elég nagy szám felbontható-e belátható időn belül prímszámok szorzatára? Miért fontos tudni egy számról, hogy azt véletlen módon adták-e meg nekünk vagy valamilyen algoritmus eredményeként? Milyen régi problémák megoldásában segíthet nekünk a számítógép s melyekben nem? Ezekre az izgalmas, mindannyiunkat érintő kérdésekre keresi a választ az előadás.

I. Bevezetés
A számítógép a 20. század hatalmas forradalma. A hardver fejlődése felveti a kérdést: nem válnak-e feleslegessé a matematikai módszerek a programozásban. Feleslegessé teszik-e a számítógépek a matematikát vagy inkább inspirálóan hatnak rá?

II. A bonyolultság új fogalma
A bonyolultság régen a megoldást nehezítő körülményt jelentette. Mára a számítógépes kommunikáció biztonságának legfőbb záloga.

II. 1. Exponenciális robbanás
Azt a jelenséget, ha egy mennyiséget ismételten egy egynél nagyobb számmal szorzunk, az igen gyorsan növekszik, exponenciális robbanásnak hívjuk. Miért fontos a számítástudományban, hogy elkerüljük a szükséges lépésszámok exponenciális robbanását?

II. 2. Prímtesztelés és -faktorizáció
Bármely nem prím, egész szám felbontható prímszámok szorzatára - ez a prímfaktorizáció. Vajon el tudjuk-e dönteni belátható időn belül egy számról, hogy prím-e, s ha nem az, akkor meg tudjuk-e adni a prímfaktorizációját?

III. A véletlen új fogalma(i)
A véletlen a modern tudomány egyik sarkalatos fogalma. Szinte minden tudomány használ olyan modelleket, melyekben a jelenségek véletlen, statisztikus jellege dominál.

III. 1. Mitől nem véletlen egy sorozat?
Ha megadnak nekünk egy fej-írás sorozatot, vajon el tudjuk-e dönteni, hogy ez pénzfeldobások eredményeként jött létre vagy valamilyen algoritmus következményeként?

III. 2. Információtartalom és véletlenség
Egy sorozat hossza és információtartalma nem feltétlenül függ össze. Hogyan lehet a véletlenséget matematikai precizitással definiálni?

III. 3. Véletlen és álvéletlen
A számítógépek által generált számok nem véletlenek, hanem ún. álvéletlen számok. Milyen kritériumoknak kell megfelelniük a véletlenszám-generátoroknak, hogy a kapott eredményeket el tudjuk fogadni véletlenként?

IV. A bizonyítás új fogalma
A bizonyítás a matematika lelke, a görög tudomány talán legfontosabb alkotása.

IV. 1. Interaktív bizonyítás
Alan Turing, angol matematikus vetette fel a kérdést, hogy vajon hogyan lehet megkülönböztetni egy nagyon fejlett számítogépet egy embertől. Mikor találkozunk efféle tesztekkel?

IV. 2. Elektronikus boríték
Számítógépes hálózataink, bankrendszerünk, katonai létesítményeink biztonsága többek között a prímtesztelésen és prímfaktorizáción múlik. Hogyan borítékolhatja lépését egy internetes sakkmeccs résztvevője?

V. Klasszikus kérdések új megvilágításban
Néha maguk a matematikusok is azt állítják, tudományuk "haszontalan". Hogyan kapcsolodik a klasszikus matematika a mindennapi életünk során felhasznált számítástudományhoz?

elkezdem olvasni