Содержание

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

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

Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.

Новости

Консультации в 153 группе переносятся со вторника 16:40-18

на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).

14 октября лекции не будет!

Лектор:

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

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

153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,

154 Козачинский Александр Николаевич, kozlach@mail.ru,ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,

155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,

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

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

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

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

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

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

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

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

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

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

Эти сроки немного различаются для разных групп (поскольку семинары в разные дни).

Сроки для 153 группы:

Первое домашнее задание 16 сентября. Второе домашнее задание 30 сентября. Третье домашнее задание 14 октября. Четвертое домашнее задание 1 ноября. Пятое домашнее задание 18 ноября. Шестое домашнее задание 2 декабря.

Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).

Экзамен - 27 декабря (дата предварительная).

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

Оценки за домашние задания (группа 153)

Оценки за домашние задания (группа 154)

Домашнее задание №1 -- дедлайн 16 сентября (для пятничных групп), 19 сентября (для групп по понедельникам) и 20 сентября (для вторничных групп)

Домашнее задание №2 -- дедлайн 30 сентября (для пятничных групп), 3 октября (для групп по понедельникам) и 4 октября (для вторничных групп)

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

Общая задача линейного программирования.

Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях

Метод исключения переменных.

Способы докательства оптимальности линейных программ.

Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема

двойственности

Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.

Полиэдры и политопы.

Симплекс метод.

Определение формулы логики высказываний.

Тавтологии, выполнимые, общезначимые и равносильные формулы.

Исчисление резолюций.

Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.

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

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

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

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

Определение вид задачи линейного программирования. Пример: задача о составлении раствора, задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде системы равенств на неотрицательные переменные. Как доказывать оптимальность решения задачи линейного программирования. Общее представление о двойственности.

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

Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0<-1. Лемма Фаркаша и ее вывод из критерия совместности.

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

Проекция полиэдра является полиэдром. Достижение максимума целевой функцией. Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).

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

Доказательство принципа двойственности. ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная к задаче о максимальном потоке.

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

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

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

Симплекс метод.

14 октября лекции не будет (лектор в командировке)

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

28 октября лекции не будет (сессия)

4 ноября лекции не будет (праздник)

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

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

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

Лекция 11 (2 декабря).

Лекция 12 (9 декабря).

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

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

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

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

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

Задачи второго семинара.

Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)

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

Изучение синтаксических следствий, применение критерия совместности.

Задачи третьего семинара

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

Двойственные задачи.

Задачи четвертого семинара

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

Эта черновик конспектов лекций М.Н.Вялого для пилотного потока. Он покрывает весь материал первых шести лекций. https://drive.google.com/file/d/0By-nGAT52Ee3cHo1c1lPNlpsSkE/view?usp=sharing

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

153 группа: среда 16:40-18 и пятница 15:10-16:30 в каб. 617.

Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313

Для 155 группы консультации будут проходить по вторникам с 13:40 до 14:30 в преподавательской и по пятницам с 11:00 до 11:50 в ауд. 304.

DM 2 2016 2017