Версия 23:38, 7 сентября 2020

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

Лекции транслируются по субботам в 18:10 -- 19:30.

Новости

No news is good news.

Лектор

Евгений Владимирович Дашков. Почта: edashkov@gmail.com; ТГ: @edashkov; vk.com/evgeny.v.dashkov

Семинаристы и ассистенты

195 группа: Оноприенко Анастасия Александровна, почта ansidiana@yandex.ru. Для быстрой связи лучше писать в телеграм @ansidiana.

196 группа: Евгений Дашков; ассистент – Лямзин Алексей, почта: adlyamzin@edu.hse.ru, телеграмм: @almondflower

197 группа: Антон Гнатенко, почта: agnatenko@hse.ru, телеграм: @antongnatenko. Ассистент: Мануйленко Никита, почта: nsmanuylenko@edu.hse.ru, телеграм: @WheelDeal

Краткое описание

Курс состоит из двух частей. В первом модуле будет общая теория вычислимости, во втором модуле будет изучаться математическая логика: формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами логики предикатов, исчисление резолюций.

Отчётность по курсу и критерии оценки

6 домашних заданий, коллоквиум и экзамен.

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

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

Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по теории вычислимости, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. Экзамен состоит из 8 задач и тоже оценивается по десятибалльной системе. Задачи нужно решить за две пары.

Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.35, а оценка за домашние задания - с коэффициентом 0.3. Округление делается один раз --- при вычислении итоговой оценки. Применяются стандартные правила, но полуцелые числа округляются вверх.

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен или получил на нем менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.

Сроки контрольных мероприятий

Сдача домашних заданий

Первое домашнее задание: срок сдачи

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

Второе домашнее задание: срок сдачи

Коллоквиум

Коллоквиум пройдет в с

Экзамен

Пересдачи

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

Домашнее задание № 1

Текущая успеваемость

Таблица текущих результатов.

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

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

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

Запись лекции.

Семинары

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

Листок 1

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

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

Конспект лекций профессора Н.К. Верещагина о методе резолюций

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

Группа в ТГ для обсуждения вопросов по курсу.

Сервер телеконференций. (Рекомендуется использовать Chrome.)

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

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

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

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