Algoritmusok tervezése és elemzése II.
Előadás harmadéves alkalmazott matematikus
hallgatóknak
2019 ősz
Hétfő 12:15-13:45, Déli tömb, 0.820
Csak a hallgatóimnak / Only for my students
Hirdetmények
- A
jegyzet.
- Vizsgázni az előadáson és a
gyakorlaton
elhangzott anyagból kell, kivéve a legrövidebb utak keresését világméretű
hálózatokban.
- Vizsgára csak az jöhet, akinek a Neptunban
be van írva a gyakjegye.
Ajánlott irodalom
- [RISz] Rónyai-Ivanyos-Szabó: Algoritmusok, Typotex, 1998
- [CLRS] Cormen, Leiserson, Rivest, Stein: Új Algoritmusok, Scolar
Kiadó, 2003
- [AHU] Aho-Hopcroft-Ullman:
Számítógépalgoritmusok tervezése és
analízise, Mûszaki
Kiadó, 1982
- [Algbony] Lovász: Algoritmusok bonyolultsága
jegyzet.
- [KRS] Katona-Recski-Szabó: A számítástudomány alapjai, Typotex, 2002
- [GL] Gács-Lovász: Algoritmusok, Tankönyvkiadó, 1989
- [K] Knuth: A számítógépprogramozás
mûvészete,Mûszaki
Kiadó, 1987
- [Adat] Adatstruktúrák
jegyzet.
1. előadás (IX. 9.)
Kódolás, Billy, a könyvelő. Prüfer-kód.
Huffman-kód {RISz].
2. előadás (IX. 16.)
Szófa.
Lempel-Ziv-Welch tömörítési eljárása [RISz].
Középső elem keresése. Gyorsrendezés.
3. előadás (IX. 23.)
Legrövidebb utak az összes pontpár között: Floyd és Johnson algoritmusai.
Topologikus sorrend, lerövidebb utak aciklikus gráfban,
PERT módszer (ismétlés).
4. előadás (IX. 30.)
Mélységi keresés irányított gráfokon, erősen összefüggő
komponensek megtalálása.
Mintaillesztés. I. Kimerítő keresés (Brute Force).
II. Quick Search (Horspool).
5. előadás (X. 7.)
Mintaillesztés. III. Knuth-Morris-Pratt [RISz, CLRS].
Randomizált algoritmusok. Schwartz-Zippel-lemma [Algbony].
6. előadás (X. 14.)
Teljes párosítás létezése
páros gráfban. Monte Carlo és Las Vegas algoritmusok.
Karger minimális vágás algoritmusa.
Véletlen bolyongások,
térfogatszámítás (nagyon vázlatosan).
Mit tegyünk, ha NP-nehéz feladatokat kell megoldani?
I. Exponenciális algoritmusok.
I a) brute force
I b) heurisztika + brute force
I c) backtrack
7. előadás (X. 21.)
I d) elágazás és korlátozás (branch-and-bound).
II. Speciális input/output.
III. Közelítő algoritmusok, példák. Definíciók.
8. előadás (XI. 4.)
Metrikus utazó-ügynök, 2-közelítés.
Approximációs sémák.
FPTAS a hátizsák-feladatra.
Mese ILP-ről és a tört rexalált optimális megoldásának kikerekítéséről.
Paraméteres problémák, fix paraméteres feladatok. XP és FPT.
A minimális lefogó csúcshalmaz. Kernel.
9. előadás (XI. 11.)
Döntési fa alapú FPT a minimális lefogó csúcshalmazra, javítás maximális fokú
csúcs kiválasztásával.
On-line algoritmusok. Síbérlés vagy vásárlás. A Lapozási feladat:
a versenyképesség minimum k, minden jelölő algoritmus k-versenyképes.
A k-robot probléma. A ládapakolási probléma.
10. előadás (XI. 18.)
A párhuzamos számítások alapjai. Brent tételei. Minimum kiszámítása.
Nagy számok összeadása és szorzása.
Összefüggőség, Mátrix-szorzás alkalmazásai.
11. előadás (XI. 25.)
Alapvető geometriai algoritmusok.
Konvex burok keresése a síkon [Adat, CLRS].
Legközelebbi pontpár keresése a síkon [CLRS].
Tartomány-fa (vázlatosan).
12. előadás (XII. 2.)
Tartomány-fa részletei, javítás kaszkádolással [Adat].
Legrövidebb utak keresése világméretű úthálózatokban.
Autópálya hierarchiák (HH), összehúzási hierarchiák (CH).
13. előadás (XII. 9.)
CH részletezése Góbor Dániel BSc-szakdolgozata alapján.