Advanced Mathematics

• 26 hrs lectures
• 18 hrs exercises
• 8 hrs pc labs

• 50 pts mid-term test (written part)
• 50 pts numeric exercises

The ability to exactly and formally specify and solve problems, formally prove claims; also better understanding of the basic mathematical concepts, an overview of several areas of mathematics important in computer science. 
Improving the abilities of exact thinking, expressing ideas, and using a mathematical apparatus.

• Practice mathematical writing and thinking, formulation of problems and solving them,
• obtain deeper insight into several areas of mathematics with applications in computer science,
• learn on examples that complicated mathematics can lead to useful algorithms and tools.

The main goal is not to cover a given area of mathematics but to infect a student with an enthusiasm for the subject. The student will be given an opportunity to walk the way from abstract theory to its actual use in the real world, which might possibly convince him/her that thinking and expressing ideas with a help of formal mathematics makes sense. These skills will be exercised by solving problem assignments that should be interesting and sometimes demanding. Obtaining a better overview of several areas of mathematics important in informatics is an added benefit.

• Discrete Mathematics (IDM)
• Formal Languages and Compilers (IFJ)
• Calculus 1 (IMA1)
• Calculus 2 (IMA2)
• Probability and Statistics (IPT)

Basic knowledge of sets, relations, propositional and predicate logic, algebra, and finite automata.

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

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

1. Axioms of set theory, the axiom of choice. Countable and uncountable sets, cardinal numbers. (Dana Hliněná)
2. Application of number theory in cryptography. (Dana Hliněná)
3. Number theory: prime numbers, Fermat's little theorem, Euler's function. (Dana Hliněná)
4. Propositional logic. Syntax and semantics. Proof techniques for propositional logic: syntax tables, natural deduction, resolution. (Ondřej Lengál)
5. Predicate logic. Syntax and semantics. Proof techniques for predicate logic: semantic tables, natural deduction. (Ondřej Lengál)
6. Predicate logic. Craig interpolation. Important theories. Undecidability. Higher order logic. (Ondřej Lengál)
7. Hoare logic. Precondition, postcondition. Invariant. Deductive verification of programs. (Ondřej Lengál)
8. Decision procedures in logic: Classical decision procedures for arithmetics over integers and over rationals. (Lukáš Holík)
9. Automata-based decision procedures for arithmetics and for WS1S (Lukáš Holík)
10. Decision procedures for combined theories. (Lukáš Holík)
11. Stochastic processes: Modelling of probabilistic systems using discrete-time Markov chains. (Milan Češka)
12. Analysis (model-checking) of Markov chains. Demonstration of PRISM model-checker. (Milan Češka)
13. Extension of Markov chains: continuous-time, Markov Decision Processes, Hidden Markov Chains. (Milan Češka)

1. Proofs in set theory, Cantor's diagonalization, matching, Hilbert's hotel.
2. Prime numbers and cryptography, RSA, DSA, cyphers.
3. Proofs in number theory, Chinese remainder theorem.
4. Proofs in propositional logic.
5. Proofs in predicate logic.
6. Decision procedures.
7. Computer labs 1.
8. Computer labs 2.
9. Automata decision procedures and combination theories.
10. Computer labs 3.
11. Modelling of probabilistic systems.
12. Analysis (model-checking) of Markov chains.
13. Computer labs 4.

1. Proving programs corrects in VCC.
2. SAT and SMT solvers.
3. Tools MONA and Vampire.
4.  Analysis of probabilistic systems using PRISM tool.

Two tests, midterm and final (25 points per test), activity during exercises (5 points per exercise).
Exam prerequisites:
Obtaining at least 50 points from the 100 possible (50 tests, 50 exercises).

Obtaining at least 50 points from the 100 possible (50 tests, 50 exercises).