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

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

05
Декабрь

Discrete Mathematics 2

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

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

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

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

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

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

Assessment Elements

  • non-blocking 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.
  • non-blocking Classwork
  • non-blocking Final Exam
    The exam may be carried out online via distance learning platforms.
Interim Assessment

Interim Assessment

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

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