NDMI084 - Úvod do aproximačních a pravděpodobnostních algoritmů

Jiří Sgall

ZS 2020 - Pondělí 10:40 v S3 / zoom

Cvičení se konají jednou za 14 dnů ve čtvrtek od 14:00 v S11, vede je Matej Lieskovský

Distanční výuka proběhne formou online přednášek přes zoom. Adresa je https://cesnet.zoom.us/my/[moje příjmení] . První přednáška se koná 5. 10. 2020. Budu rád, pokud se přednášky zúčastníte interaktivně, se zapnutým videem alespoň na diskusní části, a s plným jménem.

Konzultace nabízím na stejném zoomu většinou v pondělí nebo v úterý odpoledne, případně i jindy po dohodě.

Poznámky k přednášce (verze 8. 1. 2020)

Záznamy přednášek jsou k dispozici v SISu pro zapsané studenty

English section

• English lecture takes place on Thursday at 9am in S4, it is given by Petr Kolman
• English exercises (recitations) take place once in two weeks on Thursday 2pm in S11 and are led by Matej Lieskovský

Zkoušky

Zkouška je ústní s písemnou přípravou. Po zadání otázky se většina studentů připravuje cca 10-20 minut. Poté následuje diskuse nad přípravou, doplňující otázky apod. Podobně bude probíhat i distanční zkouška.

Termíny prezenčních zkoušek jsou vypsané v SISu na pondělí dopoledne. Mají malou kapacitu, abychom mohli dodržovat potřebné odstupy. Pokud se naplní kapacita a jste ve frontě, můžete počítat s tím, že Vás v daný den vyzkouším. Pokud by se místo neuvolnilo, tak se domluvíme na čase buď dříve anebo odpoledne.

Pokud nemůžete nebo nepovažujete za bezpečné přijet na prezenční zkoušku, vyzkouším Vás distančně přes zoom. Tyto termíny dohodneme individuálně mailem. Je potřeba minimálně funkční mikrofon a kamera. Rád bych také viděl Vaše poznámky z přípravy, např. naskenované či vyfocené, v nejhorším aspoň přes kameru. Ideální by bylo psát na sdílenou obrazovku např. na tabletu, pokud máte tu možnost.

Probraná látka podle přednášek

• 1. (5. 10.)
• pravděpodobnostní protokol na výpočet průměrného platu
• definice: optimalizační a NP-optimalizační problémy [WS 1.1, V1]
• definice: aproximační algoritmus a poměr [WS 1.1, V1]
• 2. (12. 10.)
  
• problém obchodního cestujícího (TSP), kostrový 2-aproximační algoritmus [WS 2.4]
• problém obchodního cestujícího (TSP), Christofidesův 1.5 aproximační algoritmus [WS 2.4, V 3.2]
• 3. (19. 10.)
• pravděpodobnostní protokol na výpočet průměrného platu
• definice: pravděpodobnostní prostory [MU 1.2]
• modely pravděpodobnostních výpočtů [MR 1.5]
  
• definice: střední hodnota, její linearita [MU 2.1]
  
• pravděpodobnostní řešení konfliktů v distribuovaných systémech [KT 13.1, MR 12.5]
• 4. (25. 10.)
• minimální řez v grafu [MU 2.5, MR 1, KT 13.2]
• hladové algoritmy pro rozvrhování [WS 2.3, KT 11.1]
• 5. (2. 11.)
• lokální prohledávání pro rozvrhování [WS 2.3]
• online algoritmy pro rozvrhování - model a hladový algoritmus jako příklad [WS 2.3]
• hladové algoritmy pro bin packing [WS 3.3, V 9]
• 6. (9. 11.)
  
• hladové algoritmy pro hledání disjunktních cest [KT 11.5]
• hladové algoritmy pro hledání disjunktních cest s kapacitou [KT 11.5]
• 7. (16. 11.) - bohužel není nahraná
  
• vrcholové pokrytí pomocí lineárního programování
  
• pravděpodobnostní algoritmy pro splnitelnost [WS 5.1-5.5, V 16]
• jednoduchý 1/2-aproximační algoritmus pro MAXSAT, 7/8-aproximační pro MAX-E3-SAT
• jednoduchý 0.618-aproximační algoritmus pro MAXSAT - probráno na cvičeních
  
• 3/4-aproximační algoritmus pro MAXSAT
• 8. (23. 11.) a další plán
• pravděpodobnostní algoritmy pro splnitelnost [WS 5.1-5.5, V 16]
• 3/4-aproximační algoritmus pro MAXSAT - dokončení
  
• derandomizace metodou podmíněných pravděpodobností [WS 5.2, V 16.2]
• algoritmy pro vrcholové a množinové pokrytí [WS 1.2-1.6, 7.1, V 13-14]
  
• zaokrouhlování lineárního programu
  
• primárně-duální algoritmus
• hladový algoritmus a jeho analýza pomocí duálního lineárního programu
• 9. (30. 11.)
• algoritmy pro vrcholové a množinové pokrytí [WS 1.2-1.6, 7.1, V 13-14]
  
• hladový algoritmus a jeho analýza pomocí duálního lineárního programu
• rychlý paralelní pravděpodobnostní algoritmus pro maximální nezávislou množinu v grafu [MR 12.3,  Eric Vigoda napsal pěkné poznámky http://www.cc.gatech.edu/~vigoda/7530-Spring10/MIS.pdf]
• 10. (7. 12.)
• rychlý paralelní pravděpodobnostní algoritmus pro maximální nezávislou množinu v grafu - dokončení
• derandomizace pomocí po dvou nezávislých náhodných proměnných
• 11. (14. 12.)
• univerzální systémy hašovacích funkcí a jejich použití [MR 8.4, MU 13.3]
  
• dynamický slovník s očekávaným konstantním počtem operací [MR 8.4, MU 13.3.3]
  
• statický slovník s vyhledáváním v konstantním čase v nejhorším případě [MR 8.5, MU 13.3.3]
• 12. (21. 12.)
• pravděpodobnostní testování maticového násobení v lineárním čase [MR 7.1, MU 1.3]
  
• pravděpodobnostní testování rovnosti polynomů [MR 7.2, MU 1.1]
• 13. (4. 1.)
• rychlý paralelní pravděpodobnostní algoritmus pro perfektní párování v bipartitních a obecných grafech [MR 7.3, 12.4]

Probraná látka podle přednášek v r. 2018

• 1. (4. 10.)
• pravděpodobnostní protokol na výpočet průměrného platu
• definice: optimalizační a NP-optimalizační problémy [WS 1.1, V1]
• 2. (11. 10.)
  
• definice: aproximační algoritmus a poměr [WS 1.1, V1]
• problém obchodního cestujícího (TSP), kostrový 2-aproximační algoritmus [WS 2.4]
• problém obchodního cestujícího (TSP), Christofidesův 1.5 aproximační algoritmus [WS 2.4, V 3.2]
• 3. (18. 10.)
• definice: pravděpodobnostní prostory [MU 1.2]
• modely pravděpodobnostních výpočtů [MR 1.5]
  
• definice: střední hodnota, její linearita [MU 2.1]
  
• pravděpodobnostní řešení konfliktů v distribuovaných systémech [KT 13.1, MR 12.5]
  
• Quicksort jako pravděpodobnostní algoritmus [MU 2.5, MR 1, KT 13.5]
• 4. (25. 10.)
  
• minimální řez v grafu [MU 2.5, MR 1, KT 13.2]
• lokální prohledávání pro rozvrhování [WS 2.3]
• 5. (2. 11.)
  
• hladové algoritmy pro rozvrhování [WS 2.3, KT 11.1]
• online algoritmy pro rozvrhování - model a hladový algoritmus jako příklad [WS 2.3]
• hladové algoritmy pro bin packing [WS 3.3, V 9]
  
• hladové algoritmy pro hledání disjunktních cest [KT 11.5]
• 6. (9. 11.)
  
• hladové algoritmy pro hledání disjunktních cest s kapacitou [KT 11.5]
• vrcholové pokrytí pomocí lineárního programování
  
• pravděpodobnostní algoritmy pro splnitelnost [WS 5.1-5.5, V 16]
• jednoduchý 1/2-aproximační algoritmus pro MAXSAT, 7/8-aproximační pro MAX-E3-SAT
• 7. (16. 11.)
  
• pravděpodobnostní algoritmy pro splnitelnost [WS 5.1-5.5, V 16]
• jednoduchý 0.618-aproximační algoritmus pro MAXSAT - probráno na cvičeních
  
• 3/4-aproximační algoritmus pro MAXSAT
• derandomizace metodou podmíněných pravděpodobností [WS 5.2, V 16.2]
• 8. (23. 11.)
  
• algoritmy pro vrcholové a množinové pokrytí [WS 1.2-1.6, 7.1, V 13-14]
  
• zaokrouhlování lineárního programu
  
• primárně-duální algoritmus
• hladový algoritmus a jeho analýza pomocí duálního lineárního programu
• 9. (30. 11.)
• univerzální systémy hašovacích funkcí a jejich použití [MR 8.4, MU 13.3]
  
• dynamický slovník s očekávaným konstantním počtem operací [MR 8.4, MU 13.3.3]
  
• statický slovník s vyhledáváním v konstantním čase v nejhorším případě [MR 8.5, MU 13.3.3]
• 10. (7. 12.)
• rychlý paralelní pravděpodobnostní algoritmus pro maximální nezávislou množinu v grafu [MR 12.3,  Eric Vigoda napsal pěkné poznámky http://www.cc.gatech.edu/~vigoda/7530-Spring10/MIS.pdf]
• 11. (14. 12.)
• rychlý paralelní pravděpodobnostní algoritmus pro maximální nezávislou množinu v grafu - dokončení
• derandomizace pomocí po dvou nezávislých náhodných proměnných
• 12. (21. 12.)
• pravděpodobnostní algoritmus pro dělení zdrojů s lineárně mnoha řezy
• 13. (4. 1.)
• pravděpodobnostní testování maticového násobení v lineárním čase [MR 7.1, MU 1.3]
  
• pravděpodobnostní testování rovnosti polynomů [MR 7.2, MU 1.1]
• 14. (11. 1.)
• rychlý paralelní pravděpodobnostní algoritmus pro perfektní párování v bipartitních a obecných grafech [MR 7.3, 12.4]
• neprobráno
• 2-aproximační algoritmus pro rozvrhování na obecných počítačích ("unrelated machines") [V 17, WS 11.1]

Předchozí běh přednášky v r. 2019 (anglicky)

Literatura

[WS] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.

[MR] R. Motwani, P. Raghavan: Randomized algorithms, Cambridge University Press, 1995.

[MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.

[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.

[KT] J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.

Sylabus

Přednáška probírá středně pokročilé techniky pro návrh a analýzu algoritmů a ilustruje je na konkrétních kombinatorických problémech. Pro mnohé optimalizační problémy je obtížné navrhonout algoritmy, které je vyřeší optimálně a zároveň rychle (např. pro NP-úplné problémy). V takovém případě studujeme tzv. aproximační algoritmy, které pracují rychle, a najdou řešení více či méně blízké optimálnímu řešení. Často pro návrh algoritmů (aproximačních i jiných) používáme náhodnost, což umožňuje řešit některé úlohy efektivněji nebo řešit úlohy jinak neřešitelné. Doporučeno pro 3. ročník bakalářského studia.

Probírané techniky:

• Hladový algoritmus jako metoda pro návrh aproximačních a online algoritmů
• Použití lineárního programování pro návrh aproximačních algoritmů
• Po dvou nezávislé náhodné proměnné
• Odstranění náhodnosti metodou podmíněných pravděpodobností
• Lokální prohledávání

Probírané problémy a algoritmy:

• Rozvrhování a hledání disjunktních cest v grafu - hladové algoritmy
• Problém obchodního cestujícího a vrcholové pokrytí - jednoduché kombinatorické aproximační algoritmy
• Množinové pokrytí - hladový algoritmus, použití lineárního programování
• Splnitelnost (MAX-SAT) - použití lineárního programování, náhodné zaokrouhlování, derandomizace
• Hashování dynamické a statické - pravděpodobnostní algoritmy, po dvou nezávislé náhodné proměnné
• Největší řez v grafu - aproximace pomocí lokálního prohledávání
• Maximální nezávislá množina v grafu - rychlý pravděpodobnostní paralelní algoritmus
• Verifikace maticových rovnic - pravděpodobnostní protokol