PředmětyPředměty(verze: 908)
Předmět, akademický rok 2022/2023
   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: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: https://iuuk.mff.cuni.cz/~sgall/vyuka/BCALG/
Garant: prof. RNDr. Jiří Sgall, DrSc.
doc. Mgr. Petr Kolman, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Optimalizace
Anotace -
Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (14.02.2018)
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.
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Pavel Veselý, Ph.D. (12.10.2017)

Pro získání je zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru. Povaha kontroly studia neumožňuje opakování zápočtu.

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.

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.

Požadavky ke zkoušce -
Poslední úprava: prof. RNDr. Jiří Sgall, DrSc. (22.06.2019)

Zkouška je ústní s písemnou přípravou. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.

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