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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показаны 32 промежуточные версии 2 участников)
Строка 5: Строка 5:
 
==Новости==
 
==Новости==
  
 +
'''Внимание! Перенос занятий:''' лекция и семинары 6 декабря переносятся на субботу 7 декабря.
 +
 +
Лекция: 7 декабря, начало 12:10, ауд. R306
 +
 +
Семинар 182 группы: 7 декабря, начало 13:40, ауд. R207. Консультация (и защита домашних заданий): вторник, 10 декабря, начало 15:10, ауд. М203.
 +
 +
Семинар 184 группы: 7 декабря, начало 13:40, ауд. D204
  
 
==Лектор==  
 
==Лектор==  
Строка 22: Строка 29:
 
Козачинcкий: по вторникам 13:40 -- 16:30, буду либо в S831, либо в S832
 
Козачинcкий: по вторникам 13:40 -- 16:30, буду либо в S831, либо в S832
  
Вялый: '''изменение аудитории!''' по пятницам, 16:40-18:00, 11.10, 18.10 - R208
+
Вялый: по пятницам, 16:40-18:00, D206
  
 
Ассистент Тараканов: вторник, среда - любое время, договариваться за день, пятница - после 18:00 (telegram - @SetSplin)
 
Ассистент Тараканов: вторник, среда - любое время, договариваться за день, пятница - после 18:00 (telegram - @SetSplin)
Строка 56: Строка 63:
 
===Коллоквиум===
 
===Коллоквиум===
  
===Экзамен===
+
Дата: 14 декабря (суббота). Время и место 10:30-15:00: аудитория R204, '''Важное изменение''': 15:00 – 18:00: аудитория та же - R204.
  
 +
'''Расписание по группам:'''
 +
 +
на 10:30 приглашаются группы 182, 185
 +
 +
на 11:30 - группа 183
 +
 +
на 12:30 - группы 181, 186
 +
 +
на 13:30 - группа 188
 +
 +
на 15:00 - группы 184, 187
 +
 +
 +
Консультация перед коллоквиумом: 13.12, начало 13:40, аудитория R503
 +
 +
[[https://www.dropbox.com/s/eeyovnsd8a0vmw3/colloq-pilot.pdf?dl=0 Программа коллоквиума.]] Обратите внимание:
 +
 +
#  В теоретические вопросы по логике '''входят''' игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
 +
# На коллоквиуме не разрешается пользоваться '''никакими''' записями - ни в электронной, ни в бумажной форме.
 +
 +
===Экзамен (письменный)===
 +
 +
Дата:  24 декабря, время с 15:00 до 18-00. Аудитории R205, R305, R503, R504. Раскладку по аудиториям также объявим дополнительно.
 +
'''Следите за уточнениями!'''
 +
 +
Показ работ: 26 декабря.
  
 
===Пересдачи===
 
===Пересдачи===
Строка 69: Строка 102:
  
 
'''[https://www.dropbox.com/s/16yh4npnm0yb1uk/hw03DM2-pilot.pdf?dl=0 Домашнее задание 3]''' Срок сдачи:  181 группа -  29 октября; 182 группа - 18 октября; 184 группа - 18 октября.
 
'''[https://www.dropbox.com/s/16yh4npnm0yb1uk/hw03DM2-pilot.pdf?dl=0 Домашнее задание 3]''' Срок сдачи:  181 группа -  29 октября; 182 группа - 18 октября; 184 группа - 18 октября.
 +
'''Исправление условия задачи 5:''' вместо "переводит в пустую" следует читать "переводит в пустую финальную" (то есть, на ленте пусто, а машина в финальном состоянии).
 +
 +
'''[https://www.dropbox.com/s/rgq5dqib714yyl2/hw04DM2-pilot.pdf?dl=0 Домашнее задание 4]''' Срок сдачи:  181 группа -  12 ноября; 182 группа - 8 ноября; 184 группа - 8 ноября.
 +
 +
'''[https://www.dropbox.com/s/v5e6k0r4phb0uj3/hw05DM2-pilot.pdf?dl=0 Домашнее задание 5]''' Срок сдачи:  181 группа -  26 ноября; 182 группа - 22 ноября; 184 группа - 22 ноября.
 +
 +
'''[https://www.dropbox.com/s/9vk1f1472jf7kn0/hw06DM2-pilot.pdf?dl=0 Домашнее задание 6]''' Срок сдачи:  181 группа -  3 декабря; 182 группа - 29 ноября; 184 группа - 7 декабря.
 +
 +
  
 
===Оценки за домашние задания===
 
===Оценки за домашние задания===
'''[https://www.dropbox.com/s/zridzb5qtoneixv/181.xls?dl=0 181 группа]'''
+
'''[https://docs.google.com/spreadsheets/d/14C0mWdiFAqC-QFLbEhN6CoHMgEjP1UCsUaeq4kLhLOE/edit?usp=sharing 181 группа]'''
  
 
'''[https://www.dropbox.com/s/9htri9ifxs6qrc0/182.xls?dl=0 182 группа]'''
 
'''[https://www.dropbox.com/s/9htri9ifxs6qrc0/182.xls?dl=0 182 группа]'''
  
'''[https://www.dropbox.com/s/ncae7dyteo8qhpe/184.xlsx?dl=0 184 группа]'''
+
'''[https://docs.google.com/spreadsheets/d/1JeCJ4NHk3AxStLnI_H6ERsUM-TIDT63XqZQ0zIaMqXE/edit?usp=sharing 184 группа]''' ;
  
 
===Сроки защиты===
 
===Сроки защиты===
Строка 84: Строка 126:
  
 
  184 группа - 15 октября.
 
  184 группа - 15 октября.
 +
 +
====2 дз====
 +
181 группа - 19 ноября.
 +
 +
182 группа - 22 ноября.
 +
 +
184 группа - 12 ноября.
 +
 +
====3 дз====
 +
181 группа - 20 декабря.
 +
 +
184 группа - 26 ноября.
 +
 +
182 группа - 10 декабря.
 +
 +
====4 дз====
 +
184 группа - 20 декабря.
 +
181 группа - 20 декабря.
 +
182 группа - 20 декабря.
 +
 +
====5 дз====
 +
181 группа - 20 декабря.
 +
 +
182 группа - 13 декабря.
 +
 +
184 группа - 20 декабря.
  
 
==Примерное содержание лекций==
 
==Примерное содержание лекций==
Строка 116: Строка 184:
  
 
==Прочитанные лекции==
 
==Прочитанные лекции==
 +
 +
'''7 декабря''' Доказательства невыразимости предикатов методом автоморфизмов и с помощью игр Эренфойхта. Арифметика. Неперечислимость формул, истинных в арифметике. Основные идеи доказательства. Бета-функция Гёделя.
 +
 +
'''29 ноября''' Элементарно эквивалентные теории. Игры Эренфойхта.
 +
 +
'''22 ноября''' Разрешимые теории. Метод элиминации кванторов.
 +
 +
'''15 ноября''' Перечислимость множества общезначимых формул. Теории и их модели. Семантическое и синтаксическое следование, их эквивалентность. Теории с равенством, нормальные модели. Теория полугруппы. Эпиморфизмы моделей. Сохранение значения формулы при эпиморфизме. Неразрешимость множества общезначимых формул.
 +
 +
'''8 ноября''' Проверка общезначимости формул. Примеры общезначимых. Исчисление резолюций для универсальных дизъюнктов и формул первого порядка. Корректность и полнота.
 +
 +
'''1 ноября''' Исчисление резолюций для общих булевых формул. Сводимость выполнимости булевой формулы к выполнимости КНФ. Формулы первого порядка.
  
 
'''11 октября''' Булевы формулы. Тавтологии. Задача проверки тавтологичности. КНФ. Исчисление резолюций. Корректность и полнота исчисления резолюций.
 
'''11 октября''' Булевы формулы. Тавтологии. Задача проверки тавтологичности. КНФ. Исчисление резолюций. Корректность и полнота исчисления резолюций.
Строка 129: Строка 209:
 
'''6 сентября''' Вычислимые функции, разрешимые множества, перечислимые множества. Связи между разрешимыми и перечислимыми множествами: разрешимые множества - это такие перечислимые, у которых дополнение также перечислимо (теорема Поста), перечислимые множества - это проекции разрешимых.
 
'''6 сентября''' Вычислимые функции, разрешимые множества, перечислимые множества. Связи между разрешимыми и перечислимыми множествами: разрешимые множества - это такие перечислимые, у которых дополнение также перечислимо (теорема Поста), перечислимые множества - это проекции разрешимых.
  
 +
== Семинары ==
  
 +
'''[https://www.dropbox.com/s/ogrd50haqd88uww/cw13DM2-pilot.pdf?dl=0 Задачи к 13 и 14 семинару]'''
  
== Семинары ==
+
'''[https://www.dropbox.com/s/ey9nh17mwvixg8c/cw12DM2-pilot.pdf?dl=0 Задачи к 12 семинару]'''
 +
 
 +
'''[https://www.dropbox.com/s/cgktx6csmo1pjr3/cw11DM2-pilot.pdf?dl=0 Задачи к 11 семинару]'''
 +
 
 +
'''[https://www.dropbox.com/s/glh4sxcac5vxa1w/cw10DM2-pilot.pdf?dl=0 Задачи к 10 семинару]'''
 +
 
 +
'''[https://www.dropbox.com/s/in0rb2yuvg1ti0q/cw09DM2-pilot.pdf?dl=0 Задачи к 9 семинару]'''
 +
 
 +
'''[https://www.dropbox.com/s/ds7kr6hs39y7bg2/cw08DM2-pilot.pdf?dl=0 Задачи к 8 семинару]'''
 +
 
 +
'''[https://www.dropbox.com/s/u9fl6d53w519cpv/cw07DM2-pilot.pdf?dl=0 Задачи к 7 семинару]'''
  
 
'''[https://www.dropbox.com/s/g8yrrobvo66ae2a/cw06DM2-pilot.pdf?dl=0 Задачи к 6 семинару]'''
 
'''[https://www.dropbox.com/s/g8yrrobvo66ae2a/cw06DM2-pilot.pdf?dl=0 Задачи к 6 семинару]'''
Строка 151: Строка 243:
 
2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012.  
 
2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012.  
  
3. [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]
+
3. [https://www.dropbox.com/s/8lls7ctis7vwwg9/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]
  
 
4. [http://rubtsov.su/public/DM-HSE-Draft.pdf  Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень] Главы 14-16 посвящены вычислимости.
 
4. [http://rubtsov.su/public/DM-HSE-Draft.pdf  Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень] Главы 14-16 посвящены вычислимости.

Текущая версия на 11:02, 14 декабря 2019

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

Лекции проходят по пятницам в 13:40-15:00 в аудитории R406

Новости

Внимание! Перенос занятий: лекция и семинары 6 декабря переносятся на субботу 7 декабря.

Лекция: 7 декабря, начало 12:10, ауд. R306

Семинар 182 группы: 7 декабря, начало 13:40, ауд. R207. Консультация (и защита домашних заданий): вторник, 10 декабря, начало 15:10, ауд. М203.

Семинар 184 группы: 7 декабря, начало 13:40, ауд. D204

Лектор

Вялый Михаил Николаевич vyalyi@gmail.com

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

181 Козачинский Александр Николаевич kozlach@mail.ru группа в telegram, где можно задать вопрос (учебный ассистент Агамов Раджаб Эльдар оглы agamov@phystech.edu)

182 Вялый Михаил Николаевич vyalyi@gmail.com (учебный ассистент Сурин Денис Владимирович Denis.surin2011@yandex.ru)

184 Козачинский Александр Николаевич kozlach@mail.ru, группа в telegram, где можно задать вопрос (учебный ассистент Тараканов Игорь Анатольевич iatarakanov@edu.hse.ru)

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

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

Вялый: по пятницам, 16:40-18:00, D206

Ассистент Тараканов: вторник, среда - любое время, договариваться за день, пятница - после 18:00 (telegram - @SetSplin)

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

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

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

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

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

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

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

Экзамен состоит из 8 задач с указанием количества баллов за каждую задачу. Эти баллы в сумме дают 10 баллов или больше. Задачи нужно решить за две пары.

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

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

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

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

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

Коллоквиум

Дата: 14 декабря (суббота). Время и место 10:30-15:00: аудитория R204, Важное изменение: 15:00 – 18:00: аудитория та же - R204.

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

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

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

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

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

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


Консультация перед коллоквиумом: 13.12, начало 13:40, аудитория R503

[Программа коллоквиума.] Обратите внимание:

  1. В теоретические вопросы по логике входят игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
  2. На коллоквиуме не разрешается пользоваться никакими записями - ни в электронной, ни в бумажной форме.

Экзамен (письменный)

Дата: 24 декабря, время с 15:00 до 18-00. Аудитории R205, R305, R503, R504. Раскладку по аудиториям также объявим дополнительно. Следите за уточнениями!

Показ работ: 26 декабря.

Пересдачи

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

Домашнее задание 1 Срок сдачи: 181 группа - 24 сентября; 182 группа - 20 сентября; 184 группа - 20 сентября. Комментарий к условию задачи 5: для определённости считайте, что функция строго возрастающая.

Домашнее задание 2 Срок сдачи: 181 группа - 8 октября; 182 группа - 4 октября; 184 группа - 4 октября.

Домашнее задание 3 Срок сдачи: 181 группа - 29 октября; 182 группа - 18 октября; 184 группа - 18 октября. Исправление условия задачи 5: вместо "переводит в пустую" следует читать "переводит в пустую финальную" (то есть, на ленте пусто, а машина в финальном состоянии).

Домашнее задание 4 Срок сдачи: 181 группа - 12 ноября; 182 группа - 8 ноября; 184 группа - 8 ноября.

Домашнее задание 5 Срок сдачи: 181 группа - 26 ноября; 182 группа - 22 ноября; 184 группа - 22 ноября.

Домашнее задание 6 Срок сдачи: 181 группа - 3 декабря; 182 группа - 29 ноября; 184 группа - 7 декабря.


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

181 группа

182 группа

184 группа ;

Сроки защиты

1 дз

181 группа - 22 октября.
182 группа - 1 ноября.
184 группа - 15 октября.

2 дз

181 группа - 19 ноября.
182 группа - 22 ноября.
184 группа - 12 ноября.

3 дз

181 группа - 20 декабря.

184 группа - 26 ноября.

182 группа - 10 декабря.

4 дз

184 группа - 20 декабря. 181 группа - 20 декабря. 182 группа - 20 декабря.

5 дз

181 группа - 20 декабря.

182 группа - 13 декабря.

184 группа - 20 декабря.

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

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

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

7 декабря Доказательства невыразимости предикатов методом автоморфизмов и с помощью игр Эренфойхта. Арифметика. Неперечислимость формул, истинных в арифметике. Основные идеи доказательства. Бета-функция Гёделя.

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

22 ноября Разрешимые теории. Метод элиминации кванторов.

15 ноября Перечислимость множества общезначимых формул. Теории и их модели. Семантическое и синтаксическое следование, их эквивалентность. Теории с равенством, нормальные модели. Теория полугруппы. Эпиморфизмы моделей. Сохранение значения формулы при эпиморфизме. Неразрешимость множества общезначимых формул.

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

1 ноября Исчисление резолюций для общих булевых формул. Сводимость выполнимости булевой формулы к выполнимости КНФ. Формулы первого порядка.

11 октября Булевы формулы. Тавтологии. Задача проверки тавтологичности. КНФ. Исчисление резолюций. Корректность и полнота исчисления резолюций.

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

27 сентября Машины Тьюринга. Тезис Чёрча-Тьюринга и его апология. Неразрешимость проблемы остановки машины Тьюринга.

20 сентября Теорема Успенского-Райса. m-Сводимости. Теорема о неподвижной точке.

13 сентября График функции перечислим тогда и только тогда, когда функция вычислима. Совпадение классов перечислимых множеств, множеств значений вычислимых функций и областей определения вычислимых функций. Универсальные вычислимые функции. Пример перечислимого неразрешимого множества. Главные универсальные вычислимые функции.

6 сентября Вычислимые функции, разрешимые множества, перечислимые множества. Связи между разрешимыми и перечислимыми множествами: разрешимые множества - это такие перечислимые, у которых дополнение также перечислимо (теорема Поста), перечислимые множества - это проекции разрешимых.

Семинары

Задачи к 13 и 14 семинару

Задачи к 12 семинару

Задачи к 11 семинару

Задачи к 10 семинару

Задачи к 9 семинару

Задачи к 8 семинару

Задачи к 7 семинару

Задачи к 6 семинару

Задачи к 5 семинару

Задачи к 4 семинару

Задачи к 3 семинару

Задачи к 2 семинару

Задачи к 1 семинару

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

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

2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012.

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

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