Egyéb - alaptárgyhoz nem sorolt - tárgyak

Tárgyfelelős: Dr. Heckl István, egyetemi docens (heckl.istvan@mik.uni-pannon.hu)

A tárgy az alábbi tárgy ismeretét tételezi fel, arra épít:
Digitális számítás elmélete I.

Tematika:

1. Számítási komplexitás;
2. Időkorlátos Turing-gépek; Időkorlátos szimuláció
3. P és NP osztályok
4. NP-teljesség
5. NP-teljes feladatok I: korlátozott csempézési feladat, egész programozás
6. NP-teljes feladatok II: utazóügynök feladat
7. A komplexitási hierarchia
8. Ekvivalencia és normál formák;
9. Teljesség
10. Struktúrák és kielégíthetőség
11. Megoldhatatlanság és az NP-teljesség

Irodalom:

Lewis, H. R. and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, New Jersey, 1981.

Alagar, V. S, Fundamentals of Computing, Prentice-Hall, New Jersey, 1989.

Caroll, J. and D. Long, Theory of Finite Automata, Prentice-Hall, New Jersey, 1989.