I4 Diskrétní modely a algoritmy

4. Diskrétní modely a algoritmy I4

Garantující pracoviště: Katedra aplikované matematiky
Oborový garant: doc. RNDr. Martin Klazar, Dr.

Povinné předměty

¹ Předmět je povinný pouze pro zaměření Diskrétní matematika a kombinatorická optimalizace, Matematické struktury informatiky; pro zaměření Optimalizace je povinně volitelný. Posluchači, kteří zahájili studium v roce 2009 nebo dříve, mohou požádat o uznání tohoto předmětu na základě dřívějšího absolvování předmětu NDMI012 Kombinatorika a grafy II.

² Předmět je povinný pouze pro zaměření Optimalizace; pro ostatní zaměření je povinně volitelný. Posluchači, kteří zahájili studium v roce 2009 nebo dříve, mohou požádat o uznání tohoto předmětu na základě dřívějšího absolvování předmětu NOPT046 Základy spojité optimalizace.

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

¹ Předmět je povinně volitelný pouze pro zaměření Optimalizace; pro ostatní zaměření je povinný.

² Předmět je povinně volitelný pouze pro zaměření Diskrétní matematika a kombinatorická optimalizace, Matematické struktury informatiky; pro zaměření Optimalizace je povinný.

Zaměření: Diskrétní matematika a kombinatorická optimalizace

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

Zaměření: Matematické struktury informatiky

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

Zaměření: Optimalizace

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ání. 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ání. 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ární 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