Математическая логика

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

Лучший по критерию «Новизна полученных знаний»

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

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

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

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

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

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

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

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

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

Кредиты: 4

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

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

Аннотация

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

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

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

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

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

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

Неформальное понятие алгоритма. Вычислимые функции, разрешимые и перечислимые множества.
Универсальные и главные вычислимые функции. $T$-Предикаты. Неразрешимость проблем самоприменимости и остановки.
Теорема Клини о неподвижной точке. Теоремы о рекурсии. Индексные множества. Теорема Райса—Успенского.
$m$-сводимость. Примеры сведений. Другие виды сводимости. Арифметическая иерархия.
Машины Тьюринга. Примеры вычислимых функций. Время и зона.
Языки первого порядка и их интерпретации. Структуры.
Выразимость множеств в структуре. Изоморфизм и элементарная экивалентность структур. Автоморфизмы структуры и невыразимость.
Логика первого порядка. Эквивалентность, общезначимость и выполнимость. Подстановки. Нормальные формы.
Теории первого порядка. Логическое следование. Игра Эренфойхта; полные теории. Теория плотных линейных порядков и ее модели.
Система натурального вывода. Теоремы о корректности и полноте.
Теорема компактности и ее следствия. Нестандартные модели арифметики.
Формальные арифметические теории PA и Q. Перечислимые множества и $\Sigma_1$-формулы. Первая теорема Гёделя о неполноте.

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

Домашнее задание
Коллоквиум
Экзамен

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

2021/2022 учебный год 2 модуль
В течение семестра проводится устный коллоквиум (КОЛ), выдается и проверяется письменное домашнее задание (ДЗ). Домашнее задание выдается частями, каждую из которых следует сдавать в установленные сроки. Преподаватель вправе потребовать от любого студента "защитить" (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля. Оценка КОЛ выставляется по десятибалльной системе без округления (т.е. с максимальной доступной используемым вычислительным средствам точностью). Оценка ДЗ выставляется в долях единицы также без округления, причем она может превосходить единицу засчет "бонусных баллов". По курсу проводится экзамен, оцениваемый по десятибалльной системе оценкой ЭКЗ. Результирующая оценка Р по дисциплине вычисляется по формуле Р = ОКРУГЛ ( min (10, 0.35 * ЭКЗ + 0.35 * КОЛ + 3 * ДЗ) ), причем применяются обычные правила округления, но полуцелые числа округляются вверх.

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