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