• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site
Bachelor 2021/2022

# Discrete Mathematics 2

Type: Compulsory course
Area of studies: Applied Mathematics and Information Science
When: 2 year, 1, 2 module
Mode of studies: offline
Open to: students of one campus
Instructors: Boris Radislavovich Danilov, Anastasia Trofimova
Language: English
ECTS credits: 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

• 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

• Be able to explain why the problem of DNF minimization is considered hard
• Be able to prove NP-completeness of problems on practice
• Be able to provide recognition problems counterparts to search problems and vice versa
• Demonstrate the knowledge of basic and asymptotic methods of circuits synthesis
• Gain understanding of concepts of a formula and a function, the difference between them
• Obtain familiarity with circuits model of computations, be able to explain key differences between circuits and formulas
• 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
• Obtain practical skills to prove undecidability or semidecidability of problems
• The ability to recognize and use structural recursion on practice.
• The ability to transform informal inductive definitions into their formal shape.
• The understainding of the essence of induction and recursion. The understanding of the difference between these notions.
• The understanding of the principle of structural induction and the ability to apply it on practice.
• Understand basic concepts of the computability theory
• 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 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 minimization of DNF and various complexity measures for DNFs
• Understand the problem P versus NP and associated notions
• Understand the theoretical bounds of the classical algorithms #### Course Contents

• Induction and recursion on abstract sets with examples from the theory of formal languages
• Cybernetic functions, formulas and their transformations with examples from Boolean algebra
• The problem of DNF minimization and associated algorithmic obstacles
• Circuits, their complexity and methods of synthesis
• Introduction to computability theory. Decidable, semidecidable and undecidable computational problems
• The theory of complexity and P versus NP problem #### Assessment Elements

• Homework assignments
• 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.
• 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

• 2021/2022 1st module
• 2021/2022 2nd module
0.37 * Final written test + 0.26 * Homework assignments + 0.37 * Midterm written test #### 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 mathematical logic, Walicki, M., 2012
• 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