Algoritmusok alapjai

A programozás legnehezebb része az, hogy egy adott probléma megoldásához megtaláljuk a legjobb, leghatékonyabb megoldást, más szóval algoritmust. Van egy pár alap algoritmus, amit minden programozónak ismernie kell, mivel ezek szinte nap, mint nap előkerülnek egy probléma megoldása során.

Az ismerés alatt nem az értendő, hogy betűről-betűre ismerni kell az algoritmust, hanem inkább az, hogy tudni kell, hogy hogy működik és melyik esetben melyiket célszerű használni.

Az algoritmusok leíró nyelve általában a pszeudokód¹, ami egy formális nyelv. Leginkább a Pascal programozási nyelvre hasonlít. Jellemzője ennek a leírási módszernek, hogy nincs rögzített nyelve, vagyis az utasítások bármilyen létező vagy nem létező emberi nyelven megadhatóak. Tehát fogunk olyan pszeudokóddal találkozni programozói pályafutásunk során, amely angolul van írva, de olyannal is, amely magyarul van.

A könyv ezen fejezetében a pszeudokóddal nem foglalkozok külön, mivel a nyelv maga igencsak triviális, így külön magyarázatra nem szorul. Helyette az ismertetett algoritmusokat C# nyelven mutatom be, a nyelv konkrét lehetőségeivel élve, mivel ilyen módon hasznosabbak a kódrészletek, mint ha egy olyan nyelven írtuk volna meg őket, amihez nincs számítógépes fordító.

Az ebben a fejezetben szereplő C# kódok az egyszerűség kedvéért hibakezelést csak elvétve, vagy egyáltalán nem tartalmaznak, mivel a hangsúlyt inkább az algoritmusok alapvető működésére és implementációjára szerettük volna helyezni.

Az algoritmusok jóságának mérőszáma a futási idő. A futási idő lehet konstans, lineáris, négyzetes, logaritmikus és exponenciális. A lineáris azt jelenti, hogy ha n elemen végzünk műveletet, akkor n alkalommal kell végrehajtani az utasítássort. Ez a legjobb eset. A négyzetes futási idő azt jelenti, hogy n elem esetén n² alkalommal kell megismételni az utasítássort. Exponenciális esetben pedig n elem esetén nⁿ alkalommal kell megismételni azt.

A konstans futási idejű algoritmusoknak nem számít, hogy hány elemen végzünk műveletet, mivel minden esetben ugyan annyi idő alatt fognak végezni. A logaritmikus futási idő jobb, mint a lineáris, mivel lassabban növekszik a futási idő az elemek számának növekedéséhez képest, mint a lineáris esetben.

Az algoritmusok jóságának egy másik mérőszáma a tár, vagy más szóval a memória igény. A memória igény egy modern számítógép esetén nem igen mérvadó, mivel viszonylag olcsón és könnyen lehet bővíteni. Viszont beágyazott környezetben, ahol ez nem megoldható ott jelentős tényező tud lenni.

Az algoritmusok problémáinak megoldásához szükséges erőforrások megállapításával a matematika egy külön területe, a komplexitáselmélet foglalkozik.

A komplexitáselmélet egyik nagy kérdése a P=NP probléma, ami a Millenniumi Problémák² egyike. Egy feladat P-ben van, ha megoldható determinisztikus polinom idejű algoritmussal. Egy feladat NP-beli, ha megoldható nem determinisztikus polinom idejű algoritmussal, ami azt jelenti, hogy megoldása polinom idejű determinisztikus algoritmussal ellenőrizhető.

Az NP problémák közé sorolható például a sudoku is, mivel a megoldás jóval több ideig tart, mint ellenőrizni, hogy a megoldás helyes-e.

A fenti ábrából és a definícióból belátható, hogy az NP problémáknak részhalmaza a P problémák. Ezen problémák esetén bizonyított, hogy polinóm időben megoldhatóak. Az NP-teljes problémák esetén azonban nem sikerült még bizonyítani, illetve olyan algoritmust találni, ami polinóm időben megoldaná őket.

Ha sikerülne bizonyítani egy NP-teljes problémáról, hogy polinóm időben megoldható, akkor azt azt jelentené, hogy bármelyik NP-teljes probléma megoldható polinóm időben. Ezt jelenleg még senkinek sem sikerült bizonyítania vagy cáfolnia.

Ha bebizonyosodna, hogy az NP-teljes problémák megoldása polinóm időben lehetséges, akkor az komoly fejlődést jelentene, mivel az útvonaltervezés és a logisztikai problémák hatékony megoldása lehetségessé válna, de ugyanakkor ez azt is jelentené, hogy a titkosításokhoz használt algoritmusaink feltörhetőek lennének, mivel a jelenleg használt megoldások arra építenek, hogy az NP-teljes problémák nem azonosak a P problémákkal.