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

Jiří Sgall

ZS 2021 - Pátek 10:40 v S3

Cvičení se konají jednou za 14 dnů v úterý od 10:40 v S7, vede je Matej Lieskovský

Konzultace nabízím po dohodě, typicky budu k dispozici v úterý nebo v pátek po přednášce.

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ý

Probraná látka

• 1. (1. 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. (8. 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. (15. 10.)
• definice: pravděpodobnostní prostory [MU 1.2]
• definice: náhodné proměnné, indikátorové náhodné proměnné [MU 2.1]
• definice: střední hodnota, její linearita [MU 2.1]
• definice: podmíněná pravděpodobnost [MU 2.3]
  
• pravděpodobnostní řešení konfliktů v distribuovaných systémech [KT 13.1, MR 12.5]
• quicksort [MR 1, MU 2.5]
  
• 4. (22. 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]
• 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]
• 5. (29. 10.)
• hladové algoritmy pro bin packing [WS 3.3, V 9]
• hladové algoritmy pro hledání disjunktních cest [KT 11.5]
• hladové algoritmy pro hledání disjunktních cest s kapacitou [KT 11.5]
• 6. (5. 11.)
  
• 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
  
• lineární program pro MAXSAT a jeho pravděpodobnostní zaokrouhlování
  
• 7. (12. 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í
  
• 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
• 8. (19. 11.)
• derandomizace metodou podmíněných pravděpodobností [WS 5.2, V 16.2]
• 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]
• 9. (26. 11.)
• 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
• univerzální systémy hašovacích funkcí a jejich použití [MR 8.4, MU 13.3]
• 10. (3. 12.)
• 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]
• pravděpodobnostní testování maticového násobení v lineárním čase [MR 7.1, MU 1.3]
• 11. (10. 12.)
• pravděpodobnostní testování rovnosti polynomů [MR 7.2, MU 1.1]
• rychlý paralelní pravděpodobnostní algoritmus pro perfektní párování v bipartitních a obecných grafech [MR 7.3, 12.4]
• 12. (17. 12.)
• rychlý paralelní pravděpodobnostní algoritmus pro perfektní párování v bipartitních a obecných grafech = dokončení [MR 7.3, 12.4]
• 13. (7. 1.)
• 2-aproximační algoritmus pro rozvrhování na obecných počítačích ("unrelated machines") [V 17, WS 11.1]
• pravděpodobnostní algoritmus pro dělení zdrojů s lineárně mnoha řezy [S. Even, A. Paz: A note on cake cutting. Discrete Applied Mathematics 7(3):285-296, 1984. doi:10.1016/0166-218x(84)90005-2; také kniha s dalším materiálem J. Robertson, W. Webb: Cake-Cutting Algorithms: Be Fair if You Can, A K Peters, 1998]

Předchozí běh přednášky v r. 2020

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 případná distanční zkouška.

Termíny prezenčních zkoušek jsou vypsané v SISu. 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 bude potřebná distanční zkouška, domluvíme se individuálně.

V únoru budu na dovolené, poslední dva týdny zkouškového období nebudou žádné termíny.

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

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

• 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.)
  
• 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]