Дискретная математика 2

2020/2021

Учебный год

RUS

Обучение ведется на русском языке

4

Кредиты

Кто читает:

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

Статус:

Курс обязательный

Когда читается:

2-й курс, 1, 2 модуль

Преподаватели

Гнатенко Антон Романович

Дашков Евгений Владимирович

Запрягаев Александр Александрович

Оноприенко Анастасия Александровна

Райко Илья Глебович

Сысоева Любовь Николаевна

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендуемая основная литература

• Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления - Московский центр непрерывного математического образования - 2008 - 288с. - ISBN: 978-5-94057-322-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9307
• Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции - Московский центр непрерывного математического образования - 2008 - 192с. - ISBN: 978-5-94057-323-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9308

Рекомендуемая дополнительная литература

• Верещагин Н.К., Шень А.Х. - Основы теории вычислимых функций - Национальный Открытый Университет "ИНТУИТ" - 2016 - 169с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100351
• Верещагин Н.К., Шень А.Х. - Языки и исчисления - Национальный Открытый Университет "ИНТУИТ" - 2016 - 278с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100547