Содержание

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

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

Лекции проходят по вторникам в 10:30-11:50 в аудитории R3-4 за исключением первой лекции 3 сентября, которая будет в ауд. R503.

Новости

Лектор

Н.К. Верещагин nikolay.vereshchagin@gmail.com

Семинаристы

183 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com.

186 и 187 Дашков Евгений Владимирович edashkov@gmail.com.

185 Милованов Алексей Сергеевич, almas239@gmail.com.

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

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

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

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

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

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

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

Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.

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

Правила округления

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления итоговой оценок. Округление при выставлении итоговой оценки арифметическое (то есть, 6.5 округляется до 7, а 6.49 - до 6).

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

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

Первое домашнее задание: дедлайн для сдачи 18 сентября (защита до 9 октября).

В гр. 174 и 176 сдача продлена до 21 сентября.

Второе домашнее задание: дедлайн для сдачи 16 октября (защита до 30 октября).

В гр. 174, 175 и 176 защита продлена до 6 ноября.

Третье домашнее задание: дедлайн для сдачи 30 октября (защита до 13 ноября).

В гр. 174 и 176 сдача продлена до 6 ноября.

Четвертое домашнее задание: дедлайн для сдачи 13 ноября (защита до 27 ноября).

Пятое домашнее задание: дедлайн для сдачи 27 ноября (защита до 11 декабря).

Шестое домашнее задание: дедлайн для сдачи 11 декабря (защита до 25 декабря).

Коллоквиум

Коллоквиум пройдет в среду 18 декабря. Пересдача коллоквиума в

Вопросы к коллоквиуму 2018 года.

Экзамен

Экзамен (письменный) состоится во вторник 24 декабря.

Показ работ 26 декабря.

Оценки за экзамен здесь. Критерии выставления баллов за решения задач здесь. Решения задач экзамена.

Пересдачи

Пересдача коллоквиума 26 декабря. Пересдачи письменного экзамена 22 января, 29 января

Комиссия 5 февраля.

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

Домашнее задание №1 -- дедлайны: для сдачи 18 сентября, для защиты 9 октября.

Оценки за домашние задания

Примерное содержание лекций

Исчисление резолюций для пропозициональных формул.

Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели. Доказательства элементарной эквивалентности с помощью игр Эренфойхта

Исчисление резолюций для формул первого порядка.

Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.

Логическое следование и аксиоматические теории.

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

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

Лекция 2 (10 сентября).

Лекция 3 (17 сентября).

Лекция 4 (24 сентября).

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

Лекция 6 (8 октября).

Лекция 7 (15 октября).

Лекция 8 (29 октября).

Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ. (Очень кратко.)

Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности.

Лекция 9 (5 ноября).

Еще раз формулировка ИР. Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно).

Опровержение пропозициональных формул общего вида в исчислении резолюций.

Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка.

Модели (интепретации) сигнатуры.

Лекция 10 (12 ноября).

Нормальные модели. Общезначимые и выполнимые формулы. Равносильные формулы.

Теории и их модели. Семантическое следование. Теорема Черча об алгоритмической неразрешимости общезначимости, а значит и отношения семантического следования и отношения равносильности формул (без доказательства).

Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР.

Лекция 11 (19 ноября).

Непротиворечивые теории. Теорема полноты ИР (для множеств универсальных дизъюнктов). Исчисление резолюций для теорий, состоящих из формул общего вида (приведение к предваренной нормальной форме и сколемизация).

Доказательства общезначимости с помощью ИР. Выводимость формулы в теории с помощью ИР.

Лекция 12 (26 ноября).

Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Теорема о сохранении истинности при эпиморфизме (без подробного доказательства). Изоморфные модели. Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей.

Аксиомы равенства. Теорема полноты ИР для нормальных моделей (если теория не имеет нормальных моделей, то из её аксиом и аксиом равенства можно вывести пустой дизъюнкт).

Доказательство элементарной эквивалентности с помощью игры Эренфойхта. Примеры: упорядоченные множества рациональных и действительных чисел, Z и Z+Z.

Лекция 13 (3 декабря).

Доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны.

Выразимые (определимые отношения). Сохранение выразимых отношений при автоморфизмах. Доказательства невыразимости.

Cемантически полные полные теории. Критерий семантической полноты в терминах элементарной эквивалентности моделей. Задача аксиоматизации данной модели.

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

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

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

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

Семинары

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

Листок 1 (определение задач ЛП и их решение графическим методом) Ответы.

Проведённые семинары в группе 183

Семинар 1 (3 сентября)

Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.

Семинар 2 (10 сентября)

Решение задач линейного программирования методом исключения переменных.

Семинар 3 (17 сентября)

Решение задач линейного программирования методом исключения переменных. Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.

Семинар 4 (24 сентября)

Задачи на применение двойственности и соотношений дополняющей нежесткости.

Семинар 5 (1 октября)

Потоки и разрезы. Игры с нулевой суммой.

Семинар 6 (8 октября)

Решение задач ЛП симплекс-методом.

Семинар 7 (15 октября)

Задачи на пропозициональные формулы.

Семинар 8 (28 октября)

Опровержение формул в Исчислении Резолюций. Запись свойств и суждений формулами первого порядка.

Семинар 9 (5 ноября)

Выражение отношений формулами первого порядка. Модели теорий.

Семинар 10 (12 ноября)

Задачи на семантическое следование. Приведение к предварённой и сколемовской нормальным формам. Доказательство несовместности, общезначимости и семантического следования в Исчислении резолюций.

Семинар 11 (19 ноября)

Задачи на изоморфизм, элементарную эквивалентность и игры Эренфойхта.

Семинар 12 (26 ноября)

Задачи на невыразимость, элементарную эквивалентность и игры Эренфойхта (листок 9).

Семинар 13 3 декабря)

Задачи на совместность и полноту теорий, аксиоматизация элементарной теории моделей (листок 9)

Семинар 14 (10 декабря)

Семинар 15 (17 декабря)

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

Конспект лекций о линейном программировании для основного потока (содержит только то, что рассказывалось на лекциях, и еще чуть-чуть :)

Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).

Конспект лекций о методе резолюций

Консультации

173 группа: вторник с 18:10 до 19:30 в ком. 617 (Верещагин).

174 и 176 группы: с 1640 в ауд. 219 (Дашков, по согласованию) и по договоренности (ассистенты).

175 группа: вторник с 18.10 до 19.30 в ком. 617 (Милованов).

DM2-basic2019/2020