Bonyolultságelmélet előadás

informatikus-fizikusoknak

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.

A tárgy felvételének előfeltétele az "Algoritmusok" c. tárgy sikeres elvégzése, ezt ellenőrizzük vizsga előtt.

Ajánlott irodalom:

  Lovász László: Algoritmusok bonyolultsága, jegyzet (az 1992, vagy az utáni kiadások).
        Vagy ugyanez angolul, átdolgozva, ez  a legfrissebb: gzipped postscript , vagy PDF. Magyarul: PDF, illetve PS.
      VIGYÁZAT: A jegyzetboltban néha az 1992 előtti kiadásnak az utánnyomása kapható, ami nem jó!

    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 vizsgáró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).

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 illetve törölni magad az ETR oldalakon lehet.

A vizsgák 9:30-kor kezdõdnek.


Vizsgatematika:

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

Példák Turing-gépre. Palindrómák. Church tézis. 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.

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.

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

Idõ-és tárkorlátos nyelvosztályok. DSPACE(f(n)), DTIME(f(n)), P, PSPACE.

A nem-determinisztikus Turing-gép. 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. A FAKTOR  nyelv és tulajdonságai.

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.

Kommmunkációs játékok. A Mehlhorn-Schmidt tétel. Alkalmazás az ID probléma bonyolultságára. Nem-determinisztikus kommunikációs bonyolultság. Ennek jellemzése fedõ téglalapokkal. A Rabin-Simon véletlen protokoll az ID problémára.

 Véletlen algoritmusok, polinomazonosság ellenõrzése, Schwartz lemma. 

Prímtesztelés nem-pszeudo-prímek esetén. A Rabin-Miller teszt.