Бакалавриат 2023/2024

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

Статус: Курс по выбору (Экономика и анализ данных)

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

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

Где читается: Факультет экономических наук

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

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

Охват аудитории: для своего кампуса

Преподаватели: Дашков Евгений Владимирович, Оноприенко Анастасия Александровна, Таламбуца Алексей Леонидович

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

Кредиты: 6

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

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

Аннотация

Курс посвящен основам теории алгоритмов, теории сложности вычислений и математической логики. Его главные темы – логика первого порядка, абстрактная теория вычислимости, машины Тьюринга как конкретная вычислительная модель, меры сложности вычислений, булевы схемы, сложностные классы P и NP. Курс может служить теоретическим основанием для дальнейшего изучения различных областей информатики, математической логики и алгебры, а также для практической деятельности по разработке и анализу алгоритмов.

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

• Основная цель освоения дисциплины «Дискретная математика-2» - обучить студентов основным понятиям и методам теории алгоритмов и логики, необходимым как в дальнейшем обучении, так и в работе по специальности.
• Уметь представлять утверждения из различных разделов математики формулами первого порядка и понимать такие формулы.
• Иметь представление о формальной семантике языков первого порядка, а также о понятиях логического вывода и формальной теории.
• Иметь представление об алгоритмически неразрешимых и неперечислимых проблемах, уметь усмотреть таковые в научных и технических задачах, доказывать неразрешимость (неперечислимость) методом сведения.
• Иметь представление о машинах Тьюринга и связанных с ними мерах сложности “времени” и “зоны”; понимать как и какой ценой (в смысле возрастания сложности) алгоритмы, написанные на практических ЯП, могут быть представлены на машинах Тьюринга.
• Иметь представление о сложностных классах P, NP, coNP, PSPACE и уметь доказывать принадлежность практических задач этим классам.

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

• Знать основные законы логики первого порядка и уметь применять их в математических доказательствах.
• Знать несколько классических NP-полных задач и уметь доказывать NP-трудность встречающихся на практике задач методом сведения.

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

• Языки первого порядка и их интерпретации. Структуры и их изоморфизм.
• Выразимость множеств в структуре. Элементарная эквивалентность структур. Автоморфизмы структуры и невыразимость.
• Логика первого порядка. Эквивалентность, общезначимость и выполнимость. Подстановки. Нормальные формы.
• Теории первого порядка. Понятия формального вывода и логического следования. Теоремы о полноте и корректности (без доказательства). Теорема компактности.
• Неформальное понятие алгоритма. Вычислимые функции, разрешимые и перечислимые множества.
• Универсальные вычислимые функции. T-Предикаты. Неразрешимость проблем самоприменимости и остановки. Главные универсальные вычислимые функции.
• Теорема Клини о неподвижной точке. Теоремы о рекурсии. Индексные множества. Теорема Райса—Успенского.
• m-Сводимость и ее свойства. Примеры сведений. Арифметическая иерархия.
• Арифметическая иерархия (продолжение). Теорема Райса–Шапиро.
• Машины Тьюринга. Примеры вычислимых функций. Время и зона.
• Многоленточные машины Тьюринга. Теорема о сокращении числа лент.
• Универсальная машина Тьюринга. Задачи распознавания. Классы TIME(f), SPACE(f), P, PSPACE, EXP.
• Теоремы об иерархии по времени (без доказательства) и зоне.
• Класс NP. Недетерминированные машины Тьюринга. Полиномиальная сводимость (по Карпу). Полиномиальная иерархия.
• Булевы схемы; размер и глубина. Верхняя и нижняя оценки для размера булевой функции.
• Последовательности булевых схем. Класс P/Poly. Включение в него класса P.
• Теорема Кука. Дальнейшие примеры NP-полных задач.
• Вероятностные алгоритмы. Вероятностная проверка выполнимости 2-КНФ.
• Классы RP, coRP, ZPP, BPP и PP.

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

• Домашнее задание
  Домашнее задание разделено на несколько частей, которые выдаются примерно раз в одну или две недели и предполагают сдачу в письменном виде в установленные для каждой части сроки. Решение каждой задачи оценивается числом от 0 до 1. Некоторые задачи объявляются бонусными, остальные считаются обязательными. По итогам семестра вычисляется оценка за все домашнее задание в целом как отношение суммы баллов, набранных студентом за все решенные им задачи, к числу обязательных задач в домашнем задании, умноженное на 10. Преподаватель вправе потребовать от любого студента “защитить” (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля, по усмотрению преподавателя.
• Коллоквиум
  Проводится приблизительно за месяц до экзамена очно в устной форме (допускается и проведение онлайн). Студент получает три теоретических вопроса и время на подготовку ответа. Во время подготовки можно пользоваться любыми материалами, но нельзя советоваться с кем-либо. Отвечать следует “с чистого листа”; с разрешения преподавателя при этом можно использовать лишь самостоятельно написанные во время подготовки заметки. За ответ студента выставляется оценка от 0 до 10 баллов.
• Экзамен
  Письменный экзамен проводится очно во время сессии после четвертого модуля. На экзамене можно пользоваться любыми материалами на бумаге, изготовленными до начала экзамена (если это не противоречит правилам против списывания). Решение каждой задачи оценивается числом от 0 до 1. Некоторые задачи экзамена объявляются бонусными, остальные считаются обязательными. Оценкой за экзамен является отношение суммы баллов, набранных студентом за все решенные им задачи, к числу обязательных задач в экзаменационном задании, умноженное на 10.

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

• 2023/2024 4th module
  Итог = Округление(min(0,3 * ДЗ + 0,35 * КОЛ + 0,35 * Э, 10)), где ДЗ — это оценка за все домашнее задание в целом, КОЛ — оценка за коллоквиум, Э — оценка за экзамен (см. выше). Эти оценки могут быть нецелыми и приводятся без округления с наибольшей доступной точностью. Округление производится к ближайшему целому. Полуцелые числа округляются вверх.

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

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

• Введение в сложность вычислений, Крупский, В. Н., 2006
• Верещагин, Н. К. Языки и исчисления : учебное пособие / Н. К. Верещагин, А. Х. Шень. — 2-е изд. — Москва : ИНТУИТ, 2016. — 278 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100547 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Успенский, В. А. Вводный курс математической логики / В.А. Успенский, Н.К. Верещагин, В.Е. Плиско. - 2-e изд. - Москва : ФИЗМАТЛИТ, 2007. - 128 с. ISBN 978-5-9221-0278-0, 2000 экз. - Текст : электронный. - URL: https://znanium.com/catalog/product/129565

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

• Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
• Michael Sipser. (2005). Introduction to the Theory of Computation, Second Edition.
• Vereshchagin, N., & Shen, A. (2017). Lectures on mathematical logic and algorithms theory. Part 3. Computable functions. ; Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. HAL CCSD.
• Теория рекурсивных функций и эффективная вычислимость, Роджерс, Х., 1972

Авторы

• Подольский Владимир Владимирович
• Верещагин Николай Константинович
• Вялый Михаил Николаевич