Informatika - 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

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

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.

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ň 5 kreditů:

¹Pro 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.

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

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

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

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

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

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

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

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

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

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

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

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

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í, 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