[home]

ADS I (2018/2019)

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

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.

• Připomněli jsme si definici a význam asymptotické notace.
• Ukázali jsme jak dopočítat dosvědčující konstanty pro různé asymptotické třídy.
• Vyzkoušeli jsme si jak psát pseudokody a určovat časovou složitost na příkladu úseku s největším součtem v posloupnosti čísel.

1.3.

• Začali jsme s grafovými algoritmy. Zopakovali BFS a jeho časovou složitost a ukázali si jaká bude pro reprezentaci grafu pomocí matice sousednosti.
• Pomocí BFS jsme hledali nejkratší cesty i počet nejkratších cest.
• Použili jsme BFS na hledání ve stavovém prostoru (graf stavů dopředu neznáme, ale při výpočtu si ho stavíme). Příklad dvou robotů uzavřených v bludišti.

8.3.

• Začali jsme s DFS, na příkladu jsme algoritmus odkrokovali, spočítali in, out a low.
• Jako jednu z aplikací DFS jsme ukázali hledání mostů v grafu. Hledání artikulací jsme stihli jen naznačit řešení. Použili jsme DFS na hledání topologického uspořádání.
• Podívali jsme se na DAG a topologickou indukci - nejdelší, nejkratší cesty, počet nejkratších cest.

15.3.

• Pokračovali jsme v příkladech na BFS a DFS - auto na Manhattanu, polosouvislost, obarvené vrcholy na kružnici, rozestavění strážníků ve městě, hledání zdrojové komponenty v DAG.

22.3.

• Procvičovali jsem algoritmy na hledání minimálních cest - Dijkstra a Floyd-Warshall. Oba algoritmy jsme popsali a odkrokovali a připomněli si základní vlastnosti.
• Časová složitost Dijkstrova algoritmu pro různé datové struktury (pole, setříděný spoják, halda, ...). Chování Dijkstrova algoritmu na grafech se zápornou hranou (zkoumali jsme dvě varianty algoritmu - jedna, která otevírá uzavřené vrcholy a druhá, která nikoliv).
• Pomůže přičtení velkého kladného čísla k délkám hran u grafu se zápornými hranami? - ne, může to změnit nejkratší cestu.

29.3.

• Probrali jsme algoritmy na hledání minimální kostry - Jarník, Borůvka, Kruskal. Všechny jsme na příkladě odkrokovali. Ukázali jsme jakému algoritmu vadí neunikátní hrany a proč.
• Mosty jsou na průniku všech koster, souvislost Jarníka a Dijkstry, unikátní hrany zaručují unikátní minimální kostru.

5.4.

• Binární vyhledávací stromy - in-order průchod. Jak ze setříděného pole vytvořit dokonale vyvážený BVS.
• Pomocí předchozího cvičení jsme zvládli join dvou BVS a split jednoho BVS na dva podle zadané hodnoty.

12.4.

• (a,b)-stromy a jejich varianty. Insert, Delete, Join.

26.4.

• Algoritmy typu rozděl a panuj: začali jsme s Master theorem a na každou z možností ukázali příklad algoritmu.
• Násobení dlouhých čísel rekurzivním algoritmem. Nejprve triviálně, to nám čas neušetřilo, poté podle Karacuba. Obdobně násobení matic triviálním rozdělením na podmatice nepomohlo, poté podle Strassena (ověřit správnost a časovou složitost zbývá za domácí úkol). Rozmysleli jsme si, jestli má cenu tyto rekurzivní algoritmy dopočítávat až do triviálních případů - ne, lepší je ukončit dříve.
• Quickselect a úvahy o pivotech - nejhorší případ, medián, skoro-medián, skoro-skoro-medián.

3.5.

• Dokončili jsme algoritmy rozděl a panuj. Předvedli jsme linear select - hledání k-tého prvku v lineárním čase.
• Příklady ze skript: spletitý kabel, šroubky a matičky, inverze trojúhelníkové matice.

10.5.

• Třídící algoritmy, procvičili jsme si zapisování pseudokodu na bubblesortu, selectsortu a insertsortu. U všech jsme zjistili časovou složitost v růszných případech a zda se jedná o stabilní a in-place třídění.
• Zopakovali jsme spodní odhad pro počet porovnání při třídění a na tomto základě jsme hledali nejtěžší/nejlehčí/jinou kuličku.

17.5.

• Hodina odpadá

24.5.

• Hešování - začali jsme s konstrukcí náhodných čísel z náhodného bitu a podívali se jak to funguje v počítačích.
• Hešování s přihrádkami a otevřenou adresací, pár příkladů na využití - hledání dvou čísel se zadaným součtem.
• Zopakovali jsme co znamená c-univerzální systém a bez důkazu zmínili některé takové systémy.

Ú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 8.3.)

• Na vstupu máte setříděnou posloupnost čísel a číslo $s$. Nalezněte 2 (ne nutně různé) prvky z posloupnosti, které mají součet $s$. Napište pseudokod, a zdůvodněte časovou složitost. Lze udělat v lineárním čase.
• Dokažte nebo vyvraťte alespoň 3 z následujících tvrzení.
  • $f(n) \in O(h(n)) \wedge g(n) \in O(h(n))\implies f(n) + g(n) \in O(h(n))$
  • $2^{O(\log n)} \in O(n)$
  • $f(n) \in O(g(n)) \wedge g(n) \in O(h(n))\implies f(n) \in O(h(n))$
  • $f(n) \in O(g(n)) \implies 2^{f(n)} \in O(2^{g(n)})$
  • $\max(f(n), g(g)) \in \Theta(f(n) + g(n))$
  • $f(n) \in o(g(n)) \wedge g(n) \in o(h(n))\implies f(n) \in o(h(n))$

1.3. (do 15.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ů.
• 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.
• V hodině jsme vyřešili následující příklad: Koupili jste na inzerát dvojici skvělých robotů. Lacino, neboť jsou právě uvěznění v bludišti (čtvercová síť s některými políčky blokovanými). Znáte jejich polohy a můžete jim rádiem vysílat povely pro posun o políčko na sever, jih, východ či západ, abyste je dostali na okraj bludiště. Háček je ale v tom, že na každý povel reagují oba roboti. Vymyslete algoritmus, který najde nejkratší posloupnost povelů, jež vysvobodí oba roboty. Dodejme ještě, že robot ignoruje povel, který by způsobil okamžitý náraz do zdi, a že jakmile se robot dostane na okraj, odchytíme ho a další povely neposlouchá.

  Zkuste vymyslet jak příklad vyřešit, pokud počáteční pozici robotů neznáme.

8.3. (do 22.3.)

• Kdy je topologické uspořádání grafu určeno jednoznačně?
• Asfaltování: Máme mapu městečka v podobě neorientovaného grafu. Parta asfaltérů umí za jednu směnu vyasfaltovat dvě na sebe navazující ulice. Jak vyasfaltovat každou ulici právě jednou? Jde to pokaždé, když je ulic sudý počet?
• Vyvážená orientace: Hranám grafu chceme přiřadit orientace tak, aby z každého vrcholu vycházelo stejně hran, jako do něj vchází. Ukažte, že to lze, kdykoliv všechny vrcholy mají sudé stupně a vymyslete algoritmus, který danou orientaci nalezne.
• Naprogramujte algoritmus na hledání artikulací v neorientovaném grafu. Popis algoritmu lze najít ve skriptech. Jazyk můžete použít libovolný rozumný a čitelný (C/C++, C#, Java, Pascal, ...).

15.3. (do 29.3.)

• V každém neorientovaném grafu bez mostů je možné hrany zorientovat tak, aby vznikl silně souvislý orientovaný graf. Vymyslete algoritmus, který takovou orientaci najde.
• Spočítejte v rovinném grafu trojúhelníky, tedy trojice vrcholů spojené každý s každým. Pokuste se o složitost lepší než $O(n^3)$. Lze vyřešit v lineárním čase.
• Mějme souvislý orientovaný graf. Chceme mazat jeho vrcholy jeden po druhém tak, aby graf zůstal stále souvislý. Jak takové pořadí mazání najít?

22.3. (do 5.4.)

• Směnárna obchoduje s $n$ měnami (měna číslo 1 je koruna) a vyhlašuje matici kurzů $K$. Kurz $K_{ij}$ ří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.
• V Tramtárii jezdí po železnici samé rychlíky, které nikde po cestě nestaví. V jízdním řádu je pro každý rychlík uvedeno počáteční a cílové nádraží, čas odjezdu a čas příjezdu. Nyní stojíme v čase $t$ na nádraží $a$ a chceme se co nejrychleji dostat na nádraží $b$. Navrhněte algoritmus, který najde takové spojení.
• Mějme mapu města ve tvaru orientovaného grafu. Každou hranu ohodnotíme podle toho, jaký nejvyšší kamion po dané ulici může projet. Po cestě tedy projede maximálně tak vysoký náklad, kolik je minimum z ohodnocení jejích hran. Jak pro zadané dva vrcholy najít cestu, po níž projede co nejvyšší náklad?

29.3. (do 12.4.)

• Máte nalezenou minimální kostru. V grafu se změnila délka jedné hrany. Jak co nejrychleji najít novou minimální kostru?
• Implementujte libovolný ze tří algoritmů na hledání minimální kostry. Jejich detailní popis najdete ve skriptech. Jazyk můžete použít libovolný rozumný a čitelný (C/C++, C#, Java, Pascal, ...).

5.4. (do 19.4.)

• Dokažte, že projdeme-li celý strom opakovaným hledáním následníka, strávíme tím čas $\theta(n)$. Upřesnění úkolu: Uvažujme následující algoritmus. Vybereme si jeden prvek (třeba minimum ze všech prvků ve stromě) a n-krát zavoláme hledání následníka, tím postupně nalezneme všechny prvky ve stromě. Problém ale je, že hledání následníka obecně může trvat dlouho (až O(log n)), celková složitost n-krát hledání následníka by tedy měla být O(n log n). Chceme ale dokázat, že pokud projdeme celý strom popsaným algoritmem, tak nám to celkem zabere pouze $\theta(n)$.
• Ú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.
• Okénkový medián: Na vstupu postupně přicházejí čísla. Kdykoliv přijde další, vypište medián z posledních k čísel. Dosáhněte časové složitosti O(log k) na operaci.

12.4. (do 26.4.)

• Nevýhodou (a,b)-stromů je, že plýtvají pamětí – může se stát, že vrcholy jsou zaplněné jen z poloviny. Navrhněte úpravu, která zaručí zaplnění z alespoň 2/3.
• Navrhněte operaci Split(T, x), která zadaný (a,b)-strom T rozdělí na dva stromy. V jednom budou klíče menší než x, v druhém ty větší. Pokuste se o logaritmickou časovou složitost.
• Dokažte, že budeme-li reprezentovat množiny binárními vyhledávacími stromy, nelze sjednocení provést rychleji než lineárně v nejhorším případě. Platí to dokonce i tehdy, máme-li na vstupu zaručený dokonale vyvážený strom a výstup může být jakkoliv nevyvážený.

26.4. (do 10.5.)

• Dokažte, že Strassenovo násobení matic funguje (tj, skutečně vydá korektně vynásobené matice). Určete jeho časovou složitost podle Master Theorem.
• Tranzitivní uzávěr orientovaného grafu s vrcholy $\{1, \dots n\}$ je nula-jedničková matice $T$ tvaru $n \times n$, kde $T_{uv} = 1$ pravě tehdy, když v grafu existuje cesta z vrcholu u do vrcholu v. Ukažte, že umíme-li násobit matice $n \times n$ v čase $O(n^\omega)$, můžeme vypočítat tranzitivní uzávěr v čase $O(n^\omega log n)$.
• Popište třídicí algoritmus (podobný Mergesort), který bude vstup rozkládat na více než dvě části a ty pak rekurzivně třídit. Může být rychlejší než Mergesort?

3.5. (do 17.5.)

• Proč v algoritmu Linearselect používáme zrovna pětice? Fungoval by algoritmus s trojicemi? Nebo se sedmicemi? Byl by pak stále lineární? Algoritmus i důkaz složitosti s pěticemi můžete nalézt ve skriptech.
• Inverze v posloupnosti $x_1, \dots , x_n$ říkáme každé dvojici $(i, j)$ takové, že $i < j$ a současně $x_i > x_j$ . Vymyslete algoritmus, který spočítá, kolik daná posloupnost obsahuje inverzí. Pokuste se o čas lepší než O(n^2).
• 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. Můžete předpokládat, že znáte pozice začátků posloupností. (Lze řešit v čase O(log n).)

10.5. (do 24.5.)

• Jsou dány rovnoramenné váhy a 12 kuliček, z nichž právě jedna je jiná než ostatní, nevíme však zda je lehčí nebo těžší. Na misku lze dát i více kuliček naráz. Navrhněte, jak na 3 vážení najít tuto jinou kuličku a zjistit, jestli je lehčí nebo těžší. Dokažte, že na 2 vážení to nejde.
• Jsou dány rovnoramenné váhy a n kuliček, z nichž právě jedna je těžší než ostatní. Na misku lze dát i více kuliček naráz. Navrhněte obecný postup jak tuto kuličku nalézt a dokažte, že počet vážení je optimální.
• Matice: Mějme matici A tvaru $n \times n$, v níž jsou uložena celá čísla a navíc každý řádek i sloupec tvoří rostoucí posloupnost. Jak najít $i, j$ takové, že $A_{i,j} = i + j$? Pokud existuje více řešení, stačí vypsat jedno. Čas na načtení matice do paměti nepočítáme.

24.5. (do neomezeno)

• V mnoha programovacích jazycích je k dispozici funkci random, která nám vrátí rovnoměrně (pseudo)náhodné číslo z pevně daného intervalu. Lidé ji často používají pro generování čísel v rozsahu od 0 do n-1 tak, že spočtou random mod n. Jaký se v tom skrývá háček? Jak ho obejít?
• Vasil Vasiljevič míchá karty takto: připraví si n prázdných přihrádek. Pak postupně umisťuje čísla 1, ..., n do přihrádek tak, že vždy vybere rovnoměrně náhodně přihrádku a pokud v ní již něco je, vybírá znovu. Kolik pokusů bude v průměru potřebovat?
• Mějme množiny celých čísel A a T (|A| < |T|). Jak zjistit, zda je A podmnožinou T? Jakou má váš algoritmus časovou složitost?
• Máme množinu čísel {22,1,13,11,24,33,18,42,31}, kterou chceme zahešovat do m = 11 přihrádek. Máme dvě hešovací funkce $h_1(x)=x \: mod \: m$ a $h_2(x)=(x \: mod \: m-1) + 1$. Zahešujte čísla pomocí:
• přihrádkového hešování s $h(x) = h_1(x)$
• lineárního přidávání s $h(x,i) = (h_1(x) + i) mod \: m$
• dvojitého hešování s $h(x,i) = (h_1(x) + i*h_2(x)) mod \: m$