Содержание

1 Дискретная математика на 2-ом курсе ПМИ (пилотный поток)

Дискретная математика на 2-ом курсе ПМИ (пилотный поток)

Лекции проходят по субботам в 13-14:20 онлайн на платформе Zoom по ссылке https://zoom.us/j/99056983180?pwd=MkxkSjRWYm53b21oSXFOSVloS1dtZz09.

Новости

8 октября

Выложено третье домашнее задание.

21 сентября

Выложено второе домашнее задание.

1 сентября

Первая лекция будет 5 сентября.

Лектор

Верещагин Николай Константинович nikolay.vereshchagin@gmail.com

Семинары и семинаристы

191 Райко Илья Глебович mylntsa.ilya.63@gmail.com по понедельникам 9:30 - 10:50 (учебный ассистент Игорь Тараканов <79851126754@ya.ru>)

192 Верещагин Николай Константинович (e-mail: nikolay.vereshchagin@gmail.com, skype: vereshchagin, телеграмм @nikolay_vereshchagin) по субботам 14:40 - 16 онлайн на платформе Zoom по ссылке https://zoom.us/j/99063463658?pwd=bHdjZEtxNmtJTDBFcnVYUU8zSkkyUT09 (учебный ассистент Шабалина Анастасия Владимировна shabalina.nasty@gmail.com)

194 Оноприенко Анастасия Александровна ansidiana@yandex.ru по понедельникам 11:10 - 12:30 (учебный ассистент Амашукели Игорь Михайлович imamashukeli@edu.hse.ru). Для быстрой связи лучше писать в телеграм @ansidiana.

Краткое описание

Курс состоит из двух частей. В первом модуле будет общая теория вычислимости, во втором модуле будет изучаться математическая логика: формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами логики предикатов, исчисление резолюций.

Отчётность по курсу и критерии оценки

Тесты

В конце каждой лекции будет предлагаться десятиминутный тест с простыми задачами. Целью тестов является контроль за тем, чтобы студенты внимательно слушали лекцию. К написанию теста допускаются только присутствовавшие на лекции (разрешается десятиминутное опоздание к началу лекции). За каждый тест выставляется оценка, равная доле правильных ответов, умноженной на 10. Общая оценка за тесты равняется среднему арифметическому оценок за все тесты.

6 домашних заданий

В течение двух модулей студентам будет дано 6 домашних заданий. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу или ассистенту устно (очно или онлайн) или письменно. Какой из двух видов сдачи ДЗ разрешен, решается семинаристом каждой группы. Сдача домашних заданий после их срока невозможна.

В случае письменной сдачи ДЗ, оно в будет проверено в течение 10 дней после дедлайна и должно быть защищено студентом в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить семинариста или ассистента, что он понимает, что у него написано, и тем самым работа не списана. В случае устной сдачи защиты не требуется.

Коллоквиум и письменный экзамен

Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по теории вычислимости, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов, соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. Экзамен состоит из 8 задач с указанием количества баллов за каждую задачу. Эти баллы в сумме дают 10 баллов или больше. Задачи нужно решить за две пары.

Итоговая оценка

Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.3, а оценки за домашние задания и тесты - с коэффициентом 0.2.

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной. На экзамене комиссии будет выдан один билет из билетов коллоквиума (содержащий два теоретических вопроса и задачу), и при необходимости будет дана еще одна дополнительная задача.

Правила округления

В оценках за домашние задания промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления итоговой оценки. Используется арифметическое округление (то есть, 6.5 округляется до 7, а 6.49 - до 6).

Сдача домашних заданий

Группа 191: сдача домашних заданий проходит в устной форме ассистенту Игорю Тараканову (79851126754@ya.ru, тг @SetSplin) или семинаристу по четвергам (подробнее см. в разделе про консультации).

Группа 192: Сдача домашних заданий семинаристу Н.К. Верещагину проходит только в устной форме по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью Google Meet https://meet.google.com/noy-cait-jph. Сдача домашних заданий ассистенту А. Шабалиной также проходит только в устной форме в понедельник с 14:30 до 17:00, в среду с 10:00 до 15:00, в четверг с 10:00 до 12:00, в пятницу с 10:00 до 17:00, в субботу с 10:00 до 14:00, cвязаться можно через телеграм (@nastyash08) или почту (shabalina.nasty@gmail.com).

Группа 194: сдача домашних заданий проходит в устной форме, задачи принимает преимущественно ассистент Игорь Амашукели (почта imamashukeli@edu.hse.ru, телеграм @iamashukeli) в зуме. Можно также сдавать семинаристке в дискорде по четвергам после 14:00 либо в другой день по предварительной договорённости.

Сроки контрольных мероприятий

Первое домашнее задание: дедлайн для сдачи

группа 191: 21 сентября

группа 192: 19 сентября

группа 194: 21 сентября

Второе домашнее задание: дедлайн для сдачи

группа 191: 7 откября

группа 192: 5 октября

группа 194: 5 октября

Третье домашнее задание: дедлайн для сдачи

группа 191: 26 октября

группа 192: 22 октября

группа 194: 23 октября

Коллоквиум

Вопросы к коллоквиуму прошлого года.

Экзамен

Пересдачи

Работу можно посмотреть и апеллировать ...

Комиссия назначена на ... . Сдача экзамена комиссии происходит устно. Все предыдущие оценки аннулируются. На экзамене будет выдан один билет из билетов коллоквиума (содержащий два теоретических вопроса и задачу), и при необходимости будет дана еще одна дополнительная задача.

Домашние задания

Домашнее задание №1

Домашнее задание №2

Домашнее задание №3

Оценки за домашние задания и тесты

группа 191

группа 192

группа 194

Оценки за Tест 1

Оценка за Тест 2

Оценки за Тест 3

Оценки за Тест 4

Оценки за Тест 5

Оценки за Тест 6

Примерное содержание лекций

Вычислимые функции. Разрешимые и перечислимые множества.

Универсальные функции. Перечислимые неразрешимые множества. Неразрешимость проблемы остановки. Неотделимые перечислимые множества.

Теорема Клини о неподвижной точки. Теорема Райса-Успенского.

Машины Тьюринга. Тезис Чёрча-Тьюринга.

Алгоритмические проблемы. Примеры неразрешимых алгоритмических проблем.

Пропозициональные формулы.

Исчисление резолюций для пропозициональных формул.

Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели. Доказательства элементарной эквивалентности с помощью игр Эренфойхта

Исчисление резолюций для формул первого порядка.

Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.

Логическое следование и аксиоматические теории.

Прочитанные лекции

Лекция 1 (5 сентября).

Общее неформальное понятие алгоритма и конструктивного объекта. Исходное данное и результат работы алгоритма. Пошаговая работа алгоритма.

Определение вычислимой частичной функции из N в N. Счетность семейства частичных вычислимых функций, и существование невычислимых функций.

Разрешимые подмножества N. Перечислимые подножества N. Счетность семейства перечислимых множеств, и существование неперечислимых. Эквивалентные определения перечислимости (полуразрешимость, область определения вычислимой функции, множество значений вычислимой функции, проекции разрешимых множеств - без подробного доказательства). Теорема Поста. Теорема о графике.

Видеозапись лекции и семинара

Лекция 2 (12 сентября).

Универсальные вычислимые функции (нумерации) для семейства частичных вычислимых функций натурального аргумента. Несуществование универсальной вычислимой функции для семейства тотальных вычислимых функций натурального аргумента (диагональное рассуждение).

Вычислимая функция, не имеющая тотального вычислимого продолжения. Перечислимое неразрешимое множество. Неразрешимость проблемы применимости.

Перечислимые неотделимые множества.

Лекция 3 (19 сентября).

Перечислимые неотделимые множества.

Главные универсальные функции. Теорема Райса-Успенского. Теорема Клини о неподвижной точке.

Лекция 4 (26 сентября).

Еще раз о теореме Клини.

Сводимости: m-сводимость и Тьюрингова сводимость. Их свойства. Полные перечислимые множества. Теорема Мучника - Фридберга (без доказательства).

Односторонние и двусторонние ассоциативные исчисления. Полугруппы, заданные порождающими и соотношениями.

Лекция 5 (3 октября).

Определение машин Тьюринга и вычислимых на машинах Тьюринга функций. Тезис Чёрча-Тьюринга. Неразрешимость проблемы остановки машины Тьюринга.

Неразрешимость проблемы достижимости в односторонних ассоциативных исчислениях (с доказательством).

Лекция 6 (10 октября).

Неразрешимость проблемы достижимости в двусторонних ассоциативных исчислениях (с доказательством). Неразрешимость проблемы равенства слов в конечно определенных полугруппах.

Язык логики высказываний, формулы логики высказываний, связь со схемами. Выбор набора связок. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ (напоминание). Эквивалентные формулы.

Планируемые лекции

Лекция 7 (17 октября).

Основные эквивалентности.

Проблема проверки тавтологичности (выполнимости), ее NP полнота (без точных определений).

Исчисление высказываний, понятие вывода. Теорема корректности исчисления высказываний. Вывод из гипотез. Лемма о дедукции. Полезные производные правила. Теорема полноты ИВ и ее доказательство.

Лекция 8 (31 октября).

Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности. Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно).

Опровержение пропозициональных формул общего вида в исчислении резолюций.

Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка.

Модели (интепретации) сигнатуры. Нормальные модели. Общезначимые и выполнимые формулы. Равносильные формулы.

Теории и их модели. Семантическое следование.

Лекция 9 (7 ноября).

Теорема Черча об алгоритмической неразрешимости отношения семантического следования, общезначимости и равносильности формул (с доказательством).

Перечислимость множества общезначимых формул (пока без доказательства). Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР.

Лекция 10 (14 ноября).

Непротиворечивые теории. Теорема полноты ИР (для множеств универсальных дизъюнктов). Исчисление резолюций для теорий, состоящих из формул общего вида (приведение к предваренной нормальной форме и сколемизация). Доказательства общезначимости с помощью ИР. Выводимость формулы в теории с помощью ИР.

Лекция 11 (21 ноября).

Теорема компактности.

Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Теорема о сохранении истинности при эпиморфизме (с доказательством). Изоморфные модели. Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей.

Аксиомы равенства. Теорема полноты ИР для нормальных моделей (если теория не имеет нормальных моделей, то из её аксиом и аксиом равенства можно вывести пустой дизъюнкт).

Лекция 12 (28 ноября).

Игры Эренфойхта. Примеры: упорядоченные множества целых и рациональных чисел, рациональных и действительных чисел, Z и Z+Z. Доказательство элементарной эквивалентности с помощью игры Эренфойхта (доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны).

Выразимые (определимые отношения). Сохранение выразимых отношений при автоморфизмах. Доказательства невыразимости.

Лекция 13 (5 декабря).

Cемантически полные теории. Критерий семантической полноты в терминах элементарной эквивалентности моделей.

Задача аксиоматизации данной интерпретации.

Аксиоматизация элементарной теории упорядоченного множества рациональных чисел (доказательство элементарной эквивалентности моделей с помощью игры Эренфойхта).

Аксиоматизация элементарной теории упорядоченного множества целых чисел (доказательство элементарной эквивалентности моделей с помощью игры Эренфойхта).

Аксиоматизация элементарной теории упорядоченного множества действительных чисел. Аксиоматизация элементарной теории поля комплексных чисел. Обе теоремы без доказательства.

Семинары

Листки с задачами для семинаров

Листок 1. Вычислимые функции, разрешимые, полуразрешимые и перечислимые множества.

Листок 2. Универсальные функции, неразрешимые и неперечислимые множества.

Листок 3. Главные универсальные функции, теоремы Клини и Успенского - Райса.

Листок 4. Машины Тьюринга

Листок 5. Ассоциативные исчисления и проблемы разрешения

Семинары в группе 192

Семинар 1 (5 сентября)

Вычислимые функции, разрешимые и перечислимые множества (листок 1 задачи 1-14).

Семинар 2 (12 сентября)

Закончили первый листок и сделали задачи 1-13 из второго листка.

Семинар 3 (19 сентября)

Закончили второй листок. Из третьего листка сделали задачи 1, 3,4,5

Семинар 4 (26 сентября)

Закончили задачей 13 из листка 3.

Семинар 5 (3 октября)

Закончили листок 3 и листок 4.

Семинар 6 (10 октября)

Семинар 7 (17 октября)

Семинар 8 (31 октября)

Семинар 9 (7 ноября)

Семинар 10 (14 ноября)

Семинар 11 (21 ноября)

Семинар 12 (28 ноября)

Семинар 13 (5 декабря)

Семинар 14 (12 декабря)

Семинар 15 (19 декабря)

Конспекты лекций

Конспект лекций о методе резолюций

Консультации

Консультации Н.К. Верещагина: по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью skype (vereshchagin) или телеграмм (@nikolay_vereshchagin) или Google Meet https://meet.google.com/noy-cait-jph

Консультации И.Г. Райко: Очно или онлайн в соответствии с таблицей. Для онлайн связи напишите в телеграм @ilya0x2dilya -- там поймём, как нам связаться.

Консультации А.А. Оноприенко: четверг 14-20 в дискорде https://discord.gg/v5DbugV (если меня там нет, пишите в телеграм @ansidiana).

DM2-pilot2020/2021