Programátorské strategie (KIV/PRO)

Prof. Dr. Ing.Ivana Kolingerová

Okruhy:

1. Úvod do algoritmů – správnost a účinnost algoritmů, robustnost, analýza, hledání řešení neznámého problému, algoritmická složitost v praxi

2. Algoritmické strategie – hrubá síla, greedy, inkrementální algoritmy, rozděl a panuj, dynamické programování, backtracking

3. Randomizované algoritmy

4. Data stream algoritmy

5. In-place a in situ algoritmy

6. Kvantové výpočty

Okruhy mohou doznat ještě změny, pokud mě napadne nějaké zvláště vzrušující téma, o kterém byste rozhodně měli něco slyšet. Pokud máte sami nějaký návrh zajímavého tématu, dejte vědět, když to bude v mých silách a v rámci koncepce předmětu, vyhovím.

Literatura:

· základní:

• S. Skiena: The Algorithm Design Manual, Spring-Verlag, New York Berlin Heidelberg, 1998 – je dostupná na Webu přes domácí stránky autora nebo v knihovně ZČU k prezenčnímu studiu
• matriály od vyučující, podklady přednášek, problémy z ACM programátorských soutěží apod.
• doplňková: jakákoliv kniha zaměřená na algoritmické strategie, algoritmizaci, návrh řešení problémů, např.:
• J.Hromkovič: Algorithms for Hard Problems, Introduction to Combinatorial Optimization, Randomization, Approximation and Heuristics, Springer Verlag Berlin Heidelberg New York, 2000
• Z.Michalewicz, D.B. Fogel: How to Solve It: Modern Heuristics, Springer-Verlag, Berlin Heidelberg New York, 2000
• S. Dvořák: Dekompozice a rekurzivní algoritmy, Grada, 1992
• G. Gonnet, R. Baeza – Yates: Handbook of Algorithms and Data Structures, Addison-Wesley, Wokingham, UK, 1991 (2^nd edition)
• G. Rawlins: Compared to What ? Computer Science Press, New York, 1992
• B. Moret, H. Shapiro: Algorithm from P to NP: Design and Efficiency, Benjamin/Cummings, Redwood City, US, 1991

Cvičení: Hlavním bodem programu je rozbor a prezentace algoritmů a návrh nových.

Požadavky k zápočtu:

Pro každého existuje mnoho cest, jak získat zápočet. Základní možnosti jsou následující:

1. Dohodněte si s přednášející jedno velké zadání. Doporučený postup: zkonzultujete s přednášející, jaká oblast informatiky vám nejlépe vyhovuje, a v této oblasti dostanete úkol a vedoucího. Příslušný vedoucí práce s vámi sepíše zadání projektu s návrhem bodového ohodnocení podle předpokládané náročnosti úlohy a po schválení přednášející můžete na problému pracovat. Téma také může být přípravou na vaši bakalářskou či diplomovou práci nebo být rozšířením zadání z jiného předmětu, ale nesmí se se zadáním přímo překrývat. Překryvy a návaznosti si s příslušným vyučujícím zkontroluji. Zatajením návazností či duplicity s jiným projektem riskujete anulování bodů ze zápočtu. Cílem je umožnit vám dále rozšířit práci na nějakém projektu, pokud tematicky souvisí s předmětem, a nedrobit váš čas a koncentraci na další úlohy. Téma nemusí navazovat vůbec na nic, jen být pro vás zajímavé, v každém případě musí tematicky odpovídat zaměření předmětu (tj. algoritmy).

2. Během semestru budou zadány tři skupiny úloh, každý student musí vyřešit jednu úlohu z každé skupiny. Podle kvality řešení a kvality dokumentace budou přiděleny body.

3. Aktivní účast na cvičení a řešení případných povinných či nepovinných domácích úloh (obvykle jde o promyšlení nějakého problému či návrh algoritmu.)

Všechny tyto části budou bodovány podle odhadované obtížnosti a podle kvality vypracování. Pozdní odevzdání bude penalizováno bodovou ztrátou. Pokud bude úloha odevzdána až v náhradním termínu zápočtu, aniž jste k tomu měli vážný, zejména zdravotní důvod, bude bodována jen polovinou původně nabízeného počtu bodů. Je možné také všechny výše uvedené možnosti libovolně kombinovat; je na vás, jaké práce a kolik na získání potřebného počtu bodů poskládáte.

Technické požadavky na odevzdávané úlohy:

Kromě zdrojových kódů přiložte vždy nějakou spustitelnou verzi, i v případě Javy. K úloze je vždy přiložena dokumentace zaměřená především na speciality vašeho řešení, tedy algoritmu, a speciality vaší implementace, tedy programu. Délka dokumentace by měla odpovídat náročnosti úlohy, čili od pár řádek k několika stránkám. Na začátku uveďte jméno a příjmení autora a zadání úlohy. Dokumentaci stačí odevzdat v elektronické podobě, formát PS nebo PDF. Totéž platí pro úlohy, kde výstupem je textová analýza či návrh algoritmu bez implementace. Řešení odevzdáváte cvičícímu způsobem, jaký si určí.

Student, který dosáhne největšího počtu bodů, bude odměněn „zkouškou bez zkoušky“. Také student, který dosáhne nejvyššího počtu bodů za aktivitu na cvičení, bude odměněn „zkouškou bez zkoušky“. Takto odměním jednak celkové vítěze, jednak první dva ze tří vítězů skupin (tím kompenzuji případnou různost bodových zisků v různých skupinách).

Minimální požadovaný počet bodů na zápočet: 30

Minimální potřebný počet bodů z písemky u zkoušky: 15, maximální možný počet: 30 z 3 otázek po 10 bodech

Celkové hodnocení (podmínkou je dosažení min. požadovaného počtu bodů k zápočtu i u zkoušky):

61 bodů a více - výborně

51 – 60 bodů - velmi dobře

45 – 50 bodů - dobře

méně bodů - nevyhověl