Факультатив "Теория вычислений и логика"

Факультатив дополняет курс дискретной математики-2 рядом сюжетов на стыке математической логики и теории алгоритмов. Мы рассмотрим несколько универсальных моделей вычислений, вычисления с оракулом, вычисления с конечной памятью, поговорим о связи логики и теории автоматов, о логическом программировании и о логике второго порядка. Содержание курса может меняться в соответствии с желаниями слушателей: мы уделим больше внимания вопросам, заинтересовавшим аудиторию. Занятия планируется проводить в формате живой беседы участников. Мы будем пытаться самостоятельно приходить к некоторым важным идеям, прежде чем вводить формальные определения. Факультатив желательно (хотя и необязательно) посещать одновременно с изучением курса дискретной математики-2 или после прохождения этого курса.

Общая информация

Преподаватель: Антон Гнатенко

Начало занятий: на третьей неделе сентября

Время и место: TBA

Программа курса (примерная)

Теория алгоритмов

• Вычисления с оракулом
• Сведéния и арифметическая иерархия
• Частично рекурсивные функции
• Лямбда-исчисление
• Интуиционисткая логика высказываний

Вычисления с конечной памятью

• Формальные языки и автоматы. Регулярные языки. Приложения теории автоматов
• Логические способы описания языков
• Контекстно-свободные языки

Логика

• Логическое программирование (чуть-чуть)
• Выразимость и доказуемость в арифметике
• Логика второго порядка

Сводка

Пока ничего не произошло