Számítástudomány
  • 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.