Programátorské strategie (KIV/PRO)

Přednášky: Prof. Dr. Ing.Ivana Kolingerová

Cvičení: Ing. Alex Kӧnig

Okruhy:

• Základy algoritmizace, algoritmická složitost v praxi

• Brutální síla, inkrementální algoritmy

• Geometrické algoritmy

• Zábavné algoritmy

• Randomizované algoritmy

• Shlukování

• Data stream algoritmy

• In-place a in situ algoritmy

• 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í:

• materiály k jednotlivým tématům jsou přímo v podkladech k přenáškám
• S. Skiena: The Algorithm Design Manual, Spring-Verlag, New York Berlin Heidelberg, 1998 nebo novější vydání – 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:

1. Budou postupně zadány tři typy úloh. Povinné jsou první dva, třetí v případě zájmu studenta o získání dalších bodů.

Řešení budou bodována podle odhadované obtížnosti úkolu 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ů.

2. Na cvičení je možné získat body za aktivitu – nápady, postřehy, prezentace řešení úloh. Ze cvičení budou také různé povinné nebo dobrovolné domácí úkoly (obvykle jde o promyšlení nějakého problému či návrh algoritmu, případně prezentace na dohodnuté téma), které mohou přinést další body (i záporné ;-).

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