Matematika pro informační technologie

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

2. rok studia

Shrnutí studijního plánu

Povinné předměty

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.

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.

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.

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.

Ú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.