Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
teaching:ads11516 [2016/05/14 06:41] – [Domácí úkoly] Martin Koutecky | teaching:ads11516 [2020/04/01 15:50] (aktuální) – stará verze byla obnovena (2019/09/24 11:18) Martin Koutecky |
---|
| |
| |
| {{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. | |
| |
| |