Cvičení z Úvodu do aproximačních a pravděpodobnostních algoritmů

Úterý 17:20, S1, liché týdny semestru, ZS 17/18

K přednášce Úvod do aproximačních a pravděpodobnostních algoritmů doc. Petra Kolmana a prof. Jiřího Sgalla konající se v úterky v lichých týdnech semestru (sudých kalendářních týdnech) od 17:20 v S1.

Webiste of the English class on Mondays at 15:40 in even semester weeks

Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po cvičení. Také budu rád, když se v průběhu cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi emailem. Pro představu o cvičení se podívejte stránky cvičení v roce 2016 vedeného Martinem Böhmem.

Co jsme dělali

3. 10.	Opakování a procvičování pravděpodobnosti. Příklady (poslední jsme nestihli).
17. 10.	Problém obchodního cestujícího. Příklady. (Poslední jsme nestihli – zkuste si dokázat, že algoritmus je 2-aproximační, na přání poskytnu hint. U třetího příkladu je jednoudušší nahlédnout řešení pro orientovaný graf, přičemž nezakazujeme kružnice délky 2.)
31. 10.	Základy lineárního programování, vytváření celočíselných programů pro kombinatorické problémy a zmíněna též dualizace. Příklady. (Poslední si na procvičení CLP můžete vyřešit sami.)
14. 11.	Cvičil Martin Böhm: Hladové algoritmy na rozvrhování se závislostmi, batoh a problém k center. Příklady. (Příklady na SAT se nestihly.)
28. 11.	Zaokrouhlování řešení lineární programů (relaxací). Příklady (nestihli jsme akorát analýzu posledního příkladu).
12. 12.	Hašování, konstrukce slabě 2-univerzální rodiny. Příklady (poslední příklad bude dodělaný příště).
9. 1.	Bonusové cvičení, které neproběhlo (podobné nedávnému rozhovoru s M. Zemanem): po 3 nezávislé náhodné bity (dokončení důkazu z minula), paralelní algoritmy a párování algebraickými metodami. Příklady na paralelní algoritmy si můžete vyzkoušet sami, nejsou těžké. Příklad na Edmondsovu matici je podobný důkazu na přednášce, k němuž se přidá fakt, že hodnost matice je rovna velikosti největší regulární podmatice. Důkaz pro Tutteho matici.

Domácí úkoly

• 1. série – do pondělí 20. 11. 2017 15:39. Řešení př. 2-4 (anglicky).
• 2. série – do úterý 19. 12. 2017. Dejte pozor na to, že u 3. úkolu nemusí být čísla na vstupu navzájem různá. Také můžete používat pomocné paměti, kolik si stihnete alokovat.
• 3. série – do neděle 4. 2. 2018 (jestliže to ve zkouškovém nestíháte a chybí vám jen několik bodů, ozvěte se a dohodneme se na dodělání zápočtu). "Rychlý paralelní pravděpodobnostní algoritmus" znamená algoritmus běžící v polylogaritmickém čase (ve střední hodnotě) na polynomiálně procesorech. Pokud vám bude chybět pár bodů po vyřešení 3. série (ale ne nutně bonusového příkladu), dejte mi vědět a dám vám nějaký další příklad.

Studijní materiály

• Kniha The Design of Approximation Algorithms (David P. Williamson, David B. Shmoys) – skvělá učebnice aproximační algoritmů, obsahující jak základy, tak pokročilé techniky, na které v tomto kurzu nedojde. Znalost lineárního programování se ovšem předpokládá. Lze ji zdarma stáhnout.
• Poznámky k přednášce (česky) od Jiřího Sgalla, ve vývoji, takže obsahují jen část látky.
• Další doporučení na stránce přednášky.
• Úvod do pravděpodobnosti v diskrétní matematice od Jiřího Matouška.
• Lineární programování si můžete osvěžit z nějakého ze zdrojů na stránce mého cvičení Optimalizační metody.

Podmínky zápočtu

Zápočet bude za polovinu celkového počtu bodů za domácí úkoly. V průběhu semestru vyvěsím na webové stránky tři série domácích úkolů po zrhuba 4 příkladech, každý za zhruba 4-6 bodů. Na úkoly bude alespoň 14 dní. Dále bude možné získat body za bonusové příklady zadané též v sériích DÚ, které se nebudou počítat do limitu celkového počtu bodů za semestr, a za aktivitu na cvičení (až 2 body za správně předvedené řešení příkladu).

Všechny kroky se snažte pečlivě zdůvodňovat. Naopak můžete používat cokoli z přednášek či cvičení bez důkazu, jen vždy uveďte, co právě využíváte. Na jejich řešení můžete spolupracovat, důležité ale je, abyste řešení důkladně rozuměli a sami ho sepsali. Bodové hodnocení jednotlivých příkladů nemusí vždy nutně odpovídat jejich obtížnosti.

Úkoly odevzdávejte nejlépe elektronicky (ve formátu PDF, ODT, ... nebo i jen jako text emailu). Naskenované či vyfocené papíry jsou též přijímány, pokud lze vše přečíst bez problémů. Další možností je odevzdat řešení na papíře na začátku cvičení.

Účast není povinná, leč velmi doporučená kvůli porozumění látky z přednášky. Pokud se z nějakého důvodu nemůžete dostavit na cvičení, můžete zkusit jít na anglické cvičení další týden.

Tabulka výsledků

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.