Специалитет
2023/2024
Математическая логика и теория алгоритмов
Статус:
Курс обязательный (Компьютерная безопасность)
Кто читает:
Департамент прикладной математики
Когда читается:
2-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Специальность:
10.05.01. Компьютерная безопасность
Язык:
русский
Кредиты:
3
Контактные часы:
64
Программа дисциплины
Аннотация
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются: • получение представления об основных понятиях, методах и результатах теории вычислимости; • получение представления об основных понятиях и методах булевой алгебры; • получение представления об основных понятиях формальных исчислений. Дисциплина реализуется в он-лайн формате
Цель освоения дисциплины
- Получение представления об основных понятиях, методах и результатах теории вычислимости
- Получение представления об основных понятиях и методах булевой алгебры
- Получение представления об основных понятиях формальных исчислений
Планируемые результаты обучения
- Решает задаче о замкнутости и полноте систем булевых функций
- Решает задачи о булевых функциях, их совершенной, сокращенной и тупиковой дизъюнктивной нормальной форме, их полиномах Жегалкина
- Решает задачи о вычислимых функциях, включая явное построение вычисляющих их программ
- Решает задачи о вычислимых, перечислимых и диофантовых множествах.
- Решает задачи о контактных схемах.
- Решает задачи о программировании на МНР: о системе команд, их нумерации и о нумерации программ.
- Решает задачи о равномощности множеств.
- Решает задачи о формальных исчислениях, в том числе об исчислении высказываний
Содержание учебной дисциплины
- Элементы теории множеств
- Вычислимость
- Булевы функции
- Формальные исчисления
Промежуточная аттестация
- 2023/2024 учебный год 4 модуль0.1 * Активность + 0.1 * Активность + 0.2 * Контрольная работа + 0.2 * Контрольная работа + 0.4 * Устный опрос
Список литературы
Рекомендуемая основная литература
- Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2004
- Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2012
- Справочная книга по математической логике. Ч.2: Теория множеств, , 1982
- Теория множеств, Куратовский, К., 1970
Рекомендуемая дополнительная литература
- Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2002