Detail předmětu

Vybrané kapitoly z matematiky

FIT-MADAk. rok: 2021/2022

Předmět navazuje na povinné matematické předměty bakalářského a magisterské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 logiku, důkazové techniky, rozhodovací procedury, teorii formálních modelů, svazy, pravděpodobnost a statistiku.

Okruhy k SDZ:

  1. Pokročilé techniky pro konečné automaty.
  2. Automatové techniky v rozhodovacích procedurách a verifikaci.
  3. Techniky SAT/SMT dokazování.
  4. Důkazové metody pro výrokovou a predikátovou logiku. 
  5. Logické rozhodovací procedury.
  6. Galoisovo spojení, abstraktní interpretace, aplikace ve verifikaci.
  7. Modální a temporální logiky.
  8. Pokročilá teorie pravděpodobnosti.
  9. Stochastické procesy a jejich analýza.
  10. Pravděpodobnostní programovaní a inference.
  11. Pokročilé grafové algoritmy.
  12. Randomizované algoritmy.
  13. Procesové algebry.

Jazyk výuky

čeština

Garant předmětu

prof. Ing. Tomáš Vojnar, Ph.D.

Zajišťuje ústav

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

Výsledky učení 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, zejména v oblastech souvisejících s disertací.
Rozvinutí schopnosti exaktně se vyjadřovat a používat matematický aparát.

Prerekvizity

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

Způsob a kritéria hodnocení

Předmět bude hodnocen zkouškou na konci semestru.

Učební cíle

  • Umožnit doktorským studentům zorientovat se v matematických metodách používaných v informatice, zejména ve formálních metodách, se zaměřením na konkrétní téma disertace.
  • Prohloubit schopnosti aplikace matematického aparátu obecně.

Doporučená literatura

A.R. Bradley, Z. Manna. The Calculus of Computation. Springer, 2007.
B. Balcar, P. Štěpánek. Teorie množin. Academia, 2005.
Biere, A., Heule, M., Van Maaren, H., Walsh, T. Handbook of Satisfiability, IOS Press, 2009
C. M. Grinstead, J. L. Snell. Introduction to probability. American Mathematical Soc., 2012.
D. P. Bertsekas, J. N. Tsitsiklis. Introduction to Probability, Athena, 2008. Scientific
D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
G. Chartrand, A. D. Polimeni, P. Zhang. Mathematical Proofs: A Transition to Advanced Mathematics, 2013
Christel Baier and Joost-Pieter Katoen: Principles of Model Checking, MIT Press, 2008. ISBN: 978-0-262-02649-9
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.). The MIT Press.
J. Hromkovič. Algorithmic adventures: from knowledge to magic. Dordrecht: Springer, 2009.
M. Huth, M. Ryan. Logic in Computer Science. Modelling and Reasoning about Systems. Cambridge University Press, 2004.
R. Smullyan. First-Order Logic. Dover, 1995.
Steven Roman. Lattices and Ordered Sets, Springer-Verlag New York, 2008.

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

  • Program DIT doktorský 0 ročník, letní semestr, povinně volitelný
  • Program DIT doktorský 0 ročník, letní semestr, povinně volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, letní semestr, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, letní semestr, volitelný

  • Program DIT-EN doktorský 0 ročník, letní semestr, povinně volitelný
  • Program DIT-EN doktorský 0 ročník, letní semestr, povinně volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, letní semestr, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, letní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

prof. Ing. Tomáš Vojnar, Ph.D.
doc. RNDr. Milan Češka, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
Ing. Ondřej Lengál, Ph.D.

Osnova

  1. Pokročilé techniky pro konečné automaty.
  2. Automatové techniky v rozhodovacích precedurách a verifikaci.
  3. Techniky SAT/SMT dokazování.
  4. Důkazové metody pro výrokovou a predikátovou logiku. 
  5. Logické rozhodovací procedury.
  6. Galoisovo spojení, abstraktní interpretace, aplikace ve verifikaci.
  7. Modální a temporální logiky.
  8. Pokročilá teorie pravděpodobnosti.
  9. Stochastické procesy a jejich analýza.
  10. Pravděpodobnostní programovaní a inference.
  11. Pokročilé grafové algoritmy.
  12. Randomizované algoritmy.
  13. Procesové algebry.

Konzultace v kombinovaném studiu

26 hod., nepovinná

Vyučující / Lektor

Ing. Ondřej Lengál, Ph.D.
prof. Ing. Tomáš Vojnar, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
doc. RNDr. Milan Češka, Ph.D.