- Előadás helye: D 1.105, ideje: kedd 10:15-11:45
Jegyzet: Lovász László: Algoritmusok bonyolultsága. Az alábbi angol nyelvű változat egyes részekben újabb és javított:
P. Gács and L. Lovász: Complexity of Algorithms-
Hetenkénti téma
Február 20.
Bevezetés, fő témák. Turing gép definíciója. Egyszerű példák. Univerzális Turing-gép definíciója és létezése.
Február 27.
k szalagos Turing gép szimulációja 1 szalagossal. RAM gép, ekvivalenciája a Turing géppel.
Március 5.
Rekurzív és rekurzívan fölsorolható nyelvek, kapcsolatuk. Megállási probléma. Van rekurzívan fölsorolható, de nem rekurzív nyelv.
Március 12.
A dominó probléma nem oldható meg algoritmikusan. Algoritmusok idő és tárigénye. Polinomiális idő. Euklidészi algoritmus.
Március 26.
Az euklidészi algoritmus következményei. Gauss-elimináció polinomialitása. Polinomiális tár és játékok.
Április 2.
Általános tételek az idő és tárbonyolultságról. DTIME, DSPACE definíciója. Van olyan f(n) függvény, hogy DTIME(f(n)) minden rekurzív nyelvet tartalmaz, de nincs ilyen rekurzív függvény. Gyorsítási Tétel.
Április 9.
Gyorsítási tétel bizonyítása. Nem-determinisztikus Turing-gépek és bonyolultsági osztályok.
Április 16.
Példák NP-beli nyelvekre: gráfelmélet (összefüggőség és tagadása, síkbarajzolhatóság és tagadása, teljes párosítás létezése és tagadása, Hamilton-kör létezése, 3ászínezhetőség), számelmélet (prímség és összetettség, korlátos osztó létezése és nemlétezése), egyenlőtlenségrendszer megoldhatósága és nem-megoldhatósága.
Április 23.
NP-teljesség. SAT, 3-SAT NP-teljessége. 2-SAT polinomiális.
Április 30.
NP-teljes kombinatorikus és gráfelméleti problémák: hipergráf lefogás, hipergráf lefedés, partíció, gráfok színezése 3 színnel, gráfok lefogása.
Május 7.
További NP-teljes problémák: lineáris egyenlőtlenségrendszer egész megoldhatósága, algebrai egyenletrendszer valós vagz komplex megoldhatósága, részletösszeg probléma. A részletösszeg probléma unáris kódolás esetén P-ben van.
Véletlent használó algoritmusok. Polinomazonosság ellenőrzése, Schwartz Lemmája.Május 14.
A párosítás-probléma megfogalmazása, mint polinomazonosság. Prímtesztelés, Fermat-teszt és Rabin-Miller teszt. Randomizált bonyolultsági osztályok.
Last modified May 11, 2008.