Haladó algoritmusok

Régi cím: Algoritmusok és adatstruktúrák tervezése, elemzése és implementálása I

Előadás MSc-s matematikusoknak és alkalmazott matematikusoknak

2026 ősz

Előadó: Király Zoltán

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


Csak a hallgatóimnak / Only for my students


Hirdetmények


Vizsga

Vizsgára csak az jelentkezhet be, akinek megvan ebből a tárgyból a gyakjegye és az Algoritmuselmélet törzsanyag vizsgája.

A vizsgára azoknak, akik az előadások legalább kétharmadán ott voltak, csak 8 anyagrészt kell megtanulni. A 4 kötelezően megtanulandó:

Ezenkívül mindenki választhat még 4 anyagrészt (1 anyagrész = 1 előadás anyaga). Ezek listáját legkésőbb a vizsgára jelentkezéssel egyidőben nekem emailben el kell küldeni.


Ajánlott irodalom


TEMATIKA


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

Randomizált algoritmusok és bonyolultsági osztályok [Lovász].
Karger minimális vágás algoritmusa. Implementáció.
Karger és Stein rekurzív minimális vágás algoritmusa.


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

On-line algoritmusok I, síbérlés, versenyképességi hányados.
A lapozás feladat, alsó becslés, jelölő algoritmusok.
A \(k\)-robot feladat, alsó becslés, erősen versenyképes algoritmus abban a speciális esetben, ha a metrikus térnek \(k+1\) pontja van.


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

On-line algoritmusok II.
Amortizációs költség. Randomizált algoritmusok és ellenségek, randomizált algoritmus lapozásra.
On-line gráfszínezés nehézsége.


4. előadás (IX. 29.)

A VPND feladat. Eisenbrand-Grandoni-Oriolo-Skutella randomizált közelítő algoritmusa (2005).


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

Determináns számítása osztás nélkül, a Mahajan-Vinay algoritmus (1997). Urbanska gyorsítási ötlete (2010).


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

Síkgráfok síkbarajzolása lineáris időben. Boyer és Myrvold algoritmusa (2004) kombinatorikus beágyazásra ill. Kuratowski-bizonyíték keresésére.

( Segédanyag (ábrák).)


7. előadás (X. 21.)

Schnyder síkbarajzoló algoritmusa (1990).


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

Megiddo algoritmusai paraméteres feladatokra (1979 és 1983).


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

Favastagság I. Bodlaender lineáris idejű algoritmusa (1996) annak eldöntésére, hogy egy gráf favastagsága legfeljebb 100-e. És ha igen, meg is konstruálja a 100 vastagságú fa-felbontást (használva következő órán elhangzó algoritmust).

( A kiosztott segédanyag.)


TERV:


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

Favastagság II. Bodlaender és Kloks lineáris idejű algoritmusa (1996), mely adott \(k+1\) vastagságú fafelbontáshoz vagy talál egy \(k\) vastagságút, vagy bizonyítja, hogy ilyen nem létezhet.

( A kiosztott segédanyag.)


11. előadás (XI. 24.)

Algoritmus Szemerédi-partíció megkeresésére. (Dellamonica és társai cikke (2011) alapján.)

( Tételjegyzék, illetve az 5. tétel bizonyítása.)


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

FPT. Létezik-e olyan lefogó csúcshalmaz, mely a legjobb tört-lefogó értékénél csak \(k\)-val nagyobb?
Iteratív összenyomás, FVS és DFVS; valamint OCT és DOCT.