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

1. Множества и их мощности. Счётные и несчётные множества. Диагональный метод Кантора.
2. Абстрактное понятие алгоритма. Машины Тьюринга. Счётность множества всех алгоритмов.
3. Вычислимые функции. Разрешимые и перечислимые множества. Существование невычислимых функций и неразрешимых множеств из соображений мощности.
4. Неразрешимость проблем самоприменимости и остановки. Теорема Успенского-Райса.
5. Понятие m-сводимости. Построение неперечислимого множества, дополнение к которому также неперечислимо.
6. Алгоритмически неразрешимые задачи в комбинаторике и алгебре.
7. Теорема Клини о неподвижной точке. Существование в любом языке программирования программы, печатающей собственный текст.
8. Понятие формальной системы доказательств. Аксиомы формальной арифметики.
9. Теорема Гёделя о неполноте. Существование принципиально непознаваемой программы.
10. Лямбда-исчисление: синтаксис, приведение к нормальной форме, нумералы Чёрча, реализация простейших функций.
11. Лямбда-исчисление: комбинатор неподвижной точки и рекурсивное программирование.
12. Основы теории сложности вычислений: измерение времени работы программы. Классы P и NP. Проблема перебора (равны ли классы P и NP). NP-полные задачи.

Результаты обучения

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

Формат
Каждую неделю вас ждут видеолекции и проверочные задания, которые нужно выполнять в срок.
В конце – итоговая проверочная работа. Студенты, которые набрали достаточное количество баллов, смогут получить сертификат.

Требования
Все необходимые понятия будут определяться по ходу курса, однако от слушателей предполагается достаточно свободное владение аппаратом дискретной математики и булевой логики. Желателен хотя бы небольшой опыт написания программ.

Сертификат
Сертификат участника обычно выдается при достижении 60% от общего рейтинга при условии сдачи работ до жесткого дедлайна. Сертификат с отличием, как правило, выдается при достижении 90% от общего рейтинга при условии сдачи работ до мягкого дедлайна.