| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:ads11314 [2014/05/29 23:08] – zápočťáky Martin Koutecky | teaching:ads11314 [2019/09/24 13:25] (aktuální) – Martin Koutecky |
|---|
| 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. | 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.]]** | {{page>teaching:bits:ads_zapoctaky}} |
| - [[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. | |
| - **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.) | |
| - <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 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.) | |
| - [[https://github.com/tomaspavlin/disjkstrasalgorithm|Úkoly ze cvika na Dijkstrův algoritmus.]] Vypracoval Tomáš Pavlín. | |
| |
| ==== Články k rozebrání ==== | |
| |
| |
| [Časem budu doplňovat.] | |
| |
| ===== Body za úkoly ===== | ===== Body za úkoly ===== |
