Rozdíly

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

--- teaching:ads11516 [2016/03/15 16:52] – 2-du Martin Koutecky
+++ teaching:ads11516 [2020/04/01 15:50] (aktuální) – stará verze byla obnovena (2019/09/24 11:18) Martin Koutecky
@@ Řádek 9: / Řádek 9: @@
 ===== Co se dělalo na cvičení =====
- * {{:teaching:ads1_2016:ads1_01-cv.pdf|1. cvičení}}
+  * {{:teaching:ads1_2016:ads1_01-cv.pdf|1. cvičení}}
+  * {{:teaching:ads1_2016:ads1_02-cv.pdf|4. cvičení}}
+    * [[http://people.ksp.sk/~kuko/bak/index.html|Applet na hraní si s BVS + hezký souhrn/srovnání BVS a dalších datových struktur.]]
+  * {{:teaching:ads1_2016:ads1_03-cv.pdf|5. cvičení}}
+  * {{:teaching:ads1_2016:ads1_04-cv.pdf|6. cvičení}}
+  * {{:teaching:ads1_2016:ads1_05-cv.pdf|7. cvičení}}
+  * {{:teaching:ads1_2016:ads1_06-cv.pdf|8. cvičení}}
+  * {{:teaching:ads1_2016:ads1_07-cv.pdf|9. cvičení}}
+===== Co se (údajně) dělalo na přednášce =====
+  * 6. přednáška
+    * quicksort je velmi podobný jako vkládání prvků do BVS
+    * B-stromy (jak vypadají, insert, delete)
+    * úvod do třídících algoritmů (časová složitost bubble sortu, merge sortu a quicksortu)
+  * 7. přednáška
+    * znovu B-stromy
+    * halda (k čemu je + operace hledání min, sjednocení dvou hald, insert, delete)
+    * opět třídění (jak průměrně funguje bubble sort, quick sort, merge sort; důkaz toho, že když máme jakýkoli algoritmus, který třídí na základě porovnávání prvků, tak musí provést alespoň $O(n \log n)$ porovnání --> důsledek: nemůžeme vymyslet třídící algoritmus, kterému stačí méně než $\log_2 n$ operací pro jeden prvek)
+  * 8. přednáška
+    * detailně důkaz dolního odhadu třídích algoritmů ([[http://kam.mff.cuni.cz/~ludek/NTIN060texty/AverageLowerBoundSorting.pdf|zde]])
+    * radix sort (popis a ukázka toho, že pokud máme nějakou přiměřenou množinu malých čísel, tak algoritmus tohoto sortu beží v $O(n)$)
+  * 9. přednáška
+    * 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]])
+    * 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í)
 ===== Domácí úkoly =====
@@ Řádek 30: / Řádek 60: @@
 //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).
-**Ú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|))$.
+**Úloha datovka-2 (8b, plný počet do 18. 4.)**
+Elektrikář si chce udržovat seznam klientů podle jejich identifikačních
+čísel (ID) a s údajem, zda se jedná o muže či ženu. Navrhněte datovku,
+která bude umět následující operace v $O(\log n)$:
+  * ''INSERT(K,C)'' --- vloží nového klient $C$ s ID=$K$, označí ho jako ženu
+  * ''UPDATE(K)'' --- klienta s ID $K$ přeznačí na muže
+  * ''FINDDIFF(K)'' --- spočítej rozdíl počtu mužů a žen mezi klienty s ID $\leq K$.
+**Úloha min-strom (8b, plný počet do 25. 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 25. 4.)**
+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á, lze zda má majoritu zjistit a zároveň ji najít mnohem rychleji, a to v čase $O(\log n)$. Popište takový algoritmus.
+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 housenka (9b, plný počet do 2. 5.)**
+Najděte v zadaném stromě housenku na co nejvíce vrcholech. //Housenka// je podgraf, který se skládá z cesty
+na jejímž každém vrcholu jsou až čtyři listy (nožičky), ale můžou tam být i vrcholy bez nožiček. Není to totéž,
+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 kůň (8b, plný počet do 2. 5.)**
+Na jedné šachovnici $N\times N$ žil byl kulhavý kůň. To je je šachová figurka, která v sudém tahu táhne
+jako jezdec, v lichém jako pěšec (o 1 dopředu, vždy stejným směrem). Jak pro zadaná dvě políčka najít nejkratší cestu kulhavým koněm?
+**Úloha zakázka (10b, plný počet do 11. 5.)**
+Olga Opatrná najala Láďu Lenocha, aby ji pro daný neorientovaný graf $G=(V,E)$, vrchol $s\in V$ a //nezáporné// celočíselné váhy hran $w(u,v)$ (kde $w(u,v)=w(v,u)$) spočítal nejkratší cesty z vrcholu $s$ do všech ostatních vrcholů. Konkrétně má Láďa spočíst dvě funkce: $d(v)$ má být délka nejkratší cesty z $s$ do $v$ (nebo $\infty$, pokud taková není), a $\pi(v)$ má být předposlední vrchol na nějaké nejkratší cestě z $s$ do $v$ (nebo $\mathrm{NIL}$, pokud taková není).
+Olga ale moc nevěří Láďově pečlivosti, a tak si chce výsledky ověřit, což se jí zdá jednodušší, než si je spočíst sama. Konkrétně ověří následující podmínky:
+  - $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),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ě: najděte takový graf, funkci $w$, vrchol $s$ a funkce $d$ a $\pi$, nebo ještě lépe popište takové případy obecněji. Za druhé upravte či doplňte podmínky tak, aby už každé řešení splňující tyto podmínky popisovalo nejkratší vzdálenosti a cesty.
+**Úloha abeceda (9b, plný počet do 11. 5.)**
+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 "a-z", otázkou je pak pořadí znaků "a-z"
+v hledané abecedě. Zkuste najít algoritmus, který to zvládne v lineárním čase s velikostí vstupu. Můžete
+předpokládat, že se každé písmeno mezi nápisy vyskytne.
+**Ú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ý?
+**Ú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.
+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 75: / Řá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.