Специалитет
2026/2027
Математическая логика и теория алгоритмов
ID 1161417
Статус:
Курс обязательный (Компьютерная безопасность)
Кто читает:
Департамент прикладной математики
Когда читается:
2-й курс, 3, 4 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
3
Контактные часы:
64
Программа дисциплины
Аннотация
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются: • получение представления об основных понятиях, методах и результатах теории вычислимости; • получение представления об основных понятиях и методах булевой алгебры; • получение представления об основных понятиях формальных исчислений. Дисциплина реализуется в он-лайн формате
Цель освоения дисциплины
- Получение представления об основных понятиях, методах и результатах теории вычислимости
- Получение представления об основных понятиях и методах булевой алгебры
- Получение представления об основных понятиях формальных исчислений
Планируемые результаты обучения
- Решает задаче о замкнутости и полноте систем булевых функций
- Решает задачи о булевых функциях, их совершенной, сокращенной и тупиковой дизъюнктивной нормальной форме, их полиномах Жегалкина
- Решает задачи о вычислимых функциях, включая явное построение вычисляющих их программ
- Решает задачи о вычислимых, перечислимых и диофантовых множествах.
- Решает задачи о контактных схемах.
- Решает задачи о программировании на МНР: о системе команд, их нумерации и о нумерации программ.
- Решает задачи о равномощности множеств.
- Решает задачи о формальных исчислениях, в том числе об исчислении высказываний
Содержание учебной дисциплины
- Элементы теории множеств
- Вычислимость
- Булевы функции
- Формальные исчисления
Промежуточная аттестация
- 2026/2027 4th module0.1 * Activity + 0.2 * Контрольная работа №1 + 0.2 * Контрольная работа №2 + 0.4 * Oral interview
Список литературы
Рекомендуемая основная литература
- Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2004
- Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2012
- Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306
- Справочная книга по математической логике. Ч.2: Теория множеств, , 1982
- Теория множеств, Куратовский, К., 1970
Рекомендуемая дополнительная литература
- Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2002