Дискретная математика 2 2016/2017
Содержание
Дискретная математика на 2-ом курсе ПМИ (пилотный поток)
Лекции проходят по понедельникам в аудитории 205 в 10:30-11:50. Первая лекция 5 сентября.
Объявление 19 декабря занятий не будет. Курс закончен. Остался только экзамен 22 декабря (см. ниже более подробную информацию).
Лектор:
М.Н. Вялый vyalyi@gmail.com
Семинаристы:
151 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Волгин Андрей Денисович, andrewvlg@yandex.ru
152 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Святокум Полина Олеговна, pola_sv@mail.ru
Коллоквиум
Коллоквиум будет 16 декабря, 311 ауд. Начало для 151 группы 12:10, для 152 группы 13:40.
12 декабря, 10:30, будет консультация перед коллоквиумом. Предварительно, в ауд. 205 (там же, где и лекции). С аудиторией возможны изменения, следите за информацией!
Важное уточнение: на коллоквиуме при подготовке ответа не разрешается пользоваться никакими записями.
Экзамен (письменный)
состоится 22 декабря в 13:40 ауд. 622, показ работ 24 декабря.
На экзамене разрешается пользоваться письменными источниками и не разрешается пользоваться электронными приборами.
Решения задач экзамена 22.12.2016
Задачи переэкзаменовки 18.01.2017
Решения задач переэкзаменовки 18.01.2017
Задачи переэкзаменовки 24.01.2017
Решения задач переэкзаменовки 24.01.2017
Ссылки
Информация о курсе ДМ-2 (правила оценивания)
Записки по материалам курса. Они лучше соответствуют тому, что было на лекциях, чем предварительные записки, которые выкладывались ранее. Как и предыдущий вариант, содержат также дополнительный материал, который не вошел в лекции.
Материалы занятий
Консультации М.Н.Вялого
6 декабря Крайний срок защиты домашних заданий 3-4 в группе 152. 15:10-16:30. Встречаемся возле 617 ауд. (Можно попробовать найти меня после лекции Макарычева (заканчивается в 18:00), которая будет в 509 ауд.)
29 ноября Начало 15:10. Встречаемся возле 617 ауд.
22 ноября Начало 15:10. Встречаемся возле 617 ауд.
10 октября Начало 16:40 (если будут желающие). Встречаемся возле 617 ауд.
04 октября Начало 15:10. Искать возле 513 ауд.
30 сентября Начало 16:40. Искать возле 503 ауд.
23 сентября Начало 16:40. Искать возле 503 ауд.
Домашние задания
Домашнее задание 6 Срок выполнения: к 5 декабря. Обратите внимание! Срок выполнения этого домашнего задания одна неделя, а не две!
Домашнее задание 5 Срок выполнения: к 28 ноября.
Домашнее задание 4 Срок выполнения: к 14 ноября.
Домашнее задание 3 Срок выполнения: к 17 октября. (по многочисленным просьбам) Определение невырожденного полиэдра: Полиэдр в n-мерном пространстве называется невырожденным, если все минимальные грани - точки (вершины), и в каждой вершине обращается в равенство ровно n ограничений, задающих полиэдр (каждое равенство в системе ограничений считается один раз).
Домашнее задание 2 Срок выполнения: к 3 октября.
Домашнее задание 1 Срок выполнения: к 19 сентября.
Лекции
5 декабря Элементарная эквивалентность моделей. Изоморфные модели. Игры Эренфойхта.
28 ноября Доказательства невыразимости предикатов с помощью автоморфизмов. Элиминация кванторов. Приложения к доказательствам невыразимости.
21 ноября Перестановки кванторов. Перестановки связок и кванторов. Приведенная нормальная форма. Существование ПНФ, эквивалентной данной формуле. Выразимость в теории множеств и арифметике. Арифметическое кодирования конечных подмножеств множества натуральных чисел.
14 ноября Определение формул первого порядка. Параметры, сводобные и связанные вхождения. Интерпретации. Значение формулы в заданной интерпретации при заданной оценке переменных. Общезначимые формулы, выполнимые формулы. Эквивалентные формулы. Примеры эквивалентных и неэквивалентных формул. Замена переменной в кванторе.
7 ноября Доказательство полноты исчисления резолюций. Связь построения опровержения резолюциями и перебором дерева возможных присваиваний. Легкие и трудные КНФ для резолюций. Применение резолюций к произвольным формулам. Идея аксиоматического вывода применительно к задаче проверки тавтологичности. Отношения и функции. Предикатные и функциональные символы. Кванторы. Примеры.
31 октября Булевы формулы. Тавтологии и выполнимые формулы. Задача проверки тавтологичности. Исчисление резолюций. Примеры опровержений. Корректность исчисления резолюций: если есть опровержение КНФ резолюциями, то КНФ невыполнима. Формулировка утверждения о полноте: для всякой невыполнимой КНФ есть опровержение резолюциями.
10 октября Конструктивная лемма Фаркаша. Алгоритм замены базисов с правилом Бленда и его сходимость. Конечно порожденные конусы поиэдральны, полиэдральные конусы конечно порождены. Политоп - выпуклая оболочка своих вершин. Выпуклая оболочка конечного числа точек - полиэдр.
3 октября Геометрическая идея симплекс-метода. Грани полиэдров. Минимальные грани. Вершины (0-мерные грани), ребра (1-мерные грани). Политопы - ограниченные полиэдры. Задача локального улучшения целевой функции. Критерий оптимальности. Увеличение целевой функции при сдвиге по ребру. Конструктивная лемма Фаркаша. Невырожденный случай, количество ребер равно размерности.
26 сентября Приложения двойственности в линейном программировании. Вывод теоремы Форда-Фалкерсона из анализа пары двойственных задач линейного программирования. Матричные игры двух игроков с нулевой суммой. Существование равновесия в смешанных стратегиях.
19 сентября Двойственность в линейном программировании. Критерий того, что неравенство является семантическим следствием совместной системы неравенств. Двойственная задача ЛП. Виды пар прямой и двойственной задачи. Теорема двойственности. Соотношения дополняющей нежесткости.
12 сентября Метод исключения переменных для систем линейных неравенств. Проекции полиэдров и достижимость максимума в задача ЛП. Синтаксическиее и семантические следствия. Критерий совместности систем линейных неравенств. Лемма Фаркаша и ее геометрический смысл.
5 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о потоке в сети, транспортная задача. Виды ЛП задач: общий, только с неравенствами, равенства на неотрицательные переменные. Дробно-линейное программирование и сводимость к ЛП.
Семинары
Задачи к семинару 21 ноября Задача 3 будет разбираться в следующий раз. Очень рекомендуется попробовать ее решить к следующему занятию на основе тех идей, которые обсуждались в этот раз.
Задачи к семинару 14 ноября Часть задач будет разобрана на следующем семинаре.
Задачи к семинару 7 ноября Задачи 5 и 6 переносятся на следующий раз.
Задачи к семинару 19 сентября Последние две задачи не разобраны до конца, будут обсуждаться в следующий раз.
Задачи к семинару 12 сентября Задача 5 на семинаре не разбиралась, отложена на следующее занятие.
