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

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ódPředmětKredityZSLS
NTIN090Základy složitosti a vyčíslitelnosti 42/1 Z+Zk
NTIN066Datové struktury 1 62/2 Z+Zk
NMAI064Matematické struktury 52/2 Z+Zk
NSZZ023Diplomová práce I 60/4 Z
NSZZ024Diplomová práce II 90/6 Z
NSZZ025Diplomová práce III 150/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ódPředmětKredityZSLS
NAIL076Logické programování 1 32/0 Zk
NDMI010Grafové algoritmy 32/0 Zk
NDMI013Kombinatorická a výpočetní geometrie 2 52/2 Z+Zk
NDMI014Topologické metody v kombinatorice 52/2 Z+Zk
NDMI015Kombinatorické počítání 32/0 Zk
NDMI018Aproximační a online algoritmy 52/2 Z+Zk
NDMI025Pravděpodobnostní algoritmy 52/2 Z+Zk
NDMI028Aplikace lineární algebry v kombinatorice 52/2 Z+Zk
NDMI036Kombinatorické struktury 32/0 Zk
NDMI037Geometrické reprezentace grafů 1 32/0 Zk
NDMI045Analytická a kombinatorická teorie čísel 32/0 Zk
NDMI055Vybrané kapitoly z kombinatoriky 1 32/0 Zk
NDMI056Vybrané kapitoly z kombinatoriky 2 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ů 52/2 Z+Zk
NDMI066Algebraická teorie čísel 32/0 Zk
NDMI067Toky, cesty a řezy 32/0 Zk
NDMI074Algoritmy a jejich implementace 52/2 Z+Zk
NDMI087Analytická kombinatorika 42/1 Zk
NDMI088Grafové algoritmy 2 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++ 52/2 Z+Zk
NMMA901Úvod do komplexní analýzy (O) 52/2 Z+Zk
NMMA931Úvod do funkcionální analýzy (O) 84/2 Z+Zk
NOPT008Algoritmy nelineární optimalizace 52/2 Z+Zk
NOPT016Celočíselné programování 52/2 Z+Zk
NOPT017Vícekriteriální optimalizace 32/0 Zk
NOPT034Matematické programování a polyedrální kombinatorika 42/1 Z+Zk
NOPT042Programování s omezujícími podmínkami 52/2 Z+Zk
NOPT051Intervalové metody 52/2 Z+Zk
NTIN017Paralelní algoritmy 32/0 Zk
NTIN022Pravděpodobnostní techniky 52/2 Z+Zk
NTIN023Dynamické grafové datové struktury 32/0 Zk
NTIN063Složitost 42/1 Z+Zk
NTIN064Vyčíslitelnost 32/0 Zk
NTIN067Datové struktury 2 32/0 Zk
NTIN100Základy přenosu a zpracování informace 42/1 Z+Zk
NTIN103Introduction to Parameterized Algorithms 52/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ódPředmětKredityZSLS
NDMI073Kombinatorika a grafy 3 52/2 Z+Zk
NOPT018Základy nelineární optimalizace 52/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ódPředmětKredityZSLS
NDMI009Základy kombinatorické a výpočetní geometrie 52/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ódPředmětKredityZSLS
NTIN090Základy složitosti a vyčíslitelnosti 42/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ódPředmětKredityZSLS
NTIN066Datové struktury 1 62/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

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ódPředmětKredityZSLS
NDMI037Geometrické reprezentace grafů 1 32/0 Zk
NDMI059Grafové minory a stromové rozklady 32/0 Zk
NDMI060Barevnost grafů a kombinatorických struktur 32/0 Zk
NDMI073Kombinatorika a grafy 3 52/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ódPředmětKredityZSLS
NDMI015Kombinatorické počítání 32/0 Zk
NDMI087Analytická kombinatorika 42/1 Zk
NDMI025Pravděpodobnostní algoritmy 52/2 Z+Zk
NTIN022Pravděpodobnostní techniky 52/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ódPředmětKredityZSLS
NTIN090Základy složitosti a vyčíslitelnosti 42/1 Z+Zk
NDMI065Teorie matroidů 52/2 Z+Zk
NOPT034Matematické programování a polyedrální kombinatorika 42/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).

Recommended courses

kódPředmětKredityZSLS
NDMI010Grafové algoritmy 32/0 Zk
NDMI088Grafové algoritmy 2 32/0 Zk
NTIN067Datové struktury 2 32/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

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ódPředmětKredityZSLS
NDMI009Základy kombinatorické a výpočetní geometrie 52/2 Z+Zk
NDMI013Kombinatorická a výpočetní geometrie 2 52/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ódPředmětKredityZSLS
NMAI064Matematické struktury 52/2 Z+Zk
NMAI066Topologické a algebraické metody 32/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ódPředmětKredityZSLS
NMAI064Matematické struktury 52/2 Z+Zk
NDMI014Topologické metody v kombinatorice 52/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ódPředmětKredityZSLS
NMAI065Základy teorie kategorií pro informatiky 32/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ó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 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ódPředmětKredityZSLS
NOPT008Algoritmy nelineární optimalizace 52/2 Z+Zk
NOPT018Základy nelineární optimalizace 52/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 52/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í 52/2 Z+Zk
NOPT017Vícekriteriální optimalizace 32/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ódPředmětKredityZSLS
NOPT017Vícekriteriální optimalizace 32/0 Zk
NOPT051Intervalové metody 52/2 Z+Zk