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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м (Общая информация: добавлена ссылка на чат)
м
 
(не показаны 94 промежуточные версии 2 участников)
Строка 1: Строка 1:
Факультатив дополняет курс дискретной математики-2 рядом сюжетов из математической логики и теории алгоритмов. Содержание курса может меняться в соответствии с желаниями слушателей: мы уделим больше внимания вопросам, заинтересовавшим аудиторию. Занятия планируется проводить в формате живой беседы участников. Мы будем пытаться самостоятельно приходить к некоторым важным идеям, прежде чем вводить формальные определения. Факультатив желательно (хотя и необязательно) посещать одновременно с изучением курса дискретной математики-2 или после прохождения этого курса.
+
Прямая ссылка на эту страницу: [https://tinyurl.com/logicomp tinyurl.com/logicomp]
  
==Общая информация==
+
==Архив==
'''Официальное название:''' «Избранные вопросы теории вычислений и математической логики».
+
* [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%22_(%D0%9E%D1%81%D0%B5%D0%BD%D1%8C_2020) Факультатив "Вычислимость и логика", осень 2020]
  
'''Преподаватель:''' [https://www.hse.ru/org/persons/305069360 Антон Гнатенко], почта: [mailto:agnatenko@hse.ru agnatenko@hse.ru], телеграм: [https://t.me/antongnatenko @antongnatenko].
+
* [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9%22_(%D0%92%D0%B5%D1%81%D0%BD%D0%B0_2021) Факультатив "Теория вычислений", весна 2021]
 
+
'''Время и место:''' среда (с 16 сентября), 9:30-10:50, '''Zoom''': <здесь будет ссылка>
+
 
+
'''Записи занятий:''' <и здесь будет ссылка>
+
 
+
'''Телеграм-чат:''' https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w
+
 
+
Ссылка на эту страницу: https://tinyurl.com/logicomp
+
 
+
Форма для задач: https://forms.gle/erSRPvvgTbroDK5G8
+
 
+
==История==
+
Пока ничего не произошло
+
 
+
==Программа курса (примерная)==
+
 
+
Темы, ''написанные курсивом'', являются дополнительными. Мы рассмотрим их, если будет на то желание слушателей. Если ''курсивные темы'' станут реальностью, они могут вытеснить обычные темы и занять их место.
+
 
+
====Регулярные языки и автоматы====
+
* Детерминированные конечные автоматы и их языки
+
* Нерегулярные языки и лемма о накачке
+
* Недетерминированные автоматы
+
* Автоматы и поиск подстроки в строке
+
* ''Алгебраические свойства регулярных языков. Минимизация автоматов''
+
* ''Регулярные выражения''
+
* ''Автоматы на термах, на деревьях, над бесконечными словами, ...''
+
 
+
====Теория алгоритмов====
+
* Частично рекурсивные функции
+
* Лямбда-исчисление
+
* ''Вычисления с оракулом''
+
 
+
====Логика====
+
* Логические способы описания языков. Выразительная сила логик. Трансляция формул в автоматы и автоматов в формулы.
+
* Логическое программирование
+
* ''Арифметика и вычислимые функции. Теоремы Чёрча, Тарского и Гёделя''
+
* ''Доказуемость в арифметике и ещё одна теорема Гёделя''
+
* ''Логика второго порядка''
+
* '''''...''''' (это многоточие написано ''курсивом'')
+
 
+
==Правила оценивания==
+
Чтобы получить оценку, нужно набрать необходимое количество баллов (обычных и бонусных). Вот как это сделать:
+
 
+
* '''Решать задачи''', которые предлагаются на занятиях и появляются на этой страничке в разделе [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%22#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B8 «Задачи»]. Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться устная защита некоторых неслучайно выбранных задач. Баллы за задачу выставляются только в случае успешной защиты.
+
 
+
* '''Решать трудные задачи''', которые появляются там же. Отличия трудных задач от обычных:
+
** За них даются '''бонусные баллы''', и их даётся много
+
** Трудные задачи почти наверное придётся защищать устно
+
 
+
* '''Участвовать в занятиях'''. Иногда можно получить один или два '''бонусных балла''' за высказанную идею решения задачи, идею доказательства, ответ на вопрос.
+
 
+
Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр».
+
Тогда накопленная оценка равна P = min{S / M * 10, 10}.
+
 
+
Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.
+
 
+
Если P >= 4, то по желанию студента можно объявить её итоговой оценкой за факультатив. Если P < 4 или студент хочет улучшить оценку, проводится письменный экзамен, состоящий из нескольких обычных задач. Оценка за экзамен E равна доле решённых задач от общего количества, умноженной на 10. Итоговая оценка вычисляется по формуле F = 0.5P + 0.5E. Если F всё ещё меньше 4, экзамен можно пересдать. Если и это не поможет, можно сдавать устный экзамен комиссии. При этом P аннулируется и оценка, полученная на экзамене, является окончательной. (Будем надеяться, что до этого не дойдёт.)
+
 
+
==Задачи==
+
Письменные решения нужно сдавать [https://forms.gle/erSRPvvgTbroDK5G8 вот этой гугл-форме]. Пожалуйста, оформляйте решения аккуратно. Для оцифровки записей лучше всего использовать не фото, а специальные приложения-сканеры. Например, Camscanner. Если вы сдаёте несколько задач сразу, объединяйте их в один пдф или в один архив.
+
 
+
Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт.
+
 
+
Формат устной сдачи задач будет уточнён.
+
 
+
Задач пока нет. Можно расслабиться.
+
 
+
==Литература==
+
# Dexter C. Kozen. Automata and Computability. (Моя любимая книга про автоматы)
+
# Н.К. Верещагин, А. Шень. Вычислимые функции. (Незаменимая книга по курсу ДМ-2, в которой также можно почитать про рекурсивные функции, оракулы, арифметичность вычислимых функций)
+
# Дж. Булос, Р. Джеффри. Вычислимость и логика. (Немного философская книга про логику и алгоритмы, в которой есть много всего интересного и, в частности, кое-что про логику второго порядка)
+
# Dexter C. Kozen. Theory of Computation. (Ещё одна замечательная книга Декстера Козена по теории (сложности) вычислений; здесь можно прочитать про автоматы над бесконечными словами и про многое другое, не вошедшее, увы, в нашу программу)
+

Текущая версия на 14:29, 4 сентября 2021

Прямая ссылка на эту страницу: tinyurl.com/logicomp

Архив