Algoritmusok tervezése és elemzése II.

Előadás harmadéves alkalmazott matematikus hallgatóknak

2019 ősz

Előadó: Király Zoltán

Hétfő 12:15-13:45, Déli tömb, 0.820


Csak a hallgatóimnak / Only for my students


Hirdetmények


Ajánlott irodalom


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.