Számítási modellek

Előadás: Hétfő 17:45-19:15, Déli Ép. 2-502
Gyakorlat: Hétfő 19:30-21:00, Déli Ép. 0-311; Kedd 17:45-19:15, Déli Ép. 0-311

Előadó: Lukovszki Tamás

Tartalom:

Klasszikus számítási modellek: véges automaták, verem automaták, Turing gépek (TG), TG-k változatai, parciálisan rekurzív függvények, eldönthetetlenség, idő és tár komplexitás, véletlen hozzáférésü gépek (RAM), áramkörök, cella automaták. Párhuzamos és elosztott számítási modellek. Nem konvencionális számítási modellek.

Követelmények, értékelés:

1. Aktív részvétel a feladatok megoldásában és a megoldások megbeszélésében a gyakorlatokon
2. A gyakorlatok elején a 10 perces tesztek >=50%-ának teljesítése
3. Sikeres zh-k (az érdemjegy a két zh átlagaként kerül kiszámításra)

Fontos időpontok:

- félidős zh: 2023.04.03
- félév végi zh: 2023.05.15
- pót-/javító zh (a két zh közül az egyik javítható/pótolható): 2023.05.22

Fóliák:

-	fóliák
1. Bevezetés	PDF
2. Alapok, grammatikák, nyelvek	PDF
3. Grammatikák, L-rendszerek	PDF
4. Reguláris kifejezések, véges automaták	PDF
5. Véges automaták (VA), DVA, NVA, minimális DVA	PDF
6. Probabilisztikus automata, Veremautomata, környezetfüggetlen grammatika	PDF
7. Turing gép, változatok, Church-Turing tézis, recursivan felsorolható nyelvek, 0. típusú grammatikák	PDF
8. Eldönthetőség, Felismerhetőség	PDF

Irodalom:

J. E. Savage, Models of Computation: Exploring the Power of Computing, Brown University, 1998. https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf
M. Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage, 2012.