Számítási modellek

Előadás: Hétfő 16:00-17:30, Déli ép. 2.712
Gyakorlat: Hétfő 17:45-19:15, Déli ép. 2.712; 19:30-21:00, Déli ép. 2.712

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, rekurzív nyelvek, rekurzívan felsorolható nyelvek, 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: 2024.03.18.
- félév végi zh: 2024.04.29
- pót-/javító zh (a két zh közül az egyik javítható/pótolható): 2024.05.06

Fóliák:

-	fóliák
1. Bevezetés	PDF
2. Alapok, grammatikák, nyelvek	PDF
3. Grammatikák, Kontrollált grammatikák, L-rendszerek	PDF
4. Reguláris kifejezések, reguláris nyelvek, véges automaták	PDF
5. Véges automaták (VA), DVA, NVA, minimális DVA, reguláris pumping lemma	PDF
6. Probabilisztikus automaták, veremautomaták, környezetfüggetlen grammatikák, környzetfüggetlen pumping lemma	PDF
7. Turing gép, változatok, Church-Turing tézis, rekurzívan felsorolható nyelvek, 0. típusú grammatikák	PDF
8. Eldönthetőség, Felismerhetőség	PDF
9. Redukció, kiszámíthatóság, bonyolultság	PDF

Feladatok: PDF

Irodalom:

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