Aproximační a online algoritmy - NDMX018

• Anglický název: Approximation and Online Algorithms
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: letní
• E-Kredity: 6
• Rozsah, examinace: letní s.:2/2, 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
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NDMI018
• Další informace: http://iuuk.mff.cuni.cz/~sgall/vyuka/APX/
• Garant: prof. RNDr. Jiří Sgall, DrSc.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Prerekvizity : {NXXX007, NXXX008, NXXX009, NXXX036, NXXX037}
• Neslučitelnost : NDMI018
• Záměnnost : NDMI018

Anotace

čeština

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í. Tzv. online algoritmy se studují v situaci, kde není předem znám celý vstup. Přednáška se zaměří na teoretické studium aproximačních a online algoritmů pro různé problémy. Předpokládá se znalost na úrovni Bc. předmětu NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů.

Poslední úprava: IUUK (11.05.2015)

angličtina

For many optimization problems it is impossible to find an optimal solution fast. In such case, it is important to study approximation algorithms that work faster, but the solution they find is not necessarily an optimal one. Sometimes, we also have to react to partial input without knowledge of the complete input, by building a solution step by step. Such algorithms are called on-line. The subject of the course is the study of these two classes of algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and randomized algorithms.

Poslední úprava: IUUK (11.05.2015)

Cíl předmětu

čeština

Naučit středně pokročilé techniky návrhu a analýzy aproximačních a online algoritmů.

Poslední úprava: IUUK (11.05.2015)

angličtina

Teach the students selected techniques of design and analysis of approximation and online algorithms.

Poslední úprava: IUUK (11.05.2015)

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 za podmínky účasti studenta na cvičeních. Při neúčasti jsou potřeba dvě třetiny z celkového počtu bodů. 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: Sgall Jiří, prof. RNDr., DrSc. (04.03.2018)

angličtina

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed.

The exam is oral. 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. (04.03.2018)

Literatura

čeština

• D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.

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

• A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.

• A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.

Poslední úprava: IUUK (11.05.2015)

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:

• Základní pojmy, aproximační a kompetitivní poměr

• Polynomiální aproximační schémata, jejich vztah k silné NP-úplnosti

• Pokročilé použití metod lineárního programování v aproximačních algoritmech: zaokrouhlování, primárně-duální algoritmy

• Použití metod semidefinitního programování v aproximačních algoritmech

• Použití potenciálu pro online algoritmy

• Metody pro dokazování obtížnosti i přibližného řešení kombinatorických problémů: L-redukce, APX-úplnost, PCP věta

Probírané problémy a algoritmy:

• Různé modely rozvrhování a "bin packing", hladový algoritmus, další aproximační a online algoritmy

• Kombinatorické problémy: Steinerův strom, maximální řez, barvení grafů

• Online algoritmy pro paging (caching) a k-server problém

• Online algoritmy pro pohyb v neznámém prostředí

Poslední úprava: IUUK (11.05.2015)

angličtina

Techniques covered:

• Basic definitions, approximation and competitive ratio

• Polynomial-time approximation schemes, their relation to strong NP-hardness

• Advanced use of linear programming in approximation algorithms: rounding, primal-dual algorithms

• Use of semidefinite programming in approximation algorithms

• Use of potential functions for online algorithms

• Methods for proving the hardness of approximation: L-reductions, APX-completeness, PCP theorem

Problems and algorithms covered:

• Various models of scheduling and bin packing, greedy algorithms, further approximation and online algorithms

• Combinatorial problems: Steiner trees, maximal cut, coloring

• Online algorithms for paging (caching) and k-server problem

• Online algorithms for navigation in an unknown environment

Poslední úprava: IUUK (11.05.2015)