2026/2027




Дискретная математика для разработки алгоритмов и программ
ID 1122361
Статус:
Маго-лего
Где читается:
Факультет компьютерных наук
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
3
Контактные часы:
28
Программа дисциплины
Аннотация
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 балл за участие в экзамене.