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.