Az
előadásokat Grolmusz Vince tartja csütörtökön 14:00-16:00 között, a Szabó József előadóteremben (LD 0-803). (Neptun kurzuskód: szamtudm22ea-1)
Két zárthelyi lesz év közben
október-ben és
december-ben.
A zárthelyiken 7 darab 10 pontos feladat lesz kitűzve. Az év végi jegy a két zárthelyi összesített eredménye alapján az alábbiak szerint fog alakulni:
100 pont ≤ 5
080 pont ≤ 4
060 pont ≤ 3
040 pont ≤ 2 [mind a két zárthelyin külön-külön legalább 20 pontot el kell elérni a gyakorlat teljesítéséhez]
A zh-kon mindenféle elektronikus eszköz használata tilos. A "zh" kifejezés a "zárthelyi" rövidítése, ennek megfelelően a feladatsor kiosztása után a dolgozat beadásáig
tilos elhagyni a termet.
Legfeljebb 1 zh-ról lehet igazolatlanul hiányozni. Félév végén lesz egy javító zh, amin egy zh-t lehet javítani vagy pótolni. Ha valakinek a zh-k és a javító zh alapján nem sikerül jegyet szereznie, akkor a teljes félév anyagából írhat gyakuv-t, de arra már csak legfeljebb 2-est lehet kapni.
- Szeptember 11.
- Október 23. -- nemzeti ünnep
- Október 30. -- őszi szünet
A 2021-es
előadás jegyzete (nem hivatalos, lektorálatlan verzió).
Alapvető bonyolultsági osztályok:
.html
Véges automata szimulátor:
.html
Turing-gép szimulátor:
.html
RAM-gép szimulátor:
.html
Előadáshoz kapcsolódó legfrisebb jegyzet:
Lovász László: Algoritmusok bonyolultsága
Egyéb ajánlott olvasmányok: Christos H. Papadimitriou: Számítási bonyolultság, Sanjeev Arora és Boaz Barak: Computational Complexity: A Modern Approach.
Egyéb kapcsolódó ismeretterjeszto könyvek: Raymond Smullyan könyvek, pl.: To Mock a Mockingbird, Roger Penrose: A császár új elméje, Douglas L. Hofstadter: Gödel, Escher, Bach
Köszönet a tárgy korábbi oktatóinak,