Algoritmuselmélet tételsor 2006/2007 2. félév

1. Determinisztikus Turing gépek és számításaik.

2. Determinisztikus Turing gépekkel felismerhető nyelvek és nyelvosztályok.

3. Szimulációs tételek.

4. A rekurziv és a rekurzívan felsorolható nyelvek, valamint ezen nyelvek osztályainak a kapcsolata.

5. Az univerzális Turing gépek.

6. A Church tézis és eldönthetetlen problémák.

7. A Kolmogorov bonyolultság.

8. A tár-idő tétel.

9. Memdeterminisztikus Turing gépek által elfogadott nyelvek.

10. Az NP osztály, a tanú tétel.

11. Karp redukció, az NP-teljesség és a Cook-Levin tétel.

13. Néhány NP-teljes probléma.

14. Az NP osztály szerkezete.