Diskrétní modely a algoritmy

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

Zaměření:

– diskrétní matematika a algoritmy

– geometrie a matematické struktury v informatice

– optimalizace

Absolvent oboru je do hloubky seznámen s diskrétním pojetím matematiky a diskrétními strukturami nacházejícími využití v informatice a algoritmickém modelování jevů a procesů z praxe. Má podle zvoleného zaměření pokročilé znalosti v jedné či více z následujících disciplín: kombinatorika a teorie grafů, pravděpodobnostní techniky a metody v diskrétní matematice a algoritmizaci, algebraické a topologické metody v informatice a konečně různé druhy optimalizace. Umí být v kontaktu s aktuálními výsledky v dané disciplíně a v ideálním případě k nim i sám tvůrčím způsobem přispívat. Nalezne uplatnění v oblastech lidské činnosti využívajících algoritmy a diskrétní modelování, i v akademické sféře.

Povinné předměty

Povinně volitelné předměty - skupina 1

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

Povinně volitelné předměty - skupina 2¹

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

¹Pro zaměření Diskrétní matematika a algoritmy, Geometrie a matematické struktury v informatice je doporučen předmět NDMI073, pro zaměření Optimalizace předmět NOPT018. Po absolvování jednoho předmětu ze skupiny 2 jsou kredity počítány pouze do skupiny 2, která je tak splněna. Pokud student absolvuje oba předměty ze skupiny 2, jsou mu kredity za druhý z předmětů započítány v rámci skupiny 1.

Státní závěrečná zkouška

Ke dvěma povinným okruhům společným pro všechny obory si student vybere tři okruhy podle zvoleného zaměření. Minimálně dva okruhy musí být ze zvoleného zaměření, třetí okruh je možné zvolit z jiného zaměření oboru. Celkem tedy každý student dostane pět otázek.

Zaměření: Diskrétní matematika a algoritmy

Zkušební okruhy

1. Kombinatorika a teorie grafů

2. Pravděpodobnostní techniky a kombinatorická enumerace

3. Kombinatorická optimalizace

Zkušební požadavky

1. Kombinatorika a teorie grafů
Barevnost grafů (a další varianty - vybíravost), grafové minory, stromová šířka a její souvislost se složitostí, geometrické reprezentace grafů (charakterizační věty, rozpoznávající algoritmy), algebraické vlastnosti grafů, teorie párování, Ramseyova teorie a Szemerédiho lemma o regularitě, množinové systémy (Steinerovy systémy trojic, konečné geometrie).

Doporučené předměty

2. Pravděpodobnostní techniky a kombinatorická enumerace
Kombinatorické počítání, vytvořující funkce, rekurence, základní pravděpodobnostní modely, linearita střední hodnoty, použití rozptylu, Markovova nerovnost, aplikace na konkrétní příklady, Chernovova nerovnost, Lovászovo lokální lemma, asymptotické odhady funkcí, pravděpodobnostní konstrukce a algoritmy.

Doporučené předměty

3. Kombinatorická optimalizace
Grafové 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í: Geometrie a matematické struktury v informatice

Zkušební okruhy

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

2. Algebraické a topologické struktury v informatice

3. Teorie kategorií v informatice

4. Teorie čísel 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ů

Doporučené předměty

2. Algebraické a topologické struktury 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.

Doporučené předměty

3. Teorie kategorií 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

4. Teorie čísel v informatice
Diofantické aproximace (Dirichletova věta, Fareyovy zlomky, transcendentní čísla). Diofantické rovnice (Pellova rovnice, Thueho rovnice, věta o 4 čtvercích, 10. Hilbertův problém). Prvočísla (odhady prvočíselné funkce, Dirichletova věta). Geometrie čísel (mřížky, Minkowskiho věta). Kongruence (kvadratické zbytky). Číselné rozklady (rozkladové identity, např. pentagonální identita).

Doporučené předměty

Zaměření: Optimalizace

Zkušební okruhy

1. Nelineární programování

2. Diskrétní optimalizační procesy

3. Vícekriteriální a celočíselné programování

4. Parametrické programování a intervalové metody

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

Doporučené předměty

2. Diskrétní optimalizační procesy
Algoritmická teorie her, volební mechanismy, elektronické aukce, využití submodulárních funkcí v ekonomii. Optimalizace pomocí enumerací, generující funkce hranových řezů a perfektních párování, enumerační duality, problém maximálního řezu pro grafy vnořené na plochách.

Doporučené předměty

3. Vícekriteriální a celočíselné 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í. Pareto-optimální řešení. Úlohy lineární a nelineární vektorové optimalizace. Metody pro získání Pareto-optimálních řešení. Úlohy lineárního programování s podmínkami celočíselnosti, resp. s binárními proměnnými. Nelineární optimalizační problémy s podmínkami celočíselnosti.

Doporučené předměty

4. Parametrické programování a intervalové metody
Obory stability řešení. Obory řešitelnosti. Funkce řešitelnosti pro jednoparametrické a víceparametrické programování. Intervalová lineární algebra (lineární soustavy rovnic, regularita, vlastní čísla). Lineární programování s nepřesnými daty. Deterministická globální optimalizace, horní a dolní odhady na účelovou funkci a optimální hodnotu.

Doporučené předměty