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