Bonyolultságelmélet 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 (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 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.

Volt:




32 bites szám kitalálása barkochbával. , Alexander Bogomolny), MIN, MAX, (MIN, MAX) keresés, ezek optimalitása. Rendezések. A rendezéshez log n! összehasonlitás kell, log n! becslései.

Rendező algoritmusok. Beszúrásos rendezés, a beszúrás.

Az összefésüléses rendezés, az összefésülés. A Floyd-Rivest algoritmus a mediánskeresésre.

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.Church tézis.  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.

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


Lesz:

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.