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 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.
TVSZ módosítása a járvány idejére.
A JOKT októberi kiegészítései.
Az ezzel együtt járó hátrány az, hogy a kérdésekre azonnal kell válaszolni, kidolgozási időre csak nagyon korlátozottan lesz lehetőség.
Randomizált algoritmusok és bonyolultsági osztályok [Lovász].
Karger minimális vágás algoritmusa. Implementáció.
Karger-Stein rekurzív minimális vágás algoritmusa.
Az előadás táblaképe.
Az előadás videófelvétele.
On-line algoritmusok I, versenyképességi hányados.
Példák, alsó becslések a lapozás és k robot
feladatokra.
Erősen versenyképes algoritmus a k-robot problémára k+1 pontú
metrikus térben.
Az előadás táblaképe.
On-line algoritmusok II.
Jelölő algoritmusok a lapozásra.
Randomizált algoritmusok és ellenségek, randomizált algoritmus lapozásra.
On-line gráfszínezés nehézsége.
Az előadás táblaképe.
Az előadás videófelvétele. Valamint az előadás vége, ami már gyakorlaton volt.
A VPN feladat. Eisenbrand-Grandoni-Oriolo-Skutella randomizált közelítő algoritmusa.
Az előadás táblaképe.
Az előadás videófelvétele.
Determináns számítása osztás nélkül, a Mahajan-Vinay algoritmus. Urbanska gyorsítási ötlete.
Az előadás táblaképe.
Az előadás videófelvétele.
Síkgráfok síkbarajzolása lineáris időben. Boyer és Myrvold algoritmusa kombinatorikus beágyazásra ill. Kuratowski bizonyíték keresésére.
Az előadás táblaképe.
Az előadás videófelvétele.
Schnyder síkbarajzoló algoritmusa.
Az előadás táblaképe.
Az előadás videófelvétele.
Megiddo algoritmusa paraméteres feladatokra.
Az előadás táblaképe.
Az előadás videófelvétele.
Favastagság I. Bodlaender lineáris idejű algoritmusa 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).
( Nyomtatható illetve kivetített segédanyag.)
Az előadás táblaképe.
Az előadás videófelvétele.
Favastagság II. Bodlaender és Kloks lineáris idejű algoritmusa, mely adott k+1 vastagságú fafelbontáshoz vagy talál egy k vastagságút, vagy bizonyítja, hogy ilyen nem létezhet.
( Nyomtatható illetve kivetített segédanyag.)
Az előadás táblaképe.
Az előadás videófelvétele.
Algoritmus Szemerédi-partíció megkeresésére. (Dellamonica és társai cikke alapján.)
( Tételjegyzék, illetve az 5. tétel bizonyítása.)
Az előadás táblaképe (bal), táblaképe (jobb).
Az előadás videófelvétele.
FPT I. Ismétlés, jobb algoritmusok lefogó csúcshalmazra.
Létezik-e olyan lefogó csúcshalmaz,
mely a legjobb tört-lefogó értékénél csak \ell-lel
nagyobb?
Iteratív összenyomás, DVC és DFVS.
Az előadáson vetített diák.
Az előadás videófelvétele.
Fejlettebb FPT technikák II.
OCT és DOCT feladatok, amikor csak a páratlan köröket
akarjuk lefogni.
Az Edge Multiway Cut probléma.
Az előadáson vetített diák.
Az előadás videófelvétele.