DM 2 2017 2018

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Содержание

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

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

Новости

  • (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.

Лектор

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

Семинаристы

163 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич, yhn1124@gmail.com, t.me/yhn112

164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна, lena97denisova@mail.ru

165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Моисеев Андрей Андреевич, andrei.moiseev213@yandex.ru

166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Ребенко Ярослав Алексеевич, yarebenko@gmail.com

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

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

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

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

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

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

Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. Экзамен состоит из 8 задач с указанием количества баллов за каждую задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.

Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 1/3 и 2/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.

Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.

Правила округления

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок. Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.

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

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

Сроки сдачи ДЗ для 164 и 166 группы:

Первое домашнее задание 19 сентября (защита до 10 октября). Второе домашнее задание 3 октября (защита до 24 октября). Третье домашнее задание 17 октября (защита до 7 ноября). Четвертое домашнее задание 7 ноября (защита до 28 ноября). Пятое домашнее задание 21 ноября (защита до 12 декабря). Шестое домашнее задание 5 декабря (защита до 26 декабря).

Сроки сдачи ДЗ для 163 и 165 группы:

Первое домашнее задание 22 сентября (защита до 13 октября). Второе домашнее задание 6 октября (защита до 27 октября). Третье домашнее задание 20 октября (защита до 10 ноября). Четвертое домашнее задание 10 ноября (защита до 1 декабря). Пятое домашнее задание 24 ноября (защита до 15 декабря). Шестое домашнее задание 8 декабря (защита до 29 декабря).


Коллоквиум пройдет с 11 по 15 декабря.

Экзамен (письменный) с 21 по 31 декабря.

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

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

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

Домашнее задание №1 -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для группы 164).

Домашнее задание №2 -- дедлайны: для сдачи 3 октября, для защиты 24 октября (для группы 164).

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

  • Общая задача линейного программирования.
  • Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях
  • Метод исключения переменных.
  • Способы докательства оптимальности линейных программ.
  • Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема

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

  • Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.
  • Полиэдры и политопы.
  • Симплекс метод.
  • Определение формулы логики высказываний (пропозициональной формулы).
  • Тавтологии, выполнимые, общезначимые и равносильные формулы.
  • Исчисление резолюций для пропозициональных формул.
  • Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.
  • Исчисление резолюций для формул первого порядка.
  • Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.
  • Логическое следование и аксиоматические теории.

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

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

Определение задачи линейного программирования. Примеры: задача о составлении раствора, транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.

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

Синтаксические следствия систем линейных ограничений. Задача ЛП, двойственная к данной. Принципы двойственности: (1) система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 1<=0 (2) если в прямой задаче целевая функция ограничена, то оптимальные решения прямой и двойственной задач совпадают.

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

Три специальных вида ЛП и объяснение, почему любая задача ЛП может быть приведена к любому из трех видов. Доказательство первого принципа двойственности методом исключения переменных: сначала для систем неравенств вида <=, затем для систем, состоящих из неравенств вида <= и равенств. Доказательство второго вида принципа двойственности методом исключения переменных для задач максимизации и систем ограничений, состоящих из неравенств вида <= и равенств. (Доказательств первого и второго принципа двойственности для систем ограничений, состоящих из неравенств вида <=, >= и равенств, не было.)

Лемма Фаркаша, объяснение, почему она является переформулировкой первого принципа двойственности для систем равенств в неотрицательных переменных. Геометрическое доказательство леммы Фаркаша. Вывод первого принципа двойственности для систем ограничений общего вида (неравенства вида <=, >= и равенства) из леммы Фаркаша.

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

Лекция 5 (3 октября).

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

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

Лекция 8 (31 октября).

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

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

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

Лекция 12 (28 ноября).

Лекция 13 (5 декабря).

Семинары

Листки с задачами для семинаров

Листок 1 (определение задач ЛП и их решение графическим методом)

Листок 2 (решение ЛП методом исключения переменных)

Листок 3 (двойственность в ЛП)

Листок 4 (интересные задачи, сводящиеся к ЛП)

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

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

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


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

Решение задач линейного программирования методом исключения переменных.

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

Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.

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

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

Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).

Конспект лекций о методе резолюций

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

164 группа: вторник с 16:40 до 19:30 в ком. 617 (Верещагин).

166 группа: вторник с 16:30 до 17:00 в ком. 617 (Милованов)

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

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. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)

7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)