Algoritmusok tervezése és elemzése II.

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

2023 ősz

Előadó: Király Zoltán

Hétfő 10:15-11:45, D.4.713.


Csak a hallgatóimnak / Only for my students


Hirdetmények


Ajánlott irodalom


1. előadás (IX. 11.)

Kódolás:
Billy, a könyvelő.
k darab 1-est tartalmazó n hosszú bitsorozatok elkódolása. Entrópia, információelméleti alsó becslés, Kolmogorov-bonyolultság (mese). Gráfok és fák elkódolása, Prüfer-kód. [Algbony]
Huffman-kód [RISz].


2. előadás (IX. 18.)

Szófa. Lempel-Ziv-Welch tömörítési eljárása [RISz].
Mélységi keresés irányított gráfokon. Részfa-lemma. Erős komponensek és a redukált gráf top. sorrendjének megtalálása O(m) lépésben.


3. előadás (IX. 25.)

Mediáns keresés, gyorsrendezés.

Mintaillesztés. I. Kimerítő keresés (Brute Force).
II. Quick Search (Horspool).
III. Knuth-Morris-Pratt [RISz, CLRS].


4. előadás (X. 2.)

Randomizált algoritmusok. Schwartz-Zippel-lemma.
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.


5. előadás (X. 9.)

Mit tegyünk, ha NP-nehéz feladatokat kell megoldani? I. Exponenciális algoritmusok, heurisztikák.
I a) brute force
I b) heurisztika + brute force
I c) backtrack
I d) elágazás és korlátozás (branch-and-bound).

II. Speciális input/output.


6. előadás (X. 16.)

III. Közelítő algoritmusok, definíciók, egyszerű példák.
Metrikus utazó-ügynök, 2-közelítés.
Approximációs sémák.
FPTAS a hátizsák-feladatra.

2-közelítés a minimális súlyú lefogó csúcshalmaz feladatra, mese ILP-ről és a tört relaxált optimális megoldásának kikerekítéséről általában.


7. előadás (XI. 6.)

Paraméteres problémák, fix paraméteres feladatok. XP és FPT.
A minimális lefogó csúcshalmaz:
Döntési fa alapú FPT a minimális lefogó csúcshalmazra maximális fokú csúcs kiválasztásával.
Kernel, korona-redukció. 2k méretű kernel készítése.


8. előadás (XI. 13.)

On-line algoritmusok. Síbérlés vagy vásárlás. Versenyképességi hányados.
A Lapozási feladat: a versenyképesség minimum k, minden jelölő algoritmus k-versenyképes.
A k-robot probléma, tételek bizonyítás nélkül.
Röviden volt: A ládapakolási probléma, a First Fit algoritmus; on-line gráfszínezés, kapcsolat adatstruktúrákkal.


9. előadás (XI. 20.)

A párhuzamos számítások alapjai. Brent tételei. Nagy számok összeadása és szorzása. Mátrix-szorzás alkalmazásai.


10. előadás (XI. 27.)

Alapvető geometriai algoritmusok.
I. Konvex burok keresése a síkon [Adat, CLRS].
II. Legközelebbi pontpár keresése a síkon [CLRS].
III. Téglalapba eső pontok lekérdezése. Tartomány-fa felépítése/I. [Adat].


11. előadás (XII. 4.)

Tartományfa használata. Tartományfa javítása kaszkádolással, d dimenziós tartományfa [Adat]. Felépítés O(n\log n)-ben.

Legrövidebb utak keresése világméretű úthálózatokban. Kétirányú Dijkstra, A^* algoritmus.


12. előadás (XII. 11.)

Legrövidebb utak keresése világméretű úthálózatokban előfeldolgozással. Autópálya hierarchiák (HH), tranzit csúcsok (TNR), összehúzási hierarchiák (CH).

Konzultáció.