NDMI084 - Aproximační a pravděpodobnostní
algoritmy
ZS 2013 - Jiří Sgall
Přednáška se koná v pondělí 9:00 v S5, cvičení se konají
nepravidelně v pátek od 12:20 také v S5
cvičení budou formou domácích úkolů a jejich řešení na cvičeních
cca 1x za 3-4 týdny
Úkoly a cvičení
Zkoušky
Vypsal jsem dva terminy, úterý 14.1. a 28.1. od 9:00 v S7 (v
případě malého počtu studentů u mě v pracovně, 3 patro č.326, u
zadního schodiště). Zkouška je ústní, dostanete za úkol vysvětlit
některý algoritmus nebo jiné téma.
Probraná látka podle přednášek
- 1. (7. 10.)
- pravděpodobnostní protokol na výpočet průměrného platu
- modely pravděpodobnostních výpočtů [MR 1.5]
- problém obchodního cestujícího (TSP), kostrový 2-aproximační
algoritmus [WS 2.4]
- 2. (14. 10.)
- definice: optimalizační a NP-optimalizační problémy,
aproximační algoritmus a poměr [WS 1.1, V1]
- problém obchodního cestujícího (TSP), Christofidesův 1.5
aproximační algoritmus [WS 2.4, V 3.2]
- definice: pravděpodobnostní prostory [MU 1.2]
- 3. (21. 10.)
- 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. (4. 11.)
- hladové algoritmy pro rozvrhování [WS 2.3, KT 11.1]
- hladové algoritmy pro bin packing [WS 3.3, V 9]
- hladové algoritmy pro hledání disjunktních cest [KT 11.5]
- 5. (11. 11.)
- hladové algoritmy pro hledání disjunktních cest s kapacitou
[KT 11.5]
- pravděpodobnostní algoritmy pro splnitelnost [WS 5.1-5.5, V
16]
- jednoduchý 1/2 a 0.618-aproximační algoritmus pro MAXSAT,
7/8-aproximační pro MAX-E3-SAT
- 3/4-aproximační algoritmus pro MAXSAT
- 6. (18. 11.)
- 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]
- hladový algoritmus a jeho analýza pomocí duálního
lineárního programu
- 7. (25. 11.)
- algoritmy pro vrcholové a množinové pokrytí - dokončení
- zaokrouhlování lineárního programu
- primárně-duální algoritmus
- lokální prohledávání [WS 2.3]
- rozvrhování a maximální řez jako varianty hladového
algoritmu
- hledání kostry minimálního stupně
- 8. (2. 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, MU13.3.3]
- 9. (9. 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]
- 10. (16. 12.)
- rychlý paralelní pravděpodobnostní algoritmus pro perfektní
párování v bipartitních a obecných grafech [MR 7.3, 12.4]
- rychlý paralelní pravděpodobnostní algoritmus pro maximální
nezávislou množinu v grafu [MR 12.3]
- 11. (6. 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
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
Literatura
[KT] J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.
[WS] D. P. Williamson, D. B. Shmoys: The Design of
Approximation Algorithms, Cambridge university press, 2011.
[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.
[MR] R. Motwani, P. Raghavan: Randomized algorithms.
[MU] M. Mitzenmacher, E. Upfal: Probability and Computing:
Randomized Algorithms and Probabilistic Analysis.