DM2-basic2019/2020 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия 9 участников)
Строка 1: Строка 1:
 
= Дискретная математика на 2-ом курсе ПМИ (основной поток)=
 
= Дискретная математика на 2-ом курсе ПМИ (основной поток)=
  
−
Лекции проходят по вторникам  в 12:10-13:30 в аудитории R304.
+
Лекции проходят по вторникам  в 12:10-13:30 в аудитории R301.
  
 
==Новости==
 
==Новости==
 +
====25 декабря====
 +
Выложены результаты проверки экзаменационных работ: 
 +
[https://www.dropbox.com/s/bn702991y4ij7m0/exam-results-base.xls?dl=0 Оценки экзамена]. [https://www.dropbox.com/s/5o2kp4utogm5yfc/exam-19-12-24-sol.pdf?dl=0 Решения и критерии выставления баллов.]
  
 +
====8 декабря====
 +
Выложено шестое (последнее) домашнее задание.
 +
====27 ноября====
 +
Выложены вопросы коллоквиума.
 +
====6 ноября====
 +
Выложено четвертое домашнее задание.
  
 
==Лектор==  
 
==Лектор==  
Строка 18: Строка 27:
 
Охрименко Дмитрий Андреевич daokhrimenko@edu.hse.ru).
 
Охрименко Дмитрий Андреевич daokhrimenko@edu.hse.ru).
  
−
186 Дашков Евгений Владимирович edashkov@gmail.com (учебный ассистент
+
186 Дашков Евгений Владимирович edashkov@gmail.com (учебный ассистент Бочкарева Мария Игоревна, peggy-sju@ya.ru, [https://t.me/Adalanthe telegram]).
−
Марданов Эльмир Фларитович efmardanov_1@edu.hse.ru).
+
  
 
187 Дашков Евгений Владимирович edashkov@gmail.com (учебный ассистент
 
187 Дашков Евгений Владимирович edashkov@gmail.com (учебный ассистент
 
Бондаренко Наталия Сергеевна nataliyabon20142014@gmail.com).
 
Бондаренко Наталия Сергеевна nataliyabon20142014@gmail.com).
  
−
188 Козачинский Александр Николаевич kozlach@mail.ru (учебный
+
188 Козачинский Александр Николаевич kozlach@mail.ru, '''[https://t.me/joinchat/GQufoBMbdeTW4gixEfbe4A группа в telegram, где можно задать вопрос]''' (учебный
 
ассистент Моисеев Андрей Андреевич andrei.moiseev213@yandex.ru).
 
ассистент Моисеев Андрей Андреевич andrei.moiseev213@yandex.ru).
  
Строка 49: Строка 57:
  
 
====Правила округления====  
 
====Правила округления====  
 +
 +
(не забыть исправить - в следующем году округление будет только при выставлении итоговой оценки).
  
 
В оценках за домашние задания промежуточные величины не округляются. Результат
 
В оценках за домашние задания промежуточные величины не округляются. Результат
Строка 58: Строка 68:
 
===Сдача домашних заданий===
 
===Сдача домашних заданий===
  
−
Первое домашнее задание: дедлайн для сдачи  
+
====Первое домашнее задание: дедлайн для сдачи====
  
 
группа 183: 17 сентября (защита до 9 октября).
 
группа 183: 17 сентября (защита до 9 октября).
 +
 +
Группа 185: 17 сентября (защита до 9 октября).
  
 
группа 186: 17 сентября (защита до 9 октября).
 
группа 186: 17 сентября (защита до 9 октября).
  
 
группа 187: 17 сентября (защита до 9 октября).
 
группа 187: 17 сентября (защита до 9 октября).
 +
 +
группа 188: 20 сентября (защита до 15 октября)
 +
 +
====Второе домашнее задание: дедлайн для сдачи====
 +
 +
группа 183: 1 октября (защита до 29 октября).
 +
 +
Группа 185: 1 октября (защита до 23 октября).
 +
 +
группа 186: 2 октября (защита до 23 октября).
 +
 +
группа 187: 2 октября (защита до 23 октября).
 +
 +
группа 188: 4 октября (защита до 26 ноября).
 +
 +
====Третье  домашнее задание: дедлайн для сдачи====
 +
 +
группа 183: 29 октября (защита до 19 ноября).
 +
 +
Группа 185: 29 октября (защита до 19 ноября).
 +
 +
группа 186: 29 октября (защита до 19 ноября).
 +
 +
группа 187: 29 октября (защита до 19 ноября).
 +
 +
группа 188: 29 октября (защита до 26 ноября).
 +
 +
====Четвертое  домашнее задание: дедлайн для сдачи====
 +
 +
группа 183: 19 ноября (защита до 3 декабря).
 +
 +
Группа 185: 19 ноября (защита до 3 декабря).
 +
 +
группа 186: 19 ноября (защита до 3 декабря).
 +
 +
группа 187: 19 ноября (защита до 3 декабря).
 +
 +
группа 188: 22 ноября (защита до 10 декабря).
 +
 +
====Пятое  домашнее задание: дедлайн для сдачи====
 +
 +
группа 183: 3 декабря (защита до 17 декабря).
 +
 +
группа 185: 3 декабря (защита до 17 декабря).
 +
 +
группа 186: 6 декабря (защита до 20 декабря).
 +
 +
группа 187: 6 декабря (защита до 20 декабря).
 +
 +
====Шестое  домашнее задание: дедлайн для сдачи====
 +
 +
группа 183: 17 декабря (защита до 26 декабря).
 +
 +
группа 185: 17 декабря (защита до 26 декабря).
 +
 +
группа 186: 20 декабря.
 +
 +
группа 187: 20 декабря.
 +
 +
группа 188: 20 декабря.
  
 
===Коллоквиум===
 
===Коллоквиум===
  
−
Коллоквиум пройдет в субботу 14 декабря (дата предварительная).  
+
Коллоквиум пройдет в субботу 14 декабря с 10:30 до 18 в ауд. R204.  
−
Пересдача коллоквиума 26 декабря (дата предварительная).  
+
  
−
[https://www.dropbox.com/s/r6okjtbl5rjyuc5/colloq.pdf?dl=0 Вопросы к коллоквиуму 2018 года.]
 
  
−
===Экзамен===
+
на 10:30 приглашаются группы 182 185
  
−
Экзамен (письменный) состоится во вторник 24 декабря (дата предварительная).
+
на 11:30 - группа 183
  
−
Показ работ 26 декабря (дата предварительная).
+
на 12:30 - группы 181, 186
  
−
Оценки за экзамен [https://www.dropbox.com/s/ucj8g100p539hi1/exam-results-base.xls?dl=0 здесь]. Критерии выставления баллов
+
на 13:30 - группа 188
−
за решения задач [https://www.dropbox.com/s/6ynuq37i6z3lm98/exam-base-criteria.docx?dl=0 здесь]. [https://www.dropbox.com/s/qfb0fqn7zultigv/sol-18-12-21.pdf?dl=0 Решения задач экзамена.]
+
 
 +
на 15:00 - группы 184, 187
 +
 
 +
 
 +
 
 +
 
 +
Пересдача коллоквиума 26 декабря в 12:10 в R407.
 +
 
 +
[https://www.dropbox.com/s/il9qdzubwsfmcvd/colloq.pdf?dl=0 Вопросы к коллоквиуму этого года.]
 +
 
 +
===Экзамен===
 +
[https://www.dropbox.com/s/bn702991y4ij7m0/exam-results-base.xls?dl=0 Оценки экзамена 24.12.2019]. [https://www.dropbox.com/s/5o2kp4utogm5yfc/exam-19-12-24-sol.pdf?dl=0 Решения и критерии выставления баллов.]
  
 
===Пересдачи===
 
===Пересдачи===
  
−
Пересдача коллоквиума 26 декабря (дата предварительная).  
+
Пересдача коллоквиума 26 декабря.  
−
Пересдачи письменного экзамена 22 января, 29 января (даты предварительные).
+
Пересдачи письменного экзамена 15.01.2020 начало 15:10 в ауд. ауд. R503 и  30 января в 15:10 в ауд. D501.
  
−
Комиссия 5 февраля (дата предварительная).
+
 
 +
[https://www.dropbox.com/s/bn702991y4ij7m0/exam-results-base.xls?dl=0 Оценки экзамена 30.1.2020]. [https://www.dropbox.com/s/me5crykd5cfadyj/exam-20-01-30-solutions.pdf?dl=0 Решения.] Работу можно посмотреть и апеллировать во вторник 4 февраля в 16:30 в ауд. D506.
 +
 
 +
 
 +
Комиссия назначена на 6 февраля в ауд. R407 в 16:00.
 +
Сдача экзамена комиссии происходит устно. Все предыдущие оценки аннулируются. На экзамене будет выдан один билет из билетов коллоквиума (содержащий два теоретических вопроса и задачу), и при необходимости будет дана еще одна дополнительная задача.
  
 
==Домашние задания  ==
 
==Домашние задания  ==
  
−
[https://www.dropbox.com/s/nsq79r42q4c4m2f/hw1.pdf?dl=0 Домашнее задание №1]  
+
[https://www.dropbox.com/s/wt6vj0k0mnkedqy/hw1.pdf?dl=0 Домашнее задание №1]
 +
 +
[https://www.dropbox.com/s/so4p31iyfmm1ug5/hw2.pdf?dl=0 Домашнее задание №2]
 +
 
 +
[https://www.dropbox.com/s/8he14kac4db5k37/hw3.pdf?dl=0 Домашнее задание №3]
 +
 
 +
[https://www.dropbox.com/s/2ylhveh12rkiy61/hw4.pdf?dl=0 Домашнее задание №4]
 +
 
 +
[https://www.dropbox.com/s/y7dah98f1kc0qr9/hw5.pdf?dl=0 Домашнее задание №5]
 +
 
 +
[https://www.dropbox.com/s/muhabdbo35c80t1/hw6.pdf?dl=0 Домашнее задание №6]  
  
 
===Оценки за домашние задания===
 
===Оценки за домашние задания===
 
   
 
   
  
−
[https://www.dropbox.com/s/g9q5mw6eljkq17u/173.xls?dl=0 группа 173]
+
[https://www.dropbox.com/s/fr7psb6dvno52dq/183.xls?dl=0 группа 183]
 +
 
 +
[https://www.dropbox.com/s/upecabtj40r4xpv/185.xls?dl=0    группа 185]
  
−
[https://www.dropbox.com/s/qra66oyveikecp2/174.xls?dl=0 группа 174]
+
[https://www.dropbox.com/s/sbr7sl0m3moq89n/186.xls?dl=0 группа 186]
  
−
[https://www.dropbox.com/s/zp7zlmjnl3h7bja/175.xls?dl=0 группа 175]
+
[https://www.dropbox.com/s/qyk8vjntjti0b1g/187.xls?dl=0 группа 187]
  
−
[https://docs.google.com/spreadsheets/d/10mP2yoXNElULWPk2xR-sI1fsXqqAAGhfXxyGMV91XDo/edit#gid=0 группа 176]
+
[https://www.dropbox.com/s/fc7v7c9gp5wp648/188.xlsx?dl=0 группа 188]
  
 
==Примерное содержание лекций==
 
==Примерное содержание лекций==
Строка 134: Строка 232:
 
Общее неформальное понятие алгоритма и конструктивного объекта. Исходное данное и результат работы алгоритма. Пошаговая работа алгоритма.
 
Общее неформальное понятие алгоритма и конструктивного объекта. Исходное данное и результат работы алгоритма. Пошаговая работа алгоритма.
  
−
Определение вычислимой частичной функции из N в N.
+
Определение вычислимой частичной функции из N в N. Счетность семейства частичных вычислимых функций, и существование невычислимых функций.  
  
−
Разрешимые подмножества N. Перечислимые подножества N. Эквивалентные определения перечислимости (полуразрешимость, область определения вычислимой функции, множество значений вычислимой функции - без доказательства). Теорема Поста. Теорема о графике.
+
Разрешимые подмножества N. Перечислимые подножества N. Счетность семейства перечислимых множеств, и существование неперечислимых. Эквивалентные определения перечислимости (полуразрешимость, область определения вычислимой функции, множество значений вычислимой функции - без подробного доказательства). Теорема Поста. Теорема о графике.
  
 
====Лекция 2 (10 сентября).  ====
 
====Лекция 2 (10 сентября).  ====
  
−
Универсальные вычислимые функции для семейства частичных вычислимых функций натурального аргумента. Несуществование универсальной вычислимой функции для семейства тотальных вычислимых функций натурального аргумента (диагональное рассуждение).  
+
Универсальные вычислимые функции (нумерации) для семейства частичных вычислимых функций натурального аргумента. Несуществование универсальной вычислимой функции для семейства тотальных вычислимых функций натурального аргумента (диагональное рассуждение). Главные универсальные функции.  
  
 
Вычислимая функция, не имеющая тотального вычислимого продолжения. Перечислимое неразрешимое множество. Неразрешимость проблемы применимости.
 
Вычислимая функция, не имеющая тотального вычислимого продолжения. Перечислимое неразрешимое множество. Неразрешимость проблемы применимости.
Строка 148: Строка 246:
 
====Лекция 3 (17 сентября).  ====
 
====Лекция 3 (17 сентября).  ====
  
−
Главные универсальные функции. Теорема Клини о неподвижной точке. Теорема Райса-Успенского.  
+
Сводимости: m-сводимость и Тьюрингова сводимость. Их свойства. Полные перечислимые множества.  
  
−
Определение машин Тьюринга и вычислимых на машинах Тьюринга функций. Тезис Чёрча-Тьюринга. Неразрешимость проблемы остановки  машины Тьюринга.
+
Теорема Клини о неподвижной точке. Теорема Райса-Успенского.
  
 
====Лекция 4 (24 сентября).  ====
 
====Лекция 4 (24 сентября).  ====
  
−
Определения и свойства сводимостей.  
+
Определение машин Тьюринга и вычислимых на машинах Тьюринга функций. Тезис Чёрча-Тьюринга. Неразрешимость проблемы остановки  машины Тьюринга.
  
−
Неразрешимость задачи достижимости в ассоциативных исчислениях.  Полугруппы, заданные порождающими и соотношениями. Двусторонние исчисления.  Неразрешимость проблемы равенства слов в полугруппах.
+
Неразрешимость проблемы достижимости в односторонних в ассоциативных исчислениях (с доказательством).   
 +
Полугруппы, заданные порождающими и соотношениями. Неразрешимость проблемы равенства слов в конечно определенных полугруппах (без доказательства).
  
 
====Лекция 5 (1 октября).  ====
 
====Лекция 5 (1 октября).  ====
  
−
====Лекция 6 (8 октября). ====
+
Язык логики высказываний, формулы логики высказываний, связь со схемами. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ (напоминание).  
 +
Эквивалентные формулы. Основные эквивалентности.
  
−
====Лекция 7 (15 октября). ====
+
Проблема проверки тавтологичности (выполнимости), ее NP полнота (без точных определений).
  
−
====Лекция 8 (29 октября). ====
+
Исчисление высказываний, понятие вывода.
  
−
Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ. (Очень кратко.)
+
====Лекция 6 (8 октября).  ====
 +
 
 +
Теорема корректности исчисления высказываний.
 +
Вывод из гипотез. Лемма о дедукции. Полезные производные правила. Теорема полноты ИВ и ее доказательство.
 +
 
 +
====Лекция 7 (15 октября).  ====
  
 
Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности.
 
Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности.
 +
Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно).
  
−
====Лекция 9 (5 ноября).  ====
+
Опровержение пропозициональных формул общего вида в исчислении резолюций.  
−
Еще раз формулировка ИР.  Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно).  
+
  
−
Опровержение пропозициональных формул общего вида в исчислении резолюций.
+
====Лекция 8 (29 октября). ====
  
−
Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка.  
+
Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка.
  
 
Модели (интепретации) сигнатуры.  
 
Модели (интепретации) сигнатуры.  
 +
Нормальные модели. Общезначимые и выполнимые формулы. Равносильные формулы.
  
−
====Лекция 10 (12 ноября).  ====
+
Теории и их модели. Семантическое следование.  
−
Нормальные модели. Общезначимые и выполнимые формулы. Равносильные формулы.  
+
  
−
Теории и их модели. Семантическое следование. Теорема Черча об алгоритмической неразрешимости общезначимости, а значит и отношения семантического следования и отношения равносильности формул (без доказательства).  
+
====Лекция 9 (5 ноября). ====
 +
 
 +
Теорема Черча об алгоритмической неразрешимости отношения семантического следования, общезначимости и равносильности формул (с доказательством).
  
 +
Перечислимость множества общезначимых формул (пока без доказательства).
 
Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР.  
 
Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР.  
  
−
====Лекция 11 (19 ноября).  ====
+
====Лекция 10 (12 ноября).  ====
−
Непротиворечивые теории. Теорема полноты ИР (для множеств универсальных дизъюнктов). Исчисление резолюций для теорий, состоящих из формул общего вида (приведение к предваренной нормальной форме и сколемизация).  
+
Непротиворечивые теории. Теорема полноты ИР (для множеств универсальных дизъюнктов). Исчисление резолюций для теорий, состоящих из формул общего вида (приведение к предваренной нормальной форме и сколемизация).
−
 
+
 
Доказательства общезначимости с помощью ИР. Выводимость формулы в теории с помощью ИР.
 
Доказательства общезначимости с помощью ИР. Выводимость формулы в теории с помощью ИР.
  
 +
====Лекция 11 (19 ноября).  ====
 +
Теорема компактности.
  
−
 
+
Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Теорема о сохранении истинности при эпиморфизме (с доказательством).  
−
====Лекция 12 (26 ноября).  ====
+
−
Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Теорема о сохранении истинности при эпиморфизме (без подробного доказательства).  
+
 
Изоморфные модели. Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей.  
 
Изоморфные модели. Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей.  
  
Строка 200: Строка 307:
 
её аксиом и аксиом равенства можно вывести пустой дизъюнкт).
 
её аксиом и аксиом равенства можно вывести пустой дизъюнкт).
  
−
Доказательство элементарной эквивалентности с помощью игры Эренфойхта. Примеры: упорядоченные множества рациональных и действительных чисел, Z и Z+Z.  
+
====Лекция 12 (26 ноября).  ====
 +
Игры Эренфойхта. Примеры: упорядоченные множества целых и рациональных чисел,
 +
рациональных и действительных чисел, Z и Z+Z.
 +
Доказательство элементарной эквивалентности с помощью игры Эренфойхта (доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны).
  
−
====Лекция 13 (3 декабря). ====
+
Выразимые (определимые отношения). Сохранение выразимых отношений при автоморфизмах. Доказательства невыразимости.
  
−
Доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны.
 
  
−
Выразимые (определимые отношения). Сохранение выразимых отношений при автоморфизмах. Доказательства невыразимости.
+
====Лекция 13 (3 декабря). ====
  
−
Cемантически полные полные теории.  
+
Cемантически полные теории.  
 
Критерий семантической полноты в терминах элементарной эквивалентности моделей.  
 
Критерий семантической полноты в терминах элементарной эквивалентности моделей.  
−
Задача аксиоматизации данной модели.
 
−
 
−
Аксиоматизация элементарной теории упорядоченного множества целых чисел (доказательство с помощью игры Эренфойхта).
 
  
 +
Задача аксиоматизации данной интерпретации.
  
−
Аксиоматизация элементарной теории упорядоченного множества рациональных чисел (доказательство с помощью игры Эренфойхта).
+
Аксиоматизация элементарной теории упорядоченного множества рациональных чисел (доказательство элементарной эквивалентности моделей с помощью игры Эренфойхта).
  
−
Подробное доказательство аксиоматизации элементарной теории упорядоченного множества целых чисел (было лишь кратко) с помощью игры Эренфойхта.
+
Аксиоматизация элементарной теории упорядоченного множества целых чисел (доказательство  элементарной эквивалентности моделей с помощью игры Эренфойхта).
  
 
Аксиоматизация элементарной теории упорядоченного множества действительных чисел.  Аксиоматизация элементарной теории поля комплексных чисел. Обе теоремы без доказательства.
 
Аксиоматизация элементарной теории упорядоченного множества действительных чисел.  Аксиоматизация элементарной теории поля комплексных чисел. Обе теоремы без доказательства.
Строка 227: Строка 334:
 
[https://www.dropbox.com/s/sbpusqasgie1eq3/listok1.pdf?dl=0 Листок 1 (вычислимые функции, разрешимые и перечислимые множества.]
 
[https://www.dropbox.com/s/sbpusqasgie1eq3/listok1.pdf?dl=0 Листок 1 (вычислимые функции, разрешимые и перечислимые множества.]
  
−
=== Проведённые семинары в группе 183 ===
+
[https://www.dropbox.com/s/9t8zyebjmvlba0k/listok2.pdf?dl=0  Листок 2 (универсальные функции, неразрешимые и неперечислимые множества.]
 +
 
 +
[https://www.dropbox.com/s/avm3f5y32enstm7/listok3.pdf?dl=0  Листок 3 (сводимости)]
 +
 
 +
[https://www.dropbox.com/s/6azyli6ftd0h792/listok4.pdf?dl=0  Листок 4 (машины Тьюринга и проблема равенства в конечно определенных полугруппах)]
 +
 
 +
[https://www.dropbox.com/s/14r8wfwguriossw/listok5.pdf?dl=0 Листок 5. Язык логики высказываний и исчисление высказываний.]
 +
 
 +
[https://www.dropbox.com/s/8x4aro56vhgtmsz/listok6.pdf?dl=0 Листок 6. Выводы в  исчислении высказываний и исчислении резолюций.]
 +
 
 +
[https://www.dropbox.com/s/eygtq0ublmj9qt9/listok7.pdf?dl=0 Листок 7. Запись утверждений и выражение отношений формулами
  первого порядка; выполнимость, общезначимость и равносильность,
  теории и семантическое следование.]
 +
 
 +
[https://www.dropbox.com/s/s5qoqvvhxuc5tqz/listok8.pdf?dl=0 Листок 8. Выводы в ИР. Изоморфизм и элементарная эквивалентность. Игра Эренфойхта]
 +
 
 +
[https://www.dropbox.com/s/0fb8lfd0bh2enu9/listok9.pdf?dl=0 Листок 9. Выразимость и автоморфизмы. Совместные и полные теории. Аксиоматизация элементарной теории.]
 +
 
 +
=== Семинары в группе 183 ===
  
 
====Семинар 1 (3 сентября)====
 
====Семинар 1 (3 сентября)====
−
Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.
+
Вычислимые функции, разрешимые и перечислимые множества.
  
 
====Семинар 2 (10 сентября)====
 
====Семинар 2 (10 сентября)====
−
Решение задач линейного программирования методом исключения переменных.
+
 
 +
Листок 2
  
 
====Семинар 3 (17 сентября)====
 
====Семинар 3 (17 сентября)====
−
Решение задач линейного программирования методом исключения переменных. Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.
+
 
 +
Листок 3.
  
 
====Семинар 4 (24 сентября)====
 
====Семинар 4 (24 сентября)====
−
Задачи на применение двойственности и соотношений дополняющей нежесткости.
+
 
 +
Листок 4 (машины Тьюринга и проблема равенства в конечно определенных полугруппах).
  
 
====Семинар 5 (1 октября)====
 
====Семинар 5 (1 октября)====
−
Потоки и разрезы. Игры с нулевой суммой.
+
 
 +
Листок 5 (кроме выводимости)
  
 
====Семинар 6 (8 октября)====
 
====Семинар 6 (8 октября)====
  
−
Решение задач ЛП симплекс-методом.
+
Листок 6 (остановились в середине второй задачи)
  
 
====Семинар 7 (15 октября)====
 
====Семинар 7 (15 октября)====
−
 
+
Листок 6.
−
Задачи на пропозициональные формулы.
+
  
 
====Семинар 8 (28 октября)====
 
====Семинар 8 (28 октября)====
  
−
Опровержение формул в Исчислении Резолюций. Запись свойств и суждений
+
Листок 7
−
формулами первого порядка.
+
  
 
====Семинар 9 (5 ноября)====
 
====Семинар 9 (5 ноября)====
−
 
+
Листок 7
−
Выражение отношений формулами первого порядка. Модели теорий.
+
  
 
====Семинар 10 (12 ноября)====
 
====Семинар 10 (12 ноября)====
  
−
Задачи на семантическое следование. Приведение к предварённой и сколемовской нормальным формам. Доказательство несовместности, общезначимости и семантического следования в Исчислении резолюций.
+
Приведение к предварённой и сколемовской нормальной формам.
 +
Доказательство несовместности и общезначимости с помощью ИР.
 +
 
 +
Изоморфные и элементарно эквивалентные модели.
  
 
====Семинар 11 (19 ноября)====
 
====Семинар 11 (19 ноября)====
−
Задачи на изоморфизм, элементарную эквивалентность и игры Эренфойхта.
+
Изоморфные и элементарно эквивалентные модели.
 +
Игры Эренфойхта.
  
 
====Семинар 12 (26 ноября)====
 
====Семинар 12 (26 ноября)====
−
Задачи на невыразимость, элементарную эквивалентность и игры Эренфойхта (листок 9).
 
  
−
====Семинар 13 3 декабря)====
+
====Семинар 13 (3 декабря)====
−
Задачи на совместность и полноту теорий, аксиоматизация элементарной теории моделей (листок 9)
+
  
 
====Семинар 14 (10 декабря)====
 
====Семинар 14 (10 декабря)====
Строка 279: Строка 405:
  
 
==Конспекты лекций==
 
==Конспекты лекций==
−
[https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока] (содержит только то, что рассказывалось на лекциях, и еще чуть-чуть :)
 
  
−
[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).]
+
[https://www.dropbox.com/s/nhdnt5d88zk14qv/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]
−
 
+
−
[https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]
+
  
 
==Консультации ==
 
==Консультации ==
−
173 группа: вторник с 18:10 до 19:30 в ком. 617 (Верещагин).
 
  
−
174 и 176 группы: с 1640 в ауд. 219 (Дашков, по согласованию) и по договоренности (ассистенты).
+
183 группа: вторник с 15:10 до 16:30 в ком. S832 (Верещагин).
  
−
175 группа: вторник с 18.10 до 19.30 в ком. 617 (Милованов).
+
185 группа: вторник с 15:10 до 16:30 в ком. S832 (Милованов).
  
−
==Рекомендуемая литература  ==
+
186, 187 группы: понедельник с 15:10 до 17:00 в ком. S913 (Дашков).
  
−
1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998
+
Козачинcкий: по вторникам 13:40 -- 16:30, буду либо в S831, либо в S832
  
−
2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.
+
==Рекомендуемая литература  ==
  
−
3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.)
+
1. Н.К.Верещагин, А. Шень. Вычислимые функции. М.:МЦНМО, 2008.  
  
−
5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)
+
2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.)
  
−
6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)
+
3. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)
  
−
7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)
+
4. [http://rubtsov.su/public/DM-HSE-Draft.pdf  Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень] Главы 14-16 посвящены вычислимости.

Текущая версия на 14:30, 31 января 2020

Содержание

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

Лекции проходят по вторникам в 12:10-13:30 в аудитории R301.

Новости

25 декабря

Выложены результаты проверки экзаменационных работ: Оценки экзамена. Решения и критерии выставления баллов.

8 декабря

Выложено шестое (последнее) домашнее задание.

27 ноября

Выложены вопросы коллоквиума.

6 ноября

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

Лектор

Н.К. Верещагин nikolay.vereshchagin@gmail.com

Семинаристы

183 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com (учебный ассистент Бакиева Аделина Эдуардовна aebakieva@edu.hse.ru).

185 Милованов Алексей Сергеевич, almas239@gmail.com (учебный ассистент Охрименко Дмитрий Андреевич daokhrimenko@edu.hse.ru).

186 Дашков Евгений Владимирович edashkov@gmail.com (учебный ассистент Бочкарева Мария Игоревна, peggy-sju@ya.ru, telegram).

187 Дашков Евгений Владимирович edashkov@gmail.com (учебный ассистент Бондаренко Наталия Сергеевна nataliyabon20142014@gmail.com).

188 Козачинский Александр Николаевич kozlach@mail.ru, группа в telegram, где можно задать вопрос (учебный ассистент Моисеев Андрей Андреевич andrei.moiseev213@yandex.ru).

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

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

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

6 домашних заданий, коллоквиум и экзамен.

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

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

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

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

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

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

(не забыть исправить - в следующем году округление будет только при выставлении итоговой оценки).

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

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

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

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

группа 183: 17 сентября (защита до 9 октября).

Группа 185: 17 сентября (защита до 9 октября).

группа 186: 17 сентября (защита до 9 октября).

группа 187: 17 сентября (защита до 9 октября).

группа 188: 20 сентября (защита до 15 октября)

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

группа 183: 1 октября (защита до 29 октября).

Группа 185: 1 октября (защита до 23 октября).

группа 186: 2 октября (защита до 23 октября).

группа 187: 2 октября (защита до 23 октября).

группа 188: 4 октября (защита до 26 ноября).

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

группа 183: 29 октября (защита до 19 ноября).

Группа 185: 29 октября (защита до 19 ноября).

группа 186: 29 октября (защита до 19 ноября).

группа 187: 29 октября (защита до 19 ноября).

группа 188: 29 октября (защита до 26 ноября).

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

группа 183: 19 ноября (защита до 3 декабря).

Группа 185: 19 ноября (защита до 3 декабря).

группа 186: 19 ноября (защита до 3 декабря).

группа 187: 19 ноября (защита до 3 декабря).

группа 188: 22 ноября (защита до 10 декабря).

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

группа 183: 3 декабря (защита до 17 декабря).

группа 185: 3 декабря (защита до 17 декабря).

группа 186: 6 декабря (защита до 20 декабря).

группа 187: 6 декабря (защита до 20 декабря).

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

группа 183: 17 декабря (защита до 26 декабря).

группа 185: 17 декабря (защита до 26 декабря).

группа 186: 20 декабря.

группа 187: 20 декабря.

группа 188: 20 декабря.

Коллоквиум

Коллоквиум пройдет в субботу 14 декабря с 10:30 до 18 в ауд. R204.


на 10:30 приглашаются группы 182 185

на 11:30 - группа 183

на 12:30 - группы 181, 186

на 13:30 - группа 188

на 15:00 - группы 184, 187



Пересдача коллоквиума 26 декабря в 12:10 в R407.

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

Экзамен

Оценки экзамена 24.12.2019. Решения и критерии выставления баллов.

Пересдачи

Пересдача коллоквиума 26 декабря. Пересдачи письменного экзамена 15.01.2020 начало 15:10 в ауд. ауд. R503 и 30 января в 15:10 в ауд. D501.


Оценки экзамена 30.1.2020. Решения. Работу можно посмотреть и апеллировать во вторник 4 февраля в 16:30 в ауд. D506.


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

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

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

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

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

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

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

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

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

группа 183

группа 185

группа 186

группа 187

группа 188

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

  • Вычислимые функции. Разрешимые и перечислимые множества.
  • Универсальные функции. Перечислимые неразрешимые множества. Неразрешимость проблемы остановки. Неотделимые перечислимые множества.
  • Теорема Клини о неподвижной точки. Теорема Райса-Успенского.
  • Машины Тьюринга. Тезис Чёрча-Тьюринга.
  • Алгоритмические проблемы. Примеры неразрешимых алгоритмических проблем.
  • Пропозициональные формулы.
  • Исчисление резолюций для пропозициональных формул.
  • Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели. Доказательства элементарной эквивалентности с помощью игр Эренфойхта
  • Исчисление резолюций для формул первого порядка.
  • Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.
  • Логическое следование и аксиоматические теории.

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

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

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

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

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

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

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

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

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

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

Сводимости: m-сводимость и Тьюрингова сводимость. Их свойства. Полные перечислимые множества.

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

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

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

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

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

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

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

Исчисление высказываний, понятие вывода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

Семинары

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

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

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

Листок 3 (сводимости)

Листок 4 (машины Тьюринга и проблема равенства в конечно определенных полугруппах)

Листок 5. Язык логики высказываний и исчисление высказываний.

Листок 6. Выводы в исчислении высказываний и исчислении резолюций.

Листок 7. Запись утверждений и выражение отношений формулами
 первого порядка; выполнимость, общезначимость и равносильность,
 теории и семантическое следование.

Листок 8. Выводы в ИР. Изоморфизм и элементарная эквивалентность. Игра Эренфойхта

Листок 9. Выразимость и автоморфизмы. Совместные и полные теории. Аксиоматизация элементарной теории.

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

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

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

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

Листок 2

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

Листок 3.

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

Листок 4 (машины Тьюринга и проблема равенства в конечно определенных полугруппах).

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

Листок 5 (кроме выводимости)

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

Листок 6 (остановились в середине второй задачи)

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

Листок 6.

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

Листок 7

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

Листок 7

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

Приведение к предварённой и сколемовской нормальной формам. Доказательство несовместности и общезначимости с помощью ИР.

Изоморфные и элементарно эквивалентные модели.

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

Изоморфные и элементарно эквивалентные модели. Игры Эренфойхта.

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

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

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

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

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

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

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

183 группа: вторник с 15:10 до 16:30 в ком. S832 (Верещагин).

185 группа: вторник с 15:10 до 16:30 в ком. S832 (Милованов).

186, 187 группы: понедельник с 15:10 до 17:00 в ком. S913 (Дашков).

Козачинcкий: по вторникам 13:40 -- 16:30, буду либо в S831, либо в S832

Рекомендуемая литература

1. Н.К.Верещагин, А. Шень. Вычислимые функции. М.:МЦНМО, 2008.

2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.)

3. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)

4. Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень Главы 14-16 посвящены вычислимости.

Источник — «http://wiki.cs.hse.ru/index.php?title=DM2-basic2019/2020&oldid=38485»