Title:  Advanced Mathematics 

Code:  IAM 

Ac.Year:  2018/2019 

Sem:  Summer 

Curriculums:  Programme  Field/ Specialization  Year  Duty 
ITBC3  BIT  2nd  Elective 


Language of Instruction:  Czech 

Credits:  5 

Completion:  classified credit 

Type of instruction:  Hour/sem  Lectures  Seminar Exercises  Laboratory Exercises  Computer Exercises  Other 

Hours:  26  18  0  8  0 

 Exams  Tests  Exercises  Laboratories  Other 

Points:  0  50  50  0  0 



Guarantor:  Holík Lukáš, Mgr., Ph.D. (DITS) 

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

Lecturer:  Češka Milan, RNDr., Ph.D. (DITS) Hliněná Dana, doc. RNDr., Ph.D. (DMAT) Holík Lukáš, Mgr., Ph.D. (DITS) Lengál Ondřej, Ing., Ph.D. (DITS) 
Instructor:  Češka Milan, RNDr., Ph.D. (DITS) Hliněná Dana, doc. RNDr., Ph.D. (DMAT) Holík Lukáš, Mgr., Ph.D. (DITS) Lengál Ondřej, Ing., Ph.D. (DITS) 

Faculty:  Faculty of Information Technology BUT 

Department:  Department of Intelligent Systems FIT BUT 

Prerequisites:  

Schedule: 

Day  Lesson  Week  Room  Start  End  Lect.Gr.  Groups 

Tue  Hliněná  konzultace  lectures  A113  09:00  10:50   
Wed  lecture  lectures  A113  09:00  10:50  2BIA 2BIB 3BIT  xx 
Thu  exercise  cvičení IAM  lectures  A113  10:00  11:50   
Thu  comp.lab  lectures  N203  10:00  11:50  2BIA 2BIB 3BIT  xx 
  Learning objectives: 

   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.
 Description: 

  The course is a followup 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.  Knowledge and skills required for the course: 

  Basic knowledge of sets, relations, propositional and predicate logic, algebra, and finite automata.  Subject specific learning outcomes and competencies: 

  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.  Generic learning outcomes and competencies: 

  Improving the abilities of exact thinking, expressing ideas, and using a mathematical apparatus.  Why is the course taught: 

  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 through 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.  Syllabus of lectures: 

  Axioms of set theory, axiom of choice. Countable and uncountable sets, cardinal numbers. (Dana Hliněná)
 Application of number theory in cryptography. (Dana Hliněná)
 Number theory: prime numbers, Fermat's little theorem, Euler's function. (Dana Hliněná)
 Propositional logic. Syntax and semantics. Proof techniques for propositional logic: syntax tables, natural deduction, resolution. (Ondřej Lengál)
 Predicate logic. Syntax and semantics. Proof techniques for predicate logic: semantic tables, natural deduction. (Ondřej Lengál)
 Predicate logic. Craig interpolation. Important theories. Undecidability. Higher order logics. (Ondřej Lengál)
 Hoare logic. Precondition, postcondition. Invariant. Deductive verification of programs. (Ondřej Lengál)
 Decision procedures in logic: Classical decision procedures for arithmetics over integers and over rationals. (Lukáš Holík)
 Automatabased decision procedures for arithmetics and for WS1S (Lukáš Holík)
 Decision procedures for combined theories. (Lukáš Holík)
 Advanced combinatorics: inclusion and exclusion, Dirichlet's principle, chosen combinatorial theorems. (Milan Češka)
 Conditional probability, statistical inference, Bayesian networks. (Milan Češka)
 Probabilistic processes: Markov and Poisson process. Applications in informatics: quantitative analysis, performance analysis.
 Syllabus of numerical exercises: 

  Proofs in set theory, Cantor's diagonalization, matching, Hilbert's hotel.
 Prime numbers and cryptography, RSA, DSA, cyphers.
 Proofs in number theory, Chinese reminder theorem.
 Proofs in propositional logic.
 Proofs in predicate logic.
 Decision procedures.
 Computer labs 1.
 Computer labs 2.
 Automata decision procedures and combination theories.
 Computer labs 3.
 Proofs in combinatorics.
 Conditional probability and statistical inference in practice.
 Computer labs 4.
 Syllabus of computer exercises: 

  Proving programs corrects in VCC.
 SAT and SMT solvers.
 Tools MONA and Vampire.
 Analysis of probabilistic systems, PRISM.
 Fundamental literature: 

  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.
 Study literature: 

  R. Smullyan. FirstOrder 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, SpringerVerlag New York, 2008.
 A. Doxiadis, C. Papadimitriou. Logicomix: An Epic Search for Truth. Bloomsbury, 2009.
 Links: 

 The course is open for students at their second and third year.  Progress assessment: 

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