Algoritmy a datové struktury II – cvičení ZS 2016/17

Materiály k přednášce

• Skripta Martina Mareše – skvělý studijní materiál v češtině, který pokrývá naprostou většinu témat probíraných na přednášce.

Obsah cvičení

• 1. cvičení (6. 10.) Opakování z ADS I.
• 2. cvičení (13. 10.) Algoritmy pro vyhledávání v textu – Knuth-Morris-Pratt a Aho-Corasick. Byly zadány úkoly:
  1. pref [9]
     Je dáno slovo. Chceme nalézt jeho nejdelší prefix, který je současně jeho vlastním sufixem.
  2. ACcount [9]
     Mějme seno a jehly. Popište algoritmus, který v lineárním čase pro každou jehlu spočítá, kolikrát se v seně vyskytuje. Časová složitost by neměla záviset na počtu výskytů – ten, jak už víme, může být superlineární.
• 3. cvičení (20. 10.) Toky – úvod, Ford-Fulkersonův algoritmus a aplikace na párování v bipartitních grafech. Byly zadány úkoly:
  1. domino [10]
     Máte šachovnici $S \times R$, která obsahuje díry. Popište algoritmus, který pokryje tuto šachovnici kostkami velikosti $1 \times 2$, pokud to lze. (Kostky se nesmí překrývat, každé políčko musí být pokryté a kostky nesmí zasahovat mimo šachovnici či do děr.)
  2. lib [6] za plný počet do konce semestru
     Byla jednou jedna knihovna, ale představte si to, chodili do ní čtenáři. Cháska nezbedná – ledva vyndají knížku z pečlivě uspořádaného regálu, po chvíli listování ji založí zpět na náhodné místo. Chudák knihovník, jak tohle má napravit? Formálněji: Mějme posloupnost $N$ celých čísel, která vznikla ze setříděné posloupnosti přemístěním $K$ prvků ($K$ předem neznáme). Jak ji co nejrychleji dotřídit? Chceme složitost $O(N + K \log K)$.
• 4. cvičení (27. 10.) Zapomenutý algoritmus pro vyhledávání v textu – Rabin-Karp. Byly zadány úkoly:
  1. seqmin [9] za plný počet do konce semestru
     Máte posloupnost $n$ navzájem různých přirozených čísel a chcete najít nejmenší přirozené číslo, které se v ní nevyskytuje. Problém je, že posloupnost nesmíte měnit (tj. například ji nesmíte setřídit) a máte k dispozici pouze $O(\log n)$ paměti.
• 5. cvičení (3. 11.) Toky – Dinicův algoritmus. Byly zadány úkoly:
  1. pokr [12] prodloužen do 1. 12.
     Je dán bipartitní graf. Chcete najít jeho nejmenší vrcholové pokrytí, tj. nejmenší množinu vrcholů takovou, aby každá hrana obsahovala alespoň jeden z vybraných vrcholů. (Chceme rozestavět co nejméně strážníků na křižovatky, aby každá ulice byla hlídaná.)
  2. dinic [15] prodloužen do 1. 12.
     Vymyslete síť, na níž Dinicův algoritmus poběží řádově $n^2 m$ kroků.
• 6. cvičení (10. 11.) Toky – Goldbergův algoritmus. (Zaskakuje Martin Mareš.)
• 7. cvičení (17. 11.) Cvičení není
• 8. cvičení (24. 11.) Fourierova transformace – úvod. Byly zadány úkoly:
  1. coin [9 + 5] do 15. 12.
     Na vstupu máte seznam mincí dané měny $c_i \in {\mathbb{Z}^+}$ pro $i=1,\ldots,k$. Vždy existuje mince s hodnotou 1. Optimální algoritmus zaplatí částku tak, že použije nejmenší množný počet mincí. Hladový algoritmus vždy použije největší minci, kterou může, a poté se rekurzí na zbytek částky. Nalezněte algoritmus, který rozhodne, zda se počet použitých mincí hladovým a optimálním algoritmem shoduje pro všechny částky $\leq K$. Plus 5 bodů pokud váš algoritmus bude fungovat i pro $K = \infty$. Čas běhu algoritmu může (rozumným způsobem) záviset na hodnotách mincí a $K$.
• 9. cvičení (1. 12.) Fourierova transformace – dokončení. Byly zadány úkoly:
  1. fft1 [8]
     Spočítejte Fourierův obraz vektoru $(0,1,0,1,0,1,0,1)$.
  2. fft2 [8]
     Spočítejte Fourierův obraz vektoru $(1,i,-1,-i,1,i,-1,-i)$.
  3. dinic2 [8]
     Ukažte, že pokud Dinicův algoritmus nikdy neposílá tok proti směru hran (tj. hodnota toku $f(u,v)$ se mění (neostře) monotónně v celém průběhu algoritmu pro všechny dvojice vrcholů $u,v$), tak doběhne v čase $O(mn)$.
• 10. cvičení (8. 12.) Hradlové a komparátorové sítě. Od teď dále jsou úkoly za plný počet bodů až do konce semestru. Byly zadány úkoly:
  1. sort1 [10]
     Navrhněte komparátorovou síť pro zatřídění prvku do setříděné posloupnosti: dostane $(n-1)$-prvkovou setříděnou posloupnost a jeden prvek navíc a vydá setříděnou permutaci.
  2. nula_jedna [15]
     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.
  3. fce [12]
     Ukažte, že každou boolovskou funkci s $k$ vstupy lze spočítat boolovským obvodem hloubky $O(k)$ s $O(2^k)$ hradly.
• 11. cvičení (15. 12.) NP-úplnost: definice a převody.
• 12. cvičení (22. 12.) NP-úplnost dokončení: kachličkování a další převody.
• 13. cvičení (5. 1.) Geometrické algoritmy: konvexní obal, průsečíky úseček.
• 14. cvičení (12. 1.) Přehled o pravděpodobnostních a aproximačních algoritmech. Byly zadány úkoly:
  1. plot [12]
     V rovině je $N$ bodů, chceme najít dva mnohoúhelníky s co nejmenším součtem obvodů, které budou obsahovat všechny zadané body.
  2. tuc [12]
     Tučňáci stojí na začátku každý na své kře a chtějí se potkat všichni najednou na jedné kře. Každý tučňák může skočit na libovolnou kru ve vzdálenosti nejvýše $d$. Každým doskokem tučňáka se kra trochu poničí. Naštěstí víme, kolikrát se na kterou kru dá skočit, než se zcela rozpadne. Otázkou je, na kterých krách se mohou tučňáci potkat.
     Vstup: Množina ker (každá popsána umístěním a výdrží), množina tučňáků (každý na nějaké kře), číslo $d$.
     Výstup: Kry, na kterých se mohou tučňáci potkat.
  3. pcomp [8]
     Jak vypadají P-úplné problémy? Tedy takové, které leží v P a cokoliv z P se na ně dá převést.
  4. div [12]
     Navrhněte hradlovou síť, která otestuje, jestli je zadané $n$-bitové číslo dělitelné sedmi.
  5. psat [12]
     Problém PSAT: Vstupem je formule v CNF (tj. konjunkce disjunkcí literálů) taková, že každá klausule obsahuje nejvýše jeden negativní literál. Otázka je, zda je tato formule splnitelná.
     Rozhodněte a dokažte, zda je PSAT NP-úplný.

Zápočet

Na zápočet potřebujete nasbírat 100 bodů za řešení domácích úkolů.

Úkoly přijímám pouze elektronicky na adrese husek+ads@iuuk.mff.cuni.cz, buď jako prostý text (tzn. přímo v mailu) nebo jako PDF (ideálně vyrobené (La)TeXem, ale to není povinné, jen silně doporučené). Nechci formáty .doc, .docx, .odt atp.

Úkolů bude vypsáno za cca 170 bodů, nebudou zadávány každý týden, spíš každých 14 dní. Po následující dva týdny od zadání za ně bude možno získat plný počet bodů, poté až do konce semestru můžete úlohy odevzdávat za polovinu bodů.