Tantárgy kódja

PMB1216

Tantárgy neve

Számításelmélet

Tantárgy angol neve

Computation Theory

Kredit

2

Félévi követelmény

Vizsga

Heti óraszám

1 + 0

Elmélet + Gyakorlat

Előkövetelmény

PMB1217

Ajánlott félév

6

Cél

A számítógépmodellek matematikai elméletének, hátterének elsajátítása

Cél angol

The aim of course to learn the mathematical theory of computer models and their background

Tartalom

A Turing gép definíciója, idő- és tárbonyolultsága. Szimuláció fogalma, szimulációs tételek. Rekurzív és rekurzívan felsorolható nyelvek, és ezen nyelvosztályok kapcsolata. Univerzális Turing-gépek fogalma és létezésük bizonyítása. Church tézis. Algoritmikusan nem megoldható problémák. Megállási probléma. RAM gépek. 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 nyelvekre. NP teljes problémák. SAT nyelv és egyéb NP teljes nyelvek. Kriptográfiai alapfogalmak.

Tartalom angol

Definition of  Turing machine, time and space complexity. Concepts of simulation and simulation theorems. Recursive and recursively enumerable languages and language classes in this relationship. The concept and proof of the existence of universal Turing machines. Church thesis.  Algorithmically unsolvable problems. Halting problem. RAM machines. Kolmogorov complexity and its applications. Complexity classes. Non-deterministic Turing machines. The space-time theorem. The P and NP classes and their relationship. The concept of a witness and the witness theorem. Examples of NP languages. NP complete problems. SAT NP-complete language and other languages. Basic concepts of cryptography.

Számonkérés

vizsga

Számonkérés angol

Examination

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, egyetemi tankönyv, Budapest, Tankönyvkiadó, 1991. C. H. Papadimitriou: Számítási bonyolultság, egyetemi tankönyv, Novadat, 1999.

Irodalom angol

C. H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994.

Tantárgyfelelős intézet kódja

MII

Tantárgyfelelős oktató

Dr. Dömösi Pál Béla