[home]

ADS II (2018/2019)

Cvičení k přednášce Algoritmy a datové struktury II, kterou přednáší Ondřej Čepek

Doporučená literatura

• Průvodce labyrintem algoritmů
• Pro zájemce o složitější grafové algoritmy - Krajinou grafových algoritmů

Organizace

K získání zápočtu je nutno nasbírat 90 bodů.

Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (za vyřešení více úkolů z jednoho cvičení je stále 10 bodů).

Aktivita na cvičení bude odměněna 5 body (více aktivity na jednom cvičení je stále 5 bodů).

Body

Body budou zapsané v SISu.

Probrané příklady

1.10.

• Dnes jsme opakovali látku z ADS 1. Úkoly jsme brali z tohoto dokumentu. Stačili jsme vyřešit pouze příklady 1, 2, 7, 9 a 14. Na příštím cvičení podrobně vysvětlím jak se dělá příklad 4.

8.10.

• Začali jsme s hledáním slov v textu. Ukázali jsme konstrukci automatu pro KMP a poté i pro Aho-Corasick. U AC automatu jsme na příkladě ověřili důležitost zkratkových hran.
• Našli jsme příklad vstupu, na kterém dosahuje triviální algoritmus špatné časové složitosti.
• Umíme zjistit, zda je slovo rotací jiného a zda je slovo periodické.

15.10.

• Pokračovali jsme v hledání slov v textu a ukázali jsme si Rabin-Karpův algoritmus. Umíme nalézt lexikograficky nejmenší rotaci slova.
• U algoritmu AC jsme se podívali na to, jak je to s počtem výskytů a že jich může být více než lineárně. Přišli jsme ale na způsob jak počet výskytů spočítat, pokud je nepotřebujeme hlásit.

22.10.

• Začali jsme s toky v sítích. Připomněli si definici problému a Ford-Fulkersonův algoritmus. Ukázali jsme, že špatným výběrem cest na grafu s reálnými kapacitami nemusí FF nikdy skončit, ani konvergovat ke správnému řešení.
• Poradili jsme s grafy, ve kterých je více zdrojů a stoků, s grafy, kde mají vrcholy kapacitu a s hledáním disjunktních cest.
• Začali jsme párování na bipartitních grafech: kostičky, věže.

29.10.

• Probrali jsme Dinicův algoritmus. Na příkladu jsme odkrokovali jeho běh a připomněli jsme si odhad časové složitosti.
• Další příklady na toky: znovunalezení maximálního toku po změně kapacity nějaké hrany o 1; síť se sudými kapacitami vydá sudý maximální tok; zjištění hranové k-souvislosti

5.11.

• Probrali jsme Goldbergův algoritmus. Na příkladu jsme odkrokovali jeho běh a připomněli jsme si odhad časové složitosti. U potenciálové metody jsme si zkusili i jiný lehký příklad (zásobník s funkcemi push, pop a pop_all). Příště se podíváme trochu více na amortizovanou časovou složitost.
• Další příklady na toky: svišti, kteří utíkají před orlem (klasická úloha na bipartitní párování); pokud existují opačné hrany, pak vždy existuje tok, kde se používá nanejvýš jedna

12.11.

• Začali jsme s kapitolou Fourierova transformace. Na začátek jsme zopakovali motivaci s násobením polynomů. Ukázali jsme si jak rychle to lze udělat triviálně a jak rychle to chceme udělat trikem s rozkládáním polynomů.
• Zavedli jsme si primitivní n-tou odmocninu z jedné a ukázali její vlastnosti.
• Pomocí DFT jsme spočítali zatím jen jeden vektor, ale ukázali jsme si jak to lze obecně počítat pomocí vzorce na součet geometrické řady.

19.11.

• Probírali jsme DFT. Ukázali jsme si algoritmus FFT a jak souvisí s rychlým násobením polynomů.
• Ukázali jsme, že DFT je lineární zobrazení a jak vypadá jeho inverzní zobrazení. Ukázali jsme jak DTF souvisí se spektrálním rozkladem.
• Ručně jsme vypočítali DFT několika vektorů.

26.11.

• Začali jsme s hradlovými sítěmi a paralelními algoritmy. Nejrpve jsme si připomněli obecně hradla a binární booleovské funkce.
• Pomocí DNF jsme ukázali, že všech 16 bin. bool. fcí lze vyjádřit pomocí AND, OR a negace. Stejnou věc jsme ukázali pro NAND a NOR. Vytvořili jsme XOR ze 4 hradel NAND.
• Ukázali jsme jak sestrojit n-bitový OR z binární OR v logaritmické hloubce a proč to rychleji nejde.

3.12.

• Dokončili jsme hradlové sítě a komparátory. Sestrojili jsme komparátor pro dvě n-bitová čísla.
• Zopakovali jsem si sčítačku z přednášky a s její pomocí setrojili pak i odčítačku (jak pomocí dvojkového doplňku, tak "od základu"). V rychlosti jsme ukázali i trik jak násobit binární čísla sítí s logaritmickou hloubkou.
• Ukázali jsme si jak v řeči komparátorů vypadají bubble sort, insert sort a select sort a že jsou identické.

10.12.

• Začali jsme s třídami P a NP a převeditelností. Na začátek jsme rychle zmínili výpočetní modely (Turingův stroj a RAM model) a ukázali si dvě definice NP (pomocí nedeterministického Turingova stroje a pomocí certifikátů). O těchto definicích jsme dokázali, že jsou ekvivalentní.
• Řekli jsme si jak se problémy mezi sebou převádí a proč je nutné, aby to šlo polynomiálně. Ukázali jsme si obecný postup ne důkaz, že je problém NP-Ú.
• Na samotné převody problémů nezbylo moc času. Viděli jsme jen Barvení grafu -> SAT, loupežníci -> batoh. Příště budeme pokračovat.

17.12.

• Řešili jsme jak se vypořádat s těžkými problémy:
• Omezíme se na podproblémy - vrcholové pokrytí ve stromě, 2-SAT.
• Aproximace problémů - zopakovali jsme obchodního cestujícího, 2-loupežníky a vrcholové pokrytí hladově.

7.1.

• Na posledním cviku jsme se rychle podívali na konvexní obal a protínání úseček. U obojího jsme pouze odkrokovali algoritmus na příkladech.
• Jako opakování jsme vyřešili několik ze zadaných úkolů z celého roku.

Úkoly

Na řešení úkolů jsou vždy dva týdny. Úkoly je možné odevzdávat mailem (preferovaná varianta) nebo na papíru na cvičení. Každý úkol musí obsahovat zdůvodnění, proč je řešení korektní (např. samotný pseudokód nestačí). Pokud je úkolem navrhnout algoritmus, pak je také vždy zapotřebí uvést časovou a prostorovou složitost, včetně zdůvodnění.

8.10. (do 22.10.)

• Je dáno slovo. Chceme nalézt jeho nejdelší vlastní prefix, který je současně suffixem. Řešte v O(n).
• Ukažte, jak pro dané dva řetězce najít jejich nejdelší společný podřetězec.
• Jak v lineárním čase zrotovat řetězec, dostačuje-li paměť počítače jen na uložení jednoho řetězce a O(1) pomocných proměnných?

15.10. (do 29.10.)

• Je dán text, ve kterém hledáme nejdelší podřetězec, který se vyskytuje alespoň dvakrát.
• Substituční šifra funguje tak, že zpermutujeme znaky abecedy: například permutací abecedy abcdeo na dacebo zašifrujeme slovo "abadcode" na "dadecoeb". Zašifrovaný text je méně srozumitelný, ale například vyzradí, kde v originálu byly stejné znaky a kde různé. Buď dáno seno zašifrované substituční šifrou a nezašifrovaná jehla. Najděte všechny možné výskyty jehly v originálním seně (tedy takové pozice v seně, pro něž existuje permutace abecedy, která přeloží jehlu na příslušný kousek sena).
• Pro daný slovník chceme vytvořit datovou strukturu, která bude umět odpovídat na dotazy typu "je ve slovníku rotace slova X"?

22.10. (do 5.11.)

• Následující dva úkoly zní dost podobně, ale druhý je o něco těžší než první. Než mi pošlete řešení prvního, zkuste se zamyslet i nad tím druhým úkolem.
• Uvažujme továrny T_1, . . . , T_p a obchody O_1, . . . , O_q. Všichni vyrábějí a prodávají tentýž druh zboží. Továrna T_i ho denně vyprodukuje t_i kusů, obchod O_j denně spotřebuje o_j kusů. Navíc známe bipartitní graf určující, která továrna může dodávat zboží kterému obchodu. Najděte efektivní algoritmus, který zjistí, zda je požadavky obchodů možné splnit, aniž by se překročily výrobní kapacity továren, a pokud je to možné, vypíše, ze které továrny se má přepravit kolik zboží do kterého obchodu
• Uvažujeme o vybudování dolů D_1, . . . , D_p a továren T_1, . . . , T_q. Vybudování dolu D_i stojí cenu d_i a od té doby důl zadarmo produkuje neomezené množství i-té suroviny. Továrna T_j potřebuje ke své činnosti zadanou množinu surovin a pokud jsou v provozu všechny doly produkující tyto suroviny, vyděláme na továrně zisk t_j . Vymyslete algoritmus, jenž pro zadané ceny dolů, zisky továren a bipartitní graf závislostí továren na surovinách stanoví, které doly postavit, abychom vydělali co nejvíce.
• Nápověda pro druhý úkol:
  • Převeďte na hledání minimálního řezu.
  • Minimalizujte součet ceny zdrojů, které jste si pořídili, a projektů, které nerealizujete.
  • Úplně stejný graf jako v prvním příkladu.

29.10. (do 12.11.)

• Sestrojte vrstevnatou síť, v níž hledání blokujícího toku trvá Ω(nm). Sestrojte síť, na níž Dinicův algoritmus provede Ω(n) fází. Zkombinujte tyto dva poznatky a vytvořte síť, na níž Dinicův algoritmus běží v čase Ω(n^2m).
• Pro zadaný neorientovaný graf G nalezněte maximální k takové, že G je vrcholově k-souvislý. Složitost udejte v počtu spuštění algoritmu pro hledání maximálního toku. (snažte se udělat lépe než v n^2)
• Dokažte že v grafu s jednotkovými kapacitami poběží Dinicův algoritmus v čase O(mn).

5.11. (do 19.11.)

• Průchod šachovnicí: Je dána šachovnice n x n, kde některá políčka jsou nepřístupná. Celý dolní řádek je obsazen figurkami, které se mohou hýbat o jedno pole dopředu, šikmo vlevo dopředu, či šikmo vpravo dopředu. V jednom tahu se všechny figurky naráz pohnou (mohou i zůstat stát na místě), na jednom políčku se však musí vyskytovat nejvýše jedna figurka. Ocitne-li se figurka na některém políčku horního řádku šachovnice, zmizí. Navrhněte algoritmus, který najde minimální počet tahů takový, že z šachovnice dokážeme odstranit všechny figurky, případně oznámí, že řešení neexistuje.
• Parlamentní kluby: V parlamentu s n poslanci je m různých klubů. Jeden poslanec může být členem mnoha různých klubů. Každý klub nyní potřebuje zvolit svého předsedu a tajemníka tak, aby všichni předsedové a tajemníci byli navzájem různé osoby (tedy aby nikdo „neseděl na více křeslech“). Navrhněte algoritmus, který zvolí všechny předsedy a tajemníky, případně oznámí, že řešení neexistuje. Za jakých podmínek je existence řešení garantována?
• Minimální izolace: Je dán nepříliš velký celočíselný kvádr (dejme tomu s objemem nejvýše 20 000) a v něm k nebezpečných jednotkových kostiček. Navrhněte algoritmus, který najde podmnožinu M kostiček kvádru takovou, že každá nebezpečná kostička leží v M a zároveň M má minimální možný povrch (povrch měříme jako počet takových stěn kostiček z M, které nesousedí s jinou kostičkou z M).

12.11. (do 26.11.)

• Pro odpálení jaderné bomby je potřeba, aby se na tom shodlo alespoň k z celkového počtu n generálů. Vymyslete, jak z odpalovacího kódu odvodit n klíčů pro generály tak, aby libovolná skupina k generálů uměla ze svých klíčů kód vypočítat, ale žádná menší skupina nemohla o kódu zjistit nic než jeho délku.
• Upravme algoritmus pro násobení polynomů na dělení polynomů. Tedy chceme vydělit polynom A polynomem B. To uděláme tak, že je oba převedeme na reprezentaci v bodech, ty vydělíme a převedeme zpět. Bude tento postup fungovat?
• Dokažte, že pro primitivní n-tou odmocninu z jedné ω platí, že ω^2 je primitivní n/2-tá odmocnina z jedné.

19.11. (do 3.12.)

• Na hodině jsme ukázali, že DFT reálného vektoru je antisymetrický vektor. Ukažte opak, tedy že DFT antisymetrického vektoru je reálný vektor. Antisymetrický vektor: $y_j = \overline{y_{n-j}}$ pro všechna $j$. Pozor na to, že indexujeme od 0 do n-1 (tedy modulo n). Platí tedy $y_0 = \overline{y_0}$ a $y_{n/2} = \overline{y_{n/2}}$
• Vzorkujeme funkce $sin(2 k \pi x)$, $cos(2 k \pi x)$ na intervalu $[0,1)$ v $n$ bodech (tedy v bodech $n/j$ pro $j=1, ..., n$). Ukažte jak pro tyto funkce vypadá jejich DFT. Použijte $e^{2 \pi i/n}$ jako primitivní n-tou odmocninu. (jak toto spočítat pro exponencialu i jak to vyjde pro zadané funkce se dozvíte ve skriptech. Nicméně je stále potřeba ukázat důkaz.)
• Konvoluce vektorů $x$ a $y$ je vektor $z = x * y$ takový, že $z_j = \sum_k x_k y_{j-k}$, přičemž indexujeme modulo $n$. Tuto sumu si můžeme představit jako skalární součin vektoru $x$ s vektorem $y$ napsaným pozpátku a zrotovaným o $j$ pozic. Konvoluce nám tedy řekne, jak tyto „přetočené skalární součiny“ vypadají pro všechna $j$. Dokažte následující vlastnosti:
  a) $x * y = y * x$ (komutativita)
  b) $x * (y * z) = (x * y) * z$ (asociativita)
  c) $x * (\alpha y + \beta z) = \alpha(x * y) + \beta(x * z)$ (bilinearita)
  d) $DFT(x * y) = DFT(x) \odot DFT(y)$, kde $\odot$ je součin vektorů po složkách. To nám dává algoritmus pro výpočet konvoluce v čase O(n log n).

26.11. (do 10.12.)

• Definujeme výhybku – to je analogie operátoru ?: v jazyce C, tedy ternární booleovské hradlo se vstupy $x_0$, $x_1$ a $p$, jehož výsledkem je $x_p$. Ukažte, že libovolnou k-vstupovou booleovskou funkci lze spočítat obvodem složeným pouze z výhybek a konstant.
• Ukažte, že libovolnou booleovskou funkci s k vstupy lze spočítat booleovským obvodem hloubky $O(k)$ s $O(2^k)$ hradly (nápověda: vzpomeňte si na to jak vyjádřit formule v CNF nebo DNF). Exponenciální velikost obvodu je nepříjemná, ale bohužel nevyhnutelná: Dokažte, že pro žádné k neplatí, že všechny n-vstupové booleovské funkce lze spočítat obvody s $O(n^k)$ hradly.
• Sestrojte komparátor na jednobitová čísla z binárních hradel. Vzhledem k tomu, že budeme tvořit vícebitové komparátory na příštím cvičení, je deadline pro tento jeden úkol do cvičení dne 3.12.

3.12. (do 17.12.)

• Dokažte nula-jedničkový princip: pro ověření, že komparátorová síť třídí všechny vstupy, ji postačí otestovat na všech posloupnostech nul a jedniček.
• Navrhněte komparátorovou síť pro hledání maxima: dostane-li n prvků, vydá takovou permutaci, v níž bude poslední hodnota největší. Dokažte navíc, že vámi navržený postup je nejrychlejší možný.
• Sestrojte hradlovou síť logaritmické hloubky, která dostane matici sousednosti neorientovaného grafu a rozhodne, zda je graf souvislý.

10.12. (do 31.12.)

• Dokažte pro uvedené rozhodovací problémy (splnitelnost, klika velikosti k a nezávislá množina velikosti k), že pokud bychom je dokázali v polynomiálním čase vyřešit, uměli bychom polynomiálně řešit i jejich „zjišťovací“ verze. (tj. najít konkrétní splňující ohodnocení, kliku a nezávislou množinu).
• Vrcholové pokrytí grafu je množina vrcholů, která obsahuje alespoň jeden vrchol z každé hrany. Ukažte vzájemné převody mezi problémem nezávislé množiny a problémem „Existuje vrcholové pokrytí velikosti nejvýše k?“.
• Pokud bychom definovali P-úplnost analogicky k NP-úplnosti, které problémy z P by byly P-úplné?

17.12. (do 7.1.)

• Nalezněte $\alpha$-aproximaci bin packing: Máme n předmětů s objemem v rozsahu (0,1> a chceme je umístit do co nejméně nádob o objemu 1. Ukažte a dokažte o jaké $\alpha$ se ve vaší aproximaci jedná.
• Problém MaxCut: vrcholy zadaného grafu chceme rozdělit do dvou množin tak, aby mezi množinami vedlo co nejvíce hran. Jinými slovy chceme nalézt bipartitní podgraf s co nejvíce hranami. Rozhodovací verze tohoto problému je NP-úplná, optimalizační verzi zkuste v polynomiálním čase 2-aproximovat.
• Uvažujme následující algoritmus pro nejmenší vrcholové pokrytí grafu. Graf projdeme do hloubky, do výstupu vložíme všechny vrcholy vzniklého DFS stromu kromě listů. Dokažte, že vznikne vrcholové pokrytí a že 2-aproximuje to nejmenší.

7.1. (do 21.1.)

• Nalezněte obsah nekonvexního mnohoúhelníku.
• Nalezněte obsah konvexního mnohoúhelníku.