Elméleti számítástudomány, 1. rész

2018 tavasz



Órai feladatsorok:
1. Turing-gép  2. Turing-gép (2. rész)  3. Nevezetes nyelvek, Turing-gép kódolása  4. R, RE, coR, coRE 5. Diagonális módszer, Rice tétel   6. PCP, Dominó, felsorolós TG Extra feladatsor az első 7 előadás anyagához 7. Tár- és időbonyolultság   8. Tár-idő tétel, tanú tétel   9. Karp-redukció, NP-teljesség




Az elhangzott előadások fontosabb témakörei: címszavakban

Jegyzet  az előadáshoz (9., 10. és 11. fejezet).  Megtalált hibák eddig. Aki talál még benne hibát, kérem jelezze!

Nem biztos, hogy mindig pontosan ezen jegyzet  alapján fogunk haladni, de nagy eltérések nem várhatóak. A számonkérések anyaga az, ami az órán elhangzik.


Csima Judit, BME   VIK   SZIT