Matematika pro informační technologie

Tato stránka vychází z podkladů pro tištěné studijní plány (tzv. Karolinku).

Garantující pracoviště: Katedra algebry
Oborový garant: doc. Mgr. Pavel Příhoda, Ph.D.

Studijní program je orientován zejména na prohloubení a algoritmické uchopení teoretických znalostí matematických oborů, které nacházejí uplatnění v informačních technologiích. V rámci studijního programu se lze zaměřit na kryptologii, počítačové vidění a robotiku nebo zpracování obrazu a počítačovou grafiku. Absolvent má rozvinuté analytické schopnosti, je schopen identifikovat matematickou podstatu problémů z IT praxe a umí aplikovat složitější matematickou teorii a další odborné znalosti k řešení těchto problémů. Absolventi naleznou uplatnění ve firmách zaměřených na vývoj náročných, specializovaných aplikací.

Vstupní požadavky

Předpokládáme, že student tohoto programu má na počátku prvního ročníku dostatečné znalosti z následujících oborů a oblastí:

Kvalitní základy lineární algebry, reálné analýzy a teorie pravděpodobnosti.
Základy obecné algebry pokrývající dělitelnost v obecných oborech integrity, vlastnosti polynomiáních okruhů, konečná tělesa, základy teorie grup a Galoisovy teorie, elementární teorie čísel.
Výpočetní aspekty uvedených disciplín: základní maticové algoritmy, diskrétní Fourierova transformace a modulární aritmetika, aritmetika polynomů. Základní ponětí o aplikacích (kryptografie, samoopravné kódy, geometrické modelování). Základy algoritmizace a programování v jazyce Python.
Pasivní znalost angličtiny umožňující dostatečné porozumění matematickým přenáškám a odborným textům.

Studentům, kteří tyto požadavky nesplňují, může garant studijního programu stanovit způsob jejich doplnění, například absolvováním vybraných předmětů bakalářského studia v rámci individuálního studijního plánu.

Doporučený průběh studia

Podrobnější informace k doporučenému průběhu studia lze najít na stránkách http://garant.karlin.mff.cuni.cz/stud/nmgr_mit_20.shtml. Při volbě povinně volitelných předmětů v průběhu studia je potřeba přihlédnout k požadavkům ke státní závěrečné zkoušce.

1. rok studia

kódPředmětKredityZSLS
NMMB409Konvexní optimalizace 94/2 Z+Zk
NMMB411Algoritmy na mřížích 42/1 Z+Zk
NMMB413Algoritmy na polynomech 42/1 Z+Zk
NMMB415Automaty a výpočetní složitost 63/1 Z+Zk
NSZZ023Diplomová práce I 60/4 Z
 Volitelné a povinně volitelné předměty 31  

2. rok studia

kódPředmětKredityZSLS
NSZZ024Diplomová práce II 90/6 Z
NSZZ025Diplomová práce III 150/10 Z
 Volitelné a povinně volitelné předměty 36  

Shrnutí studijního plánu

Povinné předměty

kódPředmětKredityZSLS
NMMB409Konvexní optimalizace 94/2 Z+Zk
NMMB411Algoritmy na mřížích 42/1 Z+Zk
NMMB413Algoritmy na polynomech 42/1 Z+Zk
NMMB415Automaty a výpočetní složitost 63/1 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 1

Z těchto předmětů je potřeba získat alespoň 46 kreditů. V závorce je uvedeno, ke kterému tématu státní zkoušky se přednáška vztahuje. Předměty, u kterých tato informace není, jsou obecného charakteru.

kódPředmětKredityZSLS
NDMI018Aproximační a online algoritmy*52/2 Z+Zk
NDMI025Pravděpodobnostní algoritmy*52/2 Z+Zk
NMAG331Matematická logika 32/0 Zk
NMAG401Algebraická geometrie 52/2 Z+Zk
NMAG403Kombinatorika 52/2 Z+Zk
NMAG430Algebraická teorie čísel 63/1 Z+Zk
NMAG436Křivky a funkční tělesa(2C)63/1 Z+Zk
NMAG535Výpočetní logika(2A)52/2 Z+Zk
NMAG563Úvod do složitosti CSP 32/0 Zk
NMMB331Booleovské funkce(2C)32/0 Zk
NMMB333Základy analýzy dat 52/2 Z+Zk
NMMB402Číselné algoritmy(2A)42/1 Z+Zk
NMMB404Kryptoanalýza(2C)63/1 Z+Zk
NMMB430Algoritmy na eliptických křivkách(2A,2C)42/1 Z+Zk
NMMB432Náhodnost a výpočty(2C)42/1 Zk
NMMB433Geometrie pro počítačovou grafiku(2E)32/0 Zk
NMMB437Právní aspekty ochrany dat(2C)32/0 Zk
NMMB438Základy spojité optimalizace(2B)62/2 Z+Zk
NMMB440Geometrie počítačového vidění(2D)*62/2 Z+Zk
NMMB442Geometrické problémy v robotice(2D)*62/2 Z+Zk
NMMB460Kryptoanalýza na úrovni instrukcí(2C)40/4 Z
NMMB464Úvod do výpočetní topologie(2A,2D,2E)42/1 Z+Zk
NMMB498Výběrová přednáška MIT 1 32/0 Zk
NMMB499Výběrová přednáška MIT 2 32/0 Zk
NMMB501Zabezpečení síťových protokolů(2C)52/2 Z+Zk
NMMB531Číselné síto(2A)32/0 Zk
NMMB532Standardy a kryptografie(2C)32/0 Zk
NMMB534Kvantová informace 63/1 Z+Zk
NMMB538Eliptické křivky a kryptografie(2C)63/1 Z+Zk
NMMO537Sedlobodové úlohy a jejich řešení(2B)52/2 Z+Zk
NMNV411Algoritmy maticových iteračních metod(2B)52/2 Z+Zk
NMNV412Analýza maticových iteračních metod – principy a souvislosti(2B)64/0 Zk
NMNV503Numerické metody optimalizace 1(2B)63/1 Z+Zk
NMNV531Inverzní úlohy a regularizace(2B)52/2 Z+Zk
NMNV532Paralelní maticové výpočty(2B)52/2 Z+Zk
NMNV533Řídké matice v numerické matematice(2B)52/2 Z+Zk
NOPT016Celočíselné programování(2B)*52/2 Z+Zk
NPFL138Hluboké učení 83/4 Z+Zk
NPGR010Pokročilá 3D grafika pro film a hry(2E)52/2 Z+Zk
NPGR013Speciální funkce a transformace ve zpracování obrazu(2E)32/0 Zk
NPGR016Aplikovaná výpočetní geometrie(2D,2E)52/1 Z+Zk
NPGR029Variační metody ve zpracování obrazu(2E)32/0 Zk
NTIN022Pravděpodobnostní techniky 52/2 Z+Zk
NTIN104Foundations of theoretical cryptography(2C)42/1 Z+Zk
NMNV468Numerical Linear Algebra for data science and informatics(2E)52/2 Z+Zk

* Předmět je obvykle vyučován pouze jednou za dva roky.

Povinně volitelné předměty 2

Tyto předměty pokrývají témata zkoušená u státních závěrečných zkoušek. V závorce je uvedeno, ke kterému tématu státní zkoušky se vztahují. Tyto předměty jsou také prvky skupiny Povinně volitelných předmětů 1. Alespoň 17 kreditů ze 46 kreditů ze skupiny Povinně volitelných předmětů 1 musí být z následujícího užšího výběru.

kódPředmětKredityZSLS
NMMB331Booleovské funkce(2C)32/0 Zk
NMMB402Číselné algoritmy(2A)42/1 Z+Zk
NMMB404Kryptoanalýza(2C)63/1 Z+Zk
NMMB432Náhodnost a výpočty(2C)42/1 Zk
NMMB433Geometrie pro počítačovou grafiku(2E)32/0 Zk
NMMB440Geometrie počítačového vidění(2D)62/2 Z+Zk
NMMB442Geometrické problémy v robotice(2D)62/2 Z+Zk
NMNV411Algoritmy maticových iteračních metod(2B)52/2 Z+Zk
NMNV503Numerické metody optimalizace 1(2B)63/1 Z+Zk
NMNV533Řídké matice v numerické matematice(2B)52/2 Z+Zk
NPGR013Speciální funkce a transformace ve zpracování obrazu(2E)32/0 Zk
NPGR029Variační metody ve zpracování obrazu(2E)32/0 Zk

Povinně volitelné předměty 3

Tuto skupinu tvoří vybrané vědecké či pracovní semináře. Za předměty z této skupiny je třeba získat alespoň 4 kredity.

kódPředmětKredityZSLS
NMMB361Kryptografické otázky současnosti 20/2 Z0/2 Z
NMMB451Aplikace matematiky v informatice 30/2 Z
NMMB473Matematické modelování bezpečnosti 20/2 Z0/2 Z
NMMB452Seminář z matematiky inspirované kryptografií 30/2 Z0/2 Z
NMMB453Studentský logický seminář 20/2 Z0/2 Z
NMMB471Výběrový seminář z MIT 20/2 Z0/2 Z
NMMB551Seminář z kombinatorické, algoritmické a finitní algebry 20/2 Z0/2 Z
NMNV451Seminář numerické matematiky 20/2 Z0/2 Z

Státní závěrečná zkouška

Podmínky pro přihlášení ke státní závěrečné zkoušce

Podmínky pro přihlášení k poslední části státní závěrečné zkoušky

Získání alespoň 120 kreditů.
Splnění všech povinných předmětů studijního plánu.
Splnění Povinně volitelných předmětů 1 v rozsahu alespoň 46 kreditů. Z toho má být alespoň 17 kreditů z užšího výběru Povinně volitelných předmětů 2.
Splnění Povinně volitelných předmětů 3 v rozsahu alespoň 4 kredity.
Odevzdání vypracované diplomové práce ve stanoveném termínu.

Podmínky pro přihlášení k jiné než poslední části státní závěrečné zkoušky

Rámcové podmínky jsou stanoveny vnitřním předpisem Pravidla pro organizaci studia na MFF UK a v programu Matematika pro informační technologie je nutné splnit tyto podmínky:

Získání alespoň 105 kreditů.
Pokud je jinou než poslední částí státní závěrečné zkoušky její ústní část, je nutné splnění všech povinných předmětů studijního plánu s výjimkou NSZZ025 Diplomová práce III a splnění Povinně volitelných předmětů 3 v rozsahu alespoň 4 kredity.
Pokud je jinou než poslední částí státní závěrečné zkoušky obhajoba, je nutné splnění všech povinných předmětů a odevzdání vypracované diplomové práce ve stanoveném termínu.
Splnění Povinně volitelných předmětů 1 v rozsahu alespoň 46 kreditů. Z toho alespoň 17 kreditů z užšího výběru Povinně volitelných předmětů 2.

Ústní část státní závěrečné zkoušky

Ústní část státní závěrečné zkoušky studijního programu Matematika pro informační technologie se skládá z dvou tematických okruhů. Z tematického okruhu 1 dostane student jednu otázku. Tématický okruh 2 je rozdělen na podokruhy 2A, 2B, 2C, 2D, 2E. Student si vybere dva z nich a ke každému zvolenému tématu dostane jednu otázku. Očekávané kombinace 2A + 2C, 2B + 2D, 2B + 2E odpovídají volbě zaměření.

Podrobnější vysvětlení požadavků k ústní části státní závěrečné zkoušky lze najít na stránkách http://garant.karlin.mff.cuni.cz/stud/nmgr_mit_20_szz.shtml.

Požadavky k ústní části státní závěrečné zkoušky

Tématický okruh 1

1. Matematika pro informační technologie
Výpočetní modely, algoritmická rozhodnutelnost, základní složitostní třídy, regulární jazyky. Základní metody konvexní optimalizace. Gröbnerovy báze a Buchbergerův algoritmus. Mříže a algoritmus LLL.

Tématický okruh 2

2A Algebraické a číselné algoritmy
Rozklady polynomů: Berlekampův algoritmus, Henselovo zdvihání a Berlekampův- Henselův algoritmus. Aplikace Gröbnerových bází v algebraické geometrii. Číselné algoritmy: Pollardova rho a p-1 metoda, algoritmus CFRAC, ECM, kvadratické síto. Souvislost faktorizace a diskrétního algoritmu.

2B Algoritmy pro lineární algebru a optimalizaci
Řídký Choleského a LU rozklad, řídký QR rozklad. Krylovovské iterační metody pro řešení soustav lineárních algebraických rovnic a lineárních aproximačních problémů, včetně konstrukce algebraických předpodmínění. Metody pro řešení nelineárních algebraických rovnic a jejich soustav, metody pro minimalizaci funkcionálu bez omezení, lokální a globální konvergence metod.

2C Kryptologie
Základy Booleovských funkcí (ohnuté funkce, APN a AB funkce, ekvivalence, S-boxy, Walshova transformace a LAT, diferenční uniformita a DDT). Posloupnosti dané posuvnými registry. Základní kryptoanalytické útoky na blokové šifry (diferenciální a lineární kryptoanalýza, útoky vyšších řádů, meet-in-the-middle) a proudové šifry (korelace, algebraické útoky), útoky postranním kanálem. Aplikace mříží: NTRU, aplikace LLL (např. útok na RSA s malým veřejným exponentem). Pravděpodobnostní složitostní třídy, pseudonáhodné generátory.

2D Počítačové vidění a robotika
Matematický model perspektivní kamery. Výpočet pohybu kalibrované kamery z obrazů neznámé scény. 3D rekonstrukce ze dvou obrazů neznámé scény. Geometrie tří kalibrovaných kamer. Denavit-Hartenbergův popis kinematiky manipulátoru. Inverzní kinematická úloha pro šestistupňový sériový manipulátor – formulace a řešení. Kalibrace parametrů manipulátoru – formulace a řešení.

2E Zpracování obrazu a počítačová grafika
Modelování inverzních problémů, regularizační metody, digitalizace obrazu, zaostřování a odšumování obrazu, detekce hran, obrazová registrace, komprese, syntéza obrazu, metody compressed sensing, analytická, kinematická a diferenciální geometrie.