Számítási modellek


Előadás: Hétfő 12:15-13:45, Déli ép. 2.502
Gyakorlat: Hétfő 14:15-15:45, 16:00-17:30, 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, 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: 2025.03.17.
- félév végi zh: 2025.05.05
- pót-/javító zh (a két zh közül az egyik javítható/pótolható): 2025.05.12

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

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