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

Jiří Sgall

ZS 2022 - pondělí 12:20 v S3

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

Konzultace nabízím po dohodě.

Poznámky k přednášce (verze 5. 1. 2023)

Záznamy přednášek z doby covidové distanční výuky jsou k dispozici v SISu pro zapsané studenty

English section

• English lecture takes place on Wednesday at 2pm in S3, it is given by Petr Kolman
• English exercises (recitations) take place once in two weeks on Tuesday 2pm in S6 and are led by Matej Lieskovský

Probraná látka a předběžný plán

• 1. (3. 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. (10. 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. (17. 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]
• minimální řez v grafu [MU 2.5, MR 1, KT 13.2]
• 4. (24. 10.)
• 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]
• hladové algoritmy pro bin packing [WS 3.3, V 9]
• 5. (31. 10.)
  
• 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. (7. 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
• vrcholové pokrytí pomocí lineárního programování
• 7. (14. 11. - přednášel Petr Kolman)
  
• 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
• derandomizace metodou podmíněných pravděpodobností [WS 5.2, V 16.2]
• 8. (21. 11. - přednášel Petr Kolman)
  
• pravděpodobnostní algoritmy pro splnitelnost [WS 5.1-5.5, V 16]
• algoritmus pomocí zaokrouhlování lineárního programu
  
• 3/4-aproximační algoritmus pro MAXSAT
  
• nástin použití semidefinitního programování pro MAX-2SAT
  
• 9. (28. 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. (5. 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. (12. 12. - přednáška zrušena)
• 12. (19. 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
• 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. (2. 1.)
• rychlý paralelní pravděpodobnostní algoritmus pro perfektní párování v bipartitních a obecných grafech [MR 7.3, 12.4]

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

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

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