Semestrální práce č. 2

Prostudujte pro zvolený problém existující metody řešení. Vyberte jednu z nich nebo navrhněte vlastní, implementujte a ověřte na experimentech. Postup a výsledky popište ve zprávě.

Volba problému a metody: Můžete buď použít článek zpracovaný v práci 1 anebo si vybrat kterýkoliv z problémů popisovaných v kapitolách 13-18 knihy [1] s výjimkou podkapitol 13.3, 13.6, 13.10, 14.1 až 14.5, 15.3, 15.4, z kapitoly 18 nejsou povolena témata týkající se textů a znakových řetězců, ale témata týkající se množin ano. Důvodem těchto omezení je nasměrovat vás přednostně k tématům, která se neprobírají ani na PRO ani na PT.

Formát zprávy: Jistým vodítkem by vám měla být vaše první práce. Na začátku bude Zadání, kde napíšete, jak přesně je definován řešený problém. Pak bude kapitola Existující metody, kde stručně a s odkazy na literaturu popíšete, jaké existují metody řešící daný problém, jejich výhody a nevýhody. V další kapitole Navržené řešení nebo Zvolené řešení (název podle toho, jestli jste vybrali hotový algoritmus nebo vymysleli řešení sami) popíšete algoritmus řešení daného problému, napřed stručně slovně, pak podrobněji pseudokódem. Nepřetěžujte text implementačními detaily, o těch pište jen v případě, že chcete upozornit na nějakou svoji „vychytávku“ anebo zdůraznit, v čem je vaše implementace originální. Následuje kapitola Experimenty a výsledky, kde napíšete, v čem jste programovali, případně, jaké existující knihovny jste použili, jaké výsledky jste dostali (výsledky nejlépe v tabulce, grafu, obrazkem..) a jak tyto výsledky a celou metodu hodnotíte. Poslední kapitolou bude Závěr, kde stručně shrnete hlavní klady a zápory. Na konci bude ještě Literatura se seznamem citovaných pramenů.

K [1] jsou k mání také implementace a k úlohám lze samozřejmě najít i jiné zdroje kódu. Pokud něco odněkud převezmete, pak byste jednak měli zdroj citovat a jednak přesně uvést, v čem se vaše řešení liší od vašeho zdroje. Původní řešení bude hodnoceno podstatně výše než převzaté. Nepřiznané nepůvodní řešení bude hodnoceno 0 body.

Úlohu odevzdáváte cvičícímu formou, jakou vám řekne na cvičení. Pokud práce nebude požadované kvality (bodový zisk bude menší než polovina maxima bodů, tedy 7-8 bodů), bude vrácena k přepracování, a to nejvýše jednou. Předělaná práce získá tolik bodů, kolik si zaslouží, minus 5 bodů penalizace. Pokud nebude ani druhá verze lepší než první, práce získá 0 bodů. Při opožděném odevzdání se zpožděním do 48 hodin bude práce penalizována stržením 5 bodů z hodnocení, pozdější odevzdání je za 0 bodů.

Hodnocení: Celkově lze získat až 15 bodů plus až 5 bodů za případnou prezentaci na cvičení (prezentace jen na výzvu cvičící). Hodnotí se správnost, kvalita a původnost implementace, kvalita otestování i dokumentace.

Reference

[1] S. Skiena: The Algorithm Design Manual,  Spring-Verlag, New York Berlin Heidelberg, 1998 nebo 2008 
2.vydání lze najít např. na: http://mimoza.marmara.edu.tr/~msakalli/cse706_12/SkienaTheAlgorithmDesignManual.pdf