Számításelmélet

Tamás Herendi

2014.


Table of Contents

1. Előszó
2. Formális nyelvek
3. Függvények növekedési rendje
4. A Turing-gép
4.1. A Turing-gép definíciója
4.2. Felismerő Turing-gépek
4.3. Turing-gépek megadása
4.3.1. Táblázatos reprezentáció:
4.3.2. Gráfreprezentáció:
4.3.3. Turing-gép megadása felsorolással:
4.3.4. Példák
4.3.5. Feladatok
4.4. Church-Turing tézis
4.5. Turing-gépek összefűzése
4.6. Többszalagos Turing-gépek, szimuláció
5. Kiszámíthatóság-elmélet
5.1. Univerzális Turing-gép és az univerzális nyelv
5.2. A diagonális nyelv
5.3. Nyelvek rekurzivitása
5.4. Megállási probléma
6. Nemdeterminisztikus Turing-gépek
6.1. Nemdeterminisztikus Turing-gépek definíciója
6.2. Nemdeterminisztikus Turing-gépek szimulációja
7. Bonyolultságfogalmak
7.1. Idő-, tár- és programbonyolultság
7.2. Bonyolultsági osztályok
7.3. Tár-idő tételek
8. Az NP nyelvosztály
8.1. A Tanú-tétel
8.2. NP-teljesség
Irodalomjegyzék

List of Figures

3.1. 1. ábra
3.2. 2. ábra
3.3. 3. ábra
4.1. Turing gép modell
4.2. Paritásellenőrző bit hozzáfűzése a bemenő szóhoz
4.3. Kezdő konfiguráció: Kezdő konfiguráció:
4.4.
4.5.
4.6.
4.7.
4.8.
4.9.
4.10.
4.11.
4.12.
4.13.
4.14.
4.15.
4.16.
4.17. A Turing-gép számítása a A Turing-gép számítása a bemeneten bemeneten
4.18. Paritásellenőrző bit tesztelése
4.19. Kezdő konfiguráció: Kezdő konfiguráció:
4.20.
4.21.
4.22.
4.23.
4.24.
4.25.
4.26.
4.27.
4.28.
4.29.
4.30.
4.31.
4.32.
4.33.
4.34.
4.35. A Turing-gép számítása a A Turing-gép számítása a bemenetenbemeneten
4.36. és kompozíciója és és kompozíciója kompozíciója
4.37. , és feltételes kompozíciója, , és feltételes kompozíciója és , és feltételes kompozíciójafeltételes kompozíciója
4.38. iterációja iterációja
4.39. Többszalagos Turing-gép
4.40. Egy kétszalagos Turing-gép szimulációja

List of Examples

3.1. 1. példa
3.2. 2. példa
3.3. 3. példa