Toto je stránka cvičení předmětu Aproximační a online algoritmy, který se koná v LS 2017/2018.
Cvičí ho Martin Böhm a Pavel Veselý.Cvičení probíhá každé úterý v 17:20 v S1 (Malostranské náměstí, 4. patro).
Průběh cvičení
Cvičení bude probíhat klasicky, to jest společným řešením příkladů s občasnou nápovědou. Můžeme také občas zopakovat látku z přednášky, pokud o to budete stát. Na cvičeních se zapisuje účast.
Podmínky zápočtu
Abyste dostali zápočet, budete potřebovat:
- 50% bodů z domácích úkolů, pokud budete mít pravidelnou účast na cvičeních;
- 66% bodů z domácích úkolů, pokud nechodíte na cvičení.
Účast se počítá klasicky, tj. tři absence jsou v pořádku bez vysvětlování a pokud budete déle v cizině nebo nemocní a budete stát o účast, tak napište email.
Studijní materiály
- stránka přednášky s odkazy na články;
- knížka The Design of Approximation Algorithms, kterou doporučujeme a která obsahuje i dost příkladů na cvičení (dostupná online);
- cvičení Dušana Knopa v předchozím běhu v roce 2016;
- a historicky také cvičení J. Sgalla z roku 2014, 2012 a 2010.
Co bylo
- 1: PTASy založené na dynamickém programování.
- 2: Primárně-duální algoritmy (1) včetně opakování lineárního programování.
- 3: Primárně-duální algoritmy (2).
- 4: Semidefinitní programování (1), mj. příklad SDP vynucující ostrou nerovnost, SDP počítající odmocninu a SDP mající řešení s dvojitě exponenciální hodnotou v počtu proměnných.
- 5: Semidefinitní programování (2), včetně ukázky, jak vypadá množina pozitivně semidefinitních matic geometricky (tj. že jde o uzavřený kužel), viz knížka Approximation Algorithms and Semidefinite Programming (kapitola 4). Poslední dva příklady jsme nestihli.
- 6: Metrické problémy a zbylé příklady na SDP.
- 7: Online algoritmy (1): Cow path (deterministický algoritmus) a Ski rental (optimální deterministický i pravděpodobnostní algoritmus)
- 8: Online algoritmy (2): Stránkování a k-server.
- 9: Online algoritmy (3): 1-kompetitivní semi-online algoritmus pro preemptivní rozvrhování a online bipartitní párování.
Body
V tabulce jsou zobrazeny inicály (v obráceném pořadí, tj. PM pro studenta Příjmení Jméno), ale můžete si zvolit přezdívku. "x.y" znamená "Série x, úkol y", "Sx" znamená součet bodů za sérii x. Otazník znamená, že řešení je potřeba ještě dovysvětlit.