„A jó kérdés jogosságát, értékét mindenki elismeri”

Staar Gyula: Egy diszkrét matematikus. Beszélgetések Lovász Lászlóval. Typotex, 2026

Egy rövid kérdés-felelet részlet a könyvből:

Mit tartasz az elmúlt évtizedek legnagyobb hatású felismerésének a matematikában?

Egyik ilyen felismerés, hogy az algoritmusok a matematika eszközeivel vizsgálható, nagyon izgalmas problémákhoz vezetnek. A másik fontos fejlemény, hogy a véletlen módszerek a matematika legkülönbözőbb ágaiban sorra meghonosodnak. Kiindulásnak Erdős Pál cikkét szokták említeni, az 1950-es évekből. Kiderült, hogy a véletlen olyan algoritmusokat is ad, melyeket más eszközökkel nem érhetünk el. Például a számítógépeinkben fut az RSA-rendszer, ami a biztonságot adja. Amikor beírjuk, hogy https:, akkor egy számelméleti módszerekkel működő biztonsági kódolást nyitunk meg. Ez a biztonsági kódolás egy nyilvános kulcsú titkosítást megvalósító algoritmus. Ennek egyik lépéseként bizonyos számról el kell dönteni, hogy az prímszám-e. Ez is a véletlen módszerek segítségül hívásával történik.

Ebbe a sorba illeszkedik az 1976-ban megfogalmazott Szemerédi-lemma, mely tulajdonképpen azt mondta ki, hogy ha egy gráf nagyon nagy, akkor annak bizonyos részei szükségképpen véletlenszerűek. Ez pedig nem hátrány, ellenkezőleg, a véletlenszerű nagyon sok jót hordoz magában. A nagy számok törvénye alapján az ilyen struktúráknak sok tulajdonságát megjósolhatjuk abból következően, hogy tudjuk róluk: véletlenszerűek.

Ez az újabb elv nagy hatású segédeszközünk lett. Amikor például egy rettentően nagy struktúrát vizsgálunk, annak tulajdonságairól képet kaphatunk, ha bizonyos részeit, melyek véletlenszerűek, elkülönítjük, ezáltal a maradék struktúrát leírhatóvá tesszük. Azóta sok mindenre kiterjesztették ezt a módszert, mellyel a vizsgált struktúrát egy véletlenszerű és egy egyszerű rész keverékeként állítják elő.

 Vissza a tartalomhoz

MEGNYITÁS/LETÖLTÉS