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.
- –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.
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ód | Předmět | Kredity | ZS | LS | |
NMMB409 | Konvexní optimalizace | 9 | 4/2 Z+Zk | — | |
NMMB411 | Algoritmy na mřížích | 4 | 2/1 Z+Zk | — | |
NMMB413 | Algoritmy na polynomech | 4 | 2/1 Z+Zk | — | |
NMMB415 | Automaty a výpočetní složitost | 6 | 3/1 Z+Zk | — | |
NSZZ023 | Diplomová práce I | 6 | — | 0/4 Z | |
Volitelné a povinně volitelné předměty | 30 |
2. rok studia
kód | Předmět | Kredity | ZS | LS | |
NSZZ024 | Diplomová práce II | 9 | 0/6 Z | — | |
NSZZ025 | Diplomová práce III | 15 | — | 0/10 Z | |
Volitelné a povinně volitelné předměty | 36 |
Shrnutí studijního plánu
Povinné předměty
kód | Předmět | Kredity | ZS | LS | |
NMMB409 | Konvexní optimalizace | 9 | 4/2 Z+Zk | — | |
NMMB411 | Algoritmy na mřížích | 4 | 2/1 Z+Zk | — | |
NMMB413 | Algoritmy na polynomech | 4 | 2/1 Z+Zk | — | |
NMMB415 | Automaty a výpočetní složitost | 6 | 3/1 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 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ód | Předmět | Kredity | ZS | LS | |
NDMI018 | Aproximační a online algoritmy | 5 | — | 2/2 Z+Zk | |
NDMI025 | Pravděpodobnostní algoritmy | 5 | — | 2/2 Z+Zk | |
NMAG331 | Matematická logika | 3 | 2/0 Zk | — | |
NMAG401 | Algebraická geometrie | 5 | 2/2 Z+Zk | — | |
NMAG403 | Kombinatorika | 5 | 2/2 Z+Zk | — | |
NMAG430 | Algebraická teorie čísel | 6 | — | 3/1 Z+Zk | |
NMAG436 | Křivky a funkční tělesa | (2C) | 6 | — | 3/1 Z+Zk |
NMAG535 | Výpočetní logika | (2A) | 5 | 2/2 Z+Zk | — |
NMAG563 | Úvod do složitosti CSP | 3 | 2/0 Zk | — | |
NMMB331 | Booleovské funkce | (2C) | 3 | 2/0 Zk | — |
NMMB333 | Základy analýzy dat | 5 | 2/2 Z+Zk | — | |
NMMB402 | Číselné algoritmy | (2A) | 4 | — | 2/1 Z+Zk |
NMMB404 | Kryptoanalýza | (2C) | 6 | — | 3/1 Z+Zk |
NMMB430 | Algoritmy na eliptických křivkách | (2A,2C) | 4 | — | 2/1 Z+Zk |
NMMB432 | Náhodnost a výpočty | (2C) | 4 | — | 2/1 Zk |
NMMB433 | Geometrie pro počítačovou grafiku | (2E) | 3 | — | 2/0 Zk |
NMMB437 | Právní aspekty ochrany dat | (2C) | 3 | 2/0 Zk | — |
NMMB438 | Základy spojité optimalizace | (2B) | 6 | — | 2/2 Z+Zk |
NMMB440 | Geometrie počítačového vidění | (2D)* | 6 | — | 2/2 Z+Zk |
NMMB442 | Geometrické problémy v robotice | (2D)* | 6 | 2/2 Z+Zk | — |
NMMB460 | Kryptoanalýza na úrovni instrukcí | (2C) | 4 | — | 0/4 Z |
NMMB464 | Úvod do výpočetní topologie | (2A,2D,2E) | 4 | — | 2/1 Z+Zk |
NMMB498 | Výběrová přednáška MIT 1 | 3 | 2/0 Zk | — | |
NMMB499 | Výběrová přednáška MIT 2 | 3 | — | 2/0 Zk | |
NMMB501 | Zabezpečení síťových protokolů | (2C) | 5 | 2/2 Z+Zk | — |
NMMB531 | Číselné síto | (2A) | 3 | 2/0 Zk | — |
NMMB532 | Standardy a kryptografie | (2C) | 3 | — | 2/0 Zk |
NMMB534 | Kvantová informace | 6 | — | 3/1 Z+Zk | |
NMMB538 | Eliptické křivky a kryptografie | (2C) | 6 | 3/1 Z+Zk | — |
NMMO537 | Sedlobodové úlohy a jejich řešení | (2B) | 5 | — | 2/2 Z+Zk |
NMNV411 | Algoritmy maticových iteračních metod | (2B) | 5 | 2/2 Z+Zk | — |
NMNV412 | Analýza maticových iteračních metod – principy a souvislosti | (2B) | 6 | — | 4/0 Zk |
NMNV503 | Numerické metody optimalizace 1 | (2B) | 6 | 3/1 Z+Zk | — |
NMNV531 | Inverzní úlohy a regularizace | (2B) | 5 | 2/2 Z+Zk | — |
NMNV532 | Paralelní maticové výpočty | (2B) | 5 | — | 2/2 Z+Zk |
NMNV533 | Řídké matice v numerické matematice | (2B) | 5 | 2/2 Z+Zk | — |
NOPT016 | Celočíselné programování | (2B) | 5 | — | 2/2 Z+Zk |
NPFL114 | Hluboké učení | 7 | — | 3/2 Z+Zk | |
NPGR010 | Pokročilá 3D grafika pro film a hry | (2E) | 5 | 2/2 Z+Zk | — |
NPGR013 | Speciální funkce a transformace ve zpracování obrazu | (2E) | 3 | — | 2/0 Zk |
NPGR016 | Aplikovaná výpočetní geometrie | (2D,2E) | 5 | — | 2/1 Z+Zk |
NPGR029 | Variační metody ve zpracování obrazu | (2E) | 3 | — | 2/0 Zk |
NTIN022 | Pravděpodobnostní techniky | 5 | 2/2 Z+Zk | — | |
NTIN104 | Foundations of theoretical cryptography | (2C) | 4 | 2/1 Z+Zk | — |
* Předmět je 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ód | Předmět | Kredity | ZS | LS | |
NMMB331 | Booleovské funkce | (2C) | 3 | 2/0 Zk | — |
NMMB402 | Číselné algoritmy | (2A) | 4 | — | 2/1 Z+Zk |
NMMB404 | Kryptoanalýza | (2C) | 6 | — | 3/1 Z+Zk |
NMMB432 | Náhodnost a výpočty | (2C) | 4 | — | 2/1 Zk |
NMMB433 | Geometrie pro počítačovou grafiku | (2E) | 3 | — | 2/0 Zk |
NMMB440 | Geometrie počítačového vidění | (2D) | 6 | — | 2/2 Z+Zk |
NMMB442 | Geometrické problémy v robotice | (2D) | 6 | 2/2 Z+Zk | — |
NMNV411 | Algoritmy maticových iteračních metod | (2B) | 5 | 2/2 Z+Zk | — |
NMNV503 | Numerické metody optimalizace 1 | (2B) | 6 | 3/1 Z+Zk | — |
NMNV533 | Řídké matice v numerické matematice | (2B) | 5 | 2/2 Z+Zk | — |
NPGR013 | Speciální funkce a transformace ve zpracování obrazu | (2E) | 3 | — | 2/0 Zk |
NPGR029 | Variační metody ve zpracování obrazu | (2E) | 3 | — | 2/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ód | Předmět | Kredity | ZS | LS | |
NMMB361 | Kryptografické otázky současnosti | 2 | — | 0/2 Z | |
NMMB451 | Aplikace matematiky v informatice | 3 | — | 0/2 Z | |
NMMB473 | Matematické modelování bezpečnosti | 2 | 0/2 Z | 0/2 Z | |
NMMB452 | Seminář z matematiky inspirované kryptografií | 3 | 0/2 Z | 0/2 Z | |
NMMB453 | Studentský logický seminář | 2 | 0/2 Z | 0/2 Z | |
NMMB471 | Výběrový seminář z MIT | 2 | — | 0/2 Z | |
NMMB551 | Seminář z kombinatorické, algoritmické a finitní algebry | 2 | 0/2 Z | 0/2 Z | |
NMNV451 | Seminář numerické matematiky | 2 | 0/2 Z | 0/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
- – 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.
- – Splnění všech povinných předmětů studijního plánu.
Ú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.