Okruhy ke zkoušce z PRO
Prof. dr. ing. I. Kolingerová
1. Úvod do algoritmizace – hodnocení a porovnávání
algoritmů, složitosti, robustnost
2. Algoritmické strategie – brutální síla, greedy strategie, inkrementální techniky, rozděl a panuj,
dynamické programování, backtracking - teorie i
praktické použití jednotlivých strategií – dokázat vytvořit algoritmus založený
na užití dané strategie pro daný problém a odhadnout předem jeho
vlastnosti
3. Randomizované algoritmy – vlastnosti, vzorkování, typické randomizované triky, algoritmy Monte
Carlo a Las Vegas,
problematika generování náhodných čísel, příklady užití randomizace
v existujících algoritmech, dokázat aplikovat randomizaci v řešení
zadané úlohy
4. Data stream
algoritmy – typické
úlohy, odhad u daného problému, zda jde řešit přesně nebo ne, existující modely
a typické triky, rámcový návrh řešení zadaného problému některým
z probíraných triků
5. In-place a
in situ algoritmy – vlastnosti, typické triky, rámcový návrh řešení
zadaného problému v duchu těchto metod
6. Kvantové výpočty – hlavní myšlenky, základní
vlastnosti, možnosti využití
7. Praktické řešení úloh, především typů řešených na
přednáškách a na cvičení, ale hodnotí se i šikovnost při řešení zcela neznámé
úlohy.
U bodů 1 a 2 kromě dynamického programování se očekává
detailní znalost a bezproblémové užití pro jakýkoliv zadaný problém. U
dynamického programování a bodů 3-5 se očekává detailní znalost u těch typů
příkladů, které byly probrány, a při aplikaci na neznámý problém se očekává, že
student dokáže danou techniku pro daný příklad užít, „vezme to za správný
konec“, ale jsou tolerovány menší chyby dané větší obtížností problematiky a
menší zkušeností s ní. U bodu 6 se praktická aplikace neočekává. Hloubka a
rozsah učiva odpovídá přednáškám a cvičením. Praktické příklady budou řešeny na
úrovni jednoznačného, ale ne nutně podrobně rozepsaného algoritmu
v nějakém pseudojazyce, zapisování přímo
v konkrétním programovacím jazyce se vyhněte.
Příklad písemky:
1. Vyjmenujte typické vlastnosti strategie Rozděl a panuj, popište, pro jaké problémy se hodí a pro
jaké ne.
2. Charakterizujte randomizované
algoritmy typu Las Vegas a Monto
Carlo. Pro každou skupinu uveďte také příklad
algoritmu. Algoritmus nemusíte vypisovat detailně.
3. Napište algoritmus, který využije greedy strategii pro problém obchodního cestujícího a
uveďte jeho složitost. Popište detailně, co je klíčovým krokem algoritmu rozhodujícím
o složitosti a jak tento krok udělat efektivně.