Дискретная математика для разработки алгоритмов и программ

2025/2026

Статус: Маго-лего

Кто читает: Департамент анализа данных и искусственного интеллекта

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

Когда читается: 1 модуль

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Кузнецов Степан Львович

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

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

Full Syllabus Ask Question

Abstract

This course includes the basics of computational complexity, Boolean logic and graph theory. The emphasis is put upon the algorithmic side: mathematical results act as a support for effecient algorithms operating in Boolean logic and graph theory. The course is actually twofold: besides usual «chalk-and-blackboard» mathematical part, it also includes a practical one, i.e., implementing the algorithms discussed in the course. The students are supposed and encouraged to (but not restricted to) use the Python language, including PLY (Python Lex&YACC) for parsing Boolean formulae.

Learning Objectives

The students are supposed to learn the basics of computational complexity and discrete mathematics needed in their further study of programming and data science.

Expected Learning Outcomes

To know resolution method and its usage to solve instances of the satisfiability of SAT (in particular, 2-SAT, i.e., satisfiability of 2-CNF).
To know how to implement algorithms operating Boolean formulae, including parsing and satisfiability checking
To use the NetworkX environment for computations on graphs, including structures of social networks
To know the ideas behind proofs of computational complexity results: Cook-Levin theorem, NP-completeness of standard problems
To understand the border between effectively solvable problems and computationally hard ones

Course Contents

Boolean Logic
Resolution Method
Parsing
P and NP. NP-Completeness. Cook-Levin Theorem
Graphs. NetworkX
NP-Completeness HAMPATH. Graph Isomorphism
Beyond NP-Completeness

Assessment Elements

ДЗ-1
программирование: проверка выполнимости булевых формул в 2-КНФ, поиск выполняющих наборов.
ДЗ-2
Теоретическое: Предлагается несколько теоретических задач по материалам 1-й половины курса
ДЗ-3
программирование: задание на поиск эго-центров во фрагменте графа социальной сети.
Эзамен
Экзамен состоит из трёх заданий на 1 балл и трёх заданий на 2 балла (при частичном решении за такое задание возможно получить 1 балл)

Interim Assessment

2025/2026 1st module
Оценка за ДЗ вычисляется как ДЗ-1 + ДЗ-2 + ДЗ-3. Экзамен состоит из трёх заданий на 1 балл и трёх заданий на 2 балла (при частичном решении за такое задание возможно получить 1 балл). Оценка равна сумме баллов, набранных студентом, плюс 1 балл за участие в экзамене.

Bibliography

Recommended Core Bibliography

Dexter C. Kozen. Theory of Computation (2006), Springer

Recommended Additional Bibliography

N. Chiba, & T. Yamanouchi. (n.d.). [7] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.C8155A74

Authors

Антропова Лариса Ивановна

Course Syllabus