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

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

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