|
|
| (не показано 112 промежуточных версии 2 участников) |
| Строка 1: |
Строка 1: |
| − | Факультатив дополняет курс дискретной математики-2 рядом сюжетов из математической логики и теории алгоритмов. Содержание курса может меняться в соответствии с желаниями слушателей: мы уделим больше внимания вопросам, заинтересовавшим аудиторию. Занятия планируется проводить в формате живой беседы участников. Мы будем пытаться самостоятельно приходить к некоторым важным идеям, прежде чем вводить формальные определения. Факультатив желательно (хотя и необязательно) посещать одновременно с изучением курса дискретной математики-2 или после прохождения этого курса.
| + | Прямая ссылка на эту страницу: [https://tinyurl.com/logicomp tinyurl.com/logicomp] |
| | | | |
| − | ==Общая информация== | + | ==Архив== |
| − | Преподаватель: [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_%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] |
| | | | |
| − | Начало занятий: на третьей неделе сентября (будет объявлено на лекциях по ДМ-2)
| + | * [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] |
| − | | + | |
| − | Время и место: TBA
| + | |
| − | | + | |
| − | ==История==
| + | |
| − | Пока ничего не произошло
| + | |
| − | | + | |
| − | ==Программа курса (примерная)==
| + | |
| − | | + | |
| − | Темы, ''написанные курсивом'', являются дополнительными. Мы рассмотрим их, если будет на то желание слушателей. Если ''курсивные темы'' станут реальностью,
| + | |
| − | они могут вытеснить обычные темы и занять их место.
| + | |
| − | | + | |
| − | ====Регулярные языки и автоматы====
| + | |
| − | * Детерминированные конечные автоматы и их языки | + | |
| − | * Нерегулярные языки и лемма о накачке
| + | |
| − | * Недетерминированные автоматы
| + | |
| − | * Автоматы и поиск подстроки в строке
| + | |
| − | * ''Минимизация автоматов''
| + | |
| − | * ''Регулярные выражения''
| + | |
| − | * ''Автоматы на термах, на деревьях, над бесконечными словами, ...''
| + | |
| − | | + | |
| − | ====Теория алгоритмов====
| + | |
| − | * Частично рекурсивные функции
| + | |
| − | * Лямбда-исчисление
| + | |
| − | * ''Вычисления с оракулом''
| + | |
| − | | + | |
| − | ====Логика====
| + | |
| − | * Логические способы описания языков. Выразительная сила логик. Трансляция формул в автоматы и автоматов в формулы.
| + | |
| − | * Логическое программирование
| + | |
| − | * ''Арифметика и вычислимые функции. Теоремы Чёрча, Тарского и Гёделя''
| + | |
| − | * ''Доказуемость в арифметике и ещё одна теорема Гёделя''
| + | |
| − | * ''Логика второго порядка''
| + | |
| − | * '''''...''''' (это многоточие набрано ''курсивом'')
| + | |
| − | | + | |
| − | ==Правила оценивания==
| + | |
| − | Чтобы получить оценку, нужно набрать необходимое количество баллов (обычных и бонусных). Вот как это сделать:
| + | |
| − | | + | |
| − | * '''Решать задачи''', которые предлагаются на занятиях и появляются на этой страничке в разделе [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 «Задачи»]. Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно на почту [mailto:agnatenko@hse.ru agnatenko@hse.ru] (с темой "logicomp-ФИО-Задачи"). В случае письменной сдачи может потребоваться устная защита некоторых неслучайно выбранных задач. Баллы за задачу выставляются только в случае успешной защиты.
| + | |
| − | | + | |
| − | * '''Решать трудные задачи''', которые появляются там же. Отличия трудных задач от обычных:
| + | |
| − | ** За них даются '''бонусные баллы''', и их даётся много
| + | |
| − | ** Трудные задачи сдаются '''только устно'''
| + | |
| − | ** На каждую трудную задачу принимается '''только одно''' решение
| + | |
| − | | + | |
| − | * '''Участвовать в занятиях'''. Иногда можно получить одно-два '''бонусных балла''' за высказанную идею решения задачи на семинаре, идею доказательства, ответ на вопрос.
| + | |
| − | | + | |
| − | Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр».
| + | |
| − | Тогда итоговая оценка за курс равна O = min{S / M * 10, 10}.
| + | |
| − | | + | |
| − | Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.
| + | |
| − | | + | |
| − | Если итоговая оценка оказывается неудовлетворительной, то... (скоро станет известно, что будет)
| + | |
| − | | + | |
| − | ==Задачи==
| + | |
| − | Задач пока нет. Можно расслабиться.
| + | |
| − | | + | |
| − | ==Материалы==
| + | |
| − | # Dexter C. Kozen. Automata and Computability. (Моя любимая книга про автоматы)
| + | |
| − | # Н.К. Верещагин, А. Шень. Вычислимые функции. (Незаменимая книга по курсу ДМ-2, в которой также можно почитать про рекурсивные функции, оракулы, арифметичность вычислимых функций)
| + | |
| − | # Дж. Булос, Р. Джеффри. Вычислимость и логика. (Немного философская книга про логику и алгоритмы, в которой есть много всего интересного и, в частности, глава про логику второго порядка)
| + | |
| − | # Dexter C. Kozen. Theory of Computation. (Ещё одна замечательная книга Декстера Козена по теории (сложности) вычислений; здесь можно прочитать про автоматы над бесконечными словами)
| + | |
