Бакалавриат 2020/2021

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

Статус: Курс обязательный (Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных")

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

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

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

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

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

Преподаватели: Дайняк Александр Борисович, Данилов Борис Радиславович

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

Кредиты: 4

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

Course Syllabus

Abstract

The course encompasses a range of topics that provide foundation to the follow-up courses on algorithms and data structures, discrete optimization, operations research. Pre-requisites: High school elementary algebra, propositional logic.

Learning Objectives

• To prepare students for studying the subsequent courses which require familiarity with Boolean algebra, computation models, graphs and networks.
• 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 master basic concepts and methods of Boolean function theory, discrete optimization, as far as these are necessary for studying more advanced courses and for the future professional life.
• Students will gain an understanding of various computation models, complexity measures and classes of problems with respect to their hardness.
• Students will gain an understanding of several major theorems in discrete mathematics (Quine–McCluskey algorithm, Cook’s theorem, Hall’s theorem, Menger’s theorem).

Course Contents

• Boolean algebra
  Boolean functions and formulas that compute them. Closure operator. Standard representations of Boolean functions: DNF and CNF, Boolean polynomials. Canonical forms. Clones (closed classes of Boolean functions); precomplete classes. Post’s functional completeness theorem. Complexity measures. Search for the optimal formula: minimization of Boolean functions. Equivalence of minimization problem for DNF and search of minimum weighted cover of the corresponding Boolean matrix. Blake canonical form. Quine–McCluskey algorithm, greedy cover algorithm and their combination.
• Computability and complexity
  Turing machines: informal and formal definitions. Church–Turing thesis. RAM model. Existence of undecidable problems: the halting problem. Computable functions. Computable and computably enumerable sets. Decision problems in discrete mathematics. P complexity class. Non-deterministic Turing machines. NP complexity class. Alternative definitions of NP. Reductions: Karp and Cook—Turing reductions, polynomial-time reductions. Polynomial-time equivalence of problems. Decision vs. evaluation vs. search versions of problems in discrete mathematics. NP-hard problems: definition and examples. Examples of dichotomy in complexity theory: 2-coloring vs 3-coloring, 2-SAT vs 3-SAT. Resolution technique for CNF
• Graphs and networks
  Graph colorings, Konig’s theorem. Planar graphs, 5-coloring of planar graphs. Flows in networks. Maximum flow vs. minimum cut in the network; Ford—Fulkerson theorem. Matchings in bipartite graphs. Hall’s theorem on perfect matchings in bipartite graphs. Application of MaxFlow-MinCut theorem to proving the Hall’s theorem. Connectivity, k-connectivity. Menger’s theorem. Biconnected graphs. Vertex separator, bridge. Blocks and tree of blocks. Complex networks: definitive properties and examples. Ways to measure the node importance for the network: closeness centrality, betweenness centrality, pagerank. Community structure in networks.

Assessment Elements

• Homework Assignments
  Homework problems will be assigned starting from second week just once a week. Each student is expected to solve the problems individually. Each homework will be represented by the mini-group printed report containing an abstract, introduction, individual solutions by every member of the mini-group, summary, and conclusion, and references. The sections of an assignment will be discussed by all members of the mini-group and reflecting the mini-group consensus.
• Classwork
• Final Exam
  The exam may be carried out online via distance learning platforms.

Interim Assessment

• Interim assessment (2 module)
  0.2 * Classwork + 0.4 * Final Exam + 0.4 * Homework Assignments

Bibliography

Recommended Core Bibliography

• Bernhard Korte, Jens Vygen. Combinatorial Optimization. Theory and Algorithms. Fifth edition. Springer-Verlag, Berlin Heidelberg, 2012.
• Michael Sipser. (2005). Introduction to the Theory of Computation, Second Edition.

Recommended Additional Bibliography

• J. A. Bondy, & U. S. R. Murty. (1976). Graph theory with applications. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.CB6871BA