Detail předmětu

Pokročilá matematika

IAM Ak. rok 2020/2021 letní semestr 5 kreditů

Aktuální akademický rok

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

Holík Lukáš, doc. Mgr., Ph.D. (UITS)

Koordinátor předmětu

Lengál Ondřej, Ing., Ph.D. (UITS)

Jazyk výuky

česky, anglicky

Zakončení

klasifikovaný zápočet

Rozsah

  • 26 hod. přednášky
  • 18 hod. cvičení
  • 8 hod. pc laboratoře

Bodové hodnocení

  • 50 bodů půlsemestrální test (písemná část)
  • 50 bodů numerická cvičení

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Přednášející

Češka Milan, doc. RNDr., Ph.D. (UITS)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)

Cvičící

Andriushchenko Roman, Ing. (UITS)
Češka Milan, doc. RNDr., Ph.D. (UITS)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)

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,
  • přesvědčit se na vlastní oči, jak komplikovaná matematika může vést k velmi užitečným algoritmům a nástrojům.

Proč je předmět vyučován

Hlavním cílem předmětu není pokrýt předem danou oblast matematiky, ale přenést nebo podpořit ve studentech nadšení pro věc. Student dostane šanci detailně si projít cestu od abstraktní matematické teorie k jejímu praktickému využití, přímo vidět, jak chytré myšlenky směřují k implementaci v reálném světe, a že exaktní a formální matematické vyjadřování a myšlení má smysl. Tyto schopnosti si také procvičí řešením příkladů, které se snaží být hlavně zajímavé a občas i náročné. Bonusem je získání nadstandardního přehledu o některých oblastech matematiky, které v poslední době hýbají částí informatického světa.

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.
  • B. Balcar, P. Štěpánek. Teorie množin. Academia, 2005.
  • C. M. Grinstead, J. L. Snell. Introduction to probability. American Mathematical Soc., 2012.
  • G. Chartrand, A. D. Polimeni, P. Zhang. Mathematical Proofs: A Transition to Advanced Mathematics, 2013
  • Steven Roman. Lattices and Ordered Sets, Springer-Verlag New York, 2008.
  • A. Doxiadis, C. Papadimitriou. Logicomix: An Epic Search for Truth. Bloomsbury, 2009.

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

  1. Axiomy teorie množin, axiom výběru. Spočetné a nespočetné množiny, kardinální čísla. (Dana Hliněná)
  2. Aplikace teorie čísel v kryptografii. (Dana Hliněná)
  3. Teorie čísel: prvočísla, dělitelnost, kongruence, Fundamentální věta aritmetiky, Malá Fermatova věta, Eulerova funkce. (Dana Hliněná)
  4. 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)
  5. 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)
  6. Predikátová logika. Craigova interpolace. Důležité teorie. Nerozhodnutelnost. Predikátová logika vyššího řádu. (Ondřej Lengál)
  7. Hoarova logika. Precondition, postcondition. Invariant. Deduktivní verifikace programů. (Ondřej Lengál)
  8. Logické rozhodovací procedury: Klasické rozhodovací procedury pro aritmetiku nad celými a racionálními čísly. (Lukáš Holík)
  9. Automatové rozhodovací procedury pro aritmetiku a WS1S. (Lukáš Holík)
  10. Rozhodovací procedury pro kombinované teorie. (Lukáš Holík)
  11. Stochastické procesy. Modelování pravděpodobnostních systémů pomocí Markovských řetězců diskrétního času. (Milan Češka)
  12. Analýza Markovských řetězců (model checking). Demonstrace nástroje PRISM. (Milan Češka)
  13. Rozšíření Markovských řetězců o nedeterminismus, Markovské řetězce ve spojitém čase. Skryté Markovské řetězce. (Milan Češka)

Osnova numerických cvičení

  1. Důkazy v teorii množin, Cantorova diagonalizace, párování, Hilbertův hotel.
  2. Prvočísla a kryptografie, RSA a DSA šifry.
  3. Důkazové úlohy v teorii čísel, Čínská věta o zbytcích.
  4. Důkazové metody pro výrokovou logiku.
  5. Důkazové metody pro predikátovou logiku.
  6. Rozhodovací procedury.
  7. Počítačové cvičení 1.
  8. Počítačové cvičení 2.
  9. Automatové rozhodovací procedury a kombinované teorie.
  10. Počítačové cvičení 3.
  11. Modelování pravděpodobnostních systémů.
  12. Analýza Markovských řetězců.
  13. Počítačové cvičení 4.

Osnova počítačových cvičení

  1. Důkazy korektnosti programů v systému VCC.
  2. Solvery - SAT, SMT.
  3. Solvery - Mona, Vampire.
  4. Analýza pravděpodobnostních systémů pomocí nástroje PRISM.

Průběžná kontrola studia

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í).
Podmínky zápočtu:
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ů).

Podmínky zápočtu

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ů).

Zařazení předmětu ve studijních plánech

  • Program BIT, 2. ročník, volitelný
  • Program IT-BC-3, obor BIT, 2. ročník, volitelný
Nahoru