Számításelmélet II
Előadás III-ad éves informatika tanárszakosoknak
2009 tavasz
Kedd 12:15-13:45, D.1.105.
Csak a hallgatóimnak / Only for my students
Hirdetmények
- A július
2-ai vizsga írásbeli része a Déli 2.502. teremben lesz.
- A vizsga két részből fog állni.
Először egy írásbeli beugró lesz az elégséges jegyhez szükséges
anyagból (definíciók, tételek, algoritmusok).
- Az első vizsga beugró
feladatsora.
- A második vizsga beugró
feladatsora.
Ajánlott irodalom
- [L] Lovász: Algoritmusok bonyolultsága
PDF formátumban
(Magyarul,
kicsit még hiányos, kicsit még hibás, de egyre javul.)
- [L] Lovász: Algoritmusok bonyolultsága
(Angolul)
- [RISz] Rónyai-Ivanyos-Szabó: Algoritmusok, Typotex
- [P] Papadimitriou: Számítási bonyolultság, Egyetemi tankönyv
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.