MK's wiki

Toto je starší verze dokumentu!

Nápady na zápočťáky

Implementovat R-B-stromy a (2,4)-stromy a graficky ukazovat jejich 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. Řešení Petra Mánka.
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 (Gap sequences) a porovnat jeho chování pro tyto parametry experimentálně.~~ (Hotovo, github)
- Nejlepší posloupnost mezer v průměrném případě je prý 1, 4, 10, 23, … (vizte 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 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.
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 Tarjanův algoritmus na hledání silně souvislých komponent v orientovaném grafu.~~ (Zamluveno)
Implementujte 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 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.)

Hotové

Samuel Slavkovský napsal porovnávač třídících algoritmů (rar s .net kódem), který doporučuji ke shlédnutí :)
Úkoly ze cvika na Dijkstrův algoritmus. Vypracoval Tomáš Pavlín.
Implementovat shellsort pro několik variant parametru mezery (Gap sequences) a porovnat jeho chování pro tyto parametry experimentálně. (Hotovo, github)