Rozdíly

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

--- teaching:bits:ads_zapoctaky [2019/09/24 13:23] – vytvořeno Martin Koutecky
+++ teaching:bits:ads_zapoctaky [2021/05/11 12:43] (aktuální) – Martin Koutecky
@@ Řádek 1: / Řádek 1: @@
+==== Jak zápočťáky fungují ====
+Zápočtová práce může mít podobu:
+  - programu implementující nějaký algoritmus z přednášky,
+  - teoretického rozboru algoritmu, který vás zaujme.
+V prvním případě jde o implementaci nějaké varianty datové struktury či algoritmu z přednášky. Jazyk je omezen jen schopnostmi cvičícího (tedy [v pořadí preferencí] Python, Lua, Java, C#, **hezké** C, Pascal, Haskell, Lisp, Prolog,; na další se případně zeptejte), implementace musí být funkční a obsahovat krátký popis (co a jak je implementováno) a testovací data či testovací kód (knihovna tedy nemusí řešit načítání dat ze souboru a pod.). Za tento druh práce budu udělovat max. 30b, pokud se bude jednat o něco velmi jednoduchého, bodů bude méně. Zeptejte se předem, kolik lze za dané téma očekávat nejvýše bodů.
+V druhém případě, tedy zejména pokud bude algoritmus či datová struktura složitější, bude práce jen teoretická, tzn. očekávám důkaz správnosti, rozbor složitosti a pseudokód. Za tento druh práce můžete očekávat do 40b, to zejména v případě, kdy si vyberete nějaký akademický článek a převyprávíte ho do mně (nezasvěcenému) srozumitelné podoby. Opět platí, že půjde-li o něco velmi jednoduchého, bodů bude méně. Zeptejte se předem, kolik lze za dané téma očekávat nejvýše bodů.
+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. **[[https://github.com/petrmanek/TreeDemo/|Řešení Petra Mánka.]]**
+  * <del>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. **[[https://github.com/petrmanek/TreeDemo/|Řešení Petra Mánka.]]** **[[https://github.com/Muph0/rb-24-tree-correspondence|Řešení Honzy Kytky.]]**</del>
+    * Nedávno se objevil článek [[https://arxiv.org/abs/2004.04344|A Pedagogically Sound yet Efficient Deletion algorithm for Red-Black Trees: The Parity-Seeking Delete Algorithm]], který tvrdí, že popisuje variantu RB stromů, která je k výuce vhodnější a v praxi efektivnější, než LLRB. Naimplementujte je a popište jejich funkci tak, aby to bylo srozumitelné i spolužákům.
   * [[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]])**
@@ Řádek 7: / Řádek 20: @@
     * 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.)
-  * <del>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.</del> **(Zamluveno)**
   * 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 kterýkoliv exponenciální algoritmus z [[https://jeffe.cs.illinois.edu/teaching/algorithms/notes/B-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.)
+  * Implementujte algoritmus, který najde [[https://en.wikipedia.org/wiki/Modular_decomposition|modulární rozklad]] grafu v lineárním čase dle článku [[https://linkinghub.elsevier.com/retrieve/pii/S0166218X04002458|Linear-time modular decomposition of directed graphs]]. **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.)
@@ Řádek 18: / Řádek 30: @@
   * [[https://github.com/tomaspavlin/disjkstrasalgorithm|Úkoly ze cvika na Dijkstrův algoritmus.]] Vypracoval Tomáš Pavlín.
   * Implementovat shellsort 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ě. **(Hotovo, [[https://github.com/Salmelu/Sorts|github]])**
+==== Články k rozebrání ====
+Obecně je dobrým zdrojem konference [[https://simplicityinalgorithms.com/|SOSA]], která se soustřeďuje na *hezké* (jednoduché) algoritmy, ačkoliv i tak mohou být přístupné spíš magisterským studentům.
+  * nastudovat a popsat Hashlife: [[https://en.wikipedia.org/wiki/Hashlife|wiki]], [[http://www.conwaylife.com/wiki/HashLife|lifewiki]], [[https://jennyhasahat.github.io/hashlife.html|existující dobrý popis]].
+  * Hledání modulárního rozkladu grafu v lineárním čase, [[https://linkinghub.elsevier.com/retrieve/pii/S0166218X04002458|Linear-time modular decomposition of directed graphs]]