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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Листки с задачами для семинаров)
 
(не показано 107 промежуточных версии 8 участников)
Строка 1: Строка 1:
 
= Дискретная математика на 2-ом курсе ПМИ (основной поток)=
 
= Дискретная математика на 2-ом курсе ПМИ (основной поток)=
  
−
Лекции транслируются по субботам в 18:10 -- 19:30.  
+
Лекции проводятся по субботам в 18:10 -- 19:30 в Zoom (см. ссылку в РУЗе).  
  
 
==Новости==
 
==Новости==
Строка 26: Строка 26:
  
 
1910 группа: Райко Илья Глебович (mailto://mylntsa.ilya.63@gmail.com), ассистент: Коваленко Влад (телеграмм: @ykeababy)
 
1910 группа: Райко Илья Глебович (mailto://mylntsa.ilya.63@gmail.com), ассистент: Коваленко Влад (телеграмм: @ykeababy)
 +
 +
1911 группа: [https://www.hse.ru/org/persons/218355200 Александр Запрягаев], почта: [mailto:rudetection@gmail.com rudetection@gmail.com], телеграм: [https://t.me/azapryagaev @azapryagaev]
  
 
==Краткое описание==
 
==Краткое описание==
Строка 44: Строка 46:
 
Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.35, а оценка за домашние задания - с коэффициентом 0.3. Округление делается один раз --- при вычислении итоговой оценки. Применяются стандартные правила, но полуцелые числа округляются вверх.
 
Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.35, а оценка за домашние задания - с коэффициентом 0.3. Округление делается один раз --- при вычислении итоговой оценки. Применяются стандартные правила, но полуцелые числа округляются вверх.
  
−
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один  раз). Это же относится и к тем, кто не смог прийти на экзамен или получил на нем менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.  
+
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один  раз). Это же относится и к тем, кто не смог прийти на экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.
  
 
==Сроки контрольных мероприятий==
 
==Сроки контрольных мероприятий==
Строка 63: Строка 65:
  
 
====Второе домашнее задание: срок сдачи====
 
====Второе домашнее задание: срок сдачи====
 +
группа 193: 9 октября до начала семинара.
  
−
группа 195: 5 октября. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])
+
группа 195: 9 октября. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])
  
 
группа 196: 9 октября.
 
группа 196: 9 октября.
 +
 +
группа 197: 9 октября, 23:59 (Сдавать [https://docs.google.com/forms/d/e/1FAIpQLSdkkKR8H1GaF4sU36ZICf8ypRicgtfgdL8mWrGFPZJoyz87sw/viewform?usp=sf_link сюда]).
 +
 +
группа 198: 7 октября.
 +
 +
группа 199: 9 октября до начала семинара.
 +
 +
группа 1910: 7 октября.
 +
 +
====Третье домашнее задание: срок сдачи====
 +
Обновлен [https://docs.google.com/spreadsheets/d/1LaeCrFF7-iydLof_Lzu7s42t63FdA4Vcyng968ZmCS4/edit?usp=sharing список ассистентов]
 +
 +
группа 193: 23:59 31го октября
 +
 +
группа 195: 31 октября. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])
 +
 +
группа 196: 31 октября 16:20
 +
 +
группа 197: 2 ноября, 23:59 (Сдавать [https://docs.google.com/forms/d/e/1FAIpQLSdkkKR8H1GaF4sU36ZICf8ypRicgtfgdL8mWrGFPZJoyz87sw/viewform?usp=sf_link сюда]).
 +
 +
группа 198: 31 октября.
 +
 +
группа 199: 23:59 31го октября
 +
 +
группа 1910: 31 октября.
 +
 +
====Четвёртое домашнее задание: срок сдачи====
 +
Обновлен [https://docs.google.com/spreadsheets/d/1LaeCrFF7-iydLof_Lzu7s42t63FdA4Vcyng968ZmCS4/edit?usp=sharing список ассистентов]
 +
 +
группа 193: 26 ноября.
 +
 +
группа 195: 26 ноября. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])
 +
 +
группа 196: 28 ноября.
 +
 +
группа 197: 4 декабря, 23:59. (Сдавать [https://docs.google.com/forms/d/e/1FAIpQLSdkkKR8H1GaF4sU36ZICf8ypRicgtfgdL8mWrGFPZJoyz87sw/viewform?usp=sf_link сюда]).
 +
Настоятельно рекомендуется сделать задачи 1-11 до 30 ноября! С этого дня будут отсчитываться две недели на дз5.
 +
 +
группа 198: 28 ноября.
 +
 +
группа 199: 26 ноября.
 +
 +
группа 1910: 26 ноября.
 +
 +
====Пятое домашнее задание: срок сдачи====
 +
Обновлен [https://docs.google.com/spreadsheets/d/1LaeCrFF7-iydLof_Lzu7s42t63FdA4Vcyng968ZmCS4/edit?usp=sharing список ассистентов]
 +
 +
группа 193: 11 декабря (до начала семинара)
 +
 +
группа 195: 14 декабря. (Сдавать [https://classroom.google.com/c/MTY0OTYzOTg2Nzk5?cjc=njl6gsd сюда])
 +
 +
группа 196: 14 декабря.
 +
 +
группа 197: 14 декабря, 23:59 (Сдавать [https://docs.google.com/forms/d/e/1FAIpQLSdkkKR8H1GaF4sU36ZICf8ypRicgtfgdL8mWrGFPZJoyz87sw/viewform?usp=sf_link сюда]).
 +
 +
группа 198:
 +
 +
группа 199: 11 декабря (до начала семинара)
 +
 +
группа 1910:
 +
 +
====Шестое домашнее задание: срок сдачи====
 +
ВСЕ ГРУППЫ: до конца суток (мск) 21 декабря.
  
 
===Коллоквиум===
 
===Коллоквиум===
  
−
Коллоквиум пройдет в  с
+
Коллоквиум пройдет 15 декабря посредством телеконференции. [https://drive.google.com/file/d/1cRS1JCZgrkJe8lB9o3C7n3VLmkND6llh/view?usp=sharing Список] вопросов и правила проведения. Ссылки появятся позже.
  
 +
Распределение групп по времени:
 +
 +
9:30-11:30 БПМИ 197 [https://drive.google.com/file/d/1tKY0Vrf9pr6QTbzICICxEARqs10dKUZF/view?usp=sharing Билеты]
 +
 +
11:00-13:00 БПМИ 198 [https://drive.google.com/file/d/1mG8Xbqz_iUyNxeDYpa_5JJHb7WeC8WhR/view?usp=sharing Билеты]
 +
 +
14:30-16:00 БПМИ 195 [https://drive.google.com/file/d/1TgPcHNMiaTyyIIeX-lX-uwHg2n7lSRmM/view?usp=sharing Билеты]
 +
 +
16:00-17:30 БПМИ 1910 [https://drive.google.com/file/d/1HRh5c6ybQ4ar8V0QZnkRXVhIGyQ-XYrY/view?usp=sharing Билеты]
 +
 +
17:30-19:00 БПМИ 193, 1911 [https://drive.google.com/file/d/1IIiT1XAD5M1nVkDWsjDrfy7O0SnV5z7N/view?usp=sharing Билеты гр. 193], [https://drive.google.com/file/d/1HvPk4hbXEtdYZmUaxYXq0j0fBiTvG5OY/view?usp=sharingбилеты гр. 1911]
 +
 +
19:00-21:00 БПМИ 196, 199 [https://drive.google.com/file/d/1mRDJjR2c2u47Pp0HASGiCZR-mk4YlfDt/view?usp=sharing Билеты гр. 196], [https://drive.google.com/file/d/1jSaE50QyWKM_gCnJNPRZIFM_GiO5EtoY/view?usp=sharing гр. 199]
  
 
===Экзамен===
 
===Экзамен===
 +
 +
Экзамен пройдет 28-го декабря с 1400 до 1640 мск в заочной письменной форме с прокторингом в Zoom'е. Начиная с 1345 студенты должны подключаться к [https://docs.google.com/document/d/1r50mDV1EsEpprl_Z2XdlpRr_nZAfUFNNdWviegdHBsQ/edit?usp=sharing назначенной им конференции].
 +
 +
[https://drive.google.com/file/d/1HdSmVPKILHOqNg7Yf3cA5Wetoj5wfB-k/view?usp=sharing Правила] проведения экзамена.
 +
 +
[https://forms.gle/Rn1c5b4Snm1V4fzD7 Форма] для загрузки работы.
 +
 +
[https://drive.google.com/file/d/1ipJdTrvO-_lmbQ3pEs-FiH2zmaS24Maw/view?usp=sharing Задание.]
 +
 +
[https://www.dropbox.com/s/yfl66pxdfcve5x0/hse-amcs-dm2-exam-sol.pdf?dl=0 Решения и критерии проверки.]
  
 
===Пересдачи===
 
===Пересдачи===
Строка 82: Строка 171:
  
 
[https://drive.google.com/file/d/1TwCjnbwY9j2bhiB3MiYAW3s-XOtmDCJR/view?usp=sharing Домашнее задание № 2]
 
[https://drive.google.com/file/d/1TwCjnbwY9j2bhiB3MiYAW3s-XOtmDCJR/view?usp=sharing Домашнее задание № 2]
 +
 +
[https://drive.google.com/file/d/1L-iLQ_gmon36407q3b_bkVjHcmcid4Dm/view?usp=sharing Домашнее задание № 3]
 +
 +
[https://drive.google.com/file/d/12tihR29wlWDrUpQah1z_51H9v7zZ92PZ/view?usp=sharing Домашнее задание № 4]
 +
 +
[https://drive.google.com/file/d/1_V50e1KS6Buc35_bUYLIoPHrKRBNSYuZ/view?usp=sharing Домашнее задание № 5]
 +
 +
[https://drive.google.com/file/d/15j1KwiInqPjhjNsrq6RfwzIucjVSUjmJ/view?usp=sharing Домашнее задание № 6]
  
 
==Текущая успеваемость==
 
==Текущая успеваемость==
Строка 94: Строка 191:
  
 
[https://youtu.be/_xAoOF9_D6M Запись лекции].
 
[https://youtu.be/_xAoOF9_D6M Запись лекции].
−
 
  
 
====Лекция 2 (12 сентября).====
 
====Лекция 2 (12 сентября).====
Строка 104: Строка 200:
 
====Лекция 3 (19 сентября).====
 
====Лекция 3 (19 сентября).====
  
−
m-Сводимость и ее свойства;  множество, полное в классе перечислимых; примеры применения; "программы" для нигде не определенной функции; пример неглавной у.в.ф.; теорема Клини о неподвижной точке.
+
m-Сводимость и ее свойства;  множество, полное в классе перечислимых; примеры применения сводимости; "программы" для нигде не определенной функции; пример неглавной у.в.ф.; теорема Клини о неподвижной точке.
  
 
[https://youtu.be/_MS9YL7hbtM Запись лекции].
 
[https://youtu.be/_MS9YL7hbtM Запись лекции].
 +
 +
====Лекция 4 (26 сентября).====
 +
 +
Теорема о рекурсии как следствие теоремы Клини; совместная рекурсия; решение "уравнений" на вычислимые функции и их систем; теорема Успенского-Райса и ее вывод из теоремы Клини; доказательство той же теоремы на основе сводимости.
 +
 +
[https://youtu.be/hxF6AuC-u4I Запись лекции].
 +
 +
====Лекция 5 (3 октября).====
 +
 +
Машины Тьюринга; неформальное и формальное определение; конфигурации; вычисление как преобразование конфигураций; вычислимые функции на словах конечного алфавита; вычислимость числовых функций, примеры; тезис Тьюринга; реализация "свойств алгоритмов" в модели машин Тьюринга; универсальная машина Тьюринга.
 +
 +
[https://youtu.be/SuVkmjBsRYk Запись лекции].
 +
 +
====Лекция 6 (10 октября).====
 +
 +
Формулы и термы языка первого порядка; сигнатуры; индуктивные определения; индукция по построению; параметры формулы.
 +
 +
[https://youtu.be/9qHMI2aN0pI Запись лекции].
 +
 +
====Лекция 7 (17 октября).====
 +
 +
Интерпретация сигнатуры \sigma; \sigma-стурктура; оценка переменных; значение терма и значение формулы в интерпретации при оценке; значение терма (формулы) в интерпретации зависит только от оценки (свободно) входящих туда переменных; значение формулы на наборе переменных; выразимость отношения формулой.
 +
 +
[https://youtu.be/jtrjpDBBrx4 Запись лекции].
 +
 +
====Лекция 8 (31 октября).====
 +
 +
Изоморфизм структур; значение терма и формулы при изоморфизме; автоморфизмы; сохранение выразимых множеств автоморфизмами; элементарная эквивалентность структур; изоморфные структуры элементарно эквивалентны.
 +
 +
[https://youtu.be/IJJMxvTv1XA Запись лекции.]
 +
 +
====Лекция 9 (7 ноября).====
 +
 +
Логика предикатов; общезначимость, выполнимость и эквивалентность; лемма о фиктивном кванторе; основные эквивалентности; булева комбинациия формул и соответствующая ей булева функция; дизъюнктивные и конъюнктивные нормальные формы.
 +
 +
[https://youtu.be/nfAn3pc55yw Запись лекции.]
 +
 +
====Лекция 10 (14 ноября).====
 +
 +
Теорема о д.н.ф. и к.н.ф.; подстановки; корректные подстановки (термы свободные для (подстановки вместо) переменной в формулу); лемма о значении формулы при корректной подстановке; общезначимость формул вида \forall x \phi \to \phi(t/x) и \phi(t/x) \to \exists x \phi при корректных подстановках; переименование связанной переменной; бескванторные и предваренные формулы; теорема о предваренной нормальной форме.
 +
 +
[https://youtu.be/Bte9XbEKID8 Запись лекции.]
 +
 +
====Лекция 11 (21 ноября).====
 +
 +
Понятие теории; логическое (семантическое) следование; примеры; теорема компактности (пока без доказательства); невозможна аксиоматизация класса конечных нормальных структур (хотя возможна для бесконечных); сколемизация: определение и примеры.
 +
 +
[https://youtu.be/eYlNy-kC6yw Запись лекции.]
 +
 +
====Лекция 12 (28 ноября).====
 +
 +
Обобщение логического следования и выполнимости на "теории" со свободными переменными; сведение задачи установления логического следования к проверке выполнимости; сколемизация: теорема о сохранении равновыполнимости; правила резолюции и подстановки; их корректность; выводимость в исчислении резолюций (ИР); корректность ИР; универсальные дизъюнкты; применение ИР к "теориям" произвольного вида --- преобразовние таковых к состоящим из универсальных дизъюнктов; формулировка теоремы о полноте ИР; пример доказательства общезначимости формулы с помощью ИР.
 +
 +
[https://youtu.be/PbZ80QuZsDk Запись лекции.]
 +
 +
====Лекция 13 (5 декабря).====
 +
 +
Выполнимость в модели ограниченной мощности множества универсальных дизъюнктов, из которого не выводится в ИР пустой дизъюнкт: (1) построение оценки и модели из всевозможных термов по "выполняющему приписыванию" 0 и 1 атомам, (2) построение "выполняющего приписывания" в случае, когда пустой дизъюнкт не выводится. Общая форма теоремы о полноте (с ограничением мощности модели). Доказательство теоремы компактности. Ограничение на нормальные модели: аксиомы равенства для сигнатуры; теория имеет нормальную модель тогда и только тогда, когда совместна с аксиомами равенства (без подробного доказательства); теорема компактности для нормальных моделей.
 +
 +
[https://youtu.be/W8li-P3xweY Запись лекции.]
 +
 +
====Лекция 14 (12 декабря).====
 +
 +
Игра Эренфойхта. Критерий элементарной эквивалентности в терминах игры (без доказательства). Примеры выигрышной стратегии Новатора. Люыбе два плотных линейных порядка без наименьшего и наибольшего элемента элементарно эквивалентны. Пример элементарно эквивалентных неизоморфных структур. Семантически полные теории. Семантическая полнота в терминах элементарной эквивалентности. Разрешимость семантически полной теории в перечислимой сигнатуре. Теория DLO разрешима. Элементарная эквивалентность порядков (\Z, <) и (\Z + \Z, <).
 +
 +
[https://youtu.be/mvzxilJiXXo Запись лекции.]
  
 
== Семинары ==
 
== Семинары ==
Строка 118: Строка 280:
  
 
[https://drive.google.com/file/d/1n8DxzdxHDoqgHN1PywBM8t14TFfq6liq/view?usp=sharing Листок 4]
 
[https://drive.google.com/file/d/1n8DxzdxHDoqgHN1PywBM8t14TFfq6liq/view?usp=sharing Листок 4]
 +
 +
[https://drive.google.com/file/d/1DTEt-ZiHRi9tlD7XPH0m_wAuG2Cwylin/view?usp=sharing Листок 5]
 +
 +
[https://drive.google.com/file/d/1sJSjRbiUeDCqaYFDdRZR95xc32WjApJD/view?usp=sharing Листок 6]
 +
 +
[https://drive.google.com/file/d/1WL251u_rGxxbmkYEGOzvtNdRL4emjDoO/view?usp=sharing Листок 7]
 +
 +
[https://drive.google.com/file/d/1Y7Qqu3Rb-U3fdPXhuQ4Kziu8KwzBYyvg/view?usp=sharing Листок 8]
 +
 +
[https://drive.google.com/file/d/1JBkh6zhhOyQe0jZ2uG77MGTeuKtgbzEl/view?usp=sharing Листок 9]
 +
 +
=== Семинары Е.В. Дашкова ===
 +
[https://youtu.be/B-DDRtD-FgQ Семинар 8:] формулы первого порядка; сигнатуры; структуры; выразимость.
 +
 +
[https://youtu.be/5wPggbQQmvc Семинар 9:] выразимость; мощность модели и монадические формулы.
 +
 +
[https://youtu.be/7v-J0POJVFQ Семинар 10:] изоморфизм структур; нормальные интерпретации и мощности моделей; конечные спектры.
 +
 +
[https://youtu.be/-Pp5MfoAnuQ Семинар 11:] конечные спектры; нахождение автоморфизмов структур; доказательство невыразимости с помощью автоморфизмов.
 +
 +
[https://youtu.be/kZR7-m7iqAQ Семинар 12:] выполнимость; доказательства и опровержения общезначимости формул.
 +
 +
[https://youtu.be/d7EhPdcRqis Семинар 13:] к.н.ф. и д.н.ф., подстановки, предванренная и сколемовская нормальные формы.
 +
 +
[https://youtu.be/u5K73-yIFeM Семинар 14:] исчисление резолюций.
 +
 +
[https://youtu.be/rzdLlmCCSCo Семинар 15:] игра Эренфойхта; исчисление резолюций для теорий с равенством; различные примененения теоремы компактности: нестандартная модель арифметики, продолжение частичного порядка до линейного, аксиоматизируемость классов структур.
  
 
== Консультации ==
 
== Консультации ==
  
 
Консультации А.А. Оноприенко: четверг 14-20 в дискорде https://discord.gg/v5DbugV (если меня там нет, пишите в телеграм @ansidiana).
 
Консультации А.А. Оноприенко: четверг 14-20 в дискорде https://discord.gg/v5DbugV (если меня там нет, пишите в телеграм @ansidiana).
 +
 +
Консультации И.Г. Райко: Очно или онлайн в соответствии с [[Участник:IRaiko#Расписание в сентябре – декабре 2020 года|таблицей]]. Для онлайн связи напишите в телеграм @ilya0x2dilya -- там поймём, как нам связаться.
 +
 +
Консультации Л.Н. Сысоевой: пятница после 16-00 (пишите в телеграм @lsysoeva, договоримся о точном времени и способе связи).
  
 
==Конспекты лекций==
 
==Конспекты лекций==
  
 
[https://drive.google.com/file/d/13QUtHNIkxE402as8tsJgCwewcZag78HV/view?usp=sharing Конспект лектора по вычислимости]
 
[https://drive.google.com/file/d/13QUtHNIkxE402as8tsJgCwewcZag78HV/view?usp=sharing Конспект лектора по вычислимости]
 +
 +
[https://drive.google.com/file/d/1ocnXQXv1Y5yLeYZfHVYwU7Ek10L_-hKz/view?usp=sharing Конспект лектора по формулам первого порядка (не вполне соответствует лекциям!)]
  
 
[https://www.dropbox.com/s/nhdnt5d88zk14qv/res-lect-revised.pdf?dl=0 Конспект лекций профессора Н.К. Верещагина о методе резолюций]
 
[https://www.dropbox.com/s/nhdnt5d88zk14qv/res-lect-revised.pdf?dl=0 Конспект лекций профессора Н.К. Верещагина о методе резолюций]
Строка 131: Строка 326:
 
==Конспекты семинаров==
 
==Конспекты семинаров==
  
−
Здесь выложены конспекты семинаров Оноприенко А.А., набранные Алисой Вернигор. Материалы будут обновляться по мере прочтения семинаров.
+
Здесь выложены конспекты семинаров Оноприенко А.А., набранные Алисой Вернигор и Ирой Голобородько. Материалы будут обновляться по мере прочтения семинаров.
  
 
[https://drive.google.com/file/d/1UWvY-GiMT9MxhbV-nLhkCm-KogaLOyUz/view Семинар 2], 14.09.2020
 
[https://drive.google.com/file/d/1UWvY-GiMT9MxhbV-nLhkCm-KogaLOyUz/view Семинар 2], 14.09.2020
  
 
[https://drive.google.com/file/d/1YuJOCbkVo4wLNELD1KvBmfeHZ-yiE9Ie/view Семинар 3], 21.09.2020
 
[https://drive.google.com/file/d/1YuJOCbkVo4wLNELD1KvBmfeHZ-yiE9Ie/view Семинар 3], 21.09.2020
 +
 +
[https://drive.google.com/file/d/1UZOgOM4BF-OxSICj8ZuezZXbStGZ2R0t/view Семинары 4 и 5], 28.09.2020 и 05.10.2020
 +
 +
[https://drive.google.com/file/d/1B0mdBkrQJmQFjTwJ_RFh3HaUgua5bnS5/view Семинар 6], 12.10.2020
 +
 +
[https://drive.google.com/file/d/1AbyIfoG4lVcnpOsTDGR8A1vN24KuCagj/view Семинар 7], 26.10.2020
 +
 +
[https://drive.google.com/file/d/1763S2t5nL8ZRK_uTvkuGM6MHMA2k0h7X/view Семинар 8], 02.11.2020
 +
 +
[https://drive.google.com/file/d/11RhbQ5dKpWZBf337cuWVz9uNiYSovQt3/view Семинар 9 и начало семинара 10], 09.11.2020 и 16.11.2020
 +
 +
[https://drive.google.com/file/d/1NnyQO4y94XOu4AWJqaeSNZRy-TLiqyYQ/view Конец семинара 10, семинар 11 и семинар 12], 16.11.2020, 23.11.2020 и 30.11.2020
 +
 +
[https://drive.google.com/file/d/1ttyjOEBKvdjNo_Jm1PI-Ar-5Hi8U64Lw/view Семинар 13 и семинар 14], 07.12.2020 и 14.12.2020
  
 
==Прочие ресурсы==
 
==Прочие ресурсы==
Строка 142: Строка 351:
 
[https://t.me/joinchat/M0dUGBBjmuJAEs3JmWbU2A Группа в ТГ для обсуждения вопросов по курсу.]
 
[https://t.me/joinchat/M0dUGBBjmuJAEs3JmWbU2A Группа в ТГ для обсуждения вопросов по курсу.]
  
−
[https://meet.edashkov.net/hse-amcs-dm2 Сервер телеконференций.] (Рекомендуется использовать Chrome.)
+
[https://meet.edashkov.net/hse-amcs Сервер телеконференций.] (Рекомендуется использовать Chrome.)
  
 
[https://docs.google.com/spreadsheets/d/1LaeCrFF7-iydLof_Lzu7s42t63FdA4Vcyng968ZmCS4/edit?usp=sharing Таблица распределения студентов по ассистентам]
 
[https://docs.google.com/spreadsheets/d/1LaeCrFF7-iydLof_Lzu7s42t63FdA4Vcyng968ZmCS4/edit?usp=sharing Таблица распределения студентов по ассистентам]
Строка 148: Строка 357:
 
==Рекомендуемая литература  ==
 
==Рекомендуемая литература  ==
  
−
1. Н.К.Верещагин, А. Шень. Вычислимые функции. М.:МЦНМО, 2008.  
+
1. Н.К.Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part3-5ed.pdf Вычислимые функции]. М.:МЦНМО, 2008.  
  
−
2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.)
+
2. Н.К.Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part2-5ed.pdf Языки и исчисления.] М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.)
  
 
3. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)
 
3. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)

Текущая версия на 00:26, 19 января 2021

Содержание

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

Лекции проводятся по субботам в 18:10 -- 19:30 в Zoom (см. ссылку в РУЗе).

Новости

No news is good news.

Лектор

Евгений Владимирович Дашков. Почта: edashkov@gmail.com; ТГ: @edashkov; vk.com/evgeny.v.dashkov

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

193 группа: Сысоева Любовь Николаевна, почта: lsysoeva@hse.ru, телеграмм: @lsysoeva. Ассистент: Залялов Александр

195 группа: Оноприенко Анастасия Александровна, почта ansidiana@yandex.ru. Для быстрой связи лучше писать в телеграм @ansidiana. Ассистент - Косакин Даниил, телеграм @nieto95.

196 группа: Евгений Дашков; ассистент – Лямзин Алексей, почта: adlyamzin@edu.hse.ru, телеграмм: @almondflower

197 группа: Антон Гнатенко, почта: agnatenko@hse.ru, телеграм: @antongnatenko. Ассистент: Мануйленко Никита, почта: nsmanuylenko@edu.hse.ru, телеграм: @WheelDeal

198 группа: Райко Илья Глебович (mailto://mylntsa.ilya.63@gmail.com).

199 группа: Сысоева Любовь Николаевна, почта lsysoeva@hse.ru, телеграмм: @lsysoeva.

1910 группа: Райко Илья Глебович (mailto://mylntsa.ilya.63@gmail.com), ассистент: Коваленко Влад (телеграмм: @ykeababy)

1911 группа: Александр Запрягаев, почта: rudetection@gmail.com, телеграм: @azapryagaev

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

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

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

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

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

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

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

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

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

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

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

Первое домашнее задание: срок сдачи

группа 193: 25 сентября 13:00

группа 195: 21 сентября. (Сдавать сюда)

группа 196: 25 сентября (защита до 16 октября).

группа 197: 25 сентября, 23:59 (Сдавать сюда).

группа 199: 25 сентября 14:40

Второе домашнее задание: срок сдачи

группа 193: 9 октября до начала семинара.

группа 195: 9 октября. (Сдавать сюда)

группа 196: 9 октября.

группа 197: 9 октября, 23:59 (Сдавать сюда).

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

группа 199: 9 октября до начала семинара.

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

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

Обновлен список ассистентов

группа 193: 23:59 31го октября

группа 195: 31 октября. (Сдавать сюда)

группа 196: 31 октября 16:20

группа 197: 2 ноября, 23:59 (Сдавать сюда).

группа 198: 31 октября.

группа 199: 23:59 31го октября

группа 1910: 31 октября.

Четвёртое домашнее задание: срок сдачи

Обновлен список ассистентов

группа 193: 26 ноября.

группа 195: 26 ноября. (Сдавать сюда)

группа 196: 28 ноября.

группа 197: 4 декабря, 23:59. (Сдавать сюда). Настоятельно рекомендуется сделать задачи 1-11 до 30 ноября! С этого дня будут отсчитываться две недели на дз5.

группа 198: 28 ноября.

группа 199: 26 ноября.

группа 1910: 26 ноября.

Пятое домашнее задание: срок сдачи

Обновлен список ассистентов

группа 193: 11 декабря (до начала семинара)

группа 195: 14 декабря. (Сдавать сюда)

группа 196: 14 декабря.

группа 197: 14 декабря, 23:59 (Сдавать сюда).

группа 198:

группа 199: 11 декабря (до начала семинара)

группа 1910:

Шестое домашнее задание: срок сдачи

ВСЕ ГРУППЫ: до конца суток (мск) 21 декабря.

Коллоквиум

Коллоквиум пройдет 15 декабря посредством телеконференции. Список вопросов и правила проведения. Ссылки появятся позже.

Распределение групп по времени:

9:30-11:30 БПМИ 197 Билеты

11:00-13:00 БПМИ 198 Билеты

14:30-16:00 БПМИ 195 Билеты

16:00-17:30 БПМИ 1910 Билеты

17:30-19:00 БПМИ 193, 1911 Билеты гр. 193, гр. 1911

19:00-21:00 БПМИ 196, 199 Билеты гр. 196, гр. 199

Экзамен

Экзамен пройдет 28-го декабря с 1400 до 1640 мск в заочной письменной форме с прокторингом в Zoom'е. Начиная с 1345 студенты должны подключаться к назначенной им конференции.

Правила проведения экзамена.

Форма для загрузки работы.

Задание.

Решения и критерии проверки.

Пересдачи

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

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

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

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

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

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

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

Текущая успеваемость

Таблица текущих результатов.

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

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

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

Запись лекции.

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

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

Запись лекции.

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

m-Сводимость и ее свойства; множество, полное в классе перечислимых; примеры применения сводимости; "программы" для нигде не определенной функции; пример неглавной у.в.ф.; теорема Клини о неподвижной точке.

Запись лекции.

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

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

Запись лекции.

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

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

Запись лекции.

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

Формулы и термы языка первого порядка; сигнатуры; индуктивные определения; индукция по построению; параметры формулы.

Запись лекции.

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

Интерпретация сигнатуры \sigma; \sigma-стурктура; оценка переменных; значение терма и значение формулы в интерпретации при оценке; значение терма (формулы) в интерпретации зависит только от оценки (свободно) входящих туда переменных; значение формулы на наборе переменных; выразимость отношения формулой.

Запись лекции.

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

Изоморфизм структур; значение терма и формулы при изоморфизме; автоморфизмы; сохранение выразимых множеств автоморфизмами; элементарная эквивалентность структур; изоморфные структуры элементарно эквивалентны.

Запись лекции.

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

Логика предикатов; общезначимость, выполнимость и эквивалентность; лемма о фиктивном кванторе; основные эквивалентности; булева комбинациия формул и соответствующая ей булева функция; дизъюнктивные и конъюнктивные нормальные формы.

Запись лекции.

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

Теорема о д.н.ф. и к.н.ф.; подстановки; корректные подстановки (термы свободные для (подстановки вместо) переменной в формулу); лемма о значении формулы при корректной подстановке; общезначимость формул вида \forall x \phi \to \phi(t/x) и \phi(t/x) \to \exists x \phi при корректных подстановках; переименование связанной переменной; бескванторные и предваренные формулы; теорема о предваренной нормальной форме.

Запись лекции.

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

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

Запись лекции.

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

Обобщение логического следования и выполнимости на "теории" со свободными переменными; сведение задачи установления логического следования к проверке выполнимости; сколемизация: теорема о сохранении равновыполнимости; правила резолюции и подстановки; их корректность; выводимость в исчислении резолюций (ИР); корректность ИР; универсальные дизъюнкты; применение ИР к "теориям" произвольного вида --- преобразовние таковых к состоящим из универсальных дизъюнктов; формулировка теоремы о полноте ИР; пример доказательства общезначимости формулы с помощью ИР.

Запись лекции.

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

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

Запись лекции.

Лекция 14 (12 декабря).

Игра Эренфойхта. Критерий элементарной эквивалентности в терминах игры (без доказательства). Примеры выигрышной стратегии Новатора. Люыбе два плотных линейных порядка без наименьшего и наибольшего элемента элементарно эквивалентны. Пример элементарно эквивалентных неизоморфных структур. Семантически полные теории. Семантическая полнота в терминах элементарной эквивалентности. Разрешимость семантически полной теории в перечислимой сигнатуре. Теория DLO разрешима. Элементарная эквивалентность порядков (\Z, <) и (\Z + \Z, <).

Запись лекции.

Семинары

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

Листок 1

Листок 2

Листок 3

Листок 4

Листок 5

Листок 6

Листок 7

Листок 8

Листок 9

Семинары Е.В. Дашкова

Семинар 8: формулы первого порядка; сигнатуры; структуры; выразимость.

Семинар 9: выразимость; мощность модели и монадические формулы.

Семинар 10: изоморфизм структур; нормальные интерпретации и мощности моделей; конечные спектры.

Семинар 11: конечные спектры; нахождение автоморфизмов структур; доказательство невыразимости с помощью автоморфизмов.

Семинар 12: выполнимость; доказательства и опровержения общезначимости формул.

Семинар 13: к.н.ф. и д.н.ф., подстановки, предванренная и сколемовская нормальные формы.

Семинар 14: исчисление резолюций.

Семинар 15: игра Эренфойхта; исчисление резолюций для теорий с равенством; различные примененения теоремы компактности: нестандартная модель арифметики, продолжение частичного порядка до линейного, аксиоматизируемость классов структур.

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

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

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

Консультации Л.Н. Сысоевой: пятница после 16-00 (пишите в телеграм @lsysoeva, договоримся о точном времени и способе связи).

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

Конспект лектора по вычислимости

Конспект лектора по формулам первого порядка (не вполне соответствует лекциям!)

Конспект лекций профессора Н.К. Верещагина о методе резолюций

Конспекты семинаров

Здесь выложены конспекты семинаров Оноприенко А.А., набранные Алисой Вернигор и Ирой Голобородько. Материалы будут обновляться по мере прочтения семинаров.

Семинар 2, 14.09.2020

Семинар 3, 21.09.2020

Семинары 4 и 5, 28.09.2020 и 05.10.2020

Семинар 6, 12.10.2020

Семинар 7, 26.10.2020

Семинар 8, 02.11.2020

Семинар 9 и начало семинара 10, 09.11.2020 и 16.11.2020

Конец семинара 10, семинар 11 и семинар 12, 16.11.2020, 23.11.2020 и 30.11.2020

Семинар 13 и семинар 14, 07.12.2020 и 14.12.2020

Прочие ресурсы

Директория с материалами курса.

Группа в ТГ для обсуждения вопросов по курсу.

Сервер телеконференций. (Рекомендуется использовать Chrome.)

Таблица распределения студентов по ассистентам

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

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

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

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

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