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

Версия 23:57, 16 сентября 2020

Факультатив дополняет курс дискретной математики-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

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

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

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

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

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

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

Логика

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

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

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

• Решать задачи, которые предлагаются на занятиях и появляются на этой страничке в разделе «Задачи». Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться устная защита некоторых неслучайно выбранных задач. Баллы за задачу выставляются только в случае успешной защиты.

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

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

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