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: angolul: gzipped postscript , vagy PDF. Magyarul: PDF, illetve PS.
 

    Papadimitriou: Algoritmusok bonyolultsága.
    Gács-Lovász: Algoritmusok
    Aho-Hopcroft-Ullman: Számítógépalgoritmusok tervezése és analízise
    Knuth: A számítógépprogramozás mûvészete
    Lawler: Kombinatorikus Optimalizálás: Hálózatok és matroidok
    Rónyai, Ivanyos, Szabó:  Algoritmusok
    Cormen, Leiserson, Rivest: Algoritmusok, Műszaki Könyvkiadó 1997


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 állítasának 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.

Tematika:

A számítógépek egy absztrakt modellje: A Turing-gép. (Illusztráció: egy remek Java applet vagy  egy   C++ program Turing-gép szimulációra )

Példák Turing-gépre. Palindrómák.

Az univerzális Turing-gép definiciója és létezése.  k-szalagos Turing gép szimulálható 1 szalagossal O(N^2) id?ben.


Rekurzív és rekurzíve felsorolható nyelvek, ezek alapvető tulajdonságai.

Church tézis.

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

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.

Idõ-és tárkorlátos nyelvosztályok. DSPACE(f(n)), DTIME(f(n)), P, PSPACE. Az eukildeszi algoritmus, ab  mod m kiszámítása polinomiális idøben.

A nem-determinisztikus Turing-gép. Példa: a G3C nyelvet elfogadó NDTG.

Nem-determinisztikus nyelvosztályok. NP, co-NP definicíói. Tanú fogalma.

Példák polinomíális tanúra. Az NP nyelvosztály jellemzése tanúkkal.

Pratt tétele.

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: SAT NP-teljes.
 

Hipergráf kétszínezhetõsége, gráf háromszínezhetõsége NP teljes. Gráf k-színezhetõség NP-teljes, ha k>2. A független halmaz NP-teljessége.
Az INDEPENDENT_k nyelv P-ben van, minden k-ra. 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.  Prímtesztelés nem-pszeudo-prímek esetén. A Rabin-Miller teszt.

Kriptográfia. Titkos kulcsú titkosírás: A One-Time-Pad. Titkos kulcs-csere protokoll. Nyilvános kulcsú titkosírás. Az RSA.

Titokmegosztás. Shamir módszere és egy optikai eljárás

A PSPACE. PSPACE teljes nyelvek. A TQBF. Interaktív bizonyítások. Interaktív bizonyítás a gráf-izomorfizmus problémára. Az IP. Shamir tétele: IP=PSPACE.