Факультатив "Теория вычислений и логика"
Факультатив дополняет курс дискретной математики-2 рядом сюжетов из математической логики и теории алгоритмов. Содержание курса может меняться в соответствии с желаниями слушателей: мы уделим больше внимания вопросам, заинтересовавшим аудиторию. Занятия планируется проводить в формате живой беседы участников. Мы будем пытаться самостоятельно приходить к некоторым важным идеям, прежде чем вводить формальные определения. Факультатив желательно (хотя и необязательно) посещать одновременно с изучением курса дискретной математики-2 или после прохождения этого курса.
Содержание
Общая информация
Официальное название: «Избранные вопросы теории вычислений и математической логики».
Преподаватель: Антон Гнатенко, почта: agnatenko@hse.ru, телеграм: @antongnatenko. Всюду на этой странице местоимение «я» обозначает именно этого человека.
Время и место: среда (с 16 сентября), 9:30-10:50, Zoom: https://zoom.us/j/99989396118
Записи занятий: https://www.youtube.com/playlist?list=PLbjUsKUoAqLPFWgiaIFX4QW__3Obyipcw
Телеграм-чат: https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w
Ссылка на эту страницу: https://tinyurl.com/logicomp
Форма для задач: https://forms.gle/erSRPvvgTbroDK5G8
История
16 сентября 2020. Занятие 1. Конечные автоматы и регулярные языки.
Видеозапись: https://youtu.be/80Ur1TKLU48
Конспект: https://drive.google.com/file/d/1Xa8nprULWAkrj5E1OFAci06ucIZoHCo_/view?usp=sharing
18 сентября 2020. Выложена первая порция задач. См. раздел «Задачи»
Программа курса (примерная)
Темы, написанные курсивом, являются дополнительными. Мы рассмотрим их, если будет на то желание слушателей. Если курсивные темы станут реальностью, они могут вытеснить обычные темы и занять их место.
Регулярные языки и автоматы
- Детерминированные конечные автоматы и их языки
- Нерегулярные языки и лемма о накачке
- Недетерминированные автоматы
- Автоматы и поиск подстроки в строке
- Алгебраические свойства регулярных языков. Минимизация автоматов
- Регулярные выражения
- Автоматы на термах, на деревьях, над бесконечными словами, ...
Теория алгоритмов
- Частично рекурсивные функции
- Лямбда-исчисление
- Вычисления с оракулом
Логика
- Логические способы описания языков. Выразительная сила логик. Трансляция формул в автоматы и автоматов в формулы.
- Логическое программирование
- Арифметика и вычислимые функции. Теоремы Чёрча, Тарского и Гёделя
- Доказуемость в арифметике и ещё одна теорема Гёделя
- Логика второго порядка
- ... (это многоточие написано курсивом)
Правила оценивания
Чтобы получить оценку, нужно набрать необходимое количество баллов (обычных и бонусных). Вот как это сделать:
- Решать задачи, которые предлагаются на занятиях и появляются на этой страничке в разделе «Задачи». Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться устная защита некоторых неслучайно выбранных задач. Баллы за задачу выставляются только в случае успешной защиты.
- Решать трудные задачи, которые появляются там же. За трудные задачи даются бонусные баллы (см. ниже).
- Участвовать в занятиях. Иногда можно получить один или два бонусных балла за высказанную идею решения задачи, идею доказательства, ответ на вопрос.
Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр». Тогда накопленная оценка равна P = min{S / M * 10, 10}.
Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.
Если P >= 4, то по желанию студента можно объявить её итоговой оценкой за факультатив. Если P < 4 или студент хочет улучшить оценку, проводится письменный экзамен, состоящий из нескольких обычных задач. Оценка за экзамен E равна доле решённых задач от общего количества, умноженной на 10. Итоговая оценка вычисляется по формуле F = 0.5P + 0.5E. Если F всё ещё меньше 4, экзамен можно пересдать. Если и это не поможет, можно сдавать устный экзамен комиссии. При этом P аннулируется и оценка, полученная на экзамене, является окончательной. (Будем надеяться, что до этого не дойдёт.)
Задачи
Письменные решения нужно сдавать вот этой гугл-форме. Пожалуйста, оформляйте решения аккуратно. Для оцифровки записей лучше всего использовать не фото, а специальные приложения-сканеры. Например, Camscanner. Если вы сдаёте несколько задач сразу, объединяйте их в один пдф или в один архив.
Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт.
Правила оформления решений. При изложении решений рекомендуется соблюдать разумный баланс между строгостью и размахиванием руками. Если требуется доказать, например, регулярность языка, то достаточно предоставить словесное описание соответствующего автомата (если только в условии явно не просят построить автомат). Описание должно быть, тем не менее, чётким и подробным (но без фанатизма). Если какие-то важные детали из этого описания будут неясны, я попрошу сделать пояснения (возможно, устные).
Формат устной сдачи задач будет уточнён.
Порция обычных задач №1. Мягкий дедлайн: 1 ноября.
Бонусные задачи (набор пополняется!). Можно сдавать до конца курса.
Литература
- Dexter C. Kozen. Automata and Computability. (Моя любимая книга про автоматы)
- Н.К. Верещагин, А. Шень. Вычислимые функции. (Незаменимая книга по курсу ДМ-2, в которой также можно почитать про рекурсивные функции, оракулы, арифметичность вычислимых функций)
- Дж. Булос, Р. Джеффри. Вычислимость и логика. (Немного философская книга про логику и алгоритмы, в которой есть много всего интересного и, в частности, кое-что про логику второго порядка)
- Dexter C. Kozen. Theory of Computation. (Ещё одна замечательная книга Декстера Козена по теории (сложности) вычислений; здесь можно прочитать про автоматы над бесконечными словами и про многое другое, не вошедшее, увы, в нашу программу)
