Course details

Selected Chapters on Mathematics

MAD Acad. year 2021/2022 Summer semester

Current academic year

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.

Guarantor

Vojnar Tomáš, prof. Ing., Ph.D. (DITS)

Course coordinator

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

Language of instruction

Czech, English

Completion

Examination (written+oral)

Time span

  • 26 hrs lectures

Assessment points

  • 100 pts final exam

Department

Department of Intelligent Systems (UITS)

Lecturer

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

Instructor

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

Subject specific learning outcomes and competences

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.

Learning objectives

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

Prerequisite knowledge and skills

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

Study literature

  • 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
  • J. Hromkovič. Algorithmic adventures: from knowledge to magic. Dordrecht: Springer, 2009.
  • Steven Roman. Lattices and Ordered Sets, Springer-Verlag New York, 2008.
  • Biere, A., Heule, M., Van Maaren, H., Walsh, T. Handbook of Satisfiability, IOS Press, 2009
  • 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.
  • D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
  • A.R. Bradley, Z. Manna. The Calculus of Computation. Springer, 2007.
  • D. P. Bertsekas, J. N. Tsitsiklis. Introduction to Probability, Athena, 2008. Scientific
  • M. Huth, M. Ryan. Logic in Computer Science. Modelling and Reasoning about Systems. Cambridge University Press, 2004.

Syllabus of lectures

  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.

Progress assessment

An exam at the end of the semester.

Course inclusion in study plans

Back to top