Rozdíly

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

--- teaching:ads11314 [2014/04/04 20:29] – Martin Koutecky
+++ teaching:ads11314 [2019/09/24 11:25] (aktuální) – Martin Koutecky
@@ Řádek 17: / Řádek 17: @@
   - {{:teaching:ads1_05-cv.pdf|Příklady z 5. cvičení}}
   - {{:teaching:ads1_06-cv.pdf|Příklady z 6. cvičení}}
+  - DFS a BFS -- opakování, vertex cover na stromech, průměr stromu, duch v bludišti, bludiště se dvěma roboty ovládanými jedním ovladačem.
 ===== Domácí úkoly =====
@@ Řádek 93: / Řádek 94: @@
 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í tytpo podmínky popisovalo nejkratší vzdálenosti a cesty.
+**Úloha housenka (9b, plný počet do 24. 4. 14:00)**
+Najděte v zadaném stromě housenku na co nejvíce vrcholech. <i>Housenka</i> 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 24. 4.)**
+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 polosouvislost (9b, plný počet do 15. 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 15. 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 abeceda (9b, plný počet do 22. 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 negative-floyd (8b, plný počet do 22. 5.)**
+Co udělá F-W algoritmus na grafu se zápornými vahami, ale bez záporných cyklů?
+A co udělá F-W na grafu se záporným cyklem? Svá tvrzení dokažte.
+Pro bonus vysvětlete (potenciálně chybný) výsledek algoritmu a význam získaných hodnot
+(tedy zda výsledná čísla přeci jen něco popisují).
+**Úloha cheating (7b, plný počet do 22. 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 (10b, plný počet do 22. 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.
 ===== Požadavky na zápočet =====
@@ Řádek 110: / Řádek 164: @@
 Termín na domluvení programu je do 15. června, termín odevzdání hotové verze pak konec června. Ostatní domácí úlohy mají až na výjimky termín do konce května.
-==== Nápady na zápočťáky ====
-  - Implementovat R-B-stromy a (2,4)-stromy a graficky ukazovat jejich [[https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_to_B-trees_of_order_4|korespondenci]]. Za prostou implementaci datové struktury dám **30b**, pokud vytvoříte interaktivní aplikaci, ve které bude uživatel zadávat operace na stromech a aplikace bude zobrazovat změny datových struktur a jejich korespondenci, dám **40b**. Zcela ideální platformou by byl (kvůli přístupnosti) Javascript nebo cokoliv webového; přijmu to ale i v jakémkoliv jiném (výše zmíněném) jazyce. //Úlohu předrezervuji Petru Mánkovi, protože vychází z jeho nápadu; pokud o ni nebude stát, může ji mít kdokoliv.//
-  - [[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:
-    - 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ě.
-    - 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.
-  - **ZAMLUVENO** [[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.
-  - Implementujte algoritmus, který rozhodne, jakou má graf //modulární šířku//. Tohle je poměrně čerstvá oblast výzkumu, na Internetu toho o ní moc nenajdete, nejradši to vysvětlím osobně :) **Pokud úkol splníte, dám za něj 45b** (+5b za prezentaci); i pokud se vám to nepodaří úplně, nebude bodová odměna malá. (Potenciálně je to taky dobrý základ pro ročníkový projekt nebo bakalářskou práci do příštích let.)
-==== Články k rozebrání ====
+{{page>teaching:bits:ads_zapoctaky}}
-[Časem budu doplňovat.]
 ===== Body za úkoly =====