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/04/29 13:54] – 11-cv Martin Koutecky | teaching:ads11920_cviceni [2020/09/04 11:51] (aktuální) – [Požadavky na zápočet] 120 -> 100 Martin Koutecky | ||
---|---|---|---|
Řádek 17: | Řádek 17: | ||
* {{ : | * {{ : | ||
* {{ : | * {{ : | ||
+ | * {{ : | ||
{{page> | {{page> | ||
Řádek 22: | Řá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 135: | Řá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, | ||
+ | |||
+ | **Ú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.1588161274.txt.gz · Poslední úprava: 2020/04/29 13:54 autor: Martin Koutecky