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ódPředmětKredityZSLS
NTIN090Základy složitosti a vyčíslitelnosti 52/1 Z+Zk
NTIN066Datové struktury I 52/1 Z+Zk
NMAI064Matematické struktury 62/2 Z+Zk
NSZZ023Diplomová práce I 60/4 Z0/4 Z
NSZZ024Diplomová práce II 90/6 Z0/6 Z
NSZZ025Diplomová práce III 150/10 Z0/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ódPředmětKredityZSLS
NAIL076Logické programování I 32/0 Zk
NDMI009Kombinatorická a výpočetní geometrie I 62/2 Z+Zk
NDMI010Grafové algoritmy 32/0 Zk
NDMI013Kombinatorická a výpočetní geometrie II 62/2 Z+Zk
NDMI015Kombinatorické počítání 32/0 Zk
NDMI018Aproximační a online algoritmy 62/2 Z+Zk
NDMI025Pravděpodobnostní algoritmy 62/2 Z+Zk
NDMI028Aplikace lineární algebry v kombinatorice 62/2 Z+Zk
NDMI036Kombinatorické struktury 32/0 Zk
NDMI037Geometrické reprezentace grafů I 32/0 Zk
NDMI045Analytická a kombinatorická teorie čísel 32/0 Zk
NDMI055Vybrané kapitoly z kombinatoriky I 32/0 Zk
NDMI056Vybrané kapitoly z kombinatoriky II 32/0 Zk
NDMI059Grafové minory a stromové rozklady 32/0 Zk
NDMI060Barevnost grafů a kombinatorických struktur 32/0 Zk
NDMI064Aplikovaná diskrétní matematika 32/0 Zk
NDMI065Teorie matroidů 62/2 Z+Zk
NDMI066Algebraická teorie čísel 32/0 Zk
NDMI067Toky, cesty a řezy 32/0 Zk
NDMI073Kombinatorika a grafy III 62/2 Z+Zk
NDMI074Algoritmy a jejich implementace 62/2 Z+Zk
NDMI088Grafové algoritmy II 32/0 Zk
NMAG337Úvod do teorie grup 52/2 Z+Zk
NMAI040Úvod do teorie čísel 32/0 Zk
NMAI065Základy teorie kategorií pro informatiky 32/0 Zk
NMAI066Topologické a algebraické metody 32/0 Zk
NMAI067Logika v informatice 32/0 Zk
NMAI071Matematika++ 62/2 Z+Zk
NMMA901Úvod do komplexní analýzy (O) 52/2 Z+Zk
NMMA903Teorie míry a integrálu (O) 84/2 Z+Zk
NMMA931Úvod do funkcionální analýzy (O) 84/2 Z+Zk
NOPT008Algoritmy nelineární optimalizace 62/2 Z+Zk
NOPT016Celočíselné programování 62/2 Z+Zk
NOPT017Vícekriteriální optimalizace 32/0 Zk
NOPT018Základy nelineární optimalizace 62/2 Z+Zk
NOPT034Matematické programování a polyedrální kombinatorika 52/1 Z+Zk
NOPT042Programování s omezujícími podmínkami 62/2 Z+Zk
NOPT051Intervalové metody 62/2 Z+Zk
NTIN017Paralelní algoritmy 32/0 Zk
NTIN022Pravděpodobnostní techniky 62/2 Z+Zk
NTIN063Složitost 52/1 Z+Zk
NTIN064Vyčíslitelnost 32/0 Zk
NTIN067Datové struktury II 32/0 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ódPředmětKredityZSLS
NDMI073Kombinatorika a grafy III 62/2 Z+Zk
NOPT018Základy nelineární optimalizace 62/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ódPředmětKredityZSLS
NDMI037Geometrické reprezentace grafů I 32/0 Zk
NDMI059Grafové minory a stromové rozklady 32/0 Zk
NDMI060Barevnost grafů a kombinatorických struktur 32/0 Zk
NDMI073Kombinatorika a grafy III 62/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ódPředmětKredityZSLS
NDMI015Kombinatorické počítání 32/0 Zk
NDMI025Pravděpodobnostní algoritmy 62/2 Z+Zk
NTIN022Pravděpodobnostní techniky 62/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ódPředmětKredityZSLS
NTIN090Základy složitosti a vyčíslitelnosti 52/1 Z+Zk
NDMI010Grafové algoritmy 32/0 Zk
NDMI065Teorie matroidů 62/2 Z+Zk
NOPT034Matematické programování a polyedrální kombinatorika 52/1 Z+Zk
NDMI088Grafové algoritmy II 32/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ódPředmětKredityZSLS
NDMI009Kombinatorická a výpočetní geometrie I 62/2 Z+Zk
NDMI013Kombinatorická a výpočetní geometrie II 62/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ódPředmětKredityZSLS
NMAI064Matematické struktury 62/2 Z+Zk
NMAI066Topologické a algebraické metody 32/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ódPředmětKredityZSLS
NMAI065Základy teorie kategorií pro informatiky 32/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ódPředmětKredityZSLS
NMAI040Úvod do teorie čísel 32/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ódPředmětKredityZSLS
NOPT018Základy nelineární optimalizace 62/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ódPředmětKredityZSLS
NDMI064Aplikovaná diskrétní matematika 32/0 Zk
NOPT018Základy nelineární optimalizace 62/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ódPředmětKredityZSLS
NOPT016Celočíselné programování 62/2 Z+Zk
NOPT017Vícekriteriální optimalizace 32/0 Zk
NOPT018Základy nelineární optimalizace 62/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ódPředmětKredityZSLS
NOPT017Vícekriteriální optimalizace 32/0 Zk
NOPT018Základy nelineární optimalizace 62/2 Z+Zk
NOPT051Intervalové metody 62/2 Z+Zk

© 2013–2017 Univerzita Karlova, Matematicko-fyzikální fakulta. Design noBrother.
Za obsah odpovídá Studijní oddělení.