imported>Nvereshagin: Migrated current public revision from wiki.cs.hse.ru

2019-08-29T09:28:36Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

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

Лекции проходят по вторникам в 15:10-16:30 в аудитории 509 за исключением первой лекции 4 сентября, которая будет в ауд. 317.

==Новости==
* '''23 декабря''' Выставлены [https://www.dropbox.com/s/ucj8g100p539hi1/exam-results-base.xls?dl=0 оценки] за экзамен. Критерии выставления баллов за решения задач [https://www.dropbox.com/s/6ynuq37i6z3lm98/exam-base-criteria.docx?dl=0 здесь]. [https://www.dropbox.com/s/qfb0fqn7zultigv/sol-18-12-21.pdf?dl=0 Решения задач экзамена.] Показ работ во вторник 25.12, 16:40-19:30, ауд.402.

* '''2 октября''' Выложено [https://www.dropbox.com/s/pfyo2vndq5p38d3/hw2.pdf?dl=0 Домашнее задание №2].

* '''18 сентября''' Лекция 25 сентября отменяется. Семинар в группе 173 в этот день также отменяется.

* '''3 сентября''' Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]

==Лектор==

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

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

173 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com. Ассистент Тульчинский Эдуард Станиславович, 153 группа, Tulchinskyi@yandex.ru

174 Дашков Евгений Владимирович edashkov@gmail.com. Ассистент Раджаб Эльдар оглы Агамов agamov@phystech.edu

175 Милованов Алексей Сергеевич, almas239@gmail.com. Ассистент Сурин Денис Владимирович denis.surin2011@yandex.ru

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

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

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

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

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.

====Экзамен====

Экзамен (письменный) состоится в пт. 21 декабря в 16:40 ауд. 622.

Показ работ во вторник 25.12, 16:40-19:30, ауд.402

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

===Сдача домашних заданий===

Первое домашнее задание: дедлайн для сдачи 18 сентября (защита до 9 октября).

'''В гр. 174 и 176 сдача продлена до 21 сентября.'''

Второе домашнее задание: дедлайн для сдачи 16 октября (защита до 30 октября).

'''В гр. 174, 175 и 176 защита продлена до 6 ноября.'''

Третье домашнее задание: дедлайн для сдачи 30 октября (защита до 13 ноября).

'''В гр. 174 и 176 сдача продлена до 6 ноября.'''

Четвертое домашнее задание: дедлайн для сдачи 13 ноября (защита до 27 ноября).

Пятое домашнее задание: дедлайн для сдачи 27 ноября (защита до 11 декабря).

Шестое домашнее задание: дедлайн для сдачи 11 декабря (защита до 25 декабря).

===Коллоквиум===

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

* 171, 173 группы с 12:10,
* 172, 175 группы с 13:30
* 174, 176 группы с 15:10

[https://www.dropbox.com/s/r6okjtbl5rjyuc5/colloq.pdf?dl=0 Вопросы к коллоквиуму 2018 года.]

===Экзамен===

Оценки за экзамен [https://www.dropbox.com/s/ucj8g100p539hi1/exam-results-base.xls?dl=0 здесь]. Критерии выставления баллов
за решения задач [https://www.dropbox.com/s/6ynuq37i6z3lm98/exam-base-criteria.docx?dl=0 здесь]. [https://www.dropbox.com/s/qfb0fqn7zultigv/sol-18-12-21.pdf?dl=0 Решения задач экзамена.]
Показ работ во вторник 25.12, 16:40-19:30, ауд.205

Экзамен (письменный) состоится в пт. 21 декабря в 16:40 ауд. 622.

===Пересдачи===

Пересдачи письменного экзамена 22 января ВТ 16:40-19:30 ауд. 300, 29 января ВТ 13:40-16:30 ауд. 400

Комиссия 5 февраля 16:40, ауд. 219

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

[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1] -- дедлайны: для сдачи 18 сентября, для защиты 9 октября.

[https://www.dropbox.com/s/pfyo2vndq5p38d3/hw2.pdf?dl=0 Домашнее задание №2] -- дедлайны: для сдачи 16 октября, для защиты 30 октября.

[https://www.dropbox.com/s/uigp382evdmv5kn/hw3.pdf?dl=0 Домашнее задание №3] -- дедлайны: для сдачи 30 октября, для защиты 13 ноября.

[https://www.dropbox.com/s/d6lzagxtetz8zgt/hw4.pdf?dl=0 Домашнее задание №4] -- дедлайны: для сдачи 13 ноября, для защиты 27 ноября.

[https://www.dropbox.com/s/0c0t2bvjbnfegpu/hw5.pdf?dl=0 Домашнее задание №5] -- дедлайны: для сдачи 27 ноября, для защиты 11 декабря.

[https://www.dropbox.com/s/cgyiulbdrfzcfwe/hw6.pdf?dl=0 Домашнее задание №6] -- дедлайны: для сдачи 11 декабря, для защиты 24 декабря.

===Оценки за домашние задания===

[https://www.dropbox.com/s/g9q5mw6eljkq17u/173.xls?dl=0 группа 173]

[https://www.dropbox.com/s/qra66oyveikecp2/174.xls?dl=0 группа 174]

[https://www.dropbox.com/s/zp7zlmjnl3h7bja/175.xls?dl=0 группа 175]

[https://docs.google.com/spreadsheets/d/10mP2yoXNElULWPk2xR-sI1fsXqqAAGhfXxyGMV91XDo/edit#gid=0 группа 176]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

====Лекция 4 (2 октября). ====

Доказательство второго принципа двойственности с помощью леммы Фаркаша.

Соотношения дополняющей нежесткости.

Задача о максимальном потоке, её представление в виде задачи ЛП, разрезы и их пропускные способности. Задача, двойственная к задаче о максимальном потоке.

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

Лемма о соотношении потоков и разрезов.
Доказательство теоремы Форда-Фалкерсона с помощью принципа двойственности.

Игры с нулевой суммой, теорема фон Ноймана и её вывод из принципа двойственности.

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

Полиэдры и их грани. Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.

====Лекция 7 (30 октября). ====
Конструктивное доказательство леммы Фаркаша и завершение описания алгоритма симплекс метода с начальным допустимым решением. Алгоритм нахождения начального допустимого решения.

Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. КНФ и ДНФ. (Очень кратко.)

Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности.

====Лекция 8 (6 ноября). ====
Еще раз формулировка ИР. Теорема полноты (любое, даже бесконечное, непротиворечивое множество дизъюнктов совместно).

Опровержение пропозициональных формул общего вида в исчислении резолюций.

Определение формулы первого порядка в данной сигнатуре. Запись утверждений формулами первого порядка.

Модели (интепретации) сигнатуры.

====Лекция 9 (13 ноября). ====
Нормальные модели. Общезначимые и выполнимые формулы. Равносильные формулы.

Теории и их модели. Семантическое следование. Теорема Черча об алгоритмической неразрешимости общезначимости, а значит и отношения семантического следования и отношения равносильности формул (без доказательства).

Дизъюнкты, универсальные дизъюнкты. Исчисление резолюций для доказательства несовместности множеств универсальных дизъюнктов. Теорема корректности ИР.

====Лекция 10 (20 ноября). ====
Непротиворечивые теории. Теорема полноты ИР (для множеств универсальных дизъюнктов). Исчисление резолюций для теорий, состоящих из формул общего вида (приведение к предваренной нормальной форме и сколемизация).

Доказательства общезначимости с помощью ИР. Выводимость формулы в теории с помощью ИР.

====Лекция 11 (27 ноября). ====
Гомоморфизмы, эпиморфизмы (сюръективные гомоморфизмы), изоморфизмы. Теорема о сохранении истинности при эпиморфизме (без подробного доказательства).
Изоморфные модели. Элементарно эквивалентные модели, элементарная эквивалентность изоморфных моделей.

Аксиомы равенства. Теорема полноты ИР для нормальных моделей (если теория не имеет нормальных моделей, то из
её аксиом и аксиом равенства можно вывести пустой дизъюнкт).

Доказательство элементарной эквивалентности с помощью игры Эренфойхта. Примеры: упорядоченные множества рациональных и действительных чисел, Z и Z+Z.

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

Доказательство в одну сторону: если Консерватор имеет выигрышную стратегию, то модели элементарно эквивалентны.

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

Cемантически полные полные теории.
Критерий семантической полноты в терминах элементарной эквивалентности моделей.
Задача аксиоматизации данной модели.

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

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

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

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

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

== Семинары ==

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

[https://www.dropbox.com/s/soeuux4bexd32va/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)] [https://www.dropbox.com/s/c8j532505sc1ekl/listok1solutions.pdf?dl=0 Ответы.]

[https://www.dropbox.com/s/ikl8a2b3fs1hqjs/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]
[https://www.dropbox.com/s/rzbnc1lp7ewgvbs/listok2solutions.pdf?dl=0 Ответы.]

[https://www.dropbox.com/s/c9omy38a8yhsew6/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]

[https://www.dropbox.com/s/llkvti0zuco5e6g/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]

[https://www.dropbox.com/s/o9ei1zqbs16zu2o/listok5.pdf?dl=0 Листок 5 (грани полиэдров и симплекс метод)]

[https://www.dropbox.com/s/o9ei1zqbs16zu2o/listok5.pdf?dl=0 Листок 6 (пропозициональные формулы и исчисление резолюций)]

[https://www.dropbox.com/s/em457o7ilb19ib8/listok7.pdf?dl=0 Листок 7 (Запись утверждений и выражение отношений формулами первого порядка; выполнимость, общезначимость и равносильность, теории и семантическое следование)]

[https://www.dropbox.com/s/b91gwe8dyde9qyf/listok8.pdf?dl=0 Листок 8 (исчисление резолюций для формул первого порядка, изоморфность, элементарная эквивалентность и игры Эренфойхта)]

[https://www.dropbox.com/s/fn6kiwd9m1jxphx/listok9.pdf?dl=0 Листок 9 (доказательства невыразимости, теории и их модели, аксиоматизация)]

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

====Семинар 1 (4 сентября)====
Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.

====Семинар 2 (11 сентября)====
Решение задач линейного программирования методом исключения переменных.

====Семинар 3 (18 сентября)====
Решение задач линейного программирования методом исключения переменных. Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.

====Семинар 4 (2 октября)====
Задачи на применение двойственности и соотношений дополняющей нежесткости.

====Семинар 5 (9 октября)====
Потоки и разрезы. Игры с нулевой суммой.

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

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

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

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

====Семинар 8 (6 ноября)====

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

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

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

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

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

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

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

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

====Семинар 14 (18 декабря, 15:10-16:30)====

====Семинар 15 (18 декабря, 16:40-18:00)====

==Конспекты лекций==
[https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока] (содержит только то, что рассказывалось на лекциях, и еще чуть-чуть :)

[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).]

[https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]

==Консультации ==
173 группа: вторник с 18:10 до 19:30 в ком. 617 (Верещагин).

174 и 176 группы: с 1640 в ауд. 219 (Дашков, по согласованию) и по договоренности (ассистенты).

175 группа: вторник с 18.10 до 19.30 в ком. 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.)

DM2-basic2018/2019 - История изменений

imported>Nvereshagin: Migrated current public revision from wiki.cs.hse.ru