NDMI084 - Úvod do aproximačních a pravděpodobnostních algoritmů

Toto jsou cvičení k přednášce prof. Sgalla. Cvičení probíhají každé liché úterý semestru od 15:40 v S7. Informace pro cvičení v angličtině jsou tady.

Jako studijní matriály doporučuju Design of Approximation Algorithms. Sekce 1.2 obsahuje poměrně dobrý úvod do lineárního programování.

Podmínky pro získání zápočtu

Během semestru budou zadány tři sady domácích úkolů. K získání zápočtu bude potřeba získat alespoň třicet ze šedesáti možných bodů. Na každou sadu úkolů budete mít alespoň dva týdny. Řešení odezvdávejte papírově, nebo na můj mail ve formátu PDF.

Úkoly

Třetí sada - Deadline 16.1.

Doporučuju odevzdat ještě před prázdninami - budete mít klid.
Odstranění trojúhelníků - 9 bodů
Dostali jste konvexní mnohostěn. Vaším cílem je jej upravit na podobně vypadající konvexní mnohostěn, který ale nemá žádnou trojúhelníkovou stěnu. Smíte pouze přidávat nové stěny zanedbatelných rozměrů (oproti původním stěnám) komolením (seseknutím) vrcholů. Vymyslete co nejlepší approximační algoritmus pro určení minimálního počtu vrcholů ke zkomolení.
Parallelní max-4-cut - 13 bodů
Vytvořte paralelní approximační algoritmus pro max-4-cut. Máte k dispozici n⁴ processorů. Cílem je deterministická ¾-approximace v čase nejhůře O(log n), ale za horší výsledky bude alespoň část bodů. HINT: Já bych začal randomizovaným algoritmem, ale nejspíše to jde i jinak.

Second set - Deadline prodloužen do 8.12.

Every task is worth 6 points.
Max k-cut
Given a graph, assign each vertex to one of k partitions such that as many edges as possible connect two vertices of different partitions. Find a deterministic (k-1)/k-approximation algorithm.

Hint: Start with randomized 2-cut. Partial points will be available for a randomized solution.
Ring network routing
Given a cycle of n computers connected in a ring topology network and a list of m messages to be sent from computer s_i to computer t_i (for i in 1,...,m), your task is to decide which direction should each message travel around the ring so that the number of messages using the most frequently used edge is as low as possible. Design a 2-approximation algorithm.
Quicksort
We have already seen that Quicksort runs in O(n log n) expected and O(n^2) worst-case time. Let us try and analyze Quicksort a little more carefully. Find an upper bound on the number of comparisons needed to sort n elements with probability at least 1-1/n.

První sada - Deadline 2.11.

Každý úkol je za čtyři body
Heads
Jaká je pravděpodobnost, že během 30 hodů férovou mincí padne hlava alespoň pětkrát v řadě? Popište (nebo rovnou dodejte) to, jak jste to počítali a ujistěte se, že výsledek je přesný na 0.01 procentního bodu. HINT: Nedoporučuju to zkoušet ručně.
NP
Předpokládejte, že Subset sum problem je NP-těžký. Dokažte, že Subset sum problem i Partition problem jsou oba NP-úplné. Subset sum problem = pro zadané cílové číslo a seznam čísel rozhodněte, zda existuje podmnožina jejíž součet je roven cílovému číslu. Partition problem = pro zadaný seznam čísel rozhodněte, zda jej jde rozdělit na dvě disjunktní skupiny které mají vzájemně stejný součet.
APX
V problému MAX SAT se snažíme splnit co nejvíce klauzulí. Představte si, že každé proměnné přiřadíme nezávisle náhodně hodnotu True s pravděpodobností 50% a False s pravděpodobností 50%. Jaký aproximační poměr má tento algoritmus? Proč?
Dice
Představte si, že chcete vybrat uniformně náhodné číslo z množiny {1,2,3,4,5,6,7} ale máte k dispozici jenom obyčejnou kostku. Jak byste to mohli udělat? Jaká je střední hodnota potřebného počtu hodů kostkou? Zkuste se co nejvíce přiblížit optimu.
Limits
Dokažte že Christofidův algoritmus není lepší než 3/2-aproximace. Formálněji, popište nekonečnou řadu grafů takovou, že poměr mezi řešením Christofida a optimem konverguje k 3/2.

Obsah cvičení

2021-10-05

Po domluvě se studenty bylo cvičení přeloženo na sudá úterý. Příští cvičení bude 26. října. Zadání úkolů ze cvičení.

2021-10-26

Druhé cvičení bylo věnováno opakování znalostí z přednášek. Konkrétně jsme formulovali důkazy pro následující tvrzení:

2021-11-09