Ú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 do 2017
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• 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

čeština

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č

angličtina

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (14.02.2018)

This course covers techniques for design and analysis of algorithms, demonstrated on concrete combinatorial problems. For many optimization problems it is impossible (or NP-hard) to design algorithms that find an optimal solution fast. In such a case we study approximation algorithms that work faster, at the cost that we find a good solution, not necessarily an optimal one. Often we use randomness in design of (approximation and other) algorithms, which allows to solve problems more efficiently or even to solve problems that are otherwise intractable. Recommended for the 3rd year.

Literatura

čeština

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

čeština

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

angličtina

Poslední úprava: prof. RNDr. Jiří Sgall, DrSc. (11.10.2017)

This course covers techniques for design and analysis of algorithms, demonstrated on concrete combinatorial problems. For many optimization problems it is impossible (or NP-hard) to design algorithms that finds an optimal solution fast. In such a case we study approximation algorithms that work faster, at the cost that we find a good solution, not necessarily an optimal one. Often we use randomness in design of (approximation and other) algorithms, which allows to solve problems more efficiently or even to solve problems that are otherwise intractable. Recommended for the 3rd year.