2.8 Matematika pro informační technologie

2.8 Matematika pro informační technologie

Garantující pracoviště: Katedra algebry
Oborový garant: prof. RNDr. Aleš Drápal, CSc., DSc.

Obor Matematika pro informační technologie má jeden studijní plán. Tento studijní plán je shodný se studijním plánem NN dobíhajícího oboru Matematické metody informační bezpečnosti.

Zaměření oboru Matematika pro informační technologie

Obor Matematika pro informační technologie umožňuje specializaci na jedno ze dvou zaměření.

1. Zaměření Matematika pro informační bezpečnost (IB) poskytuje hlubší znalosti teorie čísel, teorie samoopravných kódů, teorie eliptických křivek, a dále počítačové algebry aplikované na některé z těchto teorií. Pozornost je věnována ale i praktickým aspektům jako jsou kryptoanalytické útoky, zabezpečení toku internetových dat, kryptografické standardy a právní ochrana dat.
2. Zaměření Počítačová geometrie (PG) umožňuje získat hlubší znalosti v algebraických a geometrických oborech spolu s jejich použitím v geometrii počítačového vidění a robotiky, počítačové grafice a zpracování obrazu, optimalizačních metodách a numerické lineární algebře.

Volba zaměření

Volba zaměření zahrnuje tři postupně kroky:

 Výběr tématu diplomové práce na počátku prvního ročníku.
 Výběr povinně volitelných předmětů během studia.
 Výběr dvou volitelných okruhů ústní části státní závěrečné zkoušky, při přihlášení ke státní závěrečné zkoušce.

Vstupní požadavky

Předpokládáme, že student tohoto oboru 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 komutativní a počítačové algebry (Galoisova teorie, celistvá rozšíření, diskrétní Fourierova transformace). Modulární aritmetika, multiplikativní grupy. Konečná tělesa, základní třídy samoopravných kódů. Grupová operace na eliptických křivkách.
Základy teoretické kryptografie a geometrického modelování. Programování v jazyce C.
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_ob_mmit.shtml.

1. rok studia

kód Předmět Kredity ZS LS
NMMB405 Složitost pro kryptografii   6 4/0 Zk
NMMB409 Konvexní optimalizace   9 4/2 Z+Zk
NMMB403 Počítačová algebra 2   6 3/1 Z+Zk
NMMB407 Pravděpodobnost a kryptografie   6 4/0 Zk
NSZZ023 Diplomová práce I   6 0/4 Z
  Volitelné a povinně volitelné předměty   27    

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    

Zaměření oboru se rozlišují podle doporučených povinně volitelných předmětů.

Povinně volitelné předměty pro zaměření Matematika pro informační bezpečnost

kód Předmět Kredity ZS LS
NMMB333 Základy analýzy dat   5 2/2 Z+Zk
NMMB331 Booleovské funkce   3 2/0 Zk
NTIN104 Foundations of theoretical cryptography   5 2/1 Z+Zk
NMMB401 Automaty a konvoluční kódy   6 3/1 Z+Zk
NMMB402 Číselné algoritmy   6 3/1 Z+Zk
NMMB404 Kryptoanalytické útoky   6 3/1 Z+Zk
NMMB501 Zabezpečení síťových protokolů   5 2/2 Z+Zk
NMAG436 Křivky a funkční tělesa   6 4/0 Zk
NMMB431 Autentifikační schémata * 3 2/0 Zk
NMMB436 Steganografie a digitální média   3 2/0 Zk
NMMB437 Právní aspekty ochrany dat   3 2/0 Zk
NMMB531 Číselné síto   3 2/0 Zk
NMMB532 Standardy a kryptografie   3 2/0 Zk
NMMB533 Matematický software * 3 1/1 Z+Zk
NMMB534 Kvantová informace   6 3/1 Z+Zk
NMMB538 Eliptické křivky a kryptografie   6 3/1 Z+Zk

*) Tyto předměty nebudou od akademického roku 2018/19 vyučovány.

Povinně volitelné předměty pro zaměření Počítačová geometrie

kód Předmět Kredity ZS LS
NMMB333 Základy analýzy dat   5 2/2 Z+Zk
NMAG401 Algebraická geometrie   5 2/2 Z+Zk
NMMB440 Geometrie počítačového vidění   6 2/2 Z+Zk
NMMB442 Geometrické problémy v robotice   6 2/2 Z+Zk
NMAG563 Úvod do složitosti CSP   3 2/0 Zk
NMMB536 Optimalizace a aproximace CSP   6 2/2 Z+Zk
NMNV531 Inverzní úlohy a regularizace   5 2/2 Z+Zk
NMNV407 Maticové iterační metody 1   6 4/0 Zk
NMNV438 Maticové iterační metody 2   5 2/2 Z+Zk
NMNV534 Numerické metody optimalizace   5 2/2 Z+Zk
NMMB535 Komprimované snímání   6 2/2 Z+Zk
NPGR013 Speciální funkce a transformace ve zpracování obrazu   3 2/0 Zk
NPGR010 Počítačová grafika III   6 2/2 Z+Zk
NMMB433 Geometrie pro počítačovou grafiku   3 2/0 Zk
NPGR029 Variační metody ve zpracování obrazu   3 2/0 Zk

Shrnutí studijního plánu

Povinné předměty

kód Předmět Kredity ZS LS
NMMB403 Počítačová algebra 2   6 3/1 Z+Zk
NMMB405 Složitost pro kryptografii   6 4/0 Zk
NMMB407 Pravděpodobnost a kryptografie   6 4/0 Zk
NMMB409 Konvexní optimalizace   9 4/2 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

Z těchto předmětů je potřeba získat alespoň 45 kreditů. Předměty doporučené pro zaměření Matematika pro informační bezpečnost jsou označené (IB). Předměty doporučené pro zaměření Počítačová geometrie jsou označené (PG).

kód Předmět Kredity ZS LS
NMMB401 Automaty a konvoluční kódy (IB) 6 3/1 Z+Zk
NMMB333 Základy analýzy dat (IB, PG) 5 2/2 Z+Zk
NMMB331 Booleovské funkce (IB) 3 2/0 Zk
NTIN104 Foundations of theoretical cryptography (IB) 5 2/1 Z+Zk
NMMB402 Číselné algoritmy (IB) 6 3/1 Z+Zk
NMMB404 Kryptoanalytické útoky (IB) 6 3/1 Z+Zk
NMMB501 Zabezpečení síťových protokolů (IB) 5 2/2 Z+Zk
NMAG436 Křivky a funkční tělesa (IB) 6 4/0 Zk
NMMB431 Autentifikační schémata *, (IB) 3 2/0 Zk
NMMB436 Steganografie a digitální média (IB) 3 2/0 Zk
NMMB437 Právní aspekty ochrany dat (IB) 3 2/0 Zk
NMMB531 Číselné síto (IB) 3 2/0 Zk
NMMB532 Standardy a kryptografie (IB) 3 2/0 Zk
NMMB533 Matematický software *, (IB) 3 1/1 Z+Zk
NMMB534 Kvantová informace (IB) 6 3/1 Z+Zk
NMMB538 Eliptické křivky a kryptografie (IB) 6 3/1 Z+Zk
NMAG401 Algebraická geometrie (PG) 5 2/2 Z+Zk
NMMB440 Geometrie počítačového vidění (PG) 6 2/2 Z+Zk
NMMB442 Geometrické problémy v robotice (PG) 6 2/2 Z+Zk
NMAG563 Úvod do složitosti CSP (PG) 3 2/0 Zk
NMMB536 Optimalizace a aproximace CSP (PG) 6 2/2 Z+Zk
NMNV531 Inverzní úlohy a regularizace (PG) 5 2/2 Z+Zk
NMNV407 Maticové iterační metody 1 (PG) 6 4/0 Zk
NMNV438 Maticové iterační metody 2 (PG) 5 2/2 Z+Zk
NMNV534 Numerické metody optimalizace (PG) 5 2/2 Z+Zk
NMMB535 Komprimované snímání (PG) 6 2/2 Z+Zk
NPGR013 Speciální funkce a transformace ve zpracování obrazu (PG) 3 2/0 Zk
NPGR010 Počítačová grafika III (PG) 6 2/2 Z+Zk
NMMB433 Geometrie pro počítačovou grafiku (PG) 3 2/0 Zk
NPGR029 Variační metody ve zpracování obrazu (PG) 3 2/0 Zk

*) Tyto předměty nebudou od akademického roku 2018/19 vyučovány.

Doporučené volitelné předměty

kód Předmět Kredity ZS LS
NMMB451 Aplikace matematiky v informatice   3 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
NMMB551 Seminář z kombinatorické, algoritmické a finitní algebry   2 0/2 Z 0/2 Z
NPGR022 Speciální seminář ze zpracování obrazu   2 0/2 Z 0/2 Z
NMAG337 Úvod do teorie grup   5 2/2 Z+Zk
NSWI090 Počítačové sítě   3 2/0 Zk
NSWI021 Počítačové sítě II   3 2/0 Zk
NSWI045 Rodina protokolů TCP/IP   3 2/0 Zk
NPGR003 Základy počítačové grafiky   5 2/2 Z+Zk
NPGR004 Počítačová grafika II   5 2/1 Z+Zk

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ů v rozsahu alespoň 45 kreditů.
 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 oboru Matematické metody informační bezpečnosti se skládá z dvou tematických okruhů. Z tematického okruhu 1 dostane student jednu otázku. Z tematického okruhu 2 si student zvolí buď dvě z variant 2A, 2B, 2C pro zaměření Matematika pro informační bezpečnost, nebo dvě z variant 2D, 2E, 2F, 2G pro zaměření Počítačová geometrie. Z každé zvolené varianty dostane jednu otázku.

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_ob_mmit_szz.shtml.

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

Společný základ

1.Základní matematické obory.
Složitostní třídy a výpočetní modely, náhodnost a pseudonáhodnost, algoritmy pro práci s algebraickými strukturami, konvexní optimalizace.

Užší zaměření

2A Informace a kódy
Klasická a kvantová informace a její přenos. Důsledky kvantové Fourierovy transformace pro kryptografii. Konvoluční kódy. Práce se skrytou a poškozenou informací.

2B Číselné algoritmy
Faktorizace: metody Pollard rho a Pollard p-1, algoritmus CFRAC (včetně aproximace odmocniny pomocí řetězových zlomků a řešení Pellovy rovnice), a kvadratické síto (včetně Tonelli-Shanksova algoritmu). Základní metody řešení diskrétního logaritmu: Pohlig-Hellman, Baby steps-giant steps a indexový kalkul.

2C Eliptické křivky
Základní vlastnosti algebraických funkčních těles a jejich grupy divisorů. Weierstrassova normální forma eliptické křivky - ekvivalence a odvození. Picardova grupa a sčítání bodů eliptické křivky. Morfismy, endomorfismy a izogenie. Využití v kryptografii.

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.

2F Aproximace a optimalizace
Konvexní optimalizační problémy, dualita, Lagrangeova duální funkce. Algoritmy pro řešení úloh konvexní optimalizace, metoda vnitřního bodu. Problém splnitelnosti omezení (CSP), algebraický přístup k řešení dichotomické hypotézy. Vážený problém splnitelnosti omezení (vCSP). Příklady výpočetních problémů, které lze popsat v jazyku vCSP, algebraická teorie. Řešení problémů s extrémně velkým vstupem.

2G Numerická lineární algebra
LU a Choleského rozklad matice, metody nejmenších čtverců, Krylovovské prostory, maticové iterační metody (Arnoldiho, Lanczosova metoda, metoda sdružených gradientů, zobecněná metoda minimálních reziduí), QR algoritmus, regularizační metody pro řešení lineárních inverzních problémů, numerická stabilita.