Дискретная математика - 2 (ПМИ) 2023/24
Содержание
О курсе
Курс по выбору для студентов 2 курса в 1-2 модулях состоит из двух основных частей: теории вычислимых функции и классической логики первого порядка.
| Группы | Группа 1 | Группа 2 | Группа 4 |
|---|---|---|---|
| Лектор | Дашков Евгений Владимирович Telegram | ||
| Семинаристы | Дашков Евгений Владимирович Telegram |
Оноприенко Анастасия Александровна Telegram |
Таламбуца Алексей Леонидович Telegram |
| Ассистенты | Сиразитдинова Зарема Кульпанович Данила Пономарчук Анна Марченко Мария | ||
| Ассистент лектора | Числова Алёна | ||
Полезные ссылки
Телеграм-чат курса
Распределение ассистентов
Материалы курса
Лекции
Лекции и семинары Е. Дашкова (записи прошлого года)
Конспект по формулам логики предикатов
Конспект по структурам (только определения и список задач --- черновик!)
Семинары
Листки с задачами для семинаров
Домашние задания
Домашнее задание разделено на несколько частей, которые выдаются примерно раз в одну или две недели и предполагают сдачу в письменном виде в установленные для каждой части сроки. Решение каждой задачи оценивается числом от 0 до 1. Некоторые задачи объявляются бонусными, остальные считаются обязательными. По итогам семестра вычисляется оценка за все домашнее задание в целом как отношение суммы баллов, набранных студентом за все решенные им задачи, к числу обязательных задач в домашнем задании, умноженное на 10.
Преподаватель вправе потребовать от любого студента “защитить” (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля, по усмотрению преподавателя.
| Ссылка на классрум | Группа 1 | Группа 2 | Группа 4 |
|---|
Сроки сдачи
| Задание | Группа 1 | Группа 2 | Группа 4 |
|---|---|---|---|
| ДЗ 1 | 06.02 | 06.02 | 09.02 |
| ДЗ 2 | 24.02 | 23.02 | 26.02 |
| ДЗ 3 | 15.03 | 15.03 | 18.03 |
| ДЗ 4* | 01.04 | 01.04 | 01.04 |
| ДЗ 5 | 09.04 | 09.04 | 09.04 |
| ДЗ 6 | 30.04 | 30.04 | 30.04 |
| ДЗ 7 | 27.05 | 27.05 | 27.05 |
| ДЗ 8 | 08.06 | 08.06 | 10.06 |
| ДЗ 9 | 17.06 | 17.06 | 17.06 |
Срок сдачи задания устанавливается семинаристом группы.
Коллоквиум
Проводится приблизительно за месяц до экзамена очно в устной форме (допускается и проведение онлайн). Студент получает три теоретических вопроса и время на подготовку ответа. Во время подготовки можно пользоваться любыми материалами, но нельзя советоваться с кем-либо. Отвечать следует “с чистого листа”; с разрешения преподавателя при этом можно использовать лишь самостоятельно написанные во время подготовки заметки.
Коллоквиум пройдет 6-го июня с.г. с 1100 до 2000 в ауд. S224. Распределение студентов по времени будет выработано позже. Уточненные правила и список вопросов здесь.
Экзамен
Письменный экзамен проводится очно во время сессии после четвертого модуля. На экзамене можно пользоваться любыми материалами на бумаге, изготовленными до начала экзамена (если это не противоречит правилам против списывания). Решение каждой задачи оценивается числом от 0 до 1. Некоторые задачи экзамена объявляются бонусными, остальные считаются обязательными. Оценкой за экзамен является отношение суммы баллов, набранных студентом за все решенные им задачи, к числу обязательных задач в экзаменационном задании, умноженное на 10.
Оценки и аттестация
Предусмотрены оценки за домашнее задание, коллоквиум и экзамен.
Итог = Округление(min(0,3 * ДЗ + 0,35 * КОЛ + 0,35 * Э, 10)),
где ДЗ — это оценка за все домашнее задание в целом, КОЛ — оценка за коллоквиум, Э — оценка за экзамен. Эти оценки могут быть нецелыми и приводятся без округления с наибольшей доступной точностью.
Округление производится к ближайшему целому. Полуцелые числа округляются вверх.
Автоматы по курсу не предусмотрены.
Текущие оценки
Прочие ресурсы
Основная литература
- Н.К. Верещагин, А. Шень. Вычислимые функции. М.:МЦНМО, 2017.
- Н.К. Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 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.
