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

2026/2027

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

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

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

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

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

Язык: русский

Кредиты: 3

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

Дополнительные материалы в LMS Задать вопрос

Аннотация

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.

Цель освоения дисциплины

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

Планируемые результаты обучения

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

Содержание учебной дисциплины

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

Элементы контроля

ДЗ-1
ДЗ-2
ДЗ-3
Экзамен
Экзамен состоит из трёх заданий на 1 балл и трёх заданий на 2 балла (при частичном решении за такое задание возможно получить 1 балл)

Промежуточная аттестация

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

Список литературы

Авторы

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

Программа дисциплины