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.