====== Cvičení z ADS1 2019/20 ====== Na pravé straně této stránky vizte obsah. Silně doporučuji pečlivě vše pročíst. Při emailové komunikaci se mnou prosím **vždy** uveďte do předmětu text ''[ADS1]'' nebo pište na email ''koutecky+ads1@iuuk.mff.cuni.cz''. ===== Co se dělalo na cvičení ===== * {{ :teaching:ads11920:01-cv.pdf |1. cvičení}} * {{ :teaching:ads11920:02-cv.pdf |2. cvičení}} * {{ :teaching:ads11920:03-cv.pdf |3. cvičení}} * {{ :teaching:ads11920:04-cv.pdf |4. cvičení}} * {{ :teaching:ads11920:05-cv.pdf |5. cvičení}} * {{ :teaching:ads11920:06-cv.pdf |6. cvičení}} * {{ :teaching:ads11920:07-cv.pdf |7. cvičení}} * {{ :teaching:ads11920:08-cv.pdf |8. cvičení}} * {{ :teaching:ads11920:09-cv.pdf |9. cvičení}} * {{ :teaching:ads11920:10-cv.pdf |10. cvičení}} * {{ :teaching:ads11920:11-cv.pdf |11. cvičení}} * {{ :teaching:ads11920:12-cv.pdf |12. cvičení}} {{page>teaching:bits:zdroje_ads1}} ===== Požadavky na zápočet ===== Zápočet vám udělím, získáte-li celkově 100 bodů. Váš aktuální počet bodů bude uveden v tabulce na konci této stránky. **Pozor:** z důvodu ochrany osobních údajů nemůžu bez vašeho svolení v tabulce uvádět vaše jméno; proto mi v každém řešení domácí úlohy uveďte i svou přezdívku, pod kterou chcete být v tabulce uvedeni. Pokud přezdívku neuvedete, beru to jako souhlas k uvedení vašeho skutečného jména. Body lze získávat následujícími způsoby: * **Řešení úkolů:** celkově zadám úlohy za cca 180 bodů. Každý úkol má termín, typicky dva týdny, pak klesnou body na polovinu. Úlohy budou rozděleny do skupin označených písmeny a z každé skupiny chci, abyste vypracovali aspoň jeden úkol. Více o [[#vypracovávání domácích úloh|vypracovávání domácích úloh]]... * **Opravování úkolů:** pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, máte možnost získat **navíc až pětinásobek bodů** tím, že se stanete //korektorem// pro tuto úlohu. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr. Více o [[#korektorství|korektorství]]... * **Malé písemky:** na začátku každého cvičení budete psát krátkou (~10 minut) písemku zejména na osvěžení definic, pojmů a algoritmů z přednášky (a možná na jejich velmi jednoduché procvičení). Zápočet je možné získat i bez písemek, můžete je brát spíš jako usnadnění/urychlení získání zápočtu. * **Zápočťák:** body můžete získat taky za zápočtový projekt, který může být praktický (implementace algoritmu) či teoretický (popis a analýza nějakého složitějšího algoritmu). Více o [[#jak_zapoctaky_funguji|zápočťácích]]... ====== Domácí úkoly ====== **Úloha RAM (7b, plný počet do 4. 3.)** //[A]// Naprogramujte na RAMu nějaký třídicí algoritmus se složitostí O(N log N). Nezapomeňte popsat uložení dat v paměti. **Úloha unikum (6b, plný počet do 4. 3.)** //[A]// Najděte v posloupnosti nejdelší úsek, v němž se žádná hodnota neopakuje. **Úloha medián (8b, plný počet do 4. 3.)** //[A]// Jak v lepším než lineárním čase najít medián sjednocení dvou setříděných posloupností? Vstup je zadán jako už načtená pole jen ke čtení, nebo alternativně jako orakulum (funkce), které umí vrátit $i$-tý prvek z dané vstupní posloupnosti. //Hint:// Hledejte rekurzivně $k$-tý nejmenší ze dvou podposloupností. **Úloha housenka (9b, plný počet do 11. 3.)** //[B]// Najděte v zadaném stromě housenku na co nejvíce vrcholech. //Housenka// je podgraf, který se skládá z cesty na jejímž každém vrcholu jsou až čtyři listy (nožičky), ale můžou tam být i vrcholy bez nožiček. Není to totéž, co nejdelší cesta, protože nejde o housenku co nejdelší, ale na největším počtu vrcholů (tedy i s nožičkami). Řešení by mělo být v $O(n)$. **Úloha abeceda (9b, plný počet do 25. 3.)** //[B]// Nalezli jste knihovnu ztracené civilizace a zkoumáte její abecedu o $n$ prapodivných znacích. Každá kniha má na svém hřbetu nápis touto abecedou a doufáte, že jsou knihy seřazené abecedně (lexikograficky). Rádi byste věděli, jestli z pořadí knížek lze zjistit jednoznačné pořadí znaků abecedy, jestli je pro to informací málo, či zda dokonce takové pořadí nemůže existovat (a knihovnu tedy někdo přeházel). Zadání si představte třeba jako seznam slov bez mezer z abecedy "a-z", otázkou je pak pořadí znaků "a-z" v hledané abecedě. Zkuste najít algoritmus, který to zvládne v lineárním čase s velikostí vstupu. Můžete předpokládat, že se každé písmeno mezi nápisy vyskytne. **Úloha polosouvislost (9b, plný počet do 25. 3.)** //[B]// Řekněme, že orientovaný graf $G$ je //polosouvislý//, když pro každé dva vrcholy $u$ a $v$ platí, že existuje orientovaná cesta z $u$ do $v$ nebo orientovaná cesta z $v$ do $u$. Toto je silnější vlastnost, než slabá souvislost grafu, ale slabší vlastnost, než silná souvislost grafu. Jak v čase $O(m+n)$ zjistit, zda je $G$ polosouvislý? **Úloha holubi (9b, plný počet do 25. 3.)** //[B]// Každý poštovní holub, je-li vypuštěn se zprávou, s ní doletí jen na jedno místo, které je pro konkrétního holuba pevné. Ve spolku pěstitelů holubů má každý člen holuby, kteří mohou doručit zprávu k několika dalším členům. Svolat všepěstitelské setkání je možné jen tak, že ho jeden ze členů vyhlásí rozesláním zpráv všem členům, na které má holuby, a ti pak pošlou zprávu dál svými holuby. Když znáte strukturu spolku, v čase lineárním s počtem zúčastněných holubů a členů zjistěte, zda vůbec existuje někdo, kdo má možnost setkání všech členů svolat. **Úloha cheating (7b, plný počet do 25. 3.)** //[C]// Závod bludištěm z živých plotů! Jste rozhodnuti vyhrát a to i za cenu malé ... zkratky, kterou pravidla zapomněla zmínit. Nejste ale ochotni se křovím prodrat víc než jednou, ještě by si toho někdo všiml a mohl by to ... špatně pochopit. Bludiště je popsáno grafem se startem, cílem, délkami hran a dvěma typy hran; chodby bludištěm a zkratky křovím, kterými se ještě jde prodrat. Navrhněte algoritmus pro nejkratší cestu do cíle v co nejlepším čase. **Úloha zakázka (10b, plný počet do 25. 3.)** //[C]// Olga Opatrná najala Láďu Lenocha, aby ji pro daný neorientovaný graf $G=(V,E)$, vrchol $s\in V$ a //nezáporné// celočíselné váhy hran $w(u,v)$ (kde $w(u,v)=w(v,u)$) spočítal nejkratší cesty z vrcholu $s$ do všech ostatních vrcholů. Konkrétně má Láďa spočíst dvě funkce: $d(v)$ má být délka nejkratší cesty z $s$ do $v$ (nebo $\infty$, pokud taková není), a $\pi(v)$ má být předposlední vrchol na nějaké nejkratší cestě z $s$ do $v$ (nebo $\mathrm{NIL}$, pokud taková není). Olga ale moc nevěří Láďově pečlivosti, a tak si chce výsledky ověřit, což se jí zdá jednodušší, než si je spočíst sama. Konkrétně ověří následující podmínky: - $d(s)=0$ - $\pi(s)=\mathrm{NIL}$ - $\forall (u,v)\in E: d(v) \leq d(u) + w(u, v)$ - $\forall v\in V: \pi(v)\neq\mathrm{NIL}\Rightarrow d(v) = d(\pi(v)) + w(\pi(v),v)$ - $\forall v\in V, v\neq s: d(v) < \infty \Rightarrow \pi(v) \neq\mathrm{NIL}$ Jak může Láďa Olze dát data $d$ a $\pi$, která nejsou korektní podle Olžina zadání, ale splňují tyto ověřovací podmínky? Konkrétně: najděte takový graf, funkci $w$, vrchol $s$ a funkce $d$ a $\pi$, nebo ještě lépe popište takové případy obecněji. Za druhé upravte či doplňte podmínky tak, aby už každé řešení splňující tyto podmínky popisovalo nejkratší vzdálenosti a cesty. **Úloha listy-kostry (8b, plný počet do 15. 4.)** //[C]// Máme dánu $U$ jako podmnožinu vrcholů souvislého grafu $G$ s váhami hran $w$. Najděte minimální kostru $G$ ze všech takových koster, které mají vrcholy z $U$ jako listy. Algoritmus by měl být stejně rychlý jako jiné vám známé algoritmy na min. kostru a měl by rozpoznat situaci, že taková kostra neexistuje. **Úloha rovnováha (9b, plný počet do 22. 4.)** //[D]// Vymyslete algoritmus, který v lineárním čase přebuduje vyhledávací strom na dokonale vyvážený. Nemáte dost paměti na to, abyste si mohli pořídit ještě jednu kopii prvků – kromě stromu si smíte pamatovat $O(1)$ hodnot (pointerů, počitadel do $n$, kopií hodnot). **Úloha merge (10b, plný počet do 22. 4.)** //[D]// Navrhněte algoritmus pro sloučení dvou AVL stromů $A$ a $B$, kde všechny prvky $A$ leží před všemi prvky $B$, do jediného AVL stromu $C$. Hledáme řešení s lepší složitostí než $O(min(|A|,|B|))$. **Úloha paren (10b, plný počet do 22. 4.)** //[D]// Je dána posloupnost levých a pravých závorek délky $n$. Vymyslete datovou strukturu, která umí operace "otoč závorku na pozici i" (v $O(\log n)$ a "zjisti, jestli je posloupnost dobře uzávorkovaná" (v $O(1)$). **Úloha min-strom (8b, plný počet do 22. 4.)** //Minimový binární strom// $M(a)$ pro zadanou posloupnost $a=(a_1\dots a_n)$ bez opakujících se prvků je definován takto: Buď $a_i$ minimální prvek $a=(a_1\dots a_n)$; pak kořen $M(a)$ je $a_i$, jeho levý podstrom je $M(a_1\dots a_{i-1})$ a pravý podstrom $M(a_{i+1}\dots a_n)$. $M(\emptyset)$ je prázdný strom. Pro zadanou posloupnost postavte minimový strom v čase $O(n)$. **Úloha tridena-majorita (5+5b, plný počet do 22. 4.)** //[D]// Majorita posloupnosti je prvek, který se v ní vyskytuje na více než polovině pozic (posloupnost tedy má jednu nebo žádnou majoritu). Na cvičení ukážeme (ukázali jsme) příklad, kdy je úkolem najít majoritu, pokud existuje, s pamětí $O(1)$ (resp. $O(\log n)$ na RAMu) v čase $O(n)$. Pokud je posloupnost setříděná, lze zda má majoritu zjistit a zároveň ji najít mnohem rychleji, a to v čase $O(\log n)$. Popište takový algoritmus. Pro 5 bodů navíc dokažte, že rychleji toto není možné zjistit. Pro plný počet by tento důkaz měl být jasný a úplný. **Úloha union (12b)** //[E]// Dokažte, že pro množiny reprezentované binárními vyhledávacími stromy není možné spočítat sjednocení v lepším než lineárním čase, a to ani v případě, kdy na vstupu dostanete dokonale vyvážené stromy a výstup nemusí být vyvážený. **Úloha addmin (10b)** //[E]// Navrhněte datovou strukturu, která udržuje posloupnost x1,…,xn celých čísel. Na počátku posloupnost obsahuje samé nuly. K dispozici jsou operace Add(i,j,δ), která přičte ke všem hodnotám xi,xi+1,…,xj číslo δ, a Min(i,j), která vrátí minimum z hodnot xi,xi+1,…,xj. **Úloha prank (10b)** //[E]// Uvažme posloupnost všech permutací na množině 1,…,n uspořádanou lexikograficky. Jak nalézt k-tou permutaci v této posloupnosti? A jak pro zadanou permutaci $1,\dots,n$ určit její pořadí mezi všemi permutacemi $1,\dots,n$? **Úloha podobne (9b)** //[E]// V posloupnosti čísel na vstupu najděte nejdelší souvislý úsek, ve kterém je rozdíl libovolných dvou prvků nejvýše k. **Úloha matsoucin (9b)** //[E]// Násobíme-li matice $X\in\mathbb{R}^{a\times b}$ a~$Y\in\mathbb{R}^{b\times c}$ podle definice, počítáme $a\cdot b\cdot c$ součinů čísel. Pokud chceme spočítat maticový součin $X_1\times\ldots\times X_n$, výsledek nezávisí na uzávorkování, ale časová složitost (měřená pro jednoduchost počtem součinů čísel) ano. Vymyslete algoritmus, který stanoví, jak výraz uzávorkovat, abychom složitost minimalizovali. } **Úloha triangul (9b)** //[E]// //Minimální triangulace:// Konvexní mnohoúhelník můžeme triangulovat, tedy rozřezat neprotínajícími se úhlopříčkami na trojúhelníky. Nalezněte takovou triangulaci, aby součet délek řezů byl nejmenší možný. **Úloha mindmap (20b)** //[E]// Speciální úloha: vytvořte myšlenkovou mapu (na papíře či pomocí svého oblíbeného softwarového nástroje, např. [[https://orgpad.com/|OrgPad]]) ADS1: mapa by měla obsahovat probrané algoritmy, algoritmické principy, hlavní myšlenky a souvislosti mezi všemi zmíněnými. Mapa by měla být dost podrobná, abyste pouze s ní (a bez učebnice či dalších poznámek) dokázali složit zkoušku, tzn. dokázat jakékoliv tvrzení z přednášky -- tedy měl by to být takový váš ultimátní tahák. ===== Další informace ===== {{page>teaching:bits:vypracovavani}} {{page>teaching:bits:korektorstvi}} {{page>teaching:bits:ads_zapoctaky}} [[https://docs.google.com/spreadsheets/d/e/2PACX-1vSmEeSqpMdFxnrwkSjJOtJCDqS-7p06wg3ctzHx8sAtkAtb5nvF_CYVMLv1RujELGZSQghdCKdH-Yc2/pubhtml?gid=0&single=true|Tabulka]] {{url>https://docs.google.com/spreadsheets/d/e/2PACX-1vSmEeSqpMdFxnrwkSjJOtJCDqS-7p06wg3ctzHx8sAtkAtb5nvF_CYVMLv1RujELGZSQghdCKdH-Yc2/pubhtml?gid=0&single=true&widget=true&headers=false"}}