Tematika (címszavakban), elmszámtud

2018 tavasz

1. (február 5.): Motiváció; 1-szalagos, determinisztikus Turing-gép  definíciója, működése, elfogadott nyelv; k-szalagos, determinisztikus Turing-gép definíciója vázlatosan (ezt még majd nézzük a jövő órán) 
   
2. (február 7.): k-szalagos determinisztikusTG szimulálható 1-szalagossal; R és RE nyelvosztályok, ezekre vonatkozó Church-Turing tézis
3. (február 12.): Nemdeterminisztikus Turing-gép, szimulálása determinisztikussal; Kiszámolós Turing-gép, példa: összeadás
   
4. (február 14.): Turing-gépek kódolása, annak eldönthetősége, hogy egy szó TG kódja-e, diagonális nyelv, ez nem rekurzívan felsorolható, univerzális és megállási nyelvek, ezek bonyolultsága
   
5. (február 19.) Univerzális nyelv nem rekurzív, Megállási nyelv rekurzívan felsorolható, de nem rekurzív, R és RE is zárt unióra és metszetre, coX nyelvosztály definíciója, coR = R, R = RE metszet coRE
6. (február 21.) L_üres komplementere rekurzívan felsorolható (diagonális módszer), Rice-tétel (bizonyítás nélkül)
7. (február 26.) PCP és Dominó probléma, ezek bonyolultsága; Az RE és R osztályok jellemzése felsorolós Turing-géppel (csak az állítások)
   
8. (március 5.) Turing-gép tár és időbonyolultsága, tár- és idő-korlátos Turing gépek, TIME, NTIME, SPACE és NSPACE osztályok, ezekre vonatkozó állítások
9. (március 7.) P, NP, PSPACE, EXPTIME osztályok és ezek kapcsolata
   
10. (március 12.) Tár-idő tétel (a bizonyításnak csak az ötlete), ennek következményei; Algeles NP ugyanaz, mint a mostani (tanú-tétel)
11. (március 14.) Karp-redukció, NP-teljesség, SAT nyelv, Cook-Levin-tétel, Karp redukció 3-SAT-ról 3-SZÍN-re