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í verzeNásledující verzeObě strany příští revize | ||
teaching:ads11920_cviceni [2020/02/20 20:17] – tabulka Martin Koutecky | teaching:ads11920_cviceni [2020/04/15 13:54] – 9-cv Martin Koutecky | ||
---|---|---|---|
Řádek 7: | Řádek 7: | ||
* {{ : | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | * {{ : | ||
{{page> | {{page> | ||
Řádek 12: | Řádek 20: | ||
===== 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: | ||
- | * **Řešení úkolů:** celkově zadám úlohy za cca 150 bodů. Každý úkol má termín, typicky dva týdny, pak klesnou body na polovinu. Více o [[# | + | * **Řešení úkolů:** celkově zadám úlohy za cca 180 bodů. Každý úkol má termín, typicky dva týdny, pak klesnou body na polovinu. Úlohy budou rozděleny do skupin označených písmeny a z každé skupiny chci, abyste vypracovali aspoň jeden úkol. Více o [[# |
* **Opravování úkolů:** pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, | * **Opravování úkolů:** pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, | ||
* **Malé písemky:** na začátku každého cvičení budete psát krátkou (~10 minut) písemku zejména na osvěžení definic, pojmů a algoritmů z přednášky (a možná na jejich velmi jednoduché procvičení). Zápočet je možné získat i bez písemek, můžete je brát spíš jako usnadnění/ | * **Malé písemky:** na začátku každého cvičení budete psát krátkou (~10 minut) písemku zejména na osvěžení definic, pojmů a algoritmů z přednášky (a možná na jejich velmi jednoduché procvičení). Zápočet je možné získat i bez písemek, můžete je brát spíš jako usnadnění/ | ||
Řádek 24: | Řádek 32: | ||
====== Domácí úkoly ====== | ====== Domácí úkoly ====== | ||
- | **Úloha RAM (7b, plný počet do 4. 3.)** | + | **Úloha RAM (7b, plný počet do 4. 3.)** //[A]// |
Naprogramujte na RAMu nějaký třídicí algoritmus se složitostí O(N log N). Nezapomeňte popsat uložení dat v paměti. | Naprogramujte na RAMu nějaký třídicí algoritmus se složitostí O(N log N). Nezapomeňte popsat uložení dat v paměti. | ||
- | **Úloha unikum (6b, plný počet do 4. 3.)** | + | **Úloha unikum (6b, plný počet do 4. 3.)** //[A]// |
Najděte v posloupnosti nejdelší úsek, v němž se žádná hodnota neopakuje. | Najděte v posloupnosti nejdelší úsek, v němž se žádná hodnota neopakuje. | ||
- | **Úloha medián (8b, plný počet do 4. 3.)** | + | **Úloha medián (8b, plný počet do 4. 3.)** //[A]// |
Jak v lepším než lineárním čase najít medián sjednocení dvou setříděných posloupností? | Jak v lepším než lineárním čase najít medián sjednocení dvou setříděných posloupností? | ||
Řádek 39: | Řádek 47: | ||
//Hint:// Hledejte rekurzivně $k$-tý nejmenší ze dvou podposloupností. | //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. // | ||
+ | na jejímž každém vrcholu jsou až čtyři listy (nožičky), | ||
+ | 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 " | ||
+ | v hledané abecedě. Zkuste najít algoritmus, který to zvládne v lineárním čase s velikostí vstupu. Můžete | ||
+ | předpokládat, | ||
+ | |||
+ | **Úloha polosouvislost (9b, plný počet do 25. 3.)** //[B]// | ||
+ | |||
+ | Řekněme, že orientovaný graf $G$ je // | ||
+ | |||
+ | **Ú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 // | ||
+ | |||
+ | Olga ale moc nevěří Láďově pečlivosti, | ||
+ | |||
+ | - $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), | ||
+ | - $\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ě: | ||
+ | |||
+ | **Ú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ý. | ||
+ | |||
+ | |||
+ | |||
teaching/ads11920_cviceni.txt · Poslední úprava: 2020/09/04 11:51 autor: Martin Koutecky