Diskrétní modely a algoritmy

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

kód Předmět Kredity ZS LS
NTIN090 Základy složitosti a vyčíslitelnosti   5 2/1 Z+Zk
NTIN066 Datové struktury I   5 2/1 Z+Zk
NMAI064 Matematické struktury   6 2/2 Z+Zk
NSZZ023 Diplomová práce I   6 0/4 Z 0/4 Z
NSZZ024 Diplomová práce II   9 0/6 Z 0/6 Z
NSZZ025 Diplomová práce III   15 0/10 Z 0/10 Z

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

kód Předmět Kredity ZS LS
NAIL076 Logické programování I   3 2/0 Zk
NDMI009 Kombinatorická a výpočetní geometrie I   6 2/2 Z+Zk
NDMI010 Grafové algoritmy   3 2/0 Zk
NDMI013 Kombinatorická a výpočetní geometrie II   6 2/2 Z+Zk
NDMI015 Kombinatorické počítání   3 2/0 Zk
NDMI018 Aproximační a online algoritmy   6 2/2 Z+Zk
NDMI025 Pravděpodobnostní algoritmy   6 2/2 Z+Zk
NDMI028 Aplikace lineární algebry v kombinatorice   6 2/2 Z+Zk
NDMI036 Kombinatorické struktury   3 2/0 Zk
NDMI037 Geometrické reprezentace grafů I   3 2/0 Zk
NDMI045 Analytická a kombinatorická teorie čísel   3 2/0 Zk
NDMI055 Vybrané kapitoly z kombinatoriky I   3 2/0 Zk
NDMI056 Vybrané kapitoly z kombinatoriky II   3 2/0 Zk
NDMI059 Grafové minory a stromové rozklady   3 2/0 Zk
NDMI060 Barevnost grafů a kombinatorických struktur   3 2/0 Zk
NDMI064 Aplikovaná diskrétní matematika   3 2/0 Zk
NDMI065 Teorie matroidů   6 2/2 Z+Zk
NDMI066 Algebraická teorie čísel   3 2/0 Zk
NDMI067 Toky, cesty a řezy   3 2/0 Zk
NDMI073 Kombinatorika a grafy III   6 2/2 Z+Zk
NDMI074 Algoritmy a jejich implementace   6 2/2 Z+Zk
NDMI088 Grafové algoritmy II   3 2/0 Zk
NMAG337 Úvod do teorie grup   5 2/2 Z+Zk
NMAI040 Úvod do teorie čísel   3 2/0 Zk
NMAI065 Základy teorie kategorií pro informatiky   3 2/0 Zk
NMAI066 Topologické a algebraické metody   3 2/0 Zk
NMAI067 Logika v informatice   3 2/0 Zk
NMAI071 Matematika++   6 2/2 Z+Zk
NMMA901 Úvod do komplexní analýzy (O)   5 2/2 Z+Zk
NMMA903 Teorie míry a integrálu (O)   8 4/2 Z+Zk
NMMA931 Úvod do funkcionální analýzy (O)   8 4/2 Z+Zk
NOPT008 Algoritmy nelineární optimalizace   6 2/2 Z+Zk
NOPT016 Celočíselné programování   6 2/2 Z+Zk
NOPT017 Vícekriteriální optimalizace   3 2/0 Zk
NOPT018 Základy nelineární optimalizace   6 2/2 Z+Zk
NOPT034 Matematické programování a polyedrální kombinatorika   5 2/1 Z+Zk
NOPT042 Programování s omezujícími podmínkami   6 2/2 Z+Zk
NOPT051 Intervalové metody   6 2/2 Z+Zk
NTIN017 Paralelní algoritmy   3 2/0 Zk
NTIN022 Pravděpodobnostní techniky   6 2/2 Z+Zk
NTIN063 Složitost   5 2/1 Z+Zk
NTIN064 Vyčíslitelnost   3 2/0 Zk
NTIN067 Datové struktury II   3 2/0 Zk
NTIN103 Introduction to Parameterized Algorithms   6 2/2 Z+Zk

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

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

kód Předmět Kredity ZS LS
NDMI073 Kombinatorika a grafy III   6 2/2 Z+Zk
NOPT018 Základy nelineární optimalizace   6 2/2 Z+Zk

1Pro 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

kód Předmět Kredity ZS LS
NDMI037 Geometrické reprezentace grafů I   3 2/0 Zk
NDMI059 Grafové minory a stromové rozklady   3 2/0 Zk
NDMI060 Barevnost grafů a kombinatorických struktur   3 2/0 Zk
NDMI073 Kombinatorika a grafy III   6 2/2 Z+Zk

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

kód Předmět Kredity ZS LS
NDMI015 Kombinatorické počítání   3 2/0 Zk
NDMI025 Pravděpodobnostní algoritmy   6 2/2 Z+Zk
NTIN022 Pravděpodobnostní techniky   6 2/2 Z+Zk

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

kód Předmět Kredity ZS LS
NTIN090 Základy složitosti a vyčíslitelnosti   5 2/1 Z+Zk
NDMI010 Grafové algoritmy   3 2/0 Zk
NDMI065 Teorie matroidů   6 2/2 Z+Zk
NOPT034 Matematické programování a polyedrální kombinatorika   5 2/1 Z+Zk
NDMI088 Grafové algoritmy II   3 2/0 Zk

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

kód Předmět Kredity ZS LS
NDMI009 Kombinatorická a výpočetní geometrie I   6 2/2 Z+Zk
NDMI013 Kombinatorická a výpočetní geometrie II   6 2/2 Z+Zk

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

kód Předmět Kredity ZS LS
NMAI064 Matematické struktury   6 2/2 Z+Zk
NMAI066 Topologické a algebraické metody   3 2/0 Zk

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

kód Předmět Kredity ZS LS
NMAI065 Základy teorie kategorií pro informatiky   3 2/0 Zk

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

kód Předmět Kredity ZS LS
NMAI040 Úvod do teorie čísel   3 2/0 Zk

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

kód Předmět Kredity ZS LS
NOPT008 Algoritmy nelineární optimalizace   6 2/2 Z+Zk
NOPT018 Základy nelineární optimalizace   6 2/2 Z+Zk

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

kód Předmět Kredity ZS LS
NDMI064 Aplikovaná diskrétní matematika   3 2/0 Zk
NOPT018 Základy nelineární optimalizace   6 2/2 Z+Zk

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

kód Předmět Kredity ZS LS
NOPT016 Celočíselné programování   6 2/2 Z+Zk
NOPT017 Vícekriteriální optimalizace   3 2/0 Zk
NOPT018 Základy nelineární optimalizace   6 2/2 Z+Zk

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

kód Předmět Kredity ZS LS
NOPT017 Vícekriteriální optimalizace   3 2/0 Zk
NOPT018 Základy nelineární optimalizace   6 2/2 Z+Zk
NOPT051 Intervalové metody   6 2/2 Z+Zk