Okruhy ke zkoušce z PRO

Prof. dr. ing. I. Kolingerová

1. Algoritmizace z praktického úhlu pohledu – správnost a účinnost, robustnost algoritmu, experimentální ověření složitosti, určení „bottlenecku“, vylepšování řešení

2. Algoritmus brutální síly, greedy (hladový) algoritmus, inkrementální algoritmy

3. Geometrické algoritmy - test polohy body vůči nadrovině, konstrukce konvexní obálky (Grahamovo prohledávání, balení dárku), Voroného diagram – vlastnosti, kontrukce inkrementálním vkládáním, hledání nejbližšího souseda v množině bodů, zjednodušování polygonů (Douglas-Peucker)

4. Zábavné algoritmy – hlavní myšlenka pessimal algorithms a simplexity analysis, hlavní myšlenka slowsortu, jeden z algoritmů z bodu 4 přednášky dle vlastního výběru: přesouvání mincí nebo Tripos nebo algoritmus tvorby tvarů skládáním a jedním řezem

5. Randomizované algoritmy – princip, randomizované algoritmy inkrementální a rozděl a panuj, vzorkování, 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

6. Shlukování – popis a základní postup, využití, hierarchické a nehierarchické metody, podrobněji deterministické K-means shlukování, fuzzy C-means shlukování a aglomerativní hierarchické shlukování

7. In-place a in situ algoritmy – výhody a nevýhody, in-place algoritmus konvexní obálky, in-place merge sort

8. 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, náhodné vzorkování s rezervoárem, iceberg queries

9. Kvantové výpočty – hlavní myšlenka, základní vlastnosti kvantové sosustavy, výhody a nevýhody kvantového počítání, možnosti využití

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

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.

Konkrétní otázka navíc pro každého po stanovení známky: co se vám líbilo a nelíbilo, jaké téma byste vyřadili nebo naopak přidali.

Příklad písemky:

1. Popište tři existující datastreamové modely a uveďte příklady aplikačních úloh pro jednotlivé modely.

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