Számítástudomány előadás

Az előadás látogatása nem kötelező, azonban a vizsga anyaga minden, ami az előadáson elhangzik. Kötelező azonban ezt az honlapot rendszeresen figyelemmel kisérni, itt jelennek meg majd a vizsgaidőpontok, elmaradó órák, egyéb hirdetmények.

 Lovász László: Algoritmusok bonyolultsága, jegyzet:     (PDF),   illetve PS
 Rónyai, Ivanyos, Szabó:  Algoritmusok 
Papadimitriou: Algoritmusok bonyolultsága

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.

Vizsgaidõpontok az ETR-ben találhatóak. Halasztáshoz nem kell bejönni a vizsgára, elég csak az ETR-ben törölni a jelentkezést.
Nem szükséges ünneplõbe öltözni a vizsgára, viszont index nélkül senkit sem vizsgáztatok.

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).

Vizsgaidőpontok: Ld. az ETR-t.
 Minden vizsga a Déli tömb 3-614-es szoba környékén lesz, a szoba ajtaja melletti táblára lesz kirakva a vizsga reggelén a vizsga helye. A vizsgára jelentkezni  az ETR oldalakon lehet.
A vizsgák 9:30-kor kezdõdnek.
Vizsgatematika:

32 bites szám kitalálása barkochbával (Illusztráció: játék a géppel)

A számítógépek egy absztrakt modellje: A Turing-gép.  Nyelvek, abc. Példák Turing-gépekre. Church tézis.

A palindrómák felismerése egy- és kétszalagos Turing-géppel. (Illusztráció: egy remek Java applet) .

Az univerzális Turing-gép definiciója és létezése.

A k-szalagos Turing gép szimulálható 1 szalagossal O(N^2) idõben.

A RAM-gép. A RAM-gép és a Turing-gép ekvivalenciája: a Turing-gép szimulálása RAM-gépen. A RAM-gép szimulálása Turing gépen.

Rekurzív és rekurzíve felsorolható nyelvek, ezek alapvetõ tulajdonságai. Minden véges nyelv rekurzív.

A megállási probléma. Algoritmikusan eldönthetetlen, hogy egy leirásával adott Turing-gép az üres inputon leáll-e. A Dominó-probléma.

L_NEMRAK rekurzive felsorolható, 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.

Lineáris gyorsítási tétel. 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 nyelv van).

A nem-determinisztikus Turing-gép. Nem-determinisztikus nyelvosztályok. NP, co-NP definicíói.

Tanú fogalma. Példák polinomiális tanúra. Az NP nyelvosztály jellemzése tanúkkal.

Pratt tétele. Számok faktorizációja, A FACTOR nyelv.

Nyelvek polinomiális visszavezetése, tulajdonságai. NP-teljesség definícíója.

Boole függvények, Boole polinomok, CNF formulák, kielégíthetőség. A SAT nyelv.


Cook tétele: A SAT NP-teljes.  Halmazrendszer kétszínezhetősége, gráf háromszínezhetõsége NP-teljesek.  

Az INDEPENDENT nyelv  NP-teljessége. Az INDEPENDENT_k nyelv P-ben van, minden k-ra. A SAT3, a LEFOG, a LEFED, K-PART, PART, a SUBSET SUM, a KNAPSACK feladat NP teljessége.. A SUBSET SUM polinomiálisan vissaavezetheto a KNAPSACK-ra. Egy algoritmus a hátizsák feladat megoldására. Az algoritmus lépésszámbecslése. Ibarra és Kim skálázási eljárása közelítõ optimum keresésére.

Véletlen algoritmusok, polinomazonosság ellenõrzése, Schwartz lemma. Alkalmazás páros gráfban teljes párosítás létének eldöntésére. Prímtesztelés nem-pszeudo-prímek esetén.

Kriptográfia: titkos- és nyilvános kulcs. Titkos kulcs-csere protokoll. Az RSA titkosírás, digitális aláírás. 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. A Simon-Rabin protokoll az ID függvény gyors, randomizált kiszámítására.

Artúr-Merlin játék a gráf-nemizomorfizmus bizonyitására.