I4 - Diskrétní modely a algoritmy

Garantující pracoviště: Katedra aplikované matematiky
Odpovědný učitel: Prof. RNDr. Jan Kratochvíl, CSc.

Povinné předměty

Povinně volitelné předměty

Je požadováno splnění povinně volitelných předmětů z následujícího seznamu v rozsahu alespoň 45 kreditů:

Studijní plán: Diskrétní matematika a kombinatorická optimalizace

Garantující pracoviště: Katedra aplikované matematiky
Odpovědný učitel: Prof. RNDr. Jaroslav Nešetřil, DrSc.

Zkušební okruhy

1. Kombinatorika a teorie grafů

2. Pravděpodobnostní metody a algoritmy

3. Kombinatorická optimalizace

Zkušební požadavky

1. Kombinatorika a teorie grafů
Barevnost grafů, regulární grafy, souvislost grafů, speciální vlastnosti orientovaných grafů, algebraické vlastnosti grafů, teorie párování, Ramseyova teorie, nekonečná kombinatorika, strukturální vlastnosti množinových systémů.

2. Pravděpodobnostní metody a algoritmy
Kombinatorické počítání, vytvořující funkce, rekurence, základní pravděpodobnostní modely, linearita střední hodnoty, použití variace, aplikace na konkrétní příklady, asymptotické odhady funkcí, pravděpodobnostní konstrukce a algoritmy.

3. Kombinatorická optimalizace
Grafové algoritmy, algebraické a aritmetické algoritmy, teorie mnohostěnů, problém obchodního cestujícího, speciální matice, celočíselnost, párování a toky v sítích, teorie matroidů, elipsoidová metoda.

Doporučené předměty

Studijní plán: Matematické struktury informatiky

Garantující pracoviště: Katedra aplikované matematiky
Odpovědný učitel: Prof. RNDr. Aleš Pultr, DrSc.

Zkušební okruhy

1. Kombinatorická a výpočetní geometrie

2. Algebraické a topologické metody v informatice

3. Teorie čísel a kategorie v informatice

Zkušební požadavky

1. Kombinatorická a výpočetní geometrie
Geometrické úlohy v prostorech konečné dimenze, kombinatorické vlastnosti geometrických konfigurací, algoritmické aplikace, návrh geometrických algoritmů, geometrické reprezentace grafů.

2. Algebraické a topologické metody v informatice
Částečně uspořádané množiny; suprema a infima, polosvazy, svazy. Věty o pevných bodech. Speciální uspořádané struktury v informatice (DCPO, domény). Základy obecné topologie; topologické konstrukce. Speciální topologické otázky hrající roli v informatice (Scottova topologie, spojité svazy). Kategorie topologických prostorů a některých typů částečných uspořádání hrající roli v informatice.

3. Teorie čísel a kategorie v informatice
Kategorie, funktory, transformace, konkrétní příklady. Limity a kolimity, speciální konstrukce a vytváření dalších. Adjunkce, vztah ke kategoriálním konstrukcím. Reflexe a koreflexe. Konkrétní příklady adjungovaných situací. Kartézsky uzavřené kategorie. Kategorie a struktury, zejména struktury užívané v informatice. Monadické algebry.

Doporučené předměty

Studijní plán: Optimalizace

Garantující pracoviště: Katedra aplikované matematiky
Odpovědný učitel: Prof. RNDr. Karel Zimmermann, DrSc.

Zkušební okruhy

1. Nelineární programování

2. Optimalizační procesy

3. Parametrické, vícekriteriální a celočíselné programování

4. Nehladká optimalizace a pravděpodobnostní dynamické modely

Zkušební požadavky

1. Nelineární programování
Vlastnosti konvexních množin a konvexních funkcí. Zobecnění konvexních funkcí. Nutné a postačující podmínky optimality pro volné a vázané extrémy úloh nelineárního programovaní. Kvadratické programováni. Dualita v nelineárním programováni. Metody řešení úloh na volný a vázaný extrém,včetně penalizačních a bariérových metod. Jednorozměrná optimalizace.

2. Optimalizační procesy
Spojité: Princip maxima pro nelineární úlohy různých typů. Podmínky optimality pro základní úlohy variačního počtu. Lineární úlohy na minimalizaci času.

Diskrétní: Klasifikace úloh a jejich vztah k úloze nelineárního programováni. Lineární a kvadratické úlohy. Základy řízení markovských systémů. Diskrétní dynamické programování - optimalizace vzhledem k počátečnímu stavu, koncovému stavu a počátečnímu a koncovému stavu.

3. Parametrické, vícekriteriální a celočíselné programování
Obory stability řešení. Obory řešitelnosti. Funkce řešitelnosti pro jednoparametrické a víceparametrické programování. Různé přístupy k řešení úloh s více kritérii.

Funkcionál přiřazený k dané úloze vektorového programování. Eficientní body. Úlohy lineární a nelineární vektorové optimalizace. Metody pro získání eficientních bodů. Úlohy lineárního programování s podmínkami celočíselnosti, resp. s bivalentními proměnnými. Nelineárni optimalizační problémy s podmínkami celočíselnosti.

4. Nehladká optimalizace a pravděpodobnostní dynamické modely
Clarkeův kalkulus a základy nehladké analýzy. Podmínky optimality. Numerické metody nehladké optimalizace. Modely s diskrétními stavy (Poissonův proces, modely hromadné obsluhy, Markovovy procesy a řetězce). Porovnání pravděpodobnostních a deterministických modelů. Modely se spojitými stavy (stochastický integrál a diferenciál, lineární stochastické diferenciální rovnice).

Doporučené předměty