DM 2 2016 2017

Дискретная математика на 2-ом курсе ПМИ

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

Лектор:

Н.К. Верещагин 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 домашних заданий, коллоквиум и экзамен. Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ). Оценка за домашние задания равна доле решенных задач, умноженной на 10. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара. Оценки за каждое ДЗ будут выставляться примерно через неделю после дедлайна. Сдача домашних заданий после их срока невозможна. Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).

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

Контрольные мероприятия и их сроки

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

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

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

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

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

Домашнее задание №1 https://drive.google.com/file/d/0By-nGAT52Ee3NnFiN0IxeWdMb1E/view?usp=sharing -- дедлайн 16 сентября (для пятничных групп) и 20 сентября (для вторничных групп)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендуемая литература

1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.

3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. Для курса будут наиболее важны главы 1, 3 и

4. Глава 1 содержит материал, который практически полностью входил в программу курса "Дискретная математика -1". Материал главы 4 в курсе будет затронут очень незначительно.

5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.

6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.