Tárgy: PMB1210L, 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.): 9+0 levelező képzési rendben

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

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

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. 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.

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