Rozdíly

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

--- teaching:ads11920_cviceni [2020/03/06 15:40] – dalsi varka du Martin Koutecky
+++ teaching:ads11920_cviceni [2020/09/04 11:51] (aktuální) – [Požadavky na zápočet] 120 -> 100 Martin Koutecky
@@ Řádek 1: / Řádek 1: @@
-č====== Cvičení z ADS1 2019/20 ======
+====== Cvičení z ADS1 2019/20 ======
 Na pravé straně této stránky vizte obsah. Silně doporučuji pečlivě vše pročíst.
@@ Řádek 9: / Řádek 9: @@
   * {{ :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 14: / Řá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 90: / Řádek 99: @@
 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.