Rozdíly

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

--- teaching:ads11920_cviceni [2020/04/22 13:40] – 10-cv Martin Koutecky
+++ teaching:ads11920_cviceni [2020/09/04 11:51] (aktuální) – [Požadavky na zápočet] 120 -> 100 Martin Koutecky
@@ Řádek 16: / Řádek 16: @@
   * {{ :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 21: / Řá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 134: / Řádek 136: @@
+**Ú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.