Számítási modellek


Előadás: Kedd 8:30-10:00, Déli ép. 2.502
Gyakorlat: Kedd 12:15-13:45, 0.220; Csütörtök 19:30-21:00, 0.312

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, sejtautomaták. Párhuzamos és elosztott számítási modellek. Nem konvencionális számítási modellek.

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

0. Maximum 4 hiányzá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: 2026.03.17.
- félév végi zh: 2026.05.05
- pót-/javító zh (a két zh közül az egyik javítható/pótolható): 2026.05.12

Fóliák:

- fóliák
1. Bevezetés PDF
2. Alapok PDF
3. Programozott grammatikák, mátrix grammatikák, véletlen környezettel adott grammatikák, L-rendszerek PDF
4. Reguláris kifejezések, véges automaták PDF
5. NVA, DVA, 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
10. Sejtautomaták 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