Дискретная математика - 2 (ПМИ) 2023/24 — различия между версиями

Версия 23:06, 2 марта 2024

О курсе

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

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

Телеграм-чат курса
Распределение ассистентов

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

Лекции

Лекции и семинары Е. Дашкова (записи прошлого года)

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

Конспект по формулам логики предикатов

Конспект по структурам (только определения и список задач --- черновик!)

Семинары

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

• Листок 1

• Листок 2

• Листок 3

• Листок 4

• Листок 5

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

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

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

Сроки сдачи

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

Коллоквиум

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

Экзамен

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

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

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

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

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

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

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

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

Общая таблица.

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

• Директория с материалами курса прошлого года

• Видео лекций и некоторых семинаров 2020 г.

• Конспекты семинаров Оноприенко А.А. за 2020-2021 учебный год

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

1. Н.К. Верещагин, А. Шень. Вычислимые функции. М.:МЦНМО, 2017.
2. Н.К. Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2017.
3. В.Н. Крупский. Введение в сложность вычислений. М.: Факториал, 2006.
4. В.А. Успенский, Н.К. Верещагин, В.Е. Плиско. Вводный курс математической логики. М.: Физматлит, 2002.

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

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