PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Úvod do aproximačních a pravděpodobnostních algoritmů - NDMI084
Anglický název: Introduction to approximation and randomized algorithms
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/1 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Garant: doc. Mgr. Petr Kolman, Ph.D.
prof. RNDr. Jiří Sgall, DrSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Anotace -
Poslední úprava: (05.05.2014)

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č
Literatura -
Poslední úprava: G_I (28.05.2012)

D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.

J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.

V.V. Vazirani: Approximation Algorithms, Springer, 2001.

R. Motwani, P. Raghavan: Randomized algorithms.

M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis.

Sylabus -
Poslední úprava: prof. RNDr. Jiří Sgall, DrSc. (12.05.2015)

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

 
Univerzita Karlova | Informační systém UK