• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Бакалаврская программа «Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных"»

Discrete Mathematics

2019/2020
Учебный год
ENG
Обучение ведется на английском языке
8
Кредиты
Статус:
Курс обязательный
Когда читается:
1-й курс, 1-3 модуль

Преподаватели

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

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

Expected Learning Outcomes

  • 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.
  • Students will develop skills in formalizing and solving applied problems using the methods of Discrete Mathematics.
Course Contents

Course Contents

  • Propositional and predicate logic (an informal treatment). 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.).
  • Graphs. Vertex degree. Isomorphism. Bipartite graphs. Matchings. Connected components. Trees. Spanning tree. Eulerian and Hamiltonian paths. Directed graphs. De Bruijn graphs.
  • Formal languages. Monoid of words. Prefixes and suffixes. Semiring of languages. Inductive definitions. Regular bracket sequences and Catalan numbers.
  • 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

Assessment Elements

  • non-blocking Final exam
    A final written exam with open questions.
  • non-blocking Homework
    Average grade for the homework will be included into the cumulative grade.
  • non-blocking Colloquiums
    The grade for the colloquium will be included into the cumulative grade.
  • non-blocking Cumulative Grade
Interim Assessment

Interim Assessment

  • Interim assessment (3 module)
    0.7 * Cumulative Grade + 0.3 * Final exam
Bibliography

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