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

Версия 02:15, 7 сентября 2020

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

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

Преподаватель: Антон Гнатенко, почта: agnatenko@hse.ru, телеграм: @antongnatenko.

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

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

Ссылка на эту страницу: https://tinyurl.com/logicomp

История

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

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

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

Регулярные языки и автоматы

• Детерминированные конечные автоматы и их языки
• Нерегулярные языки и лемма о накачке
• Недетерминированные автоматы
• Автоматы и поиск подстроки в строке
• Минимизация автоматов
• Регулярные выражения
• Автоматы на термах, на деревьях, над бесконечными словами, ...

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

• Частично рекурсивные функции
• Лямбда-исчисление
• Вычисления с оракулом

Логика

• Логические способы описания языков. Выразительная сила логик. Трансляция формул в автоматы и автоматов в формулы.
• Логическое программирование
• Арифметика и вычислимые функции. Теоремы Чёрча, Тарского и Гёделя
• Доказуемость в арифметике и ещё одна теорема Гёделя
• Логика второго порядка
• ... (это многоточие набрано курсивом)

Правила оценивания

Чтобы получить оценку, нужно набрать необходимое количество баллов (обычных и бонусных). Вот как это сделать:

• Решать задачи, которые предлагаются на занятиях и появляются на этой страничке в разделе «Задачи». Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно на почту agnatenko@hse.ru (с темой "logicomp-ФИО-Задачи"). В случае письменной сдачи может потребоваться устная защита некоторых неслучайно выбранных задач. Баллы за задачу выставляются только в случае успешной защиты.

• Решать трудные задачи, которые появляются там же. Отличия трудных задач от обычных:
  • За них даются бонусные баллы, и их даётся много
  • Трудные задачи сдаются только устно
  • На каждую трудную задачу принимается только одно решение

• Участвовать в занятиях. Иногда можно получить одно-два бонусных балла за высказанную идею решения задачи на семинаре, идею доказательства, ответ на вопрос.

Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр». Тогда итоговая оценка за курс равна O = min{S / M * 10, 10}.

Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.

Если итоговая оценка оказывается неудовлетворительной, то... (скоро станет известно, что будет)

Задачи

Задач пока нет. Можно расслабиться.

Литература

1. Dexter C. Kozen. Automata and Computability. (Моя любимая книга про автоматы)
2. Н.К. Верещагин, А. Шень. Вычислимые функции. (Незаменимая книга по курсу ДМ-2, в которой также можно почитать про рекурсивные функции, оракулы, арифметичность вычислимых функций)
3. Дж. Булос, Р. Джеффри. Вычислимость и логика. (Немного философская книга про логику и алгоритмы, в которой есть много всего интересного и, в частности, глава про логику второго порядка)
4. Dexter C. Kozen. Theory of Computation. (Ещё одна замечательная книга Декстера Козена по теории (сложности) вычислений; здесь можно прочитать про автоматы над бесконечными словами)