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

Sylabus

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í

- Nejmenší řez v grafu - rychlý pravděpodobnostní algoritmus

- Maximální nezávislá množina v grafu - rychlý pravděpodobnostní paralelní algoritmus

- Verifikace maticových rovnic - pravděpodobnostní protokol

Anotace

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é navrhnout 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 Bc. studia.