Tárgy: PMB1210, Számításelmélet

Oktató: dr. Vályi Sándor

Meghirdetés féléve : 6

Kreditpont : 3

Heti kontakt óraszám (elm.+gyak.): 1+0

Félévi követelmény: kollokvium

Előfeltétel (tantárgyi kód) : PMB1203

Tantárgyfelelős neve és beosztása:  Dr. Dömösi Pál egy. tanár

Évközi követelmények:

Vizsgajegy:

Tantárgyi program:

A Turing-gép definíciója, idő- és tárbonyolultsága. Szimuláció fogalma, szimulációs tételek. RAM-gépek. Uni­verzális Turing-gépek fogalma és létezésük bizonyítása. Church-tézis. Rekurzív nyelvek és rekurzívan felsorolható nyelvek, és ezen nyelvosztályok kapcsolata. Algoritmikusan nem megoldható problémák. Megállási probléma. Primitív rekurzív, rekurzív és parciális rekurzív függvények. Kolmogorov bonyolultság és alkalmazásai. Bonyolultsági osztályok. Nemdeterminisztikus Turing-gépek. A tár-idő tétel. A P és NP osztályok és ezek kapcsolata. A tanú fogalma és a tanú tétel. Példák NP-beli nyel­vekre. NP-teljes problémák. A SAT nyelv és egyéb NP-teljes nyelvek. Kriptográfiai alap­fogalmak. A PSPACE osztály, kapcsolata a kétszemélyes játékokkal.

Oktatási segédanyag:

Az órán bemutatott és internetről letölthető elektronikus dokumentumok és előadásvázlat.A http://moodle.nyf.hu tartalomkezelő rendszeren keresztül elérhető. A kurzusfelvételi kód az első előadáson kerül közlésre.

Kötelező és ajánlott irodalom:
Rónyai Lajos: Algoritmusok, Typotex, Budapest, 1998.
T. H. Cormen, C. E. Leiserson, R.L. Rivest: Algoritmusok, Budapest, Műszaki Könyvkiadó, 1997.
Gács Péter: Algoritmusok, Budapest, Tankönyvkiadó, 1991.
C. H. Papadimitriou: Számítási bonyolultság, Novadat, 1999,
Iványi Antal szerk.: Informatikai algoritmusok I, ELTE Eötvös Kiadó, 2004
Iványi Antal szerk.: Informatikai algoritmusok II, ELTE Eötvös Kiadó, 2005