Избранные вопросы теории вычислений и математической логики

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

Модуль: 1-2

Кредиты: 2

Аннотация:

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

План занятий:

1. Детерминированные конечные автоматы и регулярные языки. 2. Недетерминированные конечные автоматы. Алгоритм детерминизации. 3. Лемма о накачке. Нерегулярные языки. 4. Алгоритмы поиска подстроки в строке с помощью теории автоматов. 5. *Алгебраическое описание регулярных языков. Минимизация автоматов. 6. *Регулярные выражения. 7. *Древесные и древоходные автоматы. 8. Частично рекурсивные функции. 9. Бестиповое лямбда-исчисление. 10. Логические системы FO(N, <), MSO(N, <), их выразительная сила. Национальный исследовательский университет «Высшая школа экономики» Программа дисциплины «Дискретная математика» для направления 01.03.02 «Прикладная математика и информатика» подготовки бакалавра 11. Автоматы Бюхи и Маллера. Трансляция формул MSO в автоматы Бюхи и обратно. 12. Основы логического программирования. Алгоритм вычисления логической программы. 13. *Формальная арифметика. Арифметичность вычислимых функций. Доказуемость. 14. *Логика второго порядка. 15. *Вычисления с оракулом. Темы, помеченные * являются дополнительными. Они могут быть включены в курс, если позволит время.

Формула оценивания:
Если О*дз не меньше 4, то по желанию студента она может быть проставлена автоматом как итоговая. То есть, О*итог = О*дз. Если О*дз меньше 4 или студент хочет улучшить оценку, проводится письменный экзамен, за который ставится оценка О*экз. Тогда О*итог= 0,5·О*дз + 0,5 О*экз

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

ПУД_Избранные вопросы теории вычислений и математической логики (PDF, 558 Кб) 

Для кого: 2 курс ПМИ

Расписание: среда 9:30-10:50 с 16 сентября (онлайн)

Подключиться к занятию