Wiki - Факультет компьютерных наук - Вклад [ru]

DM2-basic2019/2020

2019-09-13T17:19:58Z

MaryB:

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

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

==Новости==

==Лектор==

Н.К. Верещагин 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, [https://t.me/Adalanthe telegram]).

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

188 Козачинский Александр Николаевич kozlach@mail.ru, '''[https://t.me/joinchat/GQufoBMbdeTW4gixEfbe4A группа в 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 октября).

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

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

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

===Коллоквиум===

Коллоквиум пройдет в субботу 14 декабря (дата предварительная).
Пересдача коллоквиума 26 декабря (дата предварительная).

[https://www.dropbox.com/s/r6okjtbl5rjyuc5/colloq.pdf?dl=0 Вопросы к коллоквиуму 2018 года.]

===Экзамен===

Экзамен (письменный) состоится во вторник 24 декабря (дата предварительная).

Показ работ 26 декабря (дата предварительная).

Оценки за экзамен [https://www.dropbox.com/s/ucj8g100p539hi1/exam-results-base.xls?dl=0 здесь]. Критерии выставления баллов
за решения задач [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 Решения задач экзамена.]

===Пересдачи===

Пересдача коллоквиума 26 декабря (дата предварительная).
Пересдачи письменного экзамена 22 января, 29 января (даты предварительные).

Комиссия 5 февраля (дата предварительная).

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

[https://www.dropbox.com/s/nsq79r42q4c4m2f/hw1.pdf?dl=0 Домашнее задание №1]

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

[ группа 183]

[ группа 185]

[https://docs.google.com/spreadsheets/d/197O6CBvLyES_FZYFvg7sOy1KWwZUitgR3StIM_C0HLc/edit?usp=sharing группа 186]

[ группа 187]

[https://docs.google.com/spreadsheets/d/12WfhcV73sesum3PeKzE1v90gcpRx0rLHvVonC6HD4zE/edit#gid=0 группа 188]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определения и свойства сводимостей.

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

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

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

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

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

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

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

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

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

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

== Семинары ==

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

[https://www.dropbox.com/s/sbpusqasgie1eq3/listok1.pdf?dl=0 Листок 1 (вычислимые функции, разрешимые и перечислимые множества.]

[https://www.dropbox.com/s/9t8zyebjmvlba0k/listok2.pdf?dl=0 Листок 2 (универсальные функции, неразрешимые и неперечислимые множества.]

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

====Семинар 1 (3 сентября)====
Вычислимые функции, разрешимые и перечислимые множества.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]

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

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

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

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

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

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

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

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

4. [http://rubtsov.su/public/DM-HSE-Draft.pdf Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень] Главы 14-16 посвящены вычислимости.

DM2-basic2019/2020

2019-09-13T17:02:59Z

MaryB:

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

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

==Новости==

==Лектор==

Н.К. Верещагин 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, [https://t.me/joinchat/B5IiTBbpBAMFQYO-a4WXXw telegram]).

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

188 Козачинский Александр Николаевич kozlach@mail.ru, '''[https://t.me/joinchat/GQufoBMbdeTW4gixEfbe4A группа в 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 октября).

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

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

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

===Коллоквиум===

Коллоквиум пройдет в субботу 14 декабря (дата предварительная).
Пересдача коллоквиума 26 декабря (дата предварительная).

[https://www.dropbox.com/s/r6okjtbl5rjyuc5/colloq.pdf?dl=0 Вопросы к коллоквиуму 2018 года.]

===Экзамен===

Экзамен (письменный) состоится во вторник 24 декабря (дата предварительная).

Показ работ 26 декабря (дата предварительная).

Оценки за экзамен [https://www.dropbox.com/s/ucj8g100p539hi1/exam-results-base.xls?dl=0 здесь]. Критерии выставления баллов
за решения задач [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 Решения задач экзамена.]

===Пересдачи===

Пересдача коллоквиума 26 декабря (дата предварительная).
Пересдачи письменного экзамена 22 января, 29 января (даты предварительные).

Комиссия 5 февраля (дата предварительная).

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

[https://www.dropbox.com/s/nsq79r42q4c4m2f/hw1.pdf?dl=0 Домашнее задание №1]

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

[ группа 183]

[ группа 185]

[https://docs.google.com/spreadsheets/d/197O6CBvLyES_FZYFvg7sOy1KWwZUitgR3StIM_C0HLc/edit?usp=sharing группа 186]

[ группа 187]

[https://docs.google.com/spreadsheets/d/12WfhcV73sesum3PeKzE1v90gcpRx0rLHvVonC6HD4zE/edit#gid=0 группа 188]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определения и свойства сводимостей.

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

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

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

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

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

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

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

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

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

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

== Семинары ==

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

[https://www.dropbox.com/s/sbpusqasgie1eq3/listok1.pdf?dl=0 Листок 1 (вычислимые функции, разрешимые и перечислимые множества.]

[https://www.dropbox.com/s/9t8zyebjmvlba0k/listok2.pdf?dl=0 Листок 2 (универсальные функции, неразрешимые и неперечислимые множества.]

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

====Семинар 1 (3 сентября)====
Вычислимые функции, разрешимые и перечислимые множества.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]

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

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

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

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

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

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

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

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

4. [http://rubtsov.su/public/DM-HSE-Draft.pdf Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень] Главы 14-16 посвящены вычислимости.