NBT_PI156K3
Számításelmélet

A kurzusról

Algoritmusok bonyolultságát vetjük össze. Melyik a gyorsabb? Melyik használ kevesebb tárat? Hogyan fejezzük ki az idő- és tárbonyolultságot minden lehetséges inputra vonatkozóan? Mindez elméleti az idő- és tárbonyolultság elméleti fejtegetését kívánja meg.

Először választunk egy elméleti algoritmus modellt: a Turing-gépet. Majd erre felépítjük azokat a fogalmakat, melyek segítségével képesek vagyunk megragadni a Turing-gép egy-egy számítását, annak végkimenetelét, idő- és tárigényét. Megismerkedünk a Turing-gép több változatával is. Kinyomozzuk, hogy ezek milyen viszonyban állnak egymással. Tudja az egyik a másikat szimulálni? Gyorsabb egyik a másiknál?

A fő kérdés a következő lesz: Adott számítási problémát vajon milyen idő-, illetve tárkorlátú Turing-géppel tudunk eldönteni? A számítási problémákat bonyolultsági osztályokba fogjuk sorolni: L, NL, P, NP, PSPACE, EXPTIME, NEXPTIME, EXPSPACE, stb. Továbbá ezen osztályokra teljes problémákat is megismerünk: pl. NP-teljes, PSPACE-teljes stb. problémákat. Ilymódon kategorizáljuk az egyes problémákat: Melyik dönthető el kevés tárral? Melyik dönthető el gyorsan? Melyiknek az eldöntése tarthat kezelhetetlenül sok ideig?

Végül az előző eszközök segítségével fejtegetjük a bonyolultságelmélet fő, mai napig megoldatlan kérdését: vajon P=NP?