Hely: északi tömb 0.79 teremIdő: kedd 16:10-17:40,- Előadó: Grolmusz Vince
- Első alkalom: 2025. szeptember9.
……………………
A vizsgáról:
A vizsga anyaga minden, ami az előadáson elhangzik. Az ajánlott irodalomban minden elhangzott tétel megtalálható,
sokszor azonban más, hosszabb, bonyolultabb bizonyítással. Vizsgán természetesen akármilyen helyes bizonyítást elfogadok.
Jelentkezni a Neptunban lehet.
Az ezen oldalon levő tematikából kap mindenki két tételt, távolabb levő helyekről.
A sikeres vizsga feltételei:
A két kiadott tétel alapos ismerete, különösen:
A definíciók és a tételek pontos ismerete. A tétel bizonyításában
- lényeges eredmény elérése a kettes,
- a bizonyítás lényegében történő befejezése nagyobb hiánnyal a hármas,
- apró hiánnyal a négyes,
- hiánytalanul az ötös szinthez.
Hiányosság a definíciókban illetve a tételek kimondásában nem megengedett (azaz rögtön elégtelen a hibás definíció illetve
állítás kimondása).
Ajánlott irodalom:
Lovász László: Algoritmusok bonyolultsága, jegyzet: (PDF),
Rónyai, Ivanyos, Szabó: Algoritmusok
Papadimitriou: Algoritmusok bonyolultsága
Érdeklődőknek (nem tananyag a tartalma) BitCoin: Egy jó cikk az EMS Magazinból
Vizsgatematika:
32 bites szám kitalálása barkochbával
A számítógépek egy absztrakt modellje: A Turing-gép. Nyelvek, abc. Példák Turing-gépekre. A palindrómák felismerése egy- és kétszalagos Turing-géppel.
Az univerzális Turing-gép definíciója és létezése.
Church tézis.
A k-szalagos Turing gép szimulálható 1 szalagossal O(N2) időben.
Rekurzív és rekurzíve felsorolható nyelvek, ezek alapvető tulajdonságai. Minden véges nyelv rekurzív. Majdnem minden nyelv nemrekurzív,
Majdnem minden nyelv nem rekurzíve felsorolható.
A megállási probléma.
A Dominó-probléma.
L_NEMRAK rekurzíve felsorolható,
Algoritmikusan eldönthetetlen, hogy egy leírásával adott Turing-gép az üres inputon leáll-e.
L_KIRAK nem rekurzíve felsorolható.
Idő-és tárkorlátos nyelvosztályok. DSPACE(f(n)), DTIME(f(n)), P, PSPACE.
Egyszerű relációk a tárigény és az időigény között.
Példák polinomiális idejű algoritmusokra: euklideszi algoritmus; a^b mod m.
Minden rekurzív f függvényhez létezik olyan rekurzív nyelv, amely nincs benne DTIME(f(n))-ben (azaz tetszőlegesen nehéz rekurzív nyelv van).
Lineáris gyorsítási tétel.
A nem-determinisztikus Turing-gép.
Nem-determinisztikus nyelvosztályok.
NP, co-NP definíciói.
Nyelvek polinomiális visszavezetése, tulajdonságai. NP-teljesség definíciója.
Nyelvek polinomiális visszavezetése, tulajdonságai. NP-teljesség definíciója.
Az INDEPENDENT nyelv NP-teljessége. Az INDEPENDENT_k nyelv P-ben van, minden k-ra.
A független és a lefogó halmazok viszonya gráfban. A KLIKK nyelv NP-teljes. A G-LEFOG nyelv NP-teljes.
A SAT3, a LEFOG, a LEFED NP-teljes.
Gráf kromatikus számának közelítése. A minimális méretű csúcslefogó halmaz mérete 2-es faktoron belül közelíthető.
Prímtesztelő eljárások: egy egyszerű módszer, amely nem mindig működik, és a Rabin-Miller teszt.
Kriptográfia: titkos- és nyilvános kulcs. OTP : One Time Pad.
Titkos kulcs-csere protokoll.
Az RSA titkosírás, digitális aláírás.
Egy alkalmazás: A BitCoin (nem kell vizsgán)
Titokmegosztás: egy optikai és egy algebrai megoldás.
Kommunikációs játékok. A Mehlhorn-Schmidt tétel.
A nem-determinisztikus kommunikációs komplexitás jellemzése fedő téglalapokkal.
Véletlent használó protokoll az ID függvény kiszámítására.
A halmazdiszjunktsági függvény kommunikációs bonyolultsága általánosan és speciális esetekben: részfa-metszet protokoll, teljes és üres részgráf csúcsmetszete.