Дискретная математика 2 2016/2017 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 44: Строка 44:
  
 
====Лекции  ====
 
====Лекции  ====
 +
 +
'''31 октября''' Булевы формулы. Тавтологии и выполнимые формулы. Задача проверки тавтологичности. Исчисление резолюций. Примеры опровержений. Корректность исчисления резолюций: если есть опровержение КНФ резолюциями, то КНФ невыполнима. Формулировка утверждения о полноте: для всякой невыполнимой КНФ есть опровержение резолюциями.
  
 
'''10 октября''' Конструктивная лемма Фаркаша. Алгоритм замены базисов с правилом Бленда и его сходимость. Конечно порожденные конусы поиэдральны, полиэдральные конусы конечно порождены. Политоп - выпуклая оболочка своих вершин. Выпуклая оболочка конечного числа точек - полиэдр.
 
'''10 октября''' Конструктивная лемма Фаркаша. Алгоритм замены базисов с правилом Бленда и его сходимость. Конечно порожденные конусы поиэдральны, полиэдральные конусы конечно порождены. Политоп - выпуклая оболочка своих вершин. Выпуклая оболочка конечного числа точек - полиэдр.

Версия 20:59, 31 октября 2016

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

Лекции проходят по понедельникам в аудитории 205 в 10:30-11:50. Первая лекция 5 сентября.

Лектор:

М.Н. Вялый vyalyi@gmail.com

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

151 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Волгин Андрей Денисович, andrewvlg@yandex.ru

152 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Святокум Полина Олеговна, pola_sv@mail.ru

Ссылки

Информация о курсе ДМ-2 (правила оценивания)

Литература по курсу ДМ-2

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

Материалы занятий

Консультации М.Н.Вялого

10 октября Начало 16:40 (если будут желающие). Встречаемся возле 617 ауд.

04 октября Начало 15:10. Искать возле 513 ауд.

30 сентября Начало 16:40. Искать возле 503 ауд.

23 сентября Начало 16:40. Искать возле 503 ауд.

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

Домашнее задание 4 Срок выполнения: к 14 ноября.

Домашнее задание 3 Срок выполнения: к 17 октября. (по многочисленным просьбам) Определение невырожденного полиэдра: Полиэдр в n-мерном пространстве называется невырожденным, если все минимальные грани - точки (вершины), и в каждой вершине обращается в равенство ровно n ограничений, задающих полиэдр (каждое равенство в системе ограничений считается один раз).

Домашнее задание 2 Срок выполнения: к 3 октября.

Домашнее задание 1 Срок выполнения: к 19 сентября.

Лекции

31 октября Булевы формулы. Тавтологии и выполнимые формулы. Задача проверки тавтологичности. Исчисление резолюций. Примеры опровержений. Корректность исчисления резолюций: если есть опровержение КНФ резолюциями, то КНФ невыполнима. Формулировка утверждения о полноте: для всякой невыполнимой КНФ есть опровержение резолюциями.

10 октября Конструктивная лемма Фаркаша. Алгоритм замены базисов с правилом Бленда и его сходимость. Конечно порожденные конусы поиэдральны, полиэдральные конусы конечно порождены. Политоп - выпуклая оболочка своих вершин. Выпуклая оболочка конечного числа точек - полиэдр.

3 октября Геометрическая идея симплекс-метода. Грани полиэдров. Минимальные грани. Вершины (0-мерные грани), ребра (1-мерные грани). Политопы - ограниченные полиэдры. Задача локального улучшения целевой функции. Критерий оптимальности. Увеличение целевой функции при сдвиге по ребру. Конструктивная лемма Фаркаша. Невырожденный случай, количество ребер равно размерности.

26 сентября Приложения двойственности в линейном программировании. Вывод теоремы Форда-Фалкерсона из анализа пары двойственных задач линейного программирования. Матричные игры двух игроков с нулевой суммой. Существование равновесия в смешанных стратегиях.

19 сентября Двойственность в линейном программировании. Критерий того, что неравенство является семантическим следствием совместной системы неравенств. Двойственная задача ЛП. Виды пар прямой и двойственной задачи. Теорема двойственности. Соотношения дополняющей нежесткости.

12 сентября Метод исключения переменных для систем линейных неравенств. Проекции полиэдров и достижимость максимума в задача ЛП. Синтаксическиее и семантические следствия. Критерий совместности систем линейных неравенств. Лемма Фаркаша и ее геометрический смысл.

5 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о потоке в сети, транспортная задача. Виды ЛП задач: общий, только с неравенствами, равенства на неотрицательные переменные. Дробно-линейное программирование и сводимость к ЛП.

Семинары

Задачи к семинару 31 октября

Задачи к семинару 10 октября

Задачи к семинару 3 октября

Задачи к семинару 26 сентября

Задачи к семинару 19 сентября Последние две задачи не разобраны до конца, будут обсуждаться в следующий раз.

Задачи к семинару 12 сентября Задача 5 на семинаре не разбиралась, отложена на следующее занятие.

Задачи к семинару 5 сентября