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

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ó): 2024.05.12

Fóliák:

-	fóliák
1. Bevezetés	PDF
2. Alapok, grammatikák, nyelvek	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