Algoritmusok és adatstruktúrák tervezése, elemzése és implementálása I

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

2020 ősz

Előadó: Király Zoltán

Csütörtök 10:15-11:45, távolléti (on-line, TEAMS)


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 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.


Az online vizsgázásról:


Ajánlott irodalom


TEMATIKA


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

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.


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

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.


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

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.


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

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.


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

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.


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

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.

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

Az előadás táblaképe.

Az előadás videófelvétele.


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

Schnyder síkbarajzoló algoritmusa.

Az előadás táblaképe.

Az előadás videófelvétele.


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

Megiddo algoritmusa paraméteres feladatokra.

Az előadás táblaképe.

Az előadás videófelvétele.


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

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.


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

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.


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

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.


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

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.


13. előadás (XII. 10.)

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.