- Hely: Déli tömb 0-821 Bolyai terem
- Idő: csütörtök 12:00-13:30,
- Előadó: Grolmusz Vince
- Első alkalom: 2023. március 2.
…………….
A vizsgáról:
Jelentkezni a Neptunban lehet.
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.
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. Majdnem minden nyelv nemrekurzív, Minden véges nyelv rekurzí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.
Az INDEPENDENT nyelv NP-teljessége. A független és a lefogó halmazok viszonya gráfban. A KLIKK nyelv NP-teljes. A G-LEFOG nyelv NP-teljes.
Az INDEPENDENT_k nyelv P-ben van, minden k-ra.
A SAT3, a LEFOG, a LEFED NP-teljes.
Ibarra és Kim skálázási eljárása közelítő optimum keresésére.
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ő.
Véletlen algoritmusok, polinomazonosság ellenőrzése, Schwartz lemma.
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 általános iskolában tanult prímtesztek nem polinomiálisak.
Az RSA titkosírás, digitális aláírás.
Egy alkalmazás: A BitCoin
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ó protokol az ID függvény kiszámítására.