Дискретная математика 2 (углубленный курс)

Бакалавриат 2020/2021

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

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

Когда читается: 2-й курс, 1, 2 модуль

Формат изучения: с онлайн-курсом

Преподаватели: Верещагин Николай Константинович, Оноприенко Анастасия Александровна, Райко Илья Глебович

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

Кредиты: 4

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

Полная версия программы учебной дисциплины

Аннотация

Данный курс посвящен изложению основ теории алгоритмов и математической логики. Основными темами курса являются: абстрактная теория алгоритмов, машины Тьюринга, анализ алогоритмической трудности основных логических теорий (разрешимость, неразрешимость, неперечислимость). Для изложения этих тем потребуется также ввести формализм логики первого порядка и исчисление резолюций. Материал курса необходим при дальнейшем изучении многих дисциплин: машинное обучение; вычислительные методы; алгоритмы для больших данных; основы и методология программирования; теория вычислений; математическая логика и её приложения; алгоритмы и сложность; логические методы в информатике; теоретическая информатика.

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

Основная цель освоения дисциплины «Дискретная математика-2» - обучить студентов основным понятиям и методам теории алгоритмов и логики, необходимым как в дальнейшем обучении, так и в работе по специальности.

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

Знать основные понятия и результаты теории алгоритмов
Уметь применять формализм машин Тьюринга для доказательства неразрешимости алгоритмических проблем
Знать основные определения, относящиеся к логическим формулам.
Уметь проверять общезначимость формул первого порядка
Уметь применять метод резолюций для проверки выполнимости булевых формул и формул первого порядка
Уметь проверять выразимость предикатов в моделях заданной сигнатуры

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

Абстрактная теория алгоритмов
Примеры вычислимых функций. Разрешимые, перечислимые множества. Теорема Поста. Универсальные функции. Неразрешимые и неперечислимые множества. Соотношения между перечислимыми, разрешимыми множества, вычислимыми функциями. Универсальные вычислимые функции. Диагональное рассуждение. Примеры неразрешимых и неперечислимых множеств, пар неотделимых перечислимых множеств. Главные нумерации. Свойства и существование главных нумерация. Теорема о неподвижной точке. Теорема Райса-Успенского.
Машины Тьюринга
Определение машин Тьюринга и вычислимых на машинах Тьюринга функций. Тезис Чёрча-Тьюринга. Неразрешимость проблемы остановки машины Тьюринга. Сводимости и неразрешимые задачи. Определения и свойства сводимостей. Неразрешимость задачи достижимости в ассоциативных исчислениях. Полугруппы, заданные порождающими и соотношениями. Двусторонние исчисления. Неразрешимость проблемы равенства слов в полугруппах.
Логические формулы
Булевы формулы и булевы функции. Функции на произвольных множествах, предикаты. Определение формул первого порядка. Правила оценки истинности формулы. Параметры формулы и предикаты, выражаемые формулами. Общезначимые формулы, примеры. Перестановки кванторов и логических связок. Предваренная нормальная форма. Метод резолюций для булевых формул. Правило резолюции. Метод резолюций для КНФ. Метод резолюций для произвольных булевых формул. Метод резолюций для формул первого порядка. Универсальные дизъюнкты. Резолюции для универсальных дизъюнктов. Перечислимость множества общезначимых формул.
Теории и модели
Неразрешимость общезначимых формул. Выразимость предикатов. Примеры выразимости предикатов в разных моделях. Автоморфизмы и доказательства невыразимости. Выразимость в арифметике. Бета-функция Гёделя. Неперечислимость формул, истинных в арифметике. Разрешимость алгебры Тарского.

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

Домашнее задание
Домашние задания разбиты на порции, работа по каждой порции должна быть сдана в срок. Выполнение каждой порции оценивается по 10-балльной шкале и пропорционально весу решенных задач (допускаются частичные оценки за решение задачи по шкале 0 - задача не решена, 1- получены слабые результаты в решении задачи, задача решена наполовину, 3 - задача решена с недочетами, 4 - задача полностью решена).
Коллоквиум
Письменный экзамен

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

Промежуточная аттестация (2 модуль)
0.2 * Домашнее задание + 0.4 * Коллоквиум + 0.4 * Письменный экзамен

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