Дискретная математика - 2 (ПМИ) 2023/24
Содержание
О курсе
Курс по выбору для студентов 2 курса в 1-2 модулях состоит из двух основных частей: теории вычислимых функции и классической логики первого порядка.
| Группы | Группа 1 | Группа 2 | Группа 4 |
|---|---|---|---|
| Лектор | Дашков Евгений Владимирович Telegram | ||
| Семинаристы | Дашков Евгений Владимирович Telegram | Оноприенко Анастасия Александровна Telegram | Таламбуца Алексей Леонидович |
| Ассистенты | |||
| Ассистент лектора | |||
Полезные ссылки
Материалы курса
Лекции
Лекции и семинары Е. Дашкова (записи прошлого года)
Конспект по формулам логики предикатов
Конспект по структурам (только определения и список задач --- черновик!)
Семинары
Листки с задачами для семинаров
Домашние задания
Домашнее задание разделено на несколько частей, которые выдаются примерно раз в одну или две недели и предполагают сдачу в письменном виде в установленные для каждой части сроки. Решение каждой задачи оценивается числом от 0 до 1. Некоторые задачи объявляются бонусными, остальные считаются обязательными. По итогам семестра вычисляется оценка за все домашнее задание в целом как отношение суммы баллов, набранных студентом за все решенные им задачи, к числу обязательных задач в домашнем задании, умноженное на 10.
Преподаватель вправе потребовать от любого студента “защитить” (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля, по усмотрению преподавателя.
Сроки сдачи
| Задание | Группа 1 | Группа 2 | Группа 4 |
|---|---|---|---|
| ДЗ 1 | |||
| ДЗ 2 | |||
| ДЗ 3 | |||
| ДЗ 4 | |||
| ДЗ 5 |
Срок сдачи задания устанавливается семинаристом группы.
Коллоквиум
Экзамен
Оценки и аттестация
Предусмотрены оценки за домашнее задание, коллоквиум и экзамен.
Итог = Округление(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.
