- Előadás helye: É 1.71, ideje: csütörtök 8:30-10:00
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
A magyar nyelvű jegyzet részben javított változata letölthető Király Zoltán honlapjáról
-
Hetenkénti téma
Február 12.
Bevezetés. Véges automaták definíciója. 3-mal és 7-tel osztható számok felismerése véges automatával. Palindrómák nem ismerhetők fel véges automatával. Turing gép definíciója. Egyszerű példák.
Február 19.
Univerzális Turing-gép definíciója és létezése. k szalagos Turing gép szimulációja 1 szalagossal. Palindróma felismerése 2 szalagos gépen lineáris időben, 1 szalagos gépen kvadratikus idő kell.
Február 26.
RAM-gép definíciója és ekvivalenciája a Turing géppel. Boole függvény és Boole polinom definíciója, normálformák.
Március 5.
Turing gép szimulációja Boole halózattal. Church tézis. Algoritmikus eldönthetetőség, a megállási problema eldönthetetlensége. Hilbert 10-ik problémája.
Március 12.
A megállási probléma változatai, Rice tétele. A dominó probléma eldönthetetlensége. Szabad csoportok szóproblémájának eldönthetetlensége (bizonyítás nélkül).
Március 19.
Forráskorlátos számítások: tár és idő. Polinomiális idő. Aritmetikai algoritmusok: alapműveletek, euklidészi algoritmus, számolás véges testekben, hatványozás modulo m, determináns kiszámítása (Gauss-elimináció).
Március 26.
Speciális osztályok: E, EXP, lineáris idő, kvazilineáris idő, PSPACE, lineáris tár, L. Lineáris gyorsítási tétel. Idő és tárosztályok kapcsolata. Van olyan f függvény, hogy minden rekurzív nyelv DTIME(f)-ben van. Minden rekurzív f-re van olyan rekurzív nyelv, mely nincs DTIME(f)-ben. Teljesen időkonstruálható függvények, jól számolható függvények, kapcsolatuk (csak kimondva). Idő-hierarchia tétel. Tár-hierarchia tétel csak kimondva.
Április 2.
Hézagtétel, nem-lineáris gyorsítási tétel.
Április 16.
Nemdeterminisztikus Turing gép és az általa felismert nyelv. Rekurzívan felsorolható nyelvek jellemzése nemdeterminisztikus Turing géppel. Nemdeterminisztikus bonyolulsági osztályok, NP. Gráfelméleti példák NP-beli nyelvekre: összefüggőség, teljes párosítás létezése és nem-létezése, Hamilton kör, 3 színnel szinezhetőség.
Április 23.
A co-NP osztály, NP metszet co-NP mint jó karakterizáció. Prímség, Pratt tetele. A FAKTOR nyelv polinomialisan ekvivalens a primtenyezos felbontassal, NP metszet co-NP-ben van. Polinomiális visszavezetés, NP-teljesség. Boole fuggvenyek, Boole polinomok, CNF formula azonosan 0 volta (SAT probléma). Cook tétel kimondása.
Április 30.
Cook tétel bizonyítása. SAT változatai: 2-SAT polinomiális, 3-SAT NP-teljes.
Május 14.
SAT-3 NP-teljes. NP-teljes kombinatorikai problémák: halmaz-rendszer lefogása, lefedése, partíció, k-partíció. NP-teljes gréfelméleti problémák: 3-szinezhetőség, max független ponthalmaz, min éllefogás. NP-teljes algebrai problémák: lineáris egyenlőtlenségrendszer egész megoldása, kvadratikus egyenletrendszer megoldása tetszőleges számtestben.Last modified April 25, 2009.