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

Jiří Sgall

ZS 2018 - Pátek 9:00 v S4

Cvičení se konají jednou za 14 dnů ve středu od 9:00 v S7, vede je Matěj Lieskovský

Poznámky k přednášce (verze 3. 10. 2018)

English section

• English lecture takes place on Monday at 2pm in S9, it is given by Petr Kolman
• English exercises (recitations) take place once in two weeks on Wednesday at 9am in S7 and are led by Matěj Lieskovský

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

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

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