Текущая версия на 17:45, 8 февраля 2018

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

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

Новости

• (22 декабря) Проверены экзаменационные работы. Баллы за задачи и критерии их оценки (на последнем листе) находятся здесь. Показ работ 23 декабря в 16:40 в ауд. 402. Решения задач здесь

• (18 декабря) Экзамен состоится в четверг 21 декабря с 15 до 18 в ауд. 622. Объявление для группы 164: После сдачи экзаменационной работы можно будет защитить шестое ДЗ.

• (14 декабря) Объявление для группы 164: в пятницу 15 декабря после коллоквиума (до 17:15) можно защитить пятое домашнее задание Н.К. Верещагину (ауд. 617). Другого дня для защиты пятого ДЗ лектору не будет.

• (5 декабря) Выложено расписание коллоквиума:

12 декабря (вторник)

Группа 161 13:40-16:30 (первая пара 300, затем 622)

Группа 162 15:10-18:00 (первая пара 622, затем 435)

Группа 163 16:40-18:00 (и до победного конца) (ауд. 311).

Подгруппы 164-2, 165-1: 12:10 - 15:00 (первая пара 622, потом 505)

Группа 166 12:10 - 15:00 (первая пара 622, потом 219)

15 декабря (Пятница) Подгруппы 164-1 и 165-2: время 13:40-16:30 -- ауд.205.

• (24 ноября) Выложены Вопросы к коллоквиуму

• (23 ноября) Выложено Домашнее задание №6. Срок сдачи для 164 и 166 групп - 5 декабря.

• (7 ноября) Выложено Домашнее задание №5. Срок сдачи для 164 и 166 групп - 21 ноября.

• (27 октября) Выложено Домашнее задание №4. Срок сдачи для 164 и 166 групп - 7 ноября.

• (19 октября) Дедлайн защиты второго домашнего задания для группы 164 сдвинут на 31 октября (из-за сессии)

• (12 октября) Внимание! По ошибке в третьем домашнем задании первые две задачи совпадали с некоторыми задачами из второго домашнего задания. Они заменены на новые задачи.

• (10 октября) Крайний срок сдачи третьего домашнего задания для групп 164, 166 сдвинут на 24 октября (поскольку 24 октября каникулы, при сдаче 24 октября задание надо послать по компьютерной почте).

• (3 октября) Выложено Домашнее задание №3

• (19 сентября) Выложено Домашнее задание №2

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

• (1 сентября) Выложено Домашнее задание №1

Лектор

Н.К. Верещагин 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 баллов. Задачи нужно решить за две пары.

Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/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.

Экзамен

Баллы за задачи и критерии их оценки (на последнем листе) находятся здесь. Показ работ 23 декабря в 16:40 в ауд. 402. Решения задач [ https://www.dropbox.com/s/vgj8vcm2yyx63rg/main-17-12-21-sol.pdf?dl=0 здесь]

Пересдача 23.01.2018: Решения задач здесь Баллы за задачи и критерии их оценки (на предпредпоследнем листе) находятся здесь. Показ работ 30.1.18 в ауд. 617 с 16:40 до 17:15.

Пересдача 30.01.2018: Решения задач здесь Баллы за задачи и критерии их оценки (на предпоследнем листе) находятся здесь. Там же оценки (смотри на листе группы в конце списка). Показ работ 06.02.18 в ауд. 617 с 16:40 до 17:30.

Сдача экзамена комиссии состоится 3 февраля ВТ, 16:40-19:10, ауд.511. Состав комиссии: Вялый, Верещагин, Дашков. Для сдачи экзамена комиссии надо знать теорию в объеме коллоквиума и уметь решать задачи коллоквиума и задачи того типа, которые давались на письменном экзамене.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Домашнее задание №4. Срок сдачи для 164 и 166 групп - 7 ноября. Защита до 28 ноября.

Домашнее задание №5. Срок сдачи для 164 и 166 групп - 21 ноября. Защита до 12 декабря.

Домашнее задание №6. Срок сдачи для 164 и 166 групп - 5 декабря. Защита до 26 декабря.

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

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

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

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

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

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

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

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

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

• Исчисление резолюций для пропозициональных формул.

• Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели. Доказательства элементарной эквивалентности с помощью игр Эренфойхта

• Исчисление резолюций для формул первого порядка.

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

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

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

Лекция 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 ноября).

Выразимые (определимые отношения). Сохранение отношений при автоморфизмах. Доказательства невыразимости.

Cемантически полные и (дедуктивно) полные теории. Критерий семантической полноты в терминах элементарной эквивалентности моделей. Элементарная теория данной модели. Задача аксиоматизации элементарной теории модели. Аксиоматизация элементарной теории упорядоченного множества рациональных чисел (доказательство с помощью игры Эренфойхта).

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

Аксиоматизация элементарной теории упорядоченного множества целых чисел (доказательство с помощью игры Эренфойхта).

Аксиоматизация элементарной теории упорядоченного множества действительных чисел. Аксиоматизация элементарной теории поля комплексных чисел. Обе теоремы без доказательства.

Семинары

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

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

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

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

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

Листок 5 (грани полиэдров и симплекс метод)

Листок 6 (пропозициональные формулы и исчисление резолюций)

Листок 7 (Запись утверждений и выражение отношений формулами первого порядка; выполнимость, общезначимость и равносильность, теории и семантическое следование)

Листок 8 (исчисление резолюций для формул первого порядка, изоморфность, элементарная эквивалентность и игры Эренфойхта)

Листок 9 (доказательства невыразимости, теории и их модели, аксиоматизация)

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

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

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

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

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

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

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

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

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

Семинар 5 (3 октября)

Потоки и разрезы. Игры с нулевой суммой.

Семинар 6 (10 октября)

Решение задач ЛП симплекс-методом.

Семинар 7 (17 октября)

Задачи на пропозициональные формулы.

Семинар 8 (31 октября)

Опровержение формул в Исчислении Резолюций. Запись свойств и суждений формулами первого порядка.

Семинар 9 (7 ноября)

Выражение отношений формулами первого порядка. Модели теорий.

Семинар 10 (14 ноября)

Задачи на семантическое следование. Приведение к предварённой и сколемовской нормальным формам. Доказательство несовместности, общезначимости и семантического следования в Исчислении резолюций.

Семинар 11 (21 ноября)

Задачи на изоморфизм, элементарную эквивалентность и игры Эренфойхта.

Семинар 12 (28 ноября)

Задачи на невыразимость, элементарную эквивалентность и игры Эренфойхта (листок 9).

Семинар 13 (5 декабря)

Задачи на совместность и полноту теорий, аксиоматизация элементарной теории моделей (листок 9)

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

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

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

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

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

164 группа: вторник с 15:15 до 18:20 в ком. 617 (Верещагин).

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

163 и 165 группы: пятница с 16:40 до 18:20 в ком. 501 (Дашков)

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

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.)