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. Pokud je to relevantní, srovnejte s jinou existující metodou. 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 téma z některých probíraných oblastí, a to: geometrické algoritmy, zábavné algoritmy, shlukování, randomizované algoritmy, in-place a in-situ algoritmy. Konkrétní úkol si vyberte sami, naformulujte k němu zadání a nechte ho schválit přednášející.

Původnost algoritmu a implementace: Je povoleno využít různé existující algoritmy i jejich implementace, řešení by ale mělo obsahovat nějakou část vytvořenou vámi. 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 ale hodnoceno výše než převzaté. Nepřiznané nepůvodní řešení bude hodnoceno 0 body.

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ů.

Ú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.