MK's wiki

Uživatelské nástroje

Nástroje pro tento web

Historie: • ads11516
teaching:ads11516

Rozdíly

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

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze		Předchozí verze
teaching:ads11516 [2016/04/25 16:15] – Dalsi du + dalsi cv Martin Kouteckyteaching: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í, tj. uspořádání, kde prvky se stejným klíčem budou po setřídění ve stejném pořadí jako před tříděním; zmínka o třídění stabilním tříděním pozpátku - odzadu podle poslední cifry)     * 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í, tj. uspořádání, kde prvky se stejným klíčem budou po setřídění ve stejném pořadí jako před tříděním; zmínka o třídění stabilním tříděním pozpátku - odzadu podle poslední cifry)
     * hashování (základní popis, co říká (bez důkazu) ([[http://kam.mff.cuni.cz/~ludek/NTIN060texty/hash.pdf|zde]])      * hashování (základní popis, co říká (bez důkazu) ([[http://kam.mff.cuni.cz/~ludek/NTIN060texty/hash.pdf|zde]]) 
-    * 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ě, ale musíme se koukat i na prvky napravo od místa, kam nás poslala hash funkce, dokud nenarazíme na mezeru nebo hledané číslo --> implementace se hodí jen pro ukládání a vyhledávání - pokud v ní začneme mazat, nesmíme místo mazaného prvku nechat volné políčko, protože by se mohlo stát, že nějaké prvky už při hledání nikdy nenalezneme) +    * 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ě, ale musíme se koukat i na prvky napravo od místa, kam nás poslala hash funkce, dokud nenarazíme na mezeru nebo hledané číslo --> implementace se hodí jen pro ukládání a vyhledávání - pokud v ní začneme mazat, nesmíme místo mazaného prvku nechat volné políčko, protože by se mohlo stát, že nějaké prvky už při hledání nikdy nenalezneme) 
 +   * 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|,|B|))$. 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|,|B|))$.
Řá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 //polosouvislý//, když pro každé dva vrcholy $u$ a $v$ platí, že existuje orientovaná cesta z $u$ do $v$ nebo orientovaná cesta z $v$ do $u$. Toto je silnější vlastnost, než slabá souvislost grafu, ale slabší vlastnost, než silná souvislost grafu. Jak v čase $O(m+n)$ zjistit, zda je $G$ polosouvislý? Řekněme, že orientovaný graf $G$ je //polosouvislý//, když pro každé dva vrcholy $u$ a $v$ platí, že existuje orientovaná cesta z $u$ do $v$ nebo orientovaná cesta z $v$ do $u$. Toto je silnější vlastnost, než slabá souvislost grafu, ale slabší vlastnost, než silná souvislost grafu. Jak v čase $O(m+n)$ zjistit, zda je $G$ polosouvislý?
  
-**Ú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>teaching:bits:ads_zapoctaky}}
  
-==== Nápady na zápočťáky ==== 
  
-  - [[https://en.wikipedia.org/wiki/Shellsort|Shellsort]] je velice zajímavý třídící algoritmus. Je v jistém smyslu zkřížením bubblesortu a insertsortu, ale může mít lepší časovou složitost. Možností, co byste s ním mohli dělat, je několik: 
-    - <del>Implementovat ho pro několik variant parametru mezery ([[https://en.wikipedia.org/wiki/Shellsort#Gap_sequences|Gap sequences]]) a porovnat jeho chování pro tyto parametry experimentálně.</del> **(Hotovo, [[https://github.com/Salmelu/Sorts|github]])** 
-    - Nejlepší posloupnost mezer v průměrném případě je prý 1, 4, 10, 23, ... (vizte [[https://en.wikipedia.org/wiki/Shellsort#Gap_sequences|poslední odstavec této podkapitoly]]); toto bylo zjištěno experimentálně. Ověřte správnost těchto výsledků pro co největší čísla (aktuálně je známo jen prvních osm členů této posloupnosti, kdybyste přišli na devátý, dostanete celý zápočet ;). Pokud byste si vybrali toto témai, jistě by nebylo těžké vám zařídit přístup k výpočetní kapacitě fakulty.) 
-    - Co kdyby se měl Shellsort přednášet? Sestavte co nejzajímavěji materiál k výkladu na hodinu a půl (jako přednáška z ADS), kde se ukáže princip fungování tohoto sortu a pak dokáže několik (jednodušších) odhadů na časovou složitost pro různé hodnoty parametru mezery. Nejvhodnějším médiem by byl [[http://ipython.org/notebook.html|IPython notebook]] (rád předvedu, jak funguje), protože do něj lze psát matematickou notaci i kód a interaktivně vše zkoušet. 
-  - [[https://en.wikipedia.org/wiki/Splay_tree|Splay tree]] je velice zajímavá datová struktura. Jedná se o binární vyhledávací strom, který se přizpůsobuje dotazům, které na něj přichází -- pokud přichází mnoho dotazů na tytéž prvky, strom je vynese blízko ke kořeni, aby se k nim dalo přistupovat rychle. Samozřejmě má i svoje nevýhody. Implementujte ho a napište k němu několik generátorů posloupnosti operací, které budou demonstrovat, v čem je Splay strom lepší než jiné stromy (AVL, R-B, ...) a kde naopak selhává. (Generátorem posloupnosti operací myslím nějakou funkci, které řeknu, kolik operací INSERT/FIND/DELETE chci na stromu udělat [třeba za účelem testování] a on mi je vygeneruje.) 
-  - Implementujte [[https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm|Tarjanův algoritmus na hledání silně souvislých komponent]] v orientovaném grafu. 
-  - Implementujte [[https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm|Rabinův-Karpův algoritmus]] na vyhledávání podřetězce v řetězci pomocí hashování. 
-  - Implementujte kterýkoliv exponenciální algoritmus z [[http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/04-fastexpo.pdf|přednáškových poznámek Jeffa Ericksona]] a pochopte důkaz správnosti a časové/prostorové složitosti dostatečně, abyste mi ho uměli vysvětlit na tabuli. 
  
  
teaching/ads11516.1461593739.txt.gz · Poslední úprava: 2016/04/25 16:15 autor: Martin Koutecky