[home]

ADS II (2019/2020)

Cvičení k přednášce Algoritmy a datové struktury II

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 80 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

7.10.

• Opakovali jsme látku z ADS I - asymptotická notace, hledání nejkratších cest, minimální kostry.
• Podívali jsme se na konstrukci automatu KMP a odkrokování hledání na příkladu.
• Vyřešené úlohy na hledání v textu - lexikograficky minimální rotace, rozpoznání zda je slovo rotací jiného, periodičnost slova.

14.10.

• Pokračovali jsme hledáním více jehel pomocí algoritmu Aho-Corasick. Vyzkoušeli jsme konstrukci automatu, zdůvodnění zkratkových hran a superlineární počet výskytů hledaných jehel.
• Další probrané příklady: hledání fibonacciho slov, datová struktura, která rozpozná, zda je v ní obsažena rotace zadaného slova.
• Příště se podíváme na toky v síti, pokud nebylo něco jasné při hledání jehel v seně, tak napište mail. Zkusím to ještě na další hodině zopakovat.

21.10.

• Začali jsme s toky v sítích - zopakovali jsem definice a Ford-Fulkersonův algoritmus včetně jeho nevýhod. Příklad kde se nezastaví předvedu příště.
• Další příklady - síť s více zdroji a stoky, hledání disjunktních cest, kapacity ve vrcholech místo na hranách, párování v bipartitním grafu

4.11.

• Dokončili jsme toky v síti - Dinitzův a Goldbergův algoritmus.
• Další příklady - Pokud jsou v grafu opačně orientované hrany, tak existuje ekvivalentní tok, který použije jen jednu z nich. Jak rychle upravit tok, pokud se změní kapacita jedné hrany. Další párování na bipartitních grafech.

11.11.

• Začali jsme s DFT a FFT. Zopakovali jsme motivaci s rychlým násobením polynomů a zopakovali některé vlastnosti komplexních čísel. Zejména jsme se zaměřili na primitivní n-tou odmocninu z jedné.

18.11.

• Pokračovali jsme s DFT a FFT, zkusili jsme pomocí DFT vynásobit dva polynomy a spočítat FFT pro konkrétní polynom.
• Podívali jsme se na spektrální rozklad a zjistili jsme, že libovolná reálná funkce lze aproximovat pomocí sinů a cosinů.

25.11.

• Začali jsme s hradlovými sítěmi. Podívali jsem se na to jaká je souvislost mezi hradlovými sítěmi nad abecedou 0,1 a binárními funkcemi. Ukázali jsme si kolik je binárních funkcí a jak je můžeme všechny vyjádřit pomocí negace, and, or nebo pomocí nand nebo pomocí xor.
• Připomněli jsme si algoritmus na sčítání binárních čísel z přednášky - sčítačky a předpočítání přenosů do vyšších řádů. Násobení bude příště.

2.12.

• Pokračovali jsme s hradlovými sítěmi a s komparátorovými sítěmi. Nejprve jsme si sestrojili komparátor z hradel. Potom jsme si připomněli jak pracuje bitonické třídění.
• Díky komparátorům umíme hledat maximum a zařazovat prvky do setříděné posloupnosti.

9.12.

• Začali jsme kapitolu o složitostních třídách P a NP. Definovali jsme polynomiální převod problémů. Definovali jsme NP pomocí nedeterministických TS i pomocí certifikátu.
• Ukázali jsme, že omezení na rozhodovací problémy nám nevadí (konkrétní příklad na SAT). Z převodů NP-ú problémů jsme ukázali jen nezávislou množinu <-> klika a SAT -> 3-SAT.

16.12.

• Pokračovali jsme s NP-těžkými úlohami a rozmysleli jsme si jak takové příklady řešit. Uvažovali jsme také jak by fungovala P-úplnost.
• Převod podmínek na SAT.
• Speciální příklady, které lze řešit v poly čase. 2-obarvitelnost, vrcholové pokrytí stromu.
• Aproximační algoritmy.

6.1.

• Probrali jsme techniku zametání roviny přímkou - konvexní obal a počítání průsečíků úseček.
• Další úkoly: oddělení dvou množin bodů přímkou, výpočet obsahu konvexního a nekonvexního n-úhelníku.
• Hodně štěstí při zkoušce.

Ú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í.

7.10. (do 21.10.)

• Pestrý budeme říkat takovému řetězci, jehož všechny rotace jsou navzájem různé. Kolik existuje pestrých řetězců délky $n$ (kde $n$ je prvočíslo) v konečné abecedě $\Sigma$. Pokud Vám úkol přijde moc jednoduchý, zkuste si rozmyslet variantu, kdy $n$ není prvočíslo.
• Jak v lineárním čase zrotovat řetězec délky $n$ o $k$ pozic (tj. každé písmeno na pozici $i$ se posune na pozici $i+k \mod n$), dostačuje-li paměť počítače jen na uložení jednoho řetězce a $O(1)$ pomocných proměnných?
• Ukažte, jak pro dané dva řetězce najít jejich nejdelší společný podřetězec.

14.10. (do 28.10.)

• 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í.
• Je dán text a číslo K. Jak zjistit, který podřetězec délky K se v textu vyskytuje nejčastěji?
• Cenzor dostane množinu zakázaných podřetězců a text. Vždy najde nejlevější výskyt zakázaného podřetězce v textu (s nejlevějším koncem; pokud jich je více, tak nejdelší takový), vystřihne ho a postup opakuje. Ukažte, jak text cenzurovat v lineárním čase. Chování algoritmu si vyzkoušejte na textu $a^nb^n$ a zakázaných slovech $a^{n+1}$, $b$.

21.10. (do 4.11.)

• Přímočará implementace Fordova-Fulkersonova algoritmu bude nejspíš graf prohledávat do šířky, takže vždy najde nejkratší nenasycenou cestu. Pak překvapivě platí, že algoritmus zlepší tok jen $O(nm)$-krát, než se zastaví. Návod k důkazu: Nechť $l(u)$ je vzdálenost ze zdroje do vrcholu $u$ po nenasycených hranách. Nejprve si rozmyslete, že $l(u)$ během výpočtu nikdy neklesá. Pak dokažte, že mezi dvěma nasyceními libovolné hrany $uv$ se musí $l(u)$ zvýšit. Proto každou hranu nasytíme nejvýše $O(n)$-krát.
• Pro daný neorientovaný graf nalezněte co největší k takové, že graf je hranově $k$-souvislý. (To znamená, že je souvislý i po odebrání nejvýše $k − 1$ hran.) Složitost výpočtu uvádějte v počtu spuštění algoritmu pro hledání maximálního toku.
• Víme, že pokud bude Ford-Fulkerson počítat pouze s kapacitami hran a nikoliv s rezervami (tj. algoritmus jde vždy pouze po směru hran), pak nemusíme najít maximální tok. Zkuste tento problém vyřešit tím, že budete vždy vybírat nejkratší ze zlepšujících cest. Funguje toto vylepšení?
• Mějme šachovnici r × s, z níž políčkožrout sežral některá políčka. Chceme na ni rozestavět co nejvíce šachových věží tak, aby se navzájem neohrožovaly. Věž můžeme postavit na libovolné nesežrané políčko a ohrožuje všechny věže v témže řádku i sloupci, ale neohrožují se přes sežraná políčka. Navrhněte efektivní algoritmus, který takové rozestavění najde.

4.11. (do 18.11.)

• Zkuste si implementovat Dinitzův nebo Goldbergův algoritmus. Přijímám program v jakémkoliv rozumném a čitelném jazyce.
• Průchod šachovnicí: Je dána šachovnice n×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.
• Zlepšení toku z f na g: Dokažte, že ke každému toku f a většímu toku g existuje tok v síti rezerv toku f takový, že zlepšením f pomocí tohoto toku dostaneme g.
• 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.
  Tento úkol je ze zadaných nejlehčí (a tedy záchranný). Součástí řešení tedy musí být i zdůvodnění, proč se vám nepodařilo vyřešit předchozí dva příklady.

11.11. (do 25.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.
• Z následujících vektorů si vyberte libovolné tři a spočítejte jejich DFT. Správné řešení příkladu z hodiny naleznete zde. Můžete předpokládat, že délka vektoru je sudá. $\omega$ značí primitivní n-tou odmocninu z jedné.
  • $(1,-1,1,-1,1,...)$
  • $(1,0,1,0,1,0,...)$
  • $(x,x,x,x,...)$
  • $(\omega^0,\omega^1,\omega^2,\omega^3,...)$
  • $(\omega^0,\omega^2,\omega^4,\omega^6,...)$
• Dokažte, že DFT je lineární zobrazení. Protože se jedná o lineární zobrazení, tak platí, že jde reprezentovat jako násobení nějakou maticí $\Omega$, kde $\Omega_{j \: k} = \omega^{j \: k}$. Nyní chceme najít inverzní zobrazení. Tvrdíme, že inverzní zobrazení je $\Omega^{-1} = 1/n \: \overline\Omega$. Aby se toto dokázalo, stačí ověřit, že platí $\Omega \: \overline\Omega = 1/n \: E$, kde $E$ je jednotková matice.

18.11. (do 2.12.)

• Dokažte pro alespoň jednu z následujících funkcí vzorkovaných v $n$ bodech na intervalu $[0,1)$, kde $0 < k < n/2$ :
  • $DFT(\sin(2k\pi x)) = (0, \dots , 0, n/2i, 0, \dots , 0, −n/2i, 0, \dots , 0)$
  • $DFT(\cos(2k\pi x)) = (0, \dots , 0, n/2, 0, \dots , 0, n/2, 0, \dots , 0)$
  kde nenuly jsou na pozicích $k$ a $n-k$. zjistěte, jak se funkce $\sin(2k\pi x)$ a $\cos(2k\pi x)$ chovají speciálně pro $k = 0$ a $k = n/2$. Pro bližší vysvětlení okolností zadání si přečtěte kapitolu 17.4 ve skriptech.
• Mějme dvě množiny $A$ a $B$ (velikosti $n$) celých čísel v rozsahu od $0$ do $10n$. Chceme spočítat množinu $C = \{x+y | x \in A, y \in B\}$ (kartézský součet). Algoritmus by měl pracovat v čase $O(nlog n)$
• Pomocí FFT vynásobte následující dva polynomy. $A(x) = -3x + 2$, $B(x) = x^2 - x$

25.11. (do 9.12.)

• Definujeme výhybku – to je 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. Jak by se naopak skládala výhybka z binárních hradel?
• Modifikujte sčítací síť z přednášky, aby odčítala.
• Sestrojte hradlovou síť hloubky O(log n), která porovná dvě $n$-bitová čísla $x$ a $y$ a vydá jedničku, pokud $x < y$.

2.12. (do 16.12.)

• Sestrojte hradlovou síť logaritmické hloubky, která dostane matici sousednosti neorientovaného grafu a rozhodne, zda je graf souvislý.
• 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.
• Vytvořte komparátorovou síť pro bubble sort a insert sort. Sítě porovnejte. Součástí řešení by měl být pseudokod pro oba sorty. Můžete použít nejzákladnější typ algoritmu, nemusíte kontrolovat předčasné ukončení atp.

9.12. (do 23.12.)

• Dokažte o libovolném z následujících problémů, že je NP-úplný. Tj. je NP a zároveň na něj dokážete převést některý z jiných NP-těžkých problémů. Nepřijímám řešení, kde je převodem identita nebo převody, co jsme ukázali na cvičení (SAT -> 3-SAT a Nezávislá množina <-> Klika).
  • SAT: splnitelnost logických formulí v CNF
  • 3-SAT: každá klauzule obsahuje max. 3 literály
  • 3,3-SAT: navíc se každá proměnná vyskytuje nejvýše třikrát
  • Nezávislá množina: existuje množina alespoň k vrcholů, mezi nimiž nevede žádná hrana?
  • Klika: existuje úplný podgraf na k vrcholech?
  • Barvení grafu: lze obarvit vrcholy k barvami (přidělit každému vrcholu číslo od 1 do k) tak, aby vrcholy stejné barvy nebyly nikdy spojeny hranou)? To je NP-úplné už pro k = 3.
  • Hamiltonovská cesta: existuje cesta obsahující všechny vrcholy?
  • Hamiltonovská kružnice: existuje kružnice obsahující všechny vrcholy?
  • Součet podmnožiny: má daná množina přirozených čísel podmnožinu s daným součtem?
  • Batoh: jsou dány předměty s váhami a cenami a kapacita batohu, chceme najít co nejdražší podmnožinu předmětů, jejíž váha nepřesáhne kapacitu batohu. Aby se jednalo o rozhodovací problém, ptáme se, zda existuje podmnožina s cenou větší nebo rovnou zadanému číslu.
  • Dva loupežníci: lze rozdělit danou množinu čísel na dvě podmnožiny se stejným součtem?

16.12. (do 30.12.)

• Nalezněte příklad grafu, který nelze obarvit 3 barvami, ale neobsahuje jako podgraf úplný graf na 4 vrcholech. Pokud chcete složitější variantu, ukažte to samé, ale s úplným grafem na 3 vrcholech.
• Vymyslete polynomiální algoritmus, který nalezne minimální vrcholové pokrytí bipartitního grafu.
• Nalezněte 2-aproximační algoritmus pro bin packing. (bin packing := máte zadaná reálná čísla velikosti 0 až 1. Chcete je rozdělit do co nejméně přihrádek takovým způsobem, že v každé přihrádce nesmí být součet čísel větší než 1)

6.1. (do 20.1.)

• Je dána množina obdélníků, jejichž strany jsou rovnoběžné s osami souřadnic. Spočítejte obsah jejich sjednocení.
• Navrhněte algoritmus, který nalezne nejdelší vodorovnou úsečku ležící uvnitř daného (ne nutně konvexního) mnohoúhelníku.
• V rovině se nachází $n$ jabloní, které chceme oplotit. Sestrojte dva uzavřené ploty tak, aby každá jabloň byla oplocena a celkově jste spotřebovali nejméně pletiva.