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.
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.
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.
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.
A VPND feladat. Eisenbrand-Grandoni-Oriolo-Skutella randomizált közelítő algoritmusa (2005).
Determináns számítása osztás nélkül, a Mahajan-Vinay algoritmus (1997). Urbanska gyorsítási ötlete (2010).
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.
Schnyder síkbarajzoló algoritmusa (1990).
Megiddo algoritmusai paraméteres feladatokra (1979 és 1983).
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).
TERV:
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.
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.)
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.