DM2-pilot2018/2019
Содержание
Дискретная математика на 2-ом курсе ПМИ (пилотный поток)
Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября. Последняя лекция 10 декабря.
17 декабря занятий не будет (ни лекции, ни семинара в 171 группе)
Результаты коллоквиума и накопленные оценки можно посмотреть в тех же таблицах, что и результаты проверки домашних заданий.
Лектор:
М.Н. Вялый vyalyi@gmail.com
Семинаристы:
171 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Гайдамашко Даниил Олегович, dogaydamashko@edu.hse.ru
172 Козачинский Александр Николаевич, kozlach@mail.ru, группа в телеграме для вопросов, ассистент Ракитин Денис Романович, drrakitin@edu.hse.ru
Ссылки
Информация о курсе ДМ-2 (правила оценивания)
Конспект лекций о методе резолюций
Экзамен
Дата и время экзамена: 21 декабря (пятница), начало 16:40, ауд. 622, 317
Важно: основная аудитория для пилотного потока - 317. Приходите туда, кто не поместится, пойдёт в 622.
Решения задач, критерии проверки, правило выставления оценки.
Результаты экзамена (с оценками по задачам).
Обратите внимание! Время и место показа работ ЕЩЕ РАЗ ИЗМЕНИЛОСЬ!
Показ работ, 25 декабря, 16:40, ауд.402
Коллоквиум
Дата и время: 15 декабря, ауд. 622.
171 группа приглашается к 12:10.
172 группа приглашается к 13:40.
[Программа коллоквиума.] Обратите внимание:
- В теоретические вопросы по логике входят игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
- На коллоквиуме не разрешается пользоваться никакими записями - ни в электронной, ни в бумажной форме.
10 декабря, 9:00, ауд. 205: консультация перед коллоквиумом.
Консультации
171 группа: М.Вялый по вторникам 15:10-16:40, ком. 617.
172 группа: Козачинский по понедельникам 12:10-13:30, ком. 617.
Материалы занятий
Домашние задания
Домашнее задание 6 171 группа - 3 декабря; 172 группа - 7 декабря.
Домашнее задание 5 171 группа - 26 ноября; 172 группа - 30 ноября, защита до коллоквиума.
Домашнее задание 4 171 группа - 12 ноября; 172 группа - 16 ноября, защита до коллоквиума.
Домашнее задание 3 171 группа - 15 октября; 172 группа - 19 октября, защита к 3 декабря.
Домашнее задание 2 171 группа - 1 октября; 172 группа - 5 октября, защита к 26 ноября
Домашнее задание 1 Сроки выполнения: 171 группа - к 17 сентября, 172 группа - к 21 сентября, защита к 12 ноября.
| Оценки (171 группа) | Оценки (172 группа) |
|---|
Лекции
3 декабря Выразимость предикатов формулами первого порядка. Доказательства невыразимости: метод авоморфизмов, игры Эренфойхта, элиминация кванторов. Выразимость в арифметике. Лемма о бета-функции Гёделя.
26 ноября Элементарно эквивалентные модели. Игры Эренфойхта.
19 ноября Теории и модели. Изоморфизмы моделей, сохранение значения замкнутой формулы при изоморфизме.
12 ноября Проверка общезначимости формул первого порядка. Исчисление резолюций для универсальных дизъюнктов. Предваренная и сколемовская нормальные формы.
29 октября Сводимость проверки выполнимости булевых формул к проверке выполнимости КНФ. Формулы первого порядка: определение, семантика. Модели заданной сигнатуры. Общезначимые формулы.
15 октября Булевы формулы. Тавтологии и выполнимые формулы. КНФ. Исчисление резолюций: корректность и полнота.
8 октября Симплекс метод. Действия в невырожденном случае. Алгоритм замены базисов в вырожденном случае. Правило Бленда. Корректность алгоритма замены базисов при соблюдении правила Бленда. Сходимость симплекс метода. Поиск начального допустимого решения с помощью вспомогательной задачи ЛП.
1 октября Введение в симплекс-метод. Грани полиэдров, размерности граней. Грани - множества оптитмальных решений задач ЛП на полиэдре. Общая схема симплекс-метода. Локальное улучшение целевой функции. Критерий оптимальности текущего решения.
24 сентября Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях.
17 сентября Критерий совместности систем линейных неравенств и двойственность. Лемма Фаркаша и ее геометрический смысл. Конечно порожденные и полиэдральные конусы. Двойственная задача ЛП. Теорема двойственности в ЛП.
10 сентября Системы линейных неравенств. Метод исключения переменных Фурье-Моцкина. Геометрические приложения: проекция полиэдра - полиэдр, политоп (выпуклая оболочка конечного числа точек) - полиэдр. Критерий совместности системы линейных неравенств.
3 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о назначениях, транспортная задача. Семантические и синтаксические следствия из систем линейных неравенств. Полиэдры и задача ЛП. Преобразования задач ЛП и систем неравенств. Канонические виды задач ЛП.
