Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:ads11920_cviceni [2020/02/20 20:21] – Martin Koutecky
+++ teaching:ads11920_cviceni [2020/09/04 11:51] (aktuální) – [Požadavky na zápočet] 120 -> 100 Martin Koutecky
@@ Řádek 7: / Řádek 7: @@
   * {{ :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}}
@@ Řádek 12: / Řádek 23: @@
 ===== Požadavky na zápočet =====
-Zápočet vám udělím, získáte-li celkově 120 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.
+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:
@@ Řádek 39: / Řádek 50: @@
 //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.