Számításelmélet II

Előadás III-ad éves informatika tanárszakosoknak

2009 tavasz

Előadó: Király Zoltán

Kedd 12:15-13:45, D.1.105.


Csak a hallgatóimnak / Only for my students


Hirdetmények


Ajánlott irodalom


1. előadás (II. 10.)

Algoritmusok lépésszáma, polinomiális algoritmusok.
Véletlent használó algoritmusok fajtái, használatuk. LAS VEGAS, FÖLADÓS, MONTE CARLO és EGYOLDALÚ HIBÁJÚ algoritmusok. Legrosszabb és várható futási idő, hiba-valószínűség csökkentése. Kapcsolatok a LAS VEGAS, FÖLADÓS és EGYOLDALÚ HIBÁJÚ algoritmusok között.


2. előadás (II. 17.)

Hálózat, folyam, vágás, vágás kapacitása és folyamértéke. Maradék hálózat (segédgráf) készítése egy folyamhoz. Folyam-algoritmus (Ford-Fulkerson). Javítás a folyamon a megtalált javító-út segítségével. Minimális vágás megtalálása. Ford-Fulkerson tétel. Edmonds-Karp tétel (biz. nélkül), algoritmusok futási ideje.
Csúcskapacitások kezelése, több termelő/fogyasztó esete.


3. előadás (II. 24.)

Folyam irányítatlan gráfokon. Redukált folyam, felbontása utakra.
Menger tételei, gráfok többszörös összefüggősége.
Mélységi keresés és befejezési számozás. Gráf erősen összefüggővé irányítása.


4. előadás (III. 3.)

2-összefüggő blokkok keresése, erősen összefüggő komponensek keresése.
Döntési fák, függvények döntési fa bonyolultsága. Információ-elméleti alsó becslés, ellenség stratégia.


5. előadás (III. 10.)

Egyszerű döntési fák. Zárkózottság. Szimmetrikus Boole-függvény zárkózott. Gráftulajdonságok, monotonitás, az Aanderaa-Rosenberg-Karp sejtés. Összefüggőség zárkózott. Algebrai döntési fák, Ben-Or tétele, ELEM-KÜLÖNBÖZŐSÉG.
Abc, szó, nyelv. Véges automaták, reguláris nyelvek, pumpálási lemma. A palindrómák nyelve nem reguláris.


6. előadás (III. 17.)

Turing gép definíciója. Példa Turing gépre. Második példa: palindrómák felismerése kétszalagos TG-pel.
TG által felismert ill. eldöntött nyelv. TG-ek összerakása, függvényt számoló TG.
Univerzális Turing gép fogalma és konstrukciója.
k szalagos TG szimulálása egy- és két-szalagossal vázlatosan). Jobban nem lehet.


7. előadás (III. 24.)

k szalagos TG szimulálása egy-szalagossal. Turing gép futási ideje.
Közvetlen elérésű gép (RAM). Közvetlen elérésű gép ekvivalenciája Turing géppel.
Boole-függvények és Boole-hálózatok. Ekvivalencia Turing-géppel.


8. előadás (III. 31.)

Church tézis. Rekurzív és rekurzíve felsorolható nyelvek, kapcsolatuk. Megállási probléma eldönthetetlensége.
A dominó-kirakási probléma. Post feladata és Hilbert 10. problémája.
DTIME és DSPACE osztályok.


9. előadás (IV. 7.)

Lineáris gyorsítási tétel. Néhány nevezetes osztály, jelölések, néhány P-beli nyelv. Az idő- és a tár- hierarchia kapcsolata. Jól számolható függvények, hierarchia-tétel. Hézag-tétel és gyorsítási tétel.


10. előadás (IV. 21.)

Tanú és az NP osztály definíciója. (Mese: nem-determinisztikus Turing gépek, NP másik def., a két definíció ekvivalenciája.)
Néhány NP-beli nyelv. co-NP osztály.


11. előadás (IV. 28.)

Jól karakterizált nyelvek, megjegyzések.
Karp-redukció (nyelvek visszavezethetősége egymásra).
NP-teljesség. Állítások, tételek.
A SAT (k-SAT, k-SAT-l) nyelv. Cook tétel. 3-SAT-3 NP-teljes. 2-SAT P-ben van.
További NP-teljes nyelvek: halmaz lefogási/lefedési feladat, PARTÍCIÓ, Hármasítás.


12. előadás (V. 5.)

Gráfok 3-színezhetősége, max. független, max. teljes, min. lefogó ponthalmaz. Hamilton-kör, leghosszabb út, irányított éldiszjunkt s1t1 és s2t2 út, élkromatikus szám.
Diophantoszi egyenlőtlenség-rendszer, felezés, hátizsák, ládapakolás NP-teljessége.

NP-nehéz feladatok. Mit lehet ilyenekkel kezdeni?
Approximációs algoritmusok. Csúcsfedés közelítése. Közelítő algoritmus a metrikus utazó ügynök feladatra.


13. előadás (V. 12.)

Jobb közelítő algoritmus a metrikus utazó ügynök feladatra. Közelítő algoritmus a Steiner fa feladatra. Közelítés a ládapakolásra és a maximális stabil párosításra.
PTAS és FPTAS. Emlékeztető: Ibarra-Kim.
APX, APX-teljesség. Max-klikk közelíthetetlensége.