Detail předmětu
Pokročilá matematika
IAM Ak. rok 2017/2018 letní semestr 5 kreditů
Předmět navazuje na povinné matematické předměty bakalářského studia. Práce s matematickým aparátem je demonstrována spolu s prohloubením znalostí oblastí matematiky úzce souvisejících s informatikou a s ukázkou jejich aplikací v informatice. Jedná se zejména o teorii čísel a její aplikaci v kryptografii; základy teorie množin a logiky, vybrané logické systémy, techniky a rozhodovací procedury s aplikací např. v databázích či softwarovém inženýrství; teorii svazů, pevných bodů, a jejich aplikace ve verifikaci; pravděpodobnost a statistiku a aplikace v analýze pravděpodobnostních systémů a umělé inteligenci.
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 26 hod. přednášky
- 18 hod. cvičení
- 8 hod. pc laboratoře
Bodové hodnocení
- 50 bodů půlsemestrální test
- 50 bodů numerická cvičení
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z předmětu
Schopnost matematické formulace, řešení problémů pomocí matematického aparátu, zejména dokazování, prohloubení a procvičení základních matematických pojmů, přehled o některých pro informatiku stěžejních oblastech matematiky a jejich aplikacích v informatice.
Rozvinutí schopnosti exaktně se vyjadřovat a používat matematický aparát.
Cíle předmětu
- Prohloubit schopnosti aplikace matematického aparátu ve vyjadřování, formulaci a řešení problémů a posílit schopnosti exaktního vyjadřování a myšlení obecně,
- rozvinout některé partie matematiky s těsnou vazbou na informatiku a ukázat souvislost s informatikou,
- usnadnit studium matematických předmětů v navazujícím magisterském studiu.
Doporučené prerekvizity
Požadované prerekvizitní znalosti a dovednosti
Základní pojmy o relacích, množinách, základy výrokové a predikátové logiky, základy algebry, základy konečných automatů.
Literatura studijní
- R. Smullyan. First-Order Logic. Dover, 1995.
Literatura referenční
- A.R. Bradley, Z. Manna. The Calculus of Computation. Springer, 2007.
- D. P. Bertsekas, J. N. Tsitsiklis. Introduction to Probability, Athena Scientific, 2008.
- M. Huth, M. Ryan. Logic in Computer Science. Modelling and Reasoning about Systems. Cambridge University Press, 2004.
Osnova přednášek
- Teorie čísel: prvočísla, dělitělnost, kongruence, Fundamentální věta aritmetiky, Malá Fermatova věta, Eulerova funkce. (Dana Hliněná)
- Aplikace teorie čísel v kryptografii. (Dana Hliněná)
- Axiomy teorie množin, axiom výběru. Spočetné a nespočetné množiny, kardinální čísla. (Dana Hliněná)
- Výroková logika. Syntaxe, sémantika. Důkazové metody pro výrokovou logiku: metoda sémantických tabulek, přirozená dedukce, rezoluce. (Ondřej Lengál)
- Predikátová logika. Syntaxe, sémantika prvořádové predikátové logiky. Důkazové metody pro predikátovou logiku: metoda sémantických tabulek, přirozená dedukce. (Ondřej Lengál)
- Predikátová logika. Craigova interpolace. Důležité teorie. Nerozhodnutelnost. Predikátová logika vyššího řádu. (Ondřej Lengál)
- Hoarova logika. Precondition, postcondition. Invariant. Deduktivní verifikace programů. (Ondřej Lengál)
- Logické rozhodovací procedury: Presburgerova aritmetika, teorie rekurzivních datových struktur, teorie reálných čísel. (Lukáš Holík)
- Částečné uspořádání a svazy, věty o pevných bodech, Knaster-Tarski a Kleene, Kleeneho iterace, WQO, chaotická iterace. (Lukáš Holík)
- Galoisovo spojení, abstraktní interpretace, aplikace ve verifikaci. (Lukáš Holík)
- Pokročilá kombinatorika: Princip inkluze a exkluze, Dirichletův princip, vybrané kombinatorické teorémy. (Milan Češka)
- Podmíněná pravděpodobnost, základy statistické inference, Bayesovské sítě. (Milan Češka)
- Náhodné procesy: Markovův a Poissonův process. Aplikace v informatice: kvantitativní analýza, analýza výkonnosti. (Milan Češka)
Osnova numerických cvičení
- Důkazové úlohy v teorii čísel, Čínská věta o zbytcích.
- Prvočísla a kryptografie, RSA a DSA šifry.
- Důkazy v teorii množin, Cantorova diagonalizace, párování, Hilbertův hotel.
- Důkazové metody pro výrokovou logiku.
- Důkazové metody pro predikátovou logiku.
- Rozhodovací procedury.
- Počítačové cvičení 1.
- Počítačové cvičení 2.
- Základy svazů a uspořádání, úlohy na výpočet pevného bodu.
- Počítačové cvičení 3.
- Důkazové metody v kombinatorice.
- Podmíněná pravděpodobnost v praxi, použití statistické inference.
- Počítačové cvičení 4.
Osnova počítačových cvičení
- Důkazy korektnosti programů v systému VCC.
- Solvery - SAT, SMT, MONA, Vampire.
- Návrh abstraktní domény, ukázka nástrojů pro abstraktní interpretaci.
- Analýza pravděpodobnostních systémů, nástroj PRISM.
Průběžná kontrola studia
Získání 50 ze 100 možných bodů, udělovaných za aktivity v průběhu cvičení a docházku (50 bodů), průběžné testy (50 bodů).
Kontrolovaná výuka
Dva testy - v polovině a v závěru semestru (25 bodů za test), aktivita na cvičeních (5 bodů za každé cvičení).
Zařazení předmětu ve studijních plánech