Просмотр исходного текста страницы Дискретная математика - 2 (ПМИ) 2024/25

== О курсе ==

Курс по выбору для студентов 2 курса в 1-2 модулях состоит из двух основных частей: теории вычислимых функции и классической логики первого порядка. 

{| class="wikitable" style="text-align:center"
|-
 ! Группы !! Группа 1 !! Группа 2
|-
|| Лектор ||colspan="3"| [https://www.hse.ru/org/persons/104695093 Дашков Евгений Владимирович] <br/> [https://t.me/edashkov Telegram]
|- 
|| Семинаристы || [https://www.hse.ru/org/persons/104695093 Дашков Евгений Владимирович] <br/> [https://t.me/edashkov Telegram] || [https://www.hse.ru/staff/ansidiana Оноприенко Анастасия Александровна] <br/> [https://t.me/ansidiana Telegram]
|-
|| Ассистент групп || colspan="2"| [https://t.me/dopce Тищенко Михаил]
|-
|| Ассистент лектора || colspan="2"| [https://t.me/Alyona_Chislova Числова Алёна]
|}

=== Полезные ссылки ===

[https://t.me/+TSVJDOHaWwuZZtTY '''Телеграм-чат курса''']

== Материалы курса ==

=== Лекции ===

[https://www.youtube.com/playlist?list=PLEwK9wdS5g0rCmFF5jX96XItpo7M7lR99 Лекции и семинары Е. Дашкова (записи прошлого года)]

[https://drive.google.com/file/d/13QUtHNIkxE402as8tsJgCwewcZag78HV/view?usp=sharing Конспект по вычислимости]

[https://drive.google.com/file/d/1V3QNOfANqZbiacI0d_2aLy8l1gZP0rTc/view?usp=sharing Конспект по формулам логики предикатов]

[https://drive.google.com/file/d/1VfDNhIZHbYnmYljvPyxJavQV48XTtU0E/view?usp=sharing Конспект по структурам (только определения и список задач --- черновик!)]

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

==== Листки с задачами для семинаров ====
* [https://drive.google.com/file/d/1F4r09_TkTqIykYSiNQOWtz3efxcLrbgz/view?usp=drive_link Листок 1]

* [https://drive.google.com/file/d/1DblcKr3YyQw3M6rqqvBzOmg36Lmq5FQF/view?usp=drive_link Листок 2]

* [https://drive.google.com/file/d/1fHNaFRXZPQGWUdLFjlYH7IgC27LhZ5Kc/view?usp=drive_link Листок 3]

* [https://drive.google.com/file/d/19WZDz9pLysz_mvQKnWjNfTLMwUuISeNx/view?usp=drive_link Листок 4]

* [https://drive.google.com/file/d/1fFEFJiU9PqusjS2aNFBQZhnSiI98hc1n/view?usp=drive_link Листок 5]

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

Домашнее задание разделено на несколько частей, которые выдаются примерно раз в одну или две недели и предполагают сдачу в письменном виде в установленные для каждой части сроки. Решение  каждой задачи оценивается числом от 0 до 1.  Некоторые задачи объявляются бонусными, остальные считаются обязательными. По итогам семестра вычисляется оценка за все домашнее задание в целом как отношение суммы баллов, набранных студентом за все решенные им задачи, к числу обязательных задач в домашнем задании, умноженное на 10.

Преподаватель вправе потребовать от любого студента “защитить” (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля, по усмотрению преподавателя. 

{| class="wikitable" style="text-align:center"
|-
 ! Ссылка на классрум !! [https://classroom.google.com/c/NzI1Mzg2NjkxOTY3?cjc=xaie3j4 Группа 1] !! [https://classroom.google.com/c/NzI1Mzg2Nzg4NDE3?cjc=75wn3en Группа 2]
|}

'''Сроки сдачи'''
{| class="wikitable"
|-
! Задание !! Группа 1 !! Группа 2 
|-
| [https://drive.google.com/file/d/1tFxzOApeglNB3rwDdsH93_geX11_WQMb/view?usp=drive_link ДЗ 1]  || 09.02 || 11.02
|-
| [https://drive.google.com/file/d/1FKisUcoKAdQOHVLE44C68TFXpz-N-I-a/view?usp=drive_link ДЗ 2]  || 23.02 || 26.02
|-
| [https://drive.google.com/file/d/1VdQAAobRDZIFBuv-Bepf_9TD75Pxq5ZI/view?usp=drive_link ДЗ 3]  || 14.03 || 14.03
|-
| [https://drive.google.com/file/d/1Nn2vaWGKYMQKvyQPMtNSSAke9X-XEJWQ/view?usp=drive_link ДЗ 4]  || 02.04 || 02.04
|-
| ДЗ 5  ||  ||
|-
| ДЗ 6  ||  ||
|-
| ДЗ 7  ||  ||
|-
| ДЗ 8  ||  ||
|-
| ДЗ 9  ||  ||
|}

Срок сдачи задания устанавливается семинаристом группы.

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

Проводится приблизительно за месяц до экзамена очно в устной форме (допускается и проведение онлайн). Студент получает три теоретических вопроса и время на подготовку ответа. Во время подготовки можно пользоваться любыми материалами, но нельзя советоваться с кем-либо. Отвечать следует “с чистого листа”; с разрешения преподавателя при этом можно использовать лишь самостоятельно написанные во время подготовки заметки.

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

Письменный экзамен проводится очно во время сессии после четвертого модуля. На экзамене можно пользоваться любыми материалами на бумаге, изготовленными до начала экзамена (если это не противоречит правилам против списывания). Решение  каждой задачи оценивается числом от 0 до 1. Некоторые задачи экзамена объявляются бонусными, остальные считаются обязательными. Оценкой за экзамен является отношение суммы баллов, набранных студентом за все решенные им задачи, к числу обязательных задач в экзаменационном задании, умноженное на 10.

== Оценки и аттестация ==

Предусмотрены оценки за '''домашнее задание''', '''коллоквиум''' и '''экзамен'''.

Итог = Округление(min(0,3 * ДЗ + 0,35 * КОЛ + 0,35 * Э, 10)),

где ДЗ — это оценка за все домашнее задание в целом, КОЛ — оценка за коллоквиум, Э — оценка за экзамен. Эти оценки могут быть нецелыми и приводятся без округления с наибольшей доступной точностью.

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

Автоматы по курсу не предусмотрены.

== Текущие оценки ==

[https://docs.google.com/spreadsheets/d/1wjCgie0ntQILR1ubWxbPRHDh7rMVIaNS3xe_kYPXWgM/edit?usp=sharing '''Общая таблица'''].

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

* [https://drive.google.com/drive/folders/10pGBoYJ8B544pL0WZlq3hWc9cxwGaAg-?usp=sharing Директория с материалами курса прошлого года]

* [https://www.youtube.com/playlist?list=PL1Uob8iPTHGRZB9F2yjqXhGp75g1ZJFk- Видео лекций и некоторых семинаров 2020 г.]

* [http://wiki.cs.hse.ru/DM2-base2020/2021#.D0.9A.D0.BE.D0.BD.D1.81.D0.BF.D0.B5.D0.BA.D1.82.D1.8B_.D1.81.D0.B5.D0.BC.D0.B8.D0.BD.D0.B0.D1.80.D0.BE.D0.B2 Конспекты семинаров Оноприенко А.А. за 2020-2021 учебный год]

== Основная литература ==

# Н.К. Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part3-5ed.pdf Вычислимые функции]. М.:МЦНМО, 2017.
# Н.К. Верещагин, А. Шень. [https://www.mccme.ru/free-books/shen/shen-logic-part2-5ed.pdf Языки и исчисления]. М.:МЦНМО, 2017.
# В.Н. Крупский. Введение в сложность вычислений. М.: Факториал, 2006.
# В.А. Успенский, Н.К. Верещагин, В.Е. Плиско. Вводный курс математической логики. М.: Физматлит, 2002.

== Дополнительная литература ==

# X. Роджерс. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.
# S. Arora, B. Barak. Computational Complexity. A modern approach. Cambridge University Press, 2009.
# D. van Dalen. Logic and Structure. 4th ed. Springer, 2008.
# M. Sipser. Introduction to the Theory of Computation. 3rd ed. Cengage Learning, 2012.