Ú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
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• 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.
• Vyučující: doc. Mgr. Petr Kolman, Ph.D.; Mgr. Matej Lieskovský; prof. RNDr. Jiří Sgall, DrSc.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Optimalizace

Anotace

čeština

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.

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

angličtina

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 algorithms, which allows to solve problems more efficiently or even to solve problems that are otherwise intractable. Recommended for the 3rd year of Bc. studies.

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

Podmínky zakončení předmětu

čeština

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.

Poslední úprava: Veselý Pavel, Mgr., Ph.D. (12.10.2017)

angličtina

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester. Due to the requirements, additional attempts to pass the tutorial are excluded.

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam. If university attendance is limited, the exam may be held online.

Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (29.09.2020)

Literatura

čeština

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.

Poslední úprava: G_I (28.05.2012)

Požadavky ke zkoušce

čeština

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.

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

angličtina

The exam is oral with time for written preparation. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

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

Sylabus

čeština

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

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

angličtina

Detailed information about the course are given at the web page https://kam.mff.cuni.cz/~kolman/intapxalg.html .

Here is a list of the main topics.

Covered techniques:

• Greedy algorithms as a design method for approximation and online algorithms

• Use of linear programming for approximation algorithms

• Pairwise independent random variables

• Derandomization using the conditional expectations technique

• Local search

Covered problems and algorithms:

• scheduling and disjoint paths in graphs - greedy algorithms

• travelling salesperson problem - combinatorial algorithms

• set cover - greedy algorithm, use of linear programming

• satisfiability (MAX-SAT) - use of linear programming, randomized rounding, derandomization

• dynamic and static hashing - randomized algorithms, pairwise independent variables

• maximal cut - approximation using local search

• minimal cut - a fast randomized algorithm

• maximal independent set - a fast randomized parallel algorithm

• verification of matrix equation - a randomized protocol

Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (29.09.2020)