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

ZS 2014 - Jiří Sgall

Přednáška se koná v úterý od 14:00 v S5, cvičení se konají nepravidelně po přednášce od 15:40 také v S5

Úkoly a cvičení

Cvičení budou formou domácích úkolů a jejich řešení na cvičeních cca 1x za 3-4 týdny.

Data cvičení jsou 21. 10., 25. 11. a poslední buď 16. 12. nebo 6. 1.

Výsledky

1. série úkolů (termín 19. 10., cvičení budou 21. 10.)
2. série úkolů (termín 23. 11., cvičení budou 25. 11.)
3. série úkolů (termín 4. 1., cvičení budou 6. 1.)

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

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

1. (7. 10.)
- pravděpodobnostní protokol na výpočet průměrného platu
- 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]
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.)

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. (4. 11.)

hladové algoritmy pro rozvrhování [WS 2.3, KT 11.1]
online algoritmy a lokální prohledávání pro rozvrhování [WS 2.3]
hladové algoritmy pro bin packing [WS 3.3, V 9]

5. (11. 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]
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
3/4-aproximační algoritmus pro MAXSAT

6. (18. 11.)

pravděpodobnostní algoritmy pro splnitelnost - dokončení

jednoduchý 0.618-aproximační algoritmus pro MAXSAT
3/4-aproximační algoritmus pro MAXSAT

derandomizace metodou podmíněných pravděpodobností [WS 5.2, V 16.2]

7. (25. 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

zaokrouhlování lineárního programu
primárně-duální algoritmus

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, MU 13.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.) - výběr ze zbývajících témat:

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.