Bonyolultságelmélet matematika tanári mesterszakosoknak

Diszkrét matematika 3

  • Hely: Déli tömb 3-607.  terem
  • Idõ: hétfő  16:00-17:30,
  • Előadó: Grolmusz Vince, (grolmusz@pitgroup.org)

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 kísérni, itt jelennek meg majd a vizsgaidőpontok, elmaradó órák, egyéb hirdetmények.
Lovász László: Algoritmusok bonyolultsága, jegyzet:     (PDF),
Rónyai, Ivanyos, Szabó:  Algoritmusok
Papadimitriou: Számítási bonyolultság


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.

Jelentkezni a Neptunban lehet;

Nem szükséges ünneplőbe öltözni a vizsgára.

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

Minden vizsga a Déli tömb 3-614-es szoba környékén lesz, a Neptunban is feltüntetjük.



Vizsgatematika:

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 .

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.

Egyszerű számelméleti számítások polinomiális időben: euklideszi algoritmus, moduláris hatványozás.

Egyszerű prímteszt,  amely nem működik pszeudoprímekre

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

Nyelvek polinomiális visszavezetése, tulajdonságai. NP-teljesség definíció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.  A 3SAT, a LEFOG, a LEFED,  a k-PART és a PARTÍCIÓ NP-teljesek. A SUBSET SUM NP-teljes.

 A SUBSET SUM polinomiálisan visszavezethető a KNAPSACK-ra.

A KNAPSACK megoldása: Egy polinomiális algoritmus, amely apró értékek esetén működik. Ibarra és Kim epszilon-közelítő eljárása.

Döntési fák. Egyszerű döntési fák. Rejtőzködő tulajdonságok.

Kolmogorov bonyolultság és tulajdonságai.

Artúr-Merlin játék a gráf-nemizomorfizmus bizonyítására. Artúr-Merlin játék a Hamilton kör bizonyítására, Zero knowledge-dzsel.