Informatika - Diskrétní modely a algoritmy
Tato stránka vychází z podkladů pro tištěné studijní plány (tzv. Karolinku).
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
- – geometrie a matematické struktury v informatice
Studijní program Diskrétní modely a algoritmy poskytuje široké vzdělání v teoretických a matematických základech informatiky. Student získá znalosti v oblasti diskrétních modelů a souvisejících algoritmických a datových technik a různých matematických metod pro jejich návrh. Program studenta seznámí jak se současnými poznatky v oblasti diskrétních modelů, algoritmů a optimalizace, tak s možnostmi a omezeními řešení souvisejících algoritmických problémů. Student získá důkladné matematické znalosti potřebné pro analýzu a návrh diskrétních modelů a algoritmů.
Absolvent dobře ovládá problematiku modelování pomocí diskrétních struktur spolu s jeho praktickými algoritmickými a výpočetními aspekty. Tím pádem rozumí modelům výpočtů a jejich vzájemným vztahům a zná omezení efektivních výpočtů. Má povědomí o algoritmických technikách a datových strukturách. Má také přehled o některých optimalizačních postupech, technikách a výsledcích. Absolvent se během studia seznámil s matematickými přístupy k diskrétním modelům a algoritmům, což vedle vždy přítomné kombinatoriky a diskrétní matematiky zahrnuje geometrické, topologické, algebraické, číselně-teoretické, logické a v neposlední řadě pravděpodobnostní metody. Absolvent umí posoudit vhodnost a použitelnost těchto metod pro konkrétní diskrétní model. Rovněž dokáže sledovat nejnovější výzkumné trendy v daných oblastech. Absolvent nalezne uplatnění při návrhu a analýze diskrétních modelů a jejich algoritmické implementace a při vývoji odpovídajících technologií. Může tedy pracovat ve špičkových společnostech a institucích zabývajících se vývojem a výzkumem nových technologií, analýzou dat či modelováním reálných procesů (doprava, finance, ekonomie a podobně). Je připraven pro následné doktorské studium teoretické informatiky a příbuzných oborů u nás i ve světě.
Povinné předměty
kód | Předmět | Kredity | ZS | LS | |
NTIN090 | Základy složitosti a vyčíslitelnosti | 4 | 2/1 Z+Zk | — | |
NTIN066 | Datové struktury 1 | 6 | 2/2 Z+Zk | — | |
NMAI064 | Matematické struktury | 5 | — | 2/2 Z+Zk | |
NSZZ023 | Diplomová práce I | 6 | — | 0/4 Z | |
NSZZ024 | Diplomová práce II | 9 | 0/6 Z | — | |
NSZZ025 | Diplomová práce III | 15 | — | 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ů. Předměty NDMI055 a NDMI056 mohou navštěvovat studenti magisterského i doktorského studia.
kód | Předmět | Kredity | ZS | LS | |
NAIL076 | Logické programování 1 | 3 | 2/0 Zk | — | |
NDMI010 | Grafové algoritmy | 3 | 2/0 Zk | — | |
NDMI013 | Kombinatorická a výpočetní geometrie 2 | 5 | — | 2/2 Z+Zk | |
NDMI014 | Topologické metody v kombinatorice | 5 | — | 2/2 Z+Zk | |
NDMI015 | Kombinatorické počítání | 3 | — | 2/0 Zk | |
NDMI018 | Aproximační a online algoritmy | 5 | — | 2/2 Z+Zk | |
NDMI025 | Pravděpodobnostní algoritmy | 5 | — | 2/2 Z+Zk | |
NDMI028 | Aplikace lineární algebry v kombinatorice | 5 | 2/2 Z+Zk | — | |
NDMI036 | Kombinatorické struktury | 3 | — | 2/0 Zk | |
NDMI037 | Geometrické reprezentace grafů 1 | 3 | 2/0 Zk | — | |
NDMI045 | Analytická a kombinatorická teorie čísel | 3 | — | 2/0 Zk | |
NDMI055 | Vybrané kapitoly z kombinatoriky 1 | 3 | 2/0 Zk | — | |
NDMI056 | Vybrané kapitoly z kombinatoriky 2 | 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ů | 5 | — | 2/2 Z+Zk | |
NDMI066 | Algebraická teorie čísel | 3 | 2/0 Zk | — | |
NDMI067 | Toky, cesty a řezy | 3 | 2/0 Zk | — | |
NDMI074 | Algoritmy a jejich implementace | 5 | — | 2/2 Z+Zk | |
NDMI087 | Analytická kombinatorika | 4 | — | 2/1 Zk | |
NDMI088 | Grafové algoritmy 2 | 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++ | 5 | — | 2/2 Z+Zk | |
NMMA901 | Úvod do komplexní analýzy (O) | 5 | 2/2 Z+Zk | — | |
NMMA931 | Úvod do funkcionální analýzy (O) | 8 | 4/2 Z+Zk | — | |
NOPT008 | Algoritmy nelineární optimalizace | 5 | — | 2/2 Z+Zk | |
NOPT016 | Celočíselné programování | 5 | — | 2/2 Z+Zk | |
NOPT017 | Vícekriteriální optimalizace | 3 | — | 2/0 Zk | |
NOPT034 | Matematické programování a polyedrální kombinatorika | 4 | — | 2/1 Z+Zk | |
NOPT042 | Programování s omezujícími podmínkami | 5 | 2/2 Z+Zk | — | |
NOPT051 | Intervalové metody | 5 | 2/2 Z+Zk | — | |
NTIN017 | Paralelní algoritmy | 3 | — | 2/0 Zk | |
NTIN022 | Pravděpodobnostní techniky | 5 | 2/2 Z+Zk | — | |
NTIN023 | Dynamické grafové datové struktury | 3 | 2/0 Zk | — | |
NTIN063 | Složitost | 4 | — | 2/1 Z+Zk | |
NTIN064 | Vyčíslitelnost | 3 | — | 2/0 Zk | |
NTIN067 | Datové struktury 2 | 3 | — | 2/0 Zk | |
NTIN100 | Základy přenosu a zpracování informace | 4 | — | 2/1 Z+Zk | |
NTIN103 | Introduction to Parameterized Algorithms | 5 | 2/2 Z+Zk | — | |
NDMI113 | Extremal combinatorics | 3 | — | 2/0 Zk | |
NOPT059 | Optimalizace velkých problémů: přesné metody | 5 | — | 2/2 Z+Zk | |
NOPT061 | Optimalizace velkých problémů: metaheuristiky | 5 | — | 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ň 5 kreditů:
kód | Předmět | Kredity | ZS | LS | |
NDMI073 | Kombinatorika a grafy 3 | 5 | 2/2 Z+Zk | — | |
NOPT018 | Základy nelineární optimalizace | 5 | 2/2 Z+Zk | — |
1Pro dvě zaměření Diskrétní matematika a algoritmy a 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. Jsou-li absolvovány oba předměty ze skupiny 2, jsou kredity za druhý z nich započítány v rámci kreditů pro volbu studenta.
Doporučené volitelné předměty
Seznam doporučených volitelných předmětů obsahuje pouze jeden předmět, daný požadavky zkušebního okruhu Kombinatorická a výpočetní geometrie. Další volitelné předměty lze volit ze široké nabídky předmětů na MFF UK.
kód | Předmět | Kredity | ZS | LS | |
NDMI009 | Základy kombinatorické a výpočetní geometrie | 5 | 2/2 Z+Zk | — |
Státní závěrečná zkouška
Student dostane pět otázek, dvě ze společného základu (jednu z Úvodu do složitosti a vyčíslitelnosti a jednu z Datových struktur) a po jedné ze tří studentem zvolených zkušebních okruhů uvedených v následujících seznamech. Alespoň dva z těchto zkušebních okruhů musejí náležet do zvoleného studentova zaměření, jeden zkušební okruh může být z jiného zaměření.
Zkušební okruhy
- 1. Úvod do složitosti a vyčíslitelnosti
- 2. Datové struktury
Zkušební požadavky
1. Úvod do složitosti a vyčíslitelnosti
Výpočetní modely (Turingovy stroje, RAM). Základní třídy složitosti a jejich vztahy.
Aproximační algoritmy a schémata.
Doporučené předměty
kód | Předmět | Kredity | ZS | LS | |
NTIN090 | Základy složitosti a vyčíslitelnosti | 4 | 2/1 Z+Zk | — |
Zkušební požadavky
2. Datové struktury
Vyhledávací stromy ((a,b)-stromy, splay stromy). Haldy (regulární, binomiální). Hašování, řešení kolizí,
univerzální hašování, výběr hašovací funkce.
Doporučené předměty
kód | Předmět | Kredity | ZS | LS | |
NTIN066 | Datové struktury 1 | 6 | 2/2 Z+Zk | — |
Zaměření: Diskrétní matematika a algoritmy
Zkušební okruhy
- 1. Kombinatorika a teorie grafů
- 2. Pravděpodobnostní techniky a kombinatorická enumerace
- 3. Polyedrální optimalizace
- 4. Grafové algoritmy
- 2. Pravděpodobnostní techniky a kombinatorická enumerace
Zkušební požadavky
1. Kombinatorika a teorie grafů
Barevnost grafů a její varianty, např. tzv. vybíravost. Grafové minory, stromová šířka a její souvislost se složitostí. Geometrické reprezentace
grafů (charakterizační věty, rozpoznávací algoritmy), algebraické vlastnosti grafů, teorie párování. Ramseyova teorie a Szemerédiho lemma
o regularitě. Množinové systémy, např. Steinerovy systémy trojic a konečné geometrie.
Doporučené předměty
kód | Předmět | Kredity | ZS | LS | |
NDMI037 | Geometrické reprezentace grafů 1 | 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 3 | 5 | 2/2 Z+Zk | — |
2. Pravděpodobnostní techniky a kombinatorická enumerace
Kombinatorické počítání, vytvořující funkce, rekurence, asymptotické odhady funkcí. Základní pravděpodobnostní modely, linearita
střední hodnoty, použití rozptylu, Markovova nerovnost a aplikace na konkrétní příklady. Černovova nerovnost. Lovászovo lokální lemma.
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 | |
NDMI087 | Analytická kombinatorika | 4 | — | 2/1 Zk | |
NDMI025 | Pravděpodobnostní algoritmy | 5 | — | 2/2 Z+Zk | |
NTIN022 | Pravděpodobnostní techniky | 5 | 2/2 Z+Zk | — |
3. Polyedrální optimalizace
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 | 4 | 2/1 Z+Zk | — | |
NDMI065 | Teorie matroidů | 5 | — | 2/2 Z+Zk | |
NOPT034 | Matematické programování a polyedrální kombinatorika | 4 | — | 2/1 Z+Zk |
4. Grafové algoritmy
Pokročilé algoritmy pro nejkratší cesty, tranzitivní uzávěr, toky v sítích, řezy, párování
a minimální kostry, testování rovinnosti grafů a kreslení do roviny. Grafové datové struktury: union-find,
link/cut stromy, E-T stromy, plně dynamické udržování komponent souvislosti, společní předchůdci
ve stromech (LCA).
Doporučené předměty
kód | Předmět | Kredity | ZS | LS | |
NDMI010 | Grafové algoritmy | 3 | 2/0 Zk | — | |
NDMI088 | Grafové algoritmy 2 | 3 | — | 2/0 Zk | |
NTIN067 | Datové struktury 2 | 3 | — | 2/0 Zk |
Zaměření: Geometrie a matematické struktury v informatice
Zkušební okruhy
- 1. Kombinatorická a výpočetní geometrie
- 2. Struktury v informatice
- 3. Topologie v informatice a kombinatorice
- 4. Teorie kategorií v informatice
- 5. Teorie čísel v informatice
- 2. Struktury v informatice
Zkušební požadavky
1. Kombinatorická a výpočetní geometrie
Základní věty o konvexních množinách (Hellyho, Radonova, Carathéodoryho, o oddělování) a jejich rozšíření
(zlomková Hellyho věta, barevná Carathéodoryho věta, Tverbergova věta), Minkowského věta o mřížkách, incidence bodů
a přímek, geometrická dualita, konvexní mnohostěny (základní vlastnosti, kombinatorická složitost), Voroného diagramy,
konvexně nezávislé množiny, půlící přímky, složitost dolní obálky úseček.
Doporučené předměty
kód | Předmět | Kredity | ZS | LS | |
NDMI009 | Základy kombinatorické a výpočetní geometrie | 5 | 2/2 Z+Zk | — | |
NDMI013 | Kombinatorická a výpočetní geometrie 2 | 5 | — | 2/2 Z+Zk |
2. Struktury v informatice
Relace a relační struktury. Částečně uspořádané množiny. Suprema a infima, polosvazy a svazy.
Věty o pevných bodech. Distributivní svazy, Booleovy a Heytingovy algebry. Základy univerzální algebry.
Základy obecné topologie a základní topologické konstrukce. Scottova topologie. DCPO a domény.
Doporučené předměty
kód | Předmět | Kredity | ZS | LS | |
NMAI064 | Matematické struktury | 5 | — | 2/2 Z+Zk | |
NMAI066 | Topologické a algebraické metody | 3 | — | 2/0 Zk |
3. Topologie v informatice a kombinatorice
Základy metrické a obecné topologie. Topologické konstrukce, speciální
prostory, kompaktnost a souvislost. Simpliciální komplexy, simpliciální zobrazení.
Jordanova věta o kružnici (informativně, její místo v diskrétní matematice). Borsukova–Ulamova
věta a její aplikace: věta o sendviči, věta o náhrdelníku, barevnost Kneserových grafů.
Brouwerova věta o pevném bodu.
Doporučené předměty
kód | Předmět | Kredity | ZS | LS | |
NMAI064 | Matematické struktury | 5 | — | 2/2 Z+Zk | |
NDMI014 | Topologické metody v kombinatorice | 5 | — | 2/2 Z+Zk |
4. 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 | — |
5. Teorie čísel v informatice
Diofantické aproximace (Dirichletova věta, Fareyovy zlomky, transcendentní čísla). Diofantické rovnice (Pellova rovnice, Thueho rovnice,
věta o čtyřech čtvercích, desátý Hilbertův problém). Prvočísla (odhady počtů prvočísel, 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
- 2. Diskrétní optimalizační procesy
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 programování. 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 | 5 | — | 2/2 Z+Zk | |
NOPT018 | Základy nelineární optimalizace | 5 | 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 | 5 | 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í | 5 | — | 2/2 Z+Zk | |
NOPT017 | Vícekriteriální optimalizace | 3 | — | 2/0 Zk |
4. Parametrické programování a intervalové metody
Obory stability řešení, jednoparametrické a víceparametrické programování, vztah k vícekriteriální optimalizaci. Intervalová lineární algebra
(soustavy lineárních 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 | |
NOPT051 | Intervalové metody | 5 | 2/2 Z+Zk | — |