teaching:ads11920_cviceni
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze | ||
teaching:ads11920_cviceni [2020/03/18 13:42] – 04-cv, 05-cv Martin Koutecky | teaching:ads11920_cviceni [2020/09/04 11:51] (aktuální) – [Požadavky na zápočet] 120 -> 100 Martin Koutecky | ||
---|---|---|---|
Řádek 11: | Řádek 11: | ||
* {{ : | * {{ : | ||
* {{ : | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
{{page> | {{page> | ||
Řádek 16: | Řádek 23: | ||
===== Požadavky na zápočet ===== | ===== Požadavky na zápočet ===== | ||
- | Zápočet vám udělím, získáte-li celkově | + | Zápočet vám udělím, získáte-li celkově |
Body lze získávat následujícími způsoby: | Body lze získávat následujícími způsoby: | ||
Řádek 92: | Řá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ě: | 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ě: | ||
+ | **Ú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|, | ||
+ | |||
+ | **Ú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 " | ||
+ | |||
+ | **Ú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á, | ||
+ | |||
+ | 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, | ||
+ | |||
+ | **Ú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? | ||
+ | |||
+ | |||
+ | **Ú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í, | ||
+ | počtem součinů čísel) ano. Vymyslete algoritmus, který stanoví, jak výraz uzávorkovat, | ||
+ | abychom složitost minimalizovali. | ||
+ | } | ||
+ | |||
+ | **Úloha triangul (9b)** //[E]// | ||
+ | |||
+ | // | ||
+ | neprotínajícími se úhlopříčkami na trojúhelníky. Nalezněte takovou triangulaci, | ||
+ | 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:// | ||
teaching/ads11920_cviceni.1584535350.txt.gz · Poslední úprava: 2020/03/18 13:42 autor: Martin Koutecky