teaching:ads11516
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:ads11516 [2016/04/25 16:15] – Dalsi du + dalsi cv Martin Koutecky | teaching:ads11516 [2020/04/01 15:50] (aktuální) – stará verze byla obnovena (2019/09/24 11:18) Martin Koutecky | ||
---|---|---|---|
Řádek 34: | Řádek 34: | ||
* pokračování radix sort (změna oproti minulé přednášce - závěrečný for cyklus pozpátku, abychom měli stabilní uspořádání, | * pokračování radix sort (změna oproti minulé přednášce - závěrečný for cyklus pozpátku, abychom měli stabilní uspořádání, | ||
* hashování (základní popis, co říká (bez důkazu) ([[http:// | * hashování (základní popis, co říká (bez důkazu) ([[http:// | ||
- | * implementace hashování (otevřené hashování = hashovací pole minimálně 2x větší než počet prvků, pokud by více prvků hashovací funkce namířila do jednoho políčka v hashovacícm poli, tak ho uložíme do nejblížšího volného políčka napravo, v hashovací tabulce vyhledáváme standardně, | + | * implementace hashování (otevřené hashování = hashovací pole minimálně 2x větší než počet prvků, pokud by více prvků hashovací funkce namířila do jednoho políčka v hashovacícm poli, tak ho uložíme do nejblížšího volného políčka napravo, v hashovací tabulce vyhledáváme standardně, |
+ | * 10. přednáška | ||
+ | * univerzální hashování (kde počet prvku universa je prvočíslo) | ||
+ | * perfektní hashování (snaha vyhnout se kolizím -- máme k dispozici více hashovacích funkcí a vybíráme si tu, která danou podmnožinu množiny universa zobrazí bez kolizí) | ||
Řádek 57: | Řádek 60: | ||
//Hint:// Hledejte rekurzivně $k$-tý nejmenší ze dvou podposloupností. | //Hint:// Hledejte rekurzivně $k$-tý nejmenší ze dvou podposloupností. | ||
- | **Úloha rovnováha (8b, plný počet do 28. 3.)** | + | **Úloha rovnováha (9b, plný počet do 28. 3.)** |
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). | 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 (8b, plný počet do 28. 3.)** | + | **Úloha merge (10b, plný počet do 28. 3.)** |
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|, | 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|, | ||
Řádek 127: | Řádek 130: | ||
- | /* | + | |
- | **Úloha polosouvislost (9b, plný počet do 15. 5.)** | + | **Úloha polosouvislost (9b, plný počet do 30. 5.)** |
Řekněme, že orientovaný graf $G$ je // | Řekněme, že orientovaný graf $G$ je // | ||
- | **Úloha holubi (9b, plný počet do 15. 5.)** | + | **Úloha holubi (9b, plný počet do 30. 5.)** |
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. | 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. | 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 30. 5.)** | ||
+ | |||
+ | 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 listy-kostry (8b, plný počet do 30. 5.)** | ||
+ | |||
+ | 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. | ||
+ | |||
Řádek 176: | Řádek 197: | ||
+ | {{page> | ||
- | ==== Nápady na zápočťáky ==== | ||
- | - [[https:// | ||
- | - < | ||
- | - Nejlepší posloupnost mezer v průměrném případě je prý 1, 4, 10, 23, ... (vizte [[https:// | ||
- | - Co kdyby se měl Shellsort přednášet? | ||
- | - [[https:// | ||
- | - Implementujte [[https:// | ||
- | - Implementujte [[https:// | ||
- | - Implementujte kterýkoliv exponenciální algoritmus z [[http:// | ||
teaching/ads11516.txt · Poslední úprava: 2020/04/01 15:50 autor: Martin Koutecky