Course detail

Selected Chapters on Mathematics

FIT-MADAcad. year: 2021/2022

The course extends undergrad mathematical courses. Mathematical thinking is demonstrated together with broadening and deepening knowledge of the areas of mathematics and their connection to applications in computer science is shown. The particular areas are, e.g., logics, proof techniques, decision procedures, formal model theory, lattices, probability, and statistics.

Doctoral state exam topics:

  1. Advanced finite automata methods. 
  2. Automata techniques in decision procedures and verification. 
  3. SAT and SMT techniques.
  4. Proof techniques in predicate and first-order logic.
  5. Logical decision procedures.
  6. Galois connection, abstract interpretation, and applications.
  7. Modal and temporal logics.
  8. Advanced probability theory.
  9. Stochastic process and their analysis.
  10. Probabilistic programming and inference.
  11. Advanced graph algorithms. 
  12. Randomized algorithms.
  13. Process algebras.

Language of instruction

Czech

Mode of study

Not applicable.

Guarantor

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

Department

Department of Intelligent Systems (UITS)

Learning outcomes of the course unit

The ability to formalize and solve problems using mathematical apparatus, in particular proving of theorems, deepening and practicing basic mathematical terms, overview of areas of mathematics with important applications in computer science, especially in those related to the topic of the dissertation.
Broadening the ability to precisely formalize concepts and use the mathematical apparatus.

Prerequisites

Basic notions of relations, sets, propositional and first-order logic, algebra, finite automata.

Co-requisites

Not applicable.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

An exam at the end of the semester.

Course curriculum

Not applicable.

Work placements

Not applicable.

Aims

  • Provide PhD students with better knowledge of mathematical methods used in computer science, especially in formal methods, with the focus on the particular topic of the dissertation,
  • Deepen the skills of application of the mathematical apparatus in general.

Specification of controlled education, way of implementation and compensation for absences

Not applicable.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Not applicable.

Recommended reading

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.

Classification of course in study plans

  • Programme DIT Doctoral 0 year of study, summer semester, compulsory-optional
  • Programme DIT Doctoral 0 year of study, summer semester, compulsory-optional

  • Programme CSE-PHD-4 Doctoral

    branch DVI4 , 0 year of study, summer semester, elective

  • Programme CSE-PHD-4 Doctoral

    branch DVI4 , 0 year of study, summer semester, elective

  • Programme DIT-EN Doctoral 0 year of study, summer semester, compulsory-optional
  • Programme DIT-EN Doctoral 0 year of study, summer semester, compulsory-optional

  • Programme CSE-PHD-4 Doctoral

    branch DVI4 , 0 year of study, summer semester, elective

  • Programme CSE-PHD-4 Doctoral

    branch DVI4 , 0 year of study, summer semester, elective

Type of course unit

 

Lecture

26 hod., optionally

Teacher / Lecturer

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.

Syllabus

  1. Advanced finite automata methods. 
  2. Automata techniques in decision procedures and verification. 
  3. SAT and SMT techniques.
  4. Proof techniques in predicate and first-order logic.
  5. Logical decision procedures.
  6. Galois connection, abstract interpretation, and applications.
  7. Modal and temporal logics.
  8. Advanced probability theory.
  9. Stochastic process and their analysis.
  10. Probabilistic programming and inference.
  11. Advanced graph algorithms. 
  12. Randomized algorithms.
  13. Process algebras.

Guided consultation in combined form of studies

26 hod., optionally

Teacher / Lecturer

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.