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

2017-06-14T11:01:55Z

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

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

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

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

==Новости==

* Отодвинут срок сдачи последнего ДЗ для 153 группы. Новый дедлайн сдачи: понедельник 12 декабря в 15:00 (и вторник 13 для тех, у кого военная кафедра - работы нужно послать по электронной почте). Работы надо сдать Федору Когану на его консультации (ауд. 623). Крайний срок защиты не изменен.

* Коллоквиум состоится в ауд. 509 13 декабря. Получить билет для ответа нужно в начале указанного периода, но при невозможности прийти вовремя можно и в любое время в интервале 9-11 и 13:40-16. Приоритет будет отдан тем, кто пришел в свое время (группа 153 в 15-16:20, группа 154 в 10:30-11:50, группа 155 в 13:40-15, группа 156 в 9-10:20).

* Выложено [https://www.dropbox.com/s/arpstg9oypen94e/hw6.pdf?dl=0 Домашнее задание №6]

* Выложены [https://www.dropbox.com/s/du2suujppow3rfm/colloq.pdf?dl=0 вопросы к коллоквиуму].

* Определена дата коллоквиума: вторник 13 декабря. Группа 153 в 15-16:20, Группа 154 в 10:30-11:50, Группа 155 в 13:40-15, Группа 156 в 9-10:20.

* Напоминание: консультации Фёдора Когана для группы 153 проходят в понедельник с 13-40 до 16-30 (ауд. 623 и 432). Приходите защищать ДЗ и консультироваться по содержанию лекций!

* Экзамен (письменный) состоится 22 декабря в 13:40 ауд. 509 (основной поток) и 622 (пилотный), показ работ 24 декабря в 16:40 ауд. 509.

* Выложен [https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 конспект] лекций о линейном программировании.

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

* 14 октября лекции не будет! В этот день также не будет семинара в группе 153.

==Лектор==

Н.К. Верещагин 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 дней после дедлайна. Домашнее задание должно быть защищено в течение 5 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.

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

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

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

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

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

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

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

Коллоквиум пройдет 13 декабря. [https://www.dropbox.com/s/du2suujppow3rfm/colloq.pdf?dl=0 Вопросы к коллоквиуму].

Экзамен (письменный) - 22 декабря в 13:40 ауд. 509 (основной поток) и 622 (пилотный), показ работ 24 декабря в 16:40 ауд. 509.

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

'''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''

'''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''

'''[https://docs.google.com/spreadsheets/d/1zFLHjan1qJhu2o0veFnXO-izZra2Di49ImJU6rONEGA/edit#gid=94199443 Оценки за домашние задания (группа 155)]'''

'''[https://www.dropbox.com/s/n4tily98sgy7pk0/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 16 сентября, для защиты 21 октября (для пятничных групп), 19 сентября и 24 октября(для групп по понедельникам) и 20 сентября, 25 октября (для вторничных групп)

'''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайны: 30 сентября и 4 ноября (для пятничных групп), 3 октября и 7 ноября (для групп по понедельникам) и 4 октября и 8 ноября(для вторничных групп)

'''[https://www.dropbox.com/s/ojd7ffp6jq3kuyu/hw3.pdf?dl=0 Домашнее задание №3]''' -- дедлайны: 14 октября и 18 ноября для групп 153,155, 17 октября и 21 ноября для группы 156, 18 октября и 22 ноября для группы 154.
Студенты группы 153 могут сдать домашнее задание семинаристу группы 155 А. Милованову.

'''[https://www.dropbox.com/s/v0e3tepzz3zb2vl/hw4.pdf?dl=0 Домашнее задание №4]''' -- дедлайны: 18 ноября (сдача) и 2 декабря (защита) для групп 153,155, 14 ноября и 28 ноября для группы 156, 15 ноября и 29 ноября для группы 154.

'''[https://www.dropbox.com/s/3p0lpqbc0kmacsw/hw5.pdf?dl=0 Домашнее задание №5]''' дедлайны: 2 декабря (сдача) и 14 декабря (защита) для групп 153, 155, 28 ноября и 10 декабря для группы 156, 29 ноября и 11 декабря для группы 154.

'''[https://www.dropbox.com/s/arpstg9oypen94e/hw6.pdf?dl=0 Домашнее задание №6]''' дедлайны: 9 декабря и 21 декабря для групп 153, 9 декабря и 21 декабря для группы 155, 12 декабря и 17 декабря для группы 156, 16 декабря и 20 декабря для группы 154. Примечание для студентов группы 153: тем, у кого военная кафедра, разрешено сдать ДЗ в понедельник 12 декабря на консультации Ф.Когана или во вторник 13 декабря по электронной почте.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

====Лекция 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 сентября)===
Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.
'''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''

===Семинар 2 (9 сентября)===
Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое
следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы. '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''
'''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''

===Семинар 3 (16 сентября)===
Изучение синтаксических следствий, применение критерия совместности.
'''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''

===Семинар 4 (23 сентября)===
Двойственные задачи.
'''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''

===Семинар 5 (30 сентября)===
Двойственные задачи и игры с нулевой суммой. Применение соотношений
дополняющей нежесткости для поиска оптимального решения двойственной задачи
при известном оптимальном решении прямой.
'''[https://www.dropbox.com/s/qg7350m1voy1bzd/cw5.pdf?dl=0 Задачи пятого семинара]'''

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

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

'''[https://www.dropbox.com/s/7eu2de7gl5uz9ot/cw6-7.pdf?dl=0 Задачи шестого семинара]'''

===14 октября семинара в 153 группе не будет===

===Семинар 7 (21 октября)===
Эквивалентные формулы, тавтологии, выполнимые формулы. Записывание рассуждений формулами.
Приведение к КНФ и ДНФ.

'''[https://www.dropbox.com/s/bnqnq0upwtxwwk4/cw8.pdf?dl=0 Задачи седьмого семинара]'''

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

Составление формул.
Приведение формул к КНФ. Доказательство невыполнимости и тавтологичности
в исчислении резолюций (для набора дизъюнктов и для произвольных формул).
'''[https://www.dropbox.com/s/dv1v29vg1rymo4r/cw9.pdf?dl=0 Задачи]'''

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

Выражение формулами первого порядка утверждений и отношений.
'''[https://www.dropbox.com/s/lmin1nfpemgas2h/cw10.pdf?dl=0 Задачи по логике на ноябрь.]'''

===Семинар 10 (25 ноября)===
Приведение к предварённой нормальной форме. Выяснение общезначимости.
Элементарная эквивалентность и изоморфность.

===Семинар 11 (2 декабря)===
Задачи на выразимость. '''[https://www.dropbox.com/s/7zwricggx1xza8d/cw11.pdf?dl=0 Задачи по логике на декабрь.]'''

===Семинар 12 (9 декабря)===
Задачи на выразимость, изморорфность и аксиоматизацию

===Семинар 13 (16 декабря)===
'''[https://www.dropbox.com/s/n9ezlcijsyxtdp2/cw12.tex?dl=0 Задачи на игры Эренфойхта]'''

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

'''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''

==Консультации ==
153 группа: понедельник с 13-40 до 15 в ком. 623 и с 15:10 до 16-30 в ауд. 432 (Коган),
среда 16:40-18 в каб. 617 и пятница 15:10-16:30 в каб. 617 (Верещагин).

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

Для 155 группы консультации будут проходить по вторникам с 13:40 до 15:00 в 617 или в 623.

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

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

DM 2 2016 2017 - История изменений

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