Course detail

Advanced Mathematics

FIT-IAMAcad. year: 2018/2019

The course is a follow-up to compulsory mathematical courses at FIT. Students learn how to use mathematic methods on several subjects closely related to computer science. These are mainly number theory and its application in cryptography, basic set theory and logic, logical systems and decision procedures with applications in e.g. databases or software engineering, probability, statistics, and their applications in analysis of probabilistic systems and artificial intelligence. 

Language of instruction

Czech

Number of ECTS credits

5

Mode of study

Not applicable.

Guarantor

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

Department

Department of Intelligent Systems (UITS)

Learning outcomes of the course unit

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

Prerequisites

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

Co-requisites

Not applicable.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

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

Course curriculum

Not applicable.

Work placements

Not applicable.

Aims

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

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

Not applicable.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Basic literature

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.

Recommended reading

A. Doxiadis, C. Papadimitriou. Logicomix: An Epic Search for Truth. Bloomsbury, 2009.
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
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 IT-BC-3 Bachelor's

    branch BIT , 2 year of study, summer semester, elective

Type of course unit

 

Lecture

26 hod., optionally

Teacher / Lecturer

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

Syllabus

  1. Axioms of set theory, 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 logics. (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. Advanced combinatorics: inclusion and exclusion, Dirichlet's principle, chosen combinatorial theorems. (Milan Češka)
  12. Conditional probability, statistical inference, Bayesian networks. (Milan Češka)
  13. Probabilistic processes: Markov and Poisson process. Applications in informatics: quantitative analysis, performance analysis.

Fundamentals seminar

18 hod., compulsory

Teacher / Lecturer

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

Syllabus

  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 reminder 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. Proofs in combinatorics.
  12. Conditional probability and statistical inference in practice.
  13. Computer labs 4.

Exercise in computer lab

8 hod., compulsory

Teacher / Lecturer

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

Syllabus

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