Бакалавриат 2022/2023

Дискретная математика

Статус: Курс обязательный (Прикладной анализ данных)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 1-3 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Данилов Борис Радиславович, Дашков Евгений Владимирович, Осиненко Антон Андреевич, Трофимова Анастасия Алексеевна

Язык: английский

Кредиты: 7

Контактные часы: 104

Course Syllabus

Abstract

The course encompasses many topics important for both computer scientists and practitioners from their earliest stages, which are not covered by more traditional basic courses like Calculus. These come from different branches of mathematics such as logic, combinatorics, probability theory etc. Pre-requisites: High school elementary algebra.

Learning Objectives

• To prepare students for studying the subsequent courses which use the set-theoretic, combinatorial, graph or probability formalism.
• To teach students how to identify a typical problem of Discrete Mathematics in a problem given, either applied or theoretical.

Expected Learning Outcomes

• Students will develop skills in formalizing and solving applied problems using the methods of Discrete Mathematics.
• Students will gain an understanding of propositional and predicate logic.
• Students will gain an understanding of several major theorems in discrete mathematics (Euler's theorem, Fermat's little theorem, Chinese remainder theorem).
• Students will gain an understanding of the set theory.
• Students will master basic concepts and methods of Discrete Mathematics as far as these are necessary for studying more advanced courses and for the future professional life.

Course Contents

• Propositional and predicate logic (an informal treatment). Structural induction and recursion for strings (an informal case study).
• Main set-theoretic constructions. Algebra of sets. Cartesian product.
• Induction principle. Fundamental theorem of arithmetic. Euclidean algorithm. Continued fractions. Modular arithmetic. Linear congruences and Diophantine equations. Chinese remainder theorem. Fermat's little theorem, Euler’s theorem.
• Algebra of binary relations. Image of set. Special binary relations. Functions, bijections. Set equivalence. Indicator functions. Cantor’s theorem. Cantor–Schröder–Bernstein theorem. Cardinalities of sets \N^2, \Z, \Q, \R^2, \N^\N, \R^\N.
• Pigeonhole principle. Finite and countable sets. Countable union of countable sets. Rules of sum and product. Number of functions, injections, bijections. Number of subsets, binomial coefficients and their properties. Binomial and multinomial theorems. Multisets. Inclusion–exclusion principle with applications (surjections, derangements, Euler’s totient function).
• Special binary relations. Orderings. Order isomorphism. Lattices; chains and antichains. Equivalences and partitions. Counting chains and partitions for finite sets (Dilworth's theorem etc.).
• Finite differences and sums. Linear recurrences.
• Generating functions and their combinatorial applications.
• Classical probability model. Conditional probability, Bayes’ theorem. Random variable. Expectation and variance. Some inequalities. Combinatorial applications.
• Boolean functions and circuits. Clones. Functional completeness. Counting functions of various classes.

Assessment Elements

• Homework
  The homework includes a few problem sets, one in a fortnight or so (the deadlines are announced on giving each set). Every problem set consists of about 10 – 15 problems, some of which are labeled as ‘bonus’ while all the remaining are considered ‘ordinary’.
• Examination 1
  A written examination is held past Module 1. Students may not consult any sources during the exam. Some problems of the exam are labeled as ‘bonus’; the others are ‘ordinary’. Each problem solution is graded with either 0, ¼, ½, ¾, or 1 point, and the entire exan with two values: Exam1 = (the sum of points given for ordinary problems) / #(ordinary problems); Exam1* = (the sum of points given for bonus problems) / #(bonus problems)
• Colloquium
  An oral colloquium is held at the beginning of Module 3. Each student is given two questions concerning statements and definitions as well as one question requiring a proof. After no less than 45 minutes of preparation (when using any literature is allowed), the student is required to answer ‘from scratch’, that is, with no recourse to any materials. The examiner may pose additional questions as he sees fit.
• Examination 2
  A written examination is held at the end of the Course. Students may not consult any sources during the exam. The examination takes about 120 minutes. Some problems of the exam are labeled as ‘bonus’; the others are ‘ordinary’
• Bonus activities
  The students may be graded for a variety of ‘bonus activities’ (like quizzes, etc.) with an overall integer value Bonus from 0 to 25.

Interim Assessment

• 2022/2023 1st module
  Module 1 grade = round ((50*HW1 + 50*Exam1)/100);
• 2022/2023 3rd module
  For the final grading, compute the following values basic = (21*Exam1 + 21*Colloq + 28*HW + 30*Exam2)/100; adv = (30*Exam1* + Bonus + 35*HW* + 35*Exam2*)/100; Final grade = round(min(10, 8 * basic + 2 * adv)). The final grade is rounded half up to an integer. All the other values are reported with the greatest precision available.

Bibliography

Recommended Core Bibliography

• Discrete mathematics, Biggs, N. L., 2004

Recommended Additional Bibliography

• Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108