Na pravé straně této stránky vizte obsah. Silně doporučuji pečlivě vše pročíst.
Zadání úloh na cvičení i domácích úkolů bude v zde na webu. Pro komunikaci kolem DÚ budu používat systém OWL. Pokud vám do něj nepřišel ode mě kód, napište mi email.
Při emailové komunikaci se mnou prosím vždy uveďte do předmětu text [ADS1].
Zápočet vám udělím, získáte-li celkově 100 bodů. Váš aktuální počet bodů uvidíte v OWLu.
Body lze získávat následujícími způsoby:
Řešení úkolů: celkově zadám úlohy za cca 100 bodů. Každý úkol má termín, typicky dva týdny, pak klesnou body na polovinu. Úlohy budou rozděleny do skupin označených písmeny a z každé skupiny chci, abyste vypracovali aspoň jeden úkol. Více o
vypracovávání domácích úloh…
Opravování úkolů: pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, máte možnost získat
navíc až pětinásobek bodů tím, že se stanete
korektorem pro tuto úlohu. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr. Více o
korektorství…
Zápočťák: body můžete získat taky za zápočtový projekt, který může být praktický (implementace algoritmu) či teoretický (popis a analýza nějakého složitějšího algoritmu). Více o
zápočťácích…
Korektorství
Pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, po odevzdání úlohy mi napište email s předmětem [DM/ADS1/KG1][korektor] název-úlohy (první část podle předmětu, vyberte samozřejmě jen jedno). Já vaše řešení zhodnotím přednostně a pokud bude v pořádku, za opravení řešení vašich kolegů navíc až pětinásobek bodů. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr.
Technicky to bude fungovat tak, že korektorovi zpřístupním danou úlohu v OWL, kde on opravuje a uděluje body, ale já vše taky vidím a můžu případně korigovat :) Korektor si tedy řešení pečlivě přečte a zhodnotí ho. Je toto řešení korektní? Pokud ne, kde udělal autor chybu? Čemu nerozumí a jak mu můžu pomoci – jakou otázkou ho nakopnu správným směrem? Dále – je toto řešení přehledné a srozumitelné? Prospělo by řešení rozdělit do více/méně odstavců? Zavést nějaké značení? Atd. Na základě tohoto zhodnocení pak korektor navrhne bodové ohodnocení. Například:
Řešení je v zásadě správné, ale doporučil bych místo značení A, B, C, … používat indexované značení A_1, A_2, A_3, … Jinak byl důkaz poměrně přehledný.
2b
Já zhodnotím řešení úlohy a korekturu, případně se k oběma vyjádřím a přehodnotím body (ale to se často neděje).
Povinností korektora je opravit všechny přidělené úlohy do týdne od chvíle, kdy se v OWLu objeví.
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 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. Řešení Honzy Kytky.
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 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ý najde
modulární rozklad grafu v lineárním čase dle článku
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.)
Hotové
-
-
Implementovat shellsort pro několik variant parametru mezery (
Gap sequences) a porovnat jeho chování pro tyto parametry experimentálně.
(Hotovo, github)
Články k rozebrání
Obecně je dobrým zdrojem konference SOSA, která se soustřeďuje na *hezké* (jednoduché) algoritmy, ačkoliv i tak mohou být přístupné spíš magisterským studentům.