• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2021/2022

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

Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 2-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Преподаватели: Данилов Борис Радиславович, Трофимова Анастасия Алексеевна
Язык: английский
Кредиты: 4

Course Syllabus

Abstract

The course is devoted to the various kinds of computational models and is a natural follow up of the course Discrete Mathematics. It encompasses a range of topics that provide strong theoretical foundations for the courses of a more applied nature: algorithms and data structures, discrete optimization, research of operations. Pre-requisite course: Discrete Mathematics.
Learning Objectives

Learning Objectives

  • Shape the basic knowledge about the fundamental notions, models and methods of the theory of computations and complexity
  • Familiarize students with theoretical knowledge required to build proper models for applied algorithms, analyze and assess them
  • Provide the theoretical foundation for courses in programming, algorithms and discrete optimization
Expected Learning Outcomes

Expected Learning Outcomes

  • The understainding of the essence of induction and recursion. The understanding of the difference between these notions.
  • The ability to transform informal inductive definitions into their formal shape.
  • The understanding of the principle of structural induction and the ability to apply it on practice.
  • The ability to recognize and use structural recursion on practice.
  • Gain understanding of concepts of a formula and a function, the difference between them
  • Understand the problem of expressability of Boolean functions, know 5 closed classes (clones) of Boolean algebra and be able to determine membership of various Boolean functions to these classes, be ready to apply Post's completeness theorem on practice
  • Understand the problem of equivalent transformations of Boolean formulas, gain practical skills of operation with Boolean formulas based on their equivalent transformations
  • Understand the problem of minimization of DNF and various complexity measures for DNFs
  • Obtain practical skills of construction of various unambigous DNFs: Blake canonical form, core DNF, Quine's DNF, DNF the sum of irreducible DNFs
  • Obtain practical skills to look for and find all the irreducible DNFs
  • Be able to explain why the problem of DNF minimization is considered hard
  • Obtain familiarity with circuits model of computations, be able to explain key differences between circuits and formulas
  • Demonstrate the knowledge of basic and asymptotic methods of circuits synthesis
  • Understand basic concepts of the computability theory
  • Understand the theoretical bounds of the classical algorithms
  • Obtain practical skills to prove undecidability or semidecidability of problems
  • Understand the problem P versus NP and associated notions
  • Be able to provide recognition problems counterparts to search problems and vice versa
  • Be able to prove NP-completeness of problems on practice
Course Contents

Course Contents

  • Induction and recursion on abstract sets with examples from the theory of formal languages
    Inductive definitions and recursive construction of functions. The principle of structural induction and structural recursion. Formal language. Monoid of words.
  • Cybernetic functions, formulas and their transformations with examples from Boolean algebra
    The notion of a cybernetic function as opposed to the set theoretic function. The notion of a formula and it's implemented function. Equivalent transformation of Boolean formulas. Problems of expressability in Boolean algebra.
  • The problem of DNF minimization and associated algorithmic obstacles
    Various measures of DNF complexity. Blake canonical form, irreducible DNFs, their "geometirc" interpretation. Various ways of finding unambigous DNFs (Blake canonical form, core DNF, Quine DNF, etc.) Algorithmic obstacles associated with DNF minimization.
  • Circuits, their complexity and methods of synthesis
    Circuits as networks of functional elements and as a program. Measures of circuits complexity. The search for an optimal circuit. Various basic and asymptotic methods of circuits synthesis
  • Introduction to computability theory. Decidable, semidecidable and undecidable computational problems
    Basic notions from the computability theory. Universal function and impossibility of total universal function. Problems of self-applicability and halting problem. Different variants of reducibility. Computational and descriptive complexity.
  • The theory of complexity and P versus NP problem
    Problems of recognition. Complexity classes P, NP. Polynomial reducibility and polynomial equivalence of problems. Search problems and NP-hardness. Cook-Levin theorem and several NP-complete problems.
Assessment Elements

Assessment Elements

  • non-blocking Homework assignments
    Homework problems are assigned starting from the first seminar once a week at each seminar excluding the last seminar of the course. Each student is expected to solve problems individually. Solutions must be performed in hand-written form on a piece of paper and contain the full name of the student, his group number, and the list of solved problems written in clear and recognizable manner. Each problem in the homework must contain it's respective number in the assignment, the solution and the answer explicitly given after the written word "answer". When several answers are given for a task the inspector may choose any of the specified answers to score the task. When problem is not supposed to have an answer (exercises to prove facts) then the complete proof should be provided. Each step in the solution of a task must be supported by a mathematical argument, unfounded statements may lead to lowering the score up to "0" (zero) points for the task. Only statements and theorems provided on lectures or seminars can be used without a proof. The correct answer for the task without provided solution is scored with "0" (zero) points. These rules also apply for the other written tests (midterm written test and final written test).
  • non-blocking Midterm written test
    The planned form of conducting the midterm written test is the offline written test at the start of the second module. In the case of aggravating of epidemiologic state the midterm written test may be carried out online, in which case the rules and the form of the test are announced separately and may or may not match the rules announced for the offline form of the test. Rules for submitted solutions follow the rules described in the comment for the homework assignments.
  • non-blocking Final written test
    The planned form of conducting the final written test is the offline written exam. In the case of aggravating of epidemiologic state the final written test may be carried out online, in which case the rules and the form of the test are announced separately and may or may not match the rules announced for the offline form of the test. Rules for submitted solutions follow the rules described in the comment section for the homework assignments.
Interim Assessment

Interim Assessment

  • Interim assessment (2 module)
    0.37 * Final written test + 0.26 * Homework assignments + 0.37 * Midterm written test
Bibliography

Bibliography

Recommended Core Bibliography

  • Computational complexity : a modern approach, Arora, S., 2010
  • Computational complexity, Papadimitriou, C. H., 1994
  • Discrete mathematics, Biggs, N. L., 2004
  • Introduction to the theory of computation, Sipser, M., 2006
  • Introduction to the theory of computation, Sipser, M., 2013
  • Introduction to the theory of computation, Sipser, M., 2016

Recommended Additional Bibliography

  • Computational complexity : a conceptual perspective, Goldreich, O., 2008
  • Introduction to mathematical logic, Walicki, M., 2012