[home]

ADS I (2017/2018)

Cvičení k přednášce Algoritmy a datové struktury I, kterou přednáší Jan Hubička

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

22.2.

• Hledání úseku s největším součtem (zatím umíme pouze kvadraticky).
• Jak efektivně umocnit číslo na n-tou.
• Hledání dvou čísel v seřazené posloupnosti, které mají součet K.
• Jak funguje binární vyhledávání a jak je rychlé.

1.3.

• Hledání úseku s největším součtem lineárně.
• Jak rychle spočítat Fibonacciho číslo pomocí mocnění matic.
• Seznámení s $O$ notací: Hledání konstant pro konkrétní funkce; vzájemné porovnání dvou funkcí; proč u logaritmů nezáleží na jejich základu.

8.3.

• Seznámili jsme se s dalšími notacemi: $O$, $\Omega$, $\Theta$, $o$, $\omega$.
• Jak vyjádřit jednotlivé notace pomocí zbývajících notací.
• Zkoumali jsme, zda platí symetrie ($O$ a $\Omega$), tranzitivita a aritmetika pro asymptotické notace.

15.3.

• Začali jsme s BFS - jakou reprezentaci grafu použít a co to znamená pro časovou složitost.
• Jednoduché příklady na hledání nejkratší cesty pomocí BFS a zjištění počtu nejkratších cest z počátečního vrcholu.
• Jak neorientovaný graf rozdělit na komponenty souvislosti pomocí BFS.

22.3.

• Začali jsme s DFS - předvedli jsme si jeho průběh na jednoduchém příkladu, ukázali klasifikaci hran, včetně toho, že jiné druhy hran neexistují a které z nich se mohou vyskytovat v neorientovaných grafech.
• In a Out z DFS jsme použili na nalezení pořadí ve kterém mazat vrcholy z grafu tak, aby byl během mazání stále souvislý.
• Připomněli jsme si algoritmus na hledání mostů a ukázali si algoritmus na hledání artikulací. Dokázali jsme si i kdy mosty a artikulace neexistují.

29.3.

• Seznámili jsme se s DAG. Dokázali si, jak jej rozpoznat, a že právě DAG lze topologicky uspořádat. Na nalezení topologického uspořádání jsme využili DFS. Poté jsme si procvičili topologickou indukci (počet cest, nejdelší a nejkratší cesta). Nakonec jsme si také ukázali, kdy je topologické uspořádání jednoznačné.
• Připomněli jsme si algoritmus pro hledání SSK. Navíc jsme jej upravili aby v průběhu výpočtu stavěl i graf komponent.
• Zavedli jsem si co je to polosouvislost a ukázali jaké jsou inkluze mezi třemi souvislostmi (silná, polo, slabá). Jak zjistit, že je graf polosouvislý nám zůstalo za domácí úkol.

5.4.

• Na chvíli jsme se vrátili k BFS a ukázali si, jak se hledá v prostoru stavů. Tím jsme vyřešili kulhajícího koně, rozbité auto na Manhattanu i Thesea v labyrintu.
• Začali jsme s hledáním nejkratších cest. Připomněli jsme si Dijkstrův algoritmus a zmínili proč mu vadí záporné hrany. Poté jsme prozkoumali několik základních datových struktura a jakou časovou složitost s nimi bude mít.

12.4.

• Podívali jsme se na obecný relaxační algoritmus a zkusili jak se bude chovat při různém vybírání otevřeného vrcholu - fronta (Bellman-Ford) a zásobník.
• Ukázali jsme si Floyd-Warshallův algoritmus pro hledání nejkratších cest mezi všemi vrcholy.
• Hledali jsme záporné cykly pomocí B-F i F-W.

19.4.

• Podívali jsme se na minimální kostry. Připomněli jsme si Jarníkův algoritmus a vyzkoušeli hned 3 implementace - triviální, která prochází všechny hrany; haldová implementace; implementace, která se podobá Dijkstrovu algoritmu.
• Vymysleli jsme jak rychle přepočítat min. kostru, pokud se nějaká hrana zkrátí nebo prodlouží.
• Podívali jsme se i na binární vyhledávací stromy. Jakmile jsme přišli na inorder průchod, ostatní operace (split, join, lineární vyvažování) byly už jednoduché.

26.4.

• Cvičení odpadá.

3.5.

• Podívali jsme se na (a,b)-stromy. Zdůvodnili si, proč jsou nutné podmínky na volbu a a b. Počítali jsme časovou složitost operací Find, Insert a Delete vzhledem k parametrům a a b.
• Operace Insert a Delete jsme zapsali i jako pseudokód a na příkladě jsme si je zkusili odkrokovat.

10.5.

• Začali jsme s algoritmy rozděl a panuj. Nejprve jsme si připomněli počítání rekurentních rovnicí pomocí dosazení, stromů rekurze a nakonec i pomocí Master Theoremu (kuchařková věta).
• Pomocí MT jsme zjistili, že dělení na více podposloupností mergesortu nepomáhá. Nalezli jsme zástupce algoritmů pro všechny možnosti MT. Také jsme se podívali na známé rekurentní algoritmy a spočítali jejich složitost pomocí MT.
• Nakonec jsme se podívali na násobení matic. Klasické rekurzivní není o nic rychlejší než násobení podle definice. Strassenovo násobení jsme si stihli jen zapsat, spočítat složitost a korektnost zůstalo za domácí úkol.

17.5.

• Dokončili jsme algoritmy rozděl a panuj
• Připomněli jsme si hledání k-tého prvku v lineárním čase. Prozkoumali jsme si jak se algoritmus chová v případě, že volíme trojice a sedmice místo pětic. Také jsme vymysleli, jak předělat algoritmus, aby používal konstantně mnoho paměti.

24.5.

• Dnes jsme opakovali vše co jsme tento semestr probírali. Úkoly jsme brali z tohoto dokumentu. Stačili jsme vyřešit pouze příklady 1, 2, 4, 8, 9, 15.

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

22.2. (do 11.3.)

• Na vstupu je text složený pouze z písmen abecedy (ta má 26 písmen). Vymyslete co nejrychlejší algoritmus, který najde nejdelší úsek textu, v němž se žádné písmeno neopakuje. Zapište i jako pseudokód.
• Najděte v textu nejkratší úsek, který obsahuje všechny znaky abecedy (26 různých písmen). Zapište i jako pseudokód.
• Máme v poli rostoucí posloupnost přirozených čísel. Chceme najít nejmenší přirozené číslo, které v ní chybí. Vymyslete jak k tomu přesvědčit binární vyhledávání. Opět chci i pseudokód.

1.3. (do 15.3.)

• Nalezněte co nejvíce vztahů ($O$ a $\Theta$) mezi následujícími funkcemi ($n$ je proměnná, zbytek jsou konstanty): $n!$, $e^n$, $n^2$, $n$, $4^{log_2(n)}$, $n log(n)$, $1$, $2^k$
• Najděte co nejlepší asymptotický odhad funkce $log_n(n!)$
• Dokažte nebo vyvraťte: $f(n) \in O(h(n)) \wedge g(n) \in O(h(n))\implies f(n) + g(n) \in O(h(n))$.

8.3. (do 22.3.)

Pro každé z následující tvrzení nalezněte funkce f a g, tak aby splnily podmínky (stačí si vybrat jen 3 podmínky, přičemž f a g mohou být pro každý bod jiné).

• $f(n) \in O(g^2(n))$
• $f(n) \in \omega(g(n))$
• $f(n) \in \omega(log (g(n)))$
• $f(n) \in \Omega(f(n)*g(n))$
• $f(n) \in \Theta(g(n)) + \Omega(g^2(n))$

15.3. (do 29.3.)

• Na jisté šachovnici žil kulhavý kůň. To je zvláštní šachová figurka, která v sudých tazích táhne jako jezdec, v lichých jako pěšec. Vymyslete algoritmus, který z jednoho zadaného políčka dokulhá na druhé na nejmenší možný počet tahů.
• Mějme mapu Manhattanu: čtverečkovaný papír, křížení čar odpovídají křižovatkám, úsečky mezi nimi jednotlivým streets a avenues, z nichž některé jsou neprůjezdné kvůli dopravní zácpě. Zrovna se nám v jedné ulici porouchalo auto a nyní dovede pouze jezdit rovně a odbočovat doprava. Nalezněte nejkratší cestu do servisu (na zadanou křižovatku).
• Hrdina Théseus se vypravil do hlubin labyrintu a snaží se najít poklad. Chodbami labyrintu se ovšem pohybuje hladový Mínótauros a snaží se najít Thésea. Labyrint má tvar čtvercové sítě, jejíž každé políčko je buďto volné prostranství, anebo zeď. Známe mapu labyrintu a počáteční polohy Thésea, Mínótaura a pokladu. Théseus se v jednom tahu pohne na vybrané sousední políčko. Poté se vždy dvakrát pohne o políčko Mínótauros: pokaždé se pokusí zmenšit o 1 rozdíl své a Théseovy x-ové souřadnice, pokud to nejde, pak y-ové, pokud nejde ani to, stojí. Poraďte Théseovi, jak má dojít k pokladu a vyhnout se Mínótaurovi.

22.3. (do 5.4.)

• Zapište algoritmus pro hledání artikulací jako pseudokód. (Pokud jste nebyli na cvičení, kde se předváděl nebo si ho nepamatujete, pak vám pomůžou skripta
• Vrchol v orientovaném grafu nazveme "ultrašéfem", pokud se z něj lze dostat do všech ostatních vrcholů v grafu, ale z žádného jiného vrcholu se nelze dostat do něj. Navrhněte algoritmus, který nalezne ultrašéfa v zadaném grafu (nebo ohlásí, že neexistuje) v lineárním čase.
• Nalezněte v grafu Eulerovský cyklus. Můžete předpokládat, že v grafu existuje.

29.3. (do 12.4.)

• Vítěz: n sportovců sehrálo zápasy každý s každým. Chceme zjistit, zda existuje někdo, kdo vyhrál nad všemi ostatními. Máme-li matici výsledků zápasů již načtenou v paměti, lze to spočítat v čase O(n).
• Strážníci: Mapa městečka má tvar stromu. Na křižovatky chceme rozmístit co nejméně strážníků tak, aby každá ulice byla z alespoň jedné strany hlídaná.
• O orientovaném grafu řekneme, že je polosouvislý, pokud mezi každými dvěma vrcholy vede orientovaná cesta alespoň jedním směrem. Navrhněte lineární algoritmus, který polosouvislost grafu rozhoduje.

5.4. (do 19.4.)

• Ukažte, jak pro libovolné n sestrojit graf na nejvýše n vrcholech, v němž mezi nějakými dvěma vrcholy existuje $2^{\Omega(n)}$ nejkratších cest.
• Prozkoumejte, jak se bude chovat Dijkstrův algoritmus (viz skripta), pokud ho pustíme na graf, v němž se vyskytují záporné hrany. Jak to bude se zápornými cykly? Máme zaručený správný výsledek a konečnost algoritmu?
• Nechť délky hran leží v množině {0, . . . , L}. Navrhněte datovou strukturu založenou na přihrádkách, s níž Dijkstrův algoritmus poběží v čase O(nL + m). Pokuste se vystačit s pamětí O(n + m + L).

12.4. (do 26.4.)

• Lze se v algoritmech na hledání nejkratší cesty zbavit záporných hran tím, že ke všem ohodnocením hran přičteme nějaké velké číslo k?
• Počítačovou síť popíšeme orientovaným grafem, jehož vrcholy odpovídají routerům a hrany linkám mezi nimi. Pro každou linku známe pravděpodobnost toho, že bude funkční. Pravděpodobnost, že bude funkční nějaká cesta, je dána součinem pravděpodobností jejích hran. Jak pro zadané dva routery najít nejpravděpodobnější cestu mezi nimi?
• Směnárna obchoduje s n měnami (měna číslo 1 je koruna) a vyhlašuje matici kurzů K. Kurz Kij říká, kolik za jednu jednotku i-té měny dostaneme jednotek j-té měny. Vymyslete algoritmus, který zjistí, zda existuje posloupnost směn, která začne s jednou korunou a skončí s více korunami.
• Dokažte, že v grafu bez záporných cyklů se obecný relaxační algoritmus zastaví, ať už vrchol k uzavření vybíráme libovolně. Popis obecného relaxačního algoritmu naleznete opět ve skriptech.

19.4. (do 3.5.)

• Ukažte příklad stromu, který je AVL vyvážený, ale není dokonale vyvážený.
• Dokažte, že dokonalá vyváženost implikuje AVL vyváženost.
• Na hodině jsme předvedli jak dokonale vyvážit binární vyhledávací strom v čase O(n), ale použili jsme přitom i O(n) paměti. Zkuste to nyní udělat s O(log n) nebo dokonce s O(1) pamětí.
• Úsporné stromy: Obvyklá reprezentace BVS v paměti potřebuje v každém vrcholu 3 ukazatele: na levého syna, na pravého syna a na otce. Ukažte, jak si vystačit se dvěma ukazateli. Původní 3 ukazatele by z těch vašich mělo jít spočítat v konstantním čase.

3.5. (do 17.5.)

• Ukažte, že pokud budeme do prázdného (a,b)-stromu postupně vkládat klíče 1, ..., n, provedeme celkem $\Theta(n)$ operací. K tomu si potřebujeme pamatovat, ve kterém vrcholu skončil předchozí vložený klíč, abychom nemuseli pokaždé hledat znovu od kořene.
• Navrhněte operaci Join(X, Y), která dostane dva (a,b)-stromy X a Y a sloučí je do jednoho. Můžete se přitom spolehnout na to, že všechny klíče z X jsou menší než všechny z Y. Zkuste dosáhnout složitosti O(log |X| + log |Y|).
• Navrhněte operaci Split(T, x), která zadaný (a,b)-strom T rozdělí na dva (a,b)-stromy. V jednom budou klíče menší než x, v druhém ty větší. Pokuste se o logaritmickou časovou složitost.

10.5. (do 24.5.)

• Ukažte korektnost a časovou složitost (pomocí Master Theorem aka kuchařkové věty) Strassenova násobení matic. Jeho definici můžete vzít ze skript nebo wikipedie.
• Řešte rekurenci $T(n) = n^{1/2} T(n^{1/2}) + \Theta(n)$. Pozor na to, že tato rekurence nelze řešit pomocí Master Theorem.

17.5. (do 31.5.)

• Hledáme k-tý nejmenší prvek jako ve funkci linear select. Pivota ale volíme náhodně. Jaké časové složitosti dosáhneme, pokud se vždy trefíme do mediánu? Do skoro mediánu (prvek v prostředních 2 čtvrtinách setříděné posloupnosti)? Do skoro skoro mediánu (prvek v prostředních 6 osminách setříděné posloupnosti)?
• Je dáno n-prvkové pole, ve kterém jsou za sebou dvě vzestupně setříděné posloupnosti (ne nutně stejně dlouhé). Navrhněte algoritmus, který najde medián sjednocení obou posloupností v sublineárním čase. (Lze řešit v čase O(log n).)