https://wiki.cs.hse.ru/api.php?action=feedcontributions&feedformat=atom&user=%D0%A0%D1%92%D0%A0%C2%BB%D0%A0%C2%B5%D0%A0%D1%94%D0%A1%D0%83%D0%A0%C2%B5%D0%A0%E2%84%96+%D0%A0%D1%9A%D0%A0%D1%91%D0%A0%C2%BB%D0%A0%D1%95%D0%A0%D0%86%D0%A0%C2%B0%D0%A0%D0%85%D0%A0%D1%95%D0%A0%D0%86 2026-09-26T23:28:30Z Вклад MediaWiki 1.43.9 https://wiki.cs.hse.ru/index.php?title=DM_2_2017_2018&diff=25074 2017-10-10T09:55:35Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.<br /> <br /> ==Новости==<br /> * (3 октября) Выложено [https://www.dropbox.com/s/1dkxcvze0u8930l/hw3.pdf?dl=0 Домашнее задание №3]<br /> <br /> * (19 сентября) Выложено [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2]<br /> <br /> * (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.<br /> <br /> * (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 163 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич, yhn1124@gmail.com, t.me/yhn112<br /> <br /> 164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна,<br /> lena97denisova@mail.ru<br /> <br /> 165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Моисеев Андрей Андреевич, andrei.moiseev213@yandex.ru<br /> <br /> 166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Ребенко Ярослав Алексеевич, yarebenko@gmail.com<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному<br /> программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов<br /> соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. <br /> Экзамен состоит из 8 задач с указанием количества баллов за каждую<br /> задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.<br /> <br /> Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. <br /> <br /> Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его <br /> сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ====Правила округления==== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> '''Сроки сдачи ДЗ для 164 и 166 группы:'''<br /> <br /> Первое домашнее задание 19 сентября (защита до 10 октября [для 166 группы до 17 октября]) . <br /> Второе домашнее задание 3 октября (защита до 24 октября). <br /> Третье домашнее задание 17 октября (защита до 7 ноября).<br /> Четвертое домашнее задание 7 ноября (защита до 28 ноября). <br /> Пятое домашнее задание 21 ноября (защита до 12 декабря).<br /> Шестое домашнее задание 5 декабря (защита до 26 декабря).<br /> <br /> '''Сроки сдачи ДЗ для 163 и 165 группы:'''<br /> <br /> Первое домашнее задание 22 сентября (защита до 13 октября). <br /> Второе домашнее задание 6 октября (защита до 27 октября). <br /> Третье домашнее задание 20 октября (защита до 10 ноября).<br /> Четвертое домашнее задание 10 ноября (защита до 1 декабря). <br /> Пятое домашнее задание 24 ноября (защита до 15 декабря).<br /> Шестое домашнее задание 8 декабря (защита до 29 декабря).<br /> <br /> <br /> Коллоквиум пройдет с 11 по 15 декабря. <br /> <br /> Экзамен (письменный) с 21 по 31 декабря.<br /> <br /> ==Домашние задания ==<br /> '''[https://docs.google.com/spreadsheets/d/1nWh4-qMKA8gTQJ3aNhWkeVEwxaOJbSxd4Sek5plUaUg Оценки за домашние задания (группа 163)]'''<br /> <br /> '''[https://www.dropbox.com/s/vi2j0bsa6j4y8fm/164.xls?dl=0 Оценки за домашние задания (группа 164)]'''<br /> <br /> '''[https://www.dropbox.com/s/6cvpur8awoocuku/165.xls?dl=0 Оценки за домашние задания (группа 165)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1IwSAme4B9Of6xg-e-ZilB1mDy7B_PYeSuAJErX4yZKE/edit?usp=sharing Оценки за домашние задание (группа 166)]'''<br /> <br /> '''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для групп 164 и 166).<br /> <br /> [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2] -- дедлайны: для сдачи 3 октября, для защиты 24 октября (для групп 164 и 166).<br /> <br /> [https://www.dropbox.com/s/1dkxcvze0u8930l/hw3.pdf?dl=0 Домашнее задание №3] -- дедлайны: для сдачи 17 октября, для защиты 7 ноября (для групп 164 и 166).<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний (пропозициональной формулы).<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций для пропозициональных формул.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Исчисление резолюций для формул первого порядка.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (5 сентября). ====<br /> Определение задачи линейного программирования. Примеры: задача о составлении раствора,<br /> транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.<br /> <br /> ====Лекция 2 (15 сентября). ====<br /> <br /> Синтаксические следствия систем линейных ограничений. Задача ЛП, двойственная к данной. Принципы двойственности: (1) система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 1&lt;=0 (2) если в прямой задаче целевая функция ограничена, то оптимальные решения прямой и двойственной задач совпадают.<br /> <br /> ====Лекция 3 (19 сентября). ====<br /> <br /> Три специальных вида ЛП и объяснение, почему любая задача ЛП может быть приведена к любому из трех видов.<br /> Доказательство первого принципа двойственности методом исключения переменных: сначала для систем неравенств вида &lt;=, затем для систем, состоящих из неравенств вида &lt;= и равенств. Доказательство второго принципа двойственности методом исключения переменных для задач максимизации и систем ограничений, состоящих из неравенств вида &lt;= и равенств. (Доказательств первого и второго принципа двойственности для систем ограничений, состоящих из неравенств вида &lt;=, &gt;= и равенств, не было.)<br /> <br /> Лемма Фаркаша, объяснение, почему она является переформулировкой первого принципа двойственности для систем уравнений в неотрицательных переменных (систем третьего специального вида). Геометрическое доказательство леммы Фаркаша. Вывод первого принципа двойственности для систем ограничений общего вида (неравенства вида &lt;=, &gt;= и равенств) из леммы Фаркаша.<br /> <br /> ====Лекция 4 (29 сентября). ====<br /> <br /> Геометрическое доказательство второго принципа двойственности с помощью леммы Фаркаша. <br /> <br /> Соотношения дополняющей нежесткости. <br /> <br /> Задача о максимальном потоке, её представление в виде задачи ЛП, разрезы и их пропускные способности, лемма о соотношении потоков и разрезов<br /> <br /> ====Лекция 5 (3 октября). ====<br /> Задача, двойственная к задаче о максимальном потоке, доказательство теоремы Форда-Фалкерсона с помощью принципа двойственности.<br /> <br /> Игры с нулевой суммой, теорема фон Ноймана и её вывод из принципа двойственности. <br /> <br /> <br /> ====Лекция 6 (10 октября). ====<br /> <br /> Полиэдры и их грани. Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> Конструктивное доказательство леммы Фаркаша и завершение описания алгоритма симплекс метода с начальным допустимым решением. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====Лекция 7 (17 октября). ====<br /> Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, дистрибутивности, контрапозиции. КНФ и ДНФ.<br /> <br /> Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности и полноты, опровержение произвольных формул в исчислении резолюций. <br /> <br /> ====Лекция 8 (31 октября). ====<br /> <br /> ====Лекция 9 (7 ноября). ====<br /> <br /> ====Лекция 10 (14 ноября). ====<br /> <br /> ====Лекция 11 (21 ноября). ====<br /> <br /> ====Лекция 12 (28 ноября). ====<br /> <br /> ====Лекция 13 (5 декабря). ====<br /> <br /> == Семинары ==<br /> <br /> === Листки с задачами для семинаров ===<br /> <br /> [https://www.dropbox.com/s/cd7bztnxy7d1gbx/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)]<br /> <br /> [https://www.dropbox.com/s/nd4u7tpe50n3noc/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]<br /> <br /> [https://www.dropbox.com/s/u7fms5ha752o7z2/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]<br /> <br /> [https://www.dropbox.com/s/v83f2101qzdhy18/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]<br /> <br /> [https://www.dropbox.com/s/du2nhvefoh5llim/listok5.pdf?dl=0 Листок 5 (грани полиэдров и симплекс метод)]<br /> <br /> === Проведённые семинары в группе 164 ===<br /> <br /> ====Семинар 1 (5 сентября)====<br /> Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.<br /> <br /> ====Семинар 2 (15 сентября)====<br /> Решение задач линейного программирования методом исключения переменных.<br /> <br /> ====Семинар 3 (19 сентября)====<br /> Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.<br /> <br /> ====Семинар 4 (29 сентября)====<br /> Задачи на применение двойствености<br /> <br /> ====Семинар 5 (3 октября)====<br /> Потоки и разрезы. Игры с нулевой суммой.<br /> <br /> ==Конспекты лекций==<br /> [https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока (содержит только то, что рассказывалось или будет рассказано на лекциях)]<br /> <br /> [https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).]<br /> <br /> [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]<br /> <br /> ==Консультации ==<br /> 164 группа: <br /> вторник с 16:40 до 19:30 в ком. 617 (Верещагин).<br /> <br /> 166 группа:<br /> вторник с 15:00 до 17:00 в ком. 617 (Милованов)<br /> <br /> 163 и 165 группы:<br /> пятница с 16:40 до 18:20 в ком. 501 (Дашков)<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2017_2018&diff=24519 2017-09-26T13:25:30Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.<br /> <br /> ==Новости==<br /> <br /> * (19 сентября) Выложено [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2]<br /> <br /> * (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.<br /> <br /> * (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 163 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич, yhn1124@gmail.com, t.me/yhn112<br /> <br /> 164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна,<br /> lena97denisova@mail.ru<br /> <br /> 165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Моисеев Андрей Андреевич, andrei.moiseev213@yandex.ru<br /> <br /> 166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Ребенко Ярослав Алексеевич, yarebenko@gmail.com<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному<br /> программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов<br /> соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. <br /> Экзамен состоит из 8 задач с указанием количества баллов за каждую<br /> задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.<br /> <br /> Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 1/3 и 2/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. <br /> <br /> Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его <br /> сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ====Правила округления==== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> '''Сроки сдачи ДЗ для 164 и 166 группы:'''<br /> <br /> Первое домашнее задание 19 сентября (защита до 10 октября). <br /> Второе домашнее задание 3 октября (защита до 24 октября). <br /> Третье домашнее задание 17 октября (защита до 7 ноября).<br /> Четвертое домашнее задание 7 ноября (защита до 28 ноября). <br /> Пятое домашнее задание 21 ноября (защита до 12 декабря).<br /> Шестое домашнее задание 5 декабря (защита до 26 декабря).<br /> <br /> '''Сроки сдачи ДЗ для 163 и 165 группы:'''<br /> <br /> Первое домашнее задание 22 сентября (защита до 13 октября). <br /> Второе домашнее задание 6 октября (защита до 27 октября). <br /> Третье домашнее задание 20 октября (защита до 10 ноября).<br /> Четвертое домашнее задание 10 ноября (защита до 1 декабря). <br /> Пятое домашнее задание 24 ноября (защита до 15 декабря).<br /> Шестое домашнее задание 8 декабря (защита до 29 декабря).<br /> <br /> <br /> Коллоквиум пройдет с 11 по 15 декабря. <br /> <br /> Экзамен (письменный) с 21 по 31 декабря.<br /> <br /> ==Домашние задания ==<br /> '''[https://docs.google.com/spreadsheets/d/1nWh4-qMKA8gTQJ3aNhWkeVEwxaOJbSxd4Sek5plUaUg Оценки за домашние задания (группа 163)]'''<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 164)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1IwSAme4B9Of6xg-e-ZilB1mDy7B_PYeSuAJErX4yZKE/edit?usp=sharing Оценки за домашние задание (группа 166)]'''<br /> <br /> '''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для групп 164 и 166).<br /> <br /> [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2] -- дедлайны: для сдачи 3 октября, для защиты 24 октября (для групп 164 и 166).<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний (пропозициональной формулы).<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций для пропозициональных формул.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Исчисление резолюций для формул первого порядка.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (5 сентября). ====<br /> Определение задачи линейного программирования. Примеры: задача о составлении раствора,<br /> транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.<br /> <br /> ====Лекция 2 (15 сентября). ====<br /> <br /> Синтаксические следствия систем линейных ограничений. Задача ЛП, двойственная к данной. Принципы двойственности: (1) система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 1&lt;=0 (2) если в прямой задаче целевая функция ограничена, то оптимальные решения прямой и двойственной задач совпадают.<br /> <br /> ====Лекция 3 (19 сентября). ====<br /> <br /> Три специальных вида ЛП и объяснение, почему любая задача ЛП может быть приведена к любому из трех видов.<br /> Доказательство первого принципа двойственности методом исключения переменных: сначала для систем неравенств вида &lt;=, затем для систем, состоящих из неравенств вида &lt;= и равенств. Доказательство второго принципа двойственности методом исключения переменных для задач максимизации и систем ограничений, состоящих из неравенств вида &lt;= и равенств. (Доказательств первого и второго принципа двойственности для систем ограничений, состоящих из неравенств вида &lt;=, &gt;= и равенств, не было.)<br /> <br /> Лемма Фаркаша, объяснение, почему она является переформулировкой первого принципа двойственности для систем уравнений в неотрицательных переменных (систем третьего специального вида). Геометрическое доказательство леммы Фаркаша. Вывод первого принципа двойственности для систем ограничений общего вида (неравенства вида &lt;=, &gt;= и равенств) из леммы Фаркаша.<br /> <br /> ====Лекция 4 (29 сентября). ====<br /> <br /> Вывод второго принципа двойственности из первого принципа (критерия совместности) для задач первого специального вида. <br /> <br /> Соотношения дополняющей нежесткости. <br /> <br /> Задача о максимальном потоке, её представление в виде задачи ЛП, двойственная задача, доказательство теоремы Форда-Фалкерсона с помощью двойственной задачи.<br /> <br /> ====Лекция 5 (3 октября). ====<br /> <br /> Игры с нулевой суммой, теорема фон Ноймана и её вывод из принципа двойственности. <br /> <br /> Полиэдры и их грани. Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> ====Лекция 6 (10 октября). ====<br /> Конструктивное доказательство леммы Фаркаша и завершение описания алгоритма симплекс метода с начальным допустимым решением. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====Лекция 7 (17 октября). ====<br /> Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, дистрибутивности, контрапозиции. КНФ и ДНФ.<br /> <br /> Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности и полноты, опровержение произвольных формул в исчислении резолюций. <br /> <br /> ====Лекция 8 (31 октября). ====<br /> <br /> ====Лекция 9 (7 ноября). ====<br /> <br /> ====Лекция 10 (14 ноября). ====<br /> <br /> ====Лекция 11 (21 ноября). ====<br /> <br /> ====Лекция 12 (28 ноября). ====<br /> <br /> ====Лекция 13 (5 декабря). ====<br /> <br /> == Семинары ==<br /> <br /> === Листки с задачами для семинаров ===<br /> <br /> [https://www.dropbox.com/s/cd7bztnxy7d1gbx/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)]<br /> <br /> [https://www.dropbox.com/s/nd4u7tpe50n3noc/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]<br /> <br /> [https://www.dropbox.com/s/u7fms5ha752o7z2/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]<br /> <br /> [https://www.dropbox.com/s/v83f2101qzdhy18/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]<br /> <br /> === Проведённые семинары в группе 164 ===<br /> <br /> ====Семинар 1 (5 сентября)====<br /> Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.<br /> <br /> ====Семинар 2 (15 сентября)====<br /> Решение задач линейного программирования методом исключения переменных.<br /> <br /> ====Семинар 3 (19 сентября)====<br /> Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.<br /> <br /> ==Конспекты лекций==<br /> [https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока (содержит только то, что рассказывалось или будет рассказано на лекциях)]<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).]'''<br /> <br /> [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]<br /> <br /> ==Консультации ==<br /> 164 группа: <br /> вторник с 16:40 до 19:30 в ком. 617 (Верещагин).<br /> <br /> 166 группа:<br /> вторник с 15:00 до 17:00 в ком. 617 (Милованов)<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2017_2018&diff=24503 2017-09-25T20:10:49Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.<br /> <br /> ==Новости==<br /> <br /> * (19 сентября) Выложено [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2]<br /> <br /> * (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.<br /> <br /> * (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 163 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич, yhn1124@gmail.com, t.me/yhn112<br /> <br /> 164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна,<br /> lena97denisova@mail.ru<br /> <br /> 165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Моисеев Андрей Андреевич, andrei.moiseev213@yandex.ru<br /> <br /> 166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Ребенко Ярослав Алексеевич, yarebenko@gmail.com<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному<br /> программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов<br /> соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. <br /> Экзамен состоит из 8 задач с указанием количества баллов за каждую<br /> задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.<br /> <br /> Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 1/3 и 2/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. <br /> <br /> Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его <br /> сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ====Правила округления==== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> '''Сроки сдачи ДЗ для 164 и 166 группы:'''<br /> <br /> Первое домашнее задание 19 сентября (защита до 10 октября). <br /> Второе домашнее задание 3 октября (защита до 24 октября). <br /> Третье домашнее задание 17 октября (защита до 7 ноября).<br /> Четвертое домашнее задание 7 ноября (защита до 28 ноября). <br /> Пятое домашнее задание 21 ноября (защита до 12 декабря).<br /> Шестое домашнее задание 5 декабря (защита до 26 декабря).<br /> <br /> '''Сроки сдачи ДЗ для 163 и 165 группы:'''<br /> <br /> Первое домашнее задание 22 сентября (защита до 13 октября). <br /> Второе домашнее задание 6 октября (защита до 27 октября). <br /> Третье домашнее задание 20 октября (защита до 10 ноября).<br /> Четвертое домашнее задание 10 ноября (защита до 1 декабря). <br /> Пятое домашнее задание 24 ноября (защита до 15 декабря).<br /> Шестое домашнее задание 8 декабря (защита до 29 декабря).<br /> <br /> <br /> Коллоквиум пройдет с 11 по 15 декабря. <br /> <br /> Экзамен (письменный) с 21 по 31 декабря.<br /> <br /> ==Домашние задания ==<br /> '''[https://docs.google.com/spreadsheets/d/1nWh4-qMKA8gTQJ3aNhWkeVEwxaOJbSxd4Sek5plUaUg Оценки за домашние задания (группа 163)]'''<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 164)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1IwSAme4B9Of6xg-e-ZilB1mDy7B_PYeSuAJErX4yZKE/edit?usp=sharing Оценки за домашние задание (группа 166)]'''<br /> <br /> '''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для групп 164 и 166).<br /> <br /> [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2] -- дедлайны: для сдачи 3 октября, для защиты 24 октября (для групп 164 и 166).<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний (пропозициональной формулы).<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций для пропозициональных формул.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Исчисление резолюций для формул первого порядка.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (5 сентября). ====<br /> Определение задачи линейного программирования. Примеры: задача о составлении раствора,<br /> транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.<br /> <br /> ====Лекция 2 (15 сентября). ====<br /> <br /> Синтаксические следствия систем линейных ограничений. Задача ЛП, двойственная к данной. Принципы двойственности: (1) система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 1&lt;=0 (2) если в прямой задаче целевая функция ограничена, то оптимальные решения прямой и двойственной задач совпадают.<br /> <br /> ====Лекция 3 (19 сентября). ====<br /> <br /> Три специальных вида ЛП и объяснение, почему любая задача ЛП может быть приведена к любому из трех видов.<br /> Доказательство первого принципа двойственности методом исключения переменных: сначала для систем неравенств вида &lt;=, затем для систем, состоящих из неравенств вида &lt;= и равенств. Доказательство второго принципа двойственности методом исключения переменных для задач максимизации и систем ограничений, состоящих из неравенств вида &lt;= и равенств. (Доказательств первого и второго принципа двойственности для систем ограничений, состоящих из неравенств вида &lt;=, &gt;= и равенств, не было.)<br /> <br /> Лемма Фаркаша, объяснение, почему она является переформулировкой первого принципа двойственности для систем уравнений в неотрицательных переменных (систем третьего специального вида). Геометрическое доказательство леммы Фаркаша. Вывод первого принципа двойственности для систем ограничений общего вида (неравенства вида &lt;=, &gt;= и равенств) из леммы Фаркаша.<br /> <br /> ====Лекция 4 (29 сентября). ====<br /> <br /> Вывод второго принципа двойственности из первого принципа (критерия совместности) для задач первого специального вида. <br /> <br /> Соотношения дополняющей нежесткости. <br /> <br /> Задача о максимальном потоке, её представление в виде задачи ЛП, двойственная задача, доказательство теоремы Форда-Фалкерсона с помощью двойственной задачи.<br /> <br /> ====Лекция 5 (3 октября). ====<br /> <br /> Игры с нулевой суммой, теорема фон Ноймана и её вывод из принципа двойственности. <br /> <br /> Полиэдры и их грани. Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> ====Лекция 6 (10 октября). ====<br /> Конструктивное доказательство леммы Фаркаша и завершение описания алгоритма симплекс метода с начальным допустимым решением. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====Лекция 7 (17 октября). ====<br /> Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, дистрибутивности, контрапозиции. КНФ и ДНФ.<br /> <br /> Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности и полноты, опровержение произвольных формул в исчислении резолюций. <br /> <br /> ====Лекция 8 (31 октября). ====<br /> <br /> ====Лекция 9 (7 ноября). ====<br /> <br /> ====Лекция 10 (14 ноября). ====<br /> <br /> ====Лекция 11 (21 ноября). ====<br /> <br /> ====Лекция 12 (28 ноября). ====<br /> <br /> ====Лекция 13 (5 декабря). ====<br /> <br /> == Семинары ==<br /> <br /> === Листки с задачами для семинаров ===<br /> <br /> [https://www.dropbox.com/s/cd7bztnxy7d1gbx/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)]<br /> <br /> [https://www.dropbox.com/s/nd4u7tpe50n3noc/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]<br /> <br /> [https://www.dropbox.com/s/u7fms5ha752o7z2/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]<br /> <br /> [https://www.dropbox.com/s/v83f2101qzdhy18/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]<br /> <br /> === Проведённые семинары в группе 164 ===<br /> <br /> ====Семинар 1 (5 сентября)====<br /> Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.<br /> <br /> ====Семинар 2 (15 сентября)====<br /> Решение задач линейного программирования методом исключения переменных.<br /> <br /> ====Семинар 3 (19 сентября)====<br /> Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.<br /> <br /> ==Конспекты лекций==<br /> [https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока (содержит только то, что рассказывалось или будет рассказано на лекциях)]<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).]'''<br /> <br /> [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]<br /> <br /> ==Консультации ==<br /> 164 группа: <br /> вторник с 16:40 до 19:30 в ком. 617 (Верещагин).<br /> <br /> 166 группа:<br /> вторник с 16:30 до 17:00 в ком. 617 (Милованов)<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2017_2018&diff=24501 2017-09-25T20:08:35Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.<br /> <br /> ==Новости==<br /> <br /> * (19 сентября) Выложено [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2]<br /> <br /> * (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.<br /> <br /> * (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 163 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич, yhn1124@gmail.com, t.me/yhn112<br /> <br /> 164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна,<br /> lena97denisova@mail.ru<br /> <br /> 165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Моисеев Андрей Андреевич, andrei.moiseev213@yandex.ru<br /> <br /> 166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Ребенко Ярослав Алексеевич, yarebenko@gmail.com<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному<br /> программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов<br /> соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. <br /> Экзамен состоит из 8 задач с указанием количества баллов за каждую<br /> задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.<br /> <br /> Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 1/3 и 2/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. <br /> <br /> Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его <br /> сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ====Правила округления==== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> '''Сроки сдачи ДЗ для 164 и 166 группы:'''<br /> <br /> Первое домашнее задание 19 сентября (защита до 10 октября). <br /> Второе домашнее задание 3 октября (защита до 24 октября). <br /> Третье домашнее задание 17 октября (защита до 7 ноября).<br /> Четвертое домашнее задание 7 ноября (защита до 28 ноября). <br /> Пятое домашнее задание 21 ноября (защита до 12 декабря).<br /> Шестое домашнее задание 5 декабря (защита до 26 декабря).<br /> <br /> '''Сроки сдачи ДЗ для 163 и 165 группы:'''<br /> <br /> Первое домашнее задание 22 сентября (защита до 13 октября). <br /> Второе домашнее задание 6 октября (защита до 27 октября). <br /> Третье домашнее задание 20 октября (защита до 10 ноября).<br /> Четвертое домашнее задание 10 ноября (защита до 1 декабря). <br /> Пятое домашнее задание 24 ноября (защита до 15 декабря).<br /> Шестое домашнее задание 8 декабря (защита до 29 декабря).<br /> <br /> <br /> Коллоквиум пройдет с 11 по 15 декабря. <br /> <br /> Экзамен (письменный) с 21 по 31 декабря.<br /> <br /> ==Домашние задания ==<br /> '''[https://docs.google.com/spreadsheets/d/1nWh4-qMKA8gTQJ3aNhWkeVEwxaOJbSxd4Sek5plUaUg Оценки за домашние задания (группа 163)]'''<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 164)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1IwSAme4B9Of6xg-e-ZilB1mDy7B_PYeSuAJErX4yZKE/edit?usp=sharing Оценки за домашние задание (группа 166)]'''<br /> '''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для групп 164 и 166).<br /> <br /> [https://www.dropbox.com/s/jmqm4vdw0l19oqg/hw2.pdf?dl=0 Домашнее задание №2] -- дедлайны: для сдачи 3 октября, для защиты 24 октября (для групп 164 и 166).<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний (пропозициональной формулы).<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций для пропозициональных формул.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Исчисление резолюций для формул первого порядка.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (5 сентября). ====<br /> Определение задачи линейного программирования. Примеры: задача о составлении раствора,<br /> транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.<br /> <br /> ====Лекция 2 (15 сентября). ====<br /> <br /> Синтаксические следствия систем линейных ограничений. Задача ЛП, двойственная к данной. Принципы двойственности: (1) система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 1&lt;=0 (2) если в прямой задаче целевая функция ограничена, то оптимальные решения прямой и двойственной задач совпадают.<br /> <br /> ====Лекция 3 (19 сентября). ====<br /> <br /> Три специальных вида ЛП и объяснение, почему любая задача ЛП может быть приведена к любому из трех видов.<br /> Доказательство первого принципа двойственности методом исключения переменных: сначала для систем неравенств вида &lt;=, затем для систем, состоящих из неравенств вида &lt;= и равенств. Доказательство второго принципа двойственности методом исключения переменных для задач максимизации и систем ограничений, состоящих из неравенств вида &lt;= и равенств. (Доказательств первого и второго принципа двойственности для систем ограничений, состоящих из неравенств вида &lt;=, &gt;= и равенств, не было.)<br /> <br /> Лемма Фаркаша, объяснение, почему она является переформулировкой первого принципа двойственности для систем уравнений в неотрицательных переменных (систем третьего специального вида). Геометрическое доказательство леммы Фаркаша. Вывод первого принципа двойственности для систем ограничений общего вида (неравенства вида &lt;=, &gt;= и равенств) из леммы Фаркаша.<br /> <br /> ====Лекция 4 (29 сентября). ====<br /> <br /> Вывод второго принципа двойственности из первого принципа (критерия совместности) для задач первого специального вида. <br /> <br /> Соотношения дополняющей нежесткости. <br /> <br /> Задача о максимальном потоке, её представление в виде задачи ЛП, двойственная задача, доказательство теоремы Форда-Фалкерсона с помощью двойственной задачи.<br /> <br /> ====Лекция 5 (3 октября). ====<br /> <br /> Игры с нулевой суммой, теорема фон Ноймана и её вывод из принципа двойственности. <br /> <br /> Полиэдры и их грани. Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> ====Лекция 6 (10 октября). ====<br /> Конструктивное доказательство леммы Фаркаша и завершение описания алгоритма симплекс метода с начальным допустимым решением. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====Лекция 7 (17 октября). ====<br /> Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, дистрибутивности, контрапозиции. КНФ и ДНФ.<br /> <br /> Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности и полноты, опровержение произвольных формул в исчислении резолюций. <br /> <br /> ====Лекция 8 (31 октября). ====<br /> <br /> ====Лекция 9 (7 ноября). ====<br /> <br /> ====Лекция 10 (14 ноября). ====<br /> <br /> ====Лекция 11 (21 ноября). ====<br /> <br /> ====Лекция 12 (28 ноября). ====<br /> <br /> ====Лекция 13 (5 декабря). ====<br /> <br /> == Семинары ==<br /> <br /> === Листки с задачами для семинаров ===<br /> <br /> [https://www.dropbox.com/s/cd7bztnxy7d1gbx/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)]<br /> <br /> [https://www.dropbox.com/s/nd4u7tpe50n3noc/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]<br /> <br /> [https://www.dropbox.com/s/u7fms5ha752o7z2/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]<br /> <br /> [https://www.dropbox.com/s/v83f2101qzdhy18/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]<br /> <br /> === Проведённые семинары в группе 164 ===<br /> <br /> ====Семинар 1 (5 сентября)====<br /> Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.<br /> <br /> ====Семинар 2 (15 сентября)====<br /> Решение задач линейного программирования методом исключения переменных.<br /> <br /> ====Семинар 3 (19 сентября)====<br /> Построение двойственных задач. Доказательство несовместности с помощью вывода заведомо ложного неравенства.<br /> <br /> ==Конспекты лекций==<br /> [https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока (содержит только то, что рассказывалось или будет рассказано на лекциях)]<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Расширенный конспект лекций о линейном программировании (общий для пилотного и основного потока).]'''<br /> <br /> [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]<br /> <br /> ==Консультации ==<br /> 164 группа: <br /> вторник с 16:40 до 19:30 в ком. 617 (Верещагин).<br /> <br /> 166 группа:<br /> вторник с 16:30 до 17:00 в ком. 617 (Милованов)<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2017_2018&diff=23872 2017-09-05T13:20:30Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.<br /> <br /> ==Новости==<br /> <br /> * (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.<br /> <br /> * (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 163, 165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич msdiskin@edu.hse.ru<br /> <br /> 164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна<br /> lena97denisova@mail.ru<br /> <br /> 166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Денисова Елена Алексеевна lena97denisova@mail.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному<br /> программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов<br /> соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. <br /> Экзамен состоит из 8 задач с указанием количества баллов за каждую<br /> задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.<br /> <br /> Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 1/3 и 2/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. <br /> <br /> Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его <br /> сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ====Правила округления==== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки сдачи ДЗ для 164 и 166 группы:<br /> <br /> Первое домашнее задание 19 сентября (защита до 10 октября). <br /> Второе домашнее задание 3 октября (защита до 24 октября). <br /> Третье домашнее задание 17 октября (защита до 7 ноября).<br /> Четвертое домашнее задание 7 ноября (защита до 28 ноября). <br /> Пятое домашнее задание 21 ноября (защита до 12 декабря).<br /> Шестое домашнее задание 5 декабря (защита до 26 декабря).<br /> <br /> Коллоквиум пройдет с 11 по 15 декабря. <br /> <br /> Экзамен (письменный) с 21 по 31 декабря.<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 164)]'''<br /> <br /> '''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для группы 164).<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний (пропозициональной формулы).<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций для пропозициональных формул.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Исчисление резолюций для формул первого порядка.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (5 сентября). ====<br /> Определение задачи линейного программирования. Примеры: задача о составлении раствора,<br /> транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.<br /> <br /> ====Лекция 2 (15 сентября). ====<br /> <br /> Канонические формы задач линейного программирования. Как можно доказать несовместность ЛП и оптимальность решения задачи линейного программирования. Программа, двойственная к данной. Синтаксические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1.<br /> <br /> ====Лекция 3 (19 сентября). ====<br /> <br /> ====Лекция 4 (29 сентября). ====<br /> <br /> ====Лекция 5 (3 октября). ====<br /> <br /> ====Лекция 6 (10 октября). ====<br /> <br /> ====Лекция 7 (17 октября). ====<br /> <br /> ====Лекция 8 (31 октября). ====<br /> <br /> ====Лекция 9 (7 ноября). ====<br /> <br /> ====Лекция 10 (14 ноября). ====<br /> <br /> ====Лекция 11 (21 ноября). ====<br /> <br /> ====Лекция 12 (28 ноября). ====<br /> <br /> ====Лекция 13 (5 декабря). ====<br /> <br /> <br /> == Семинары ==<br /> <br /> === Листки с задачами для семинаров ===<br /> <br /> [https://www.dropbox.com/s/cd7bztnxy7d1gbx/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)]<br /> <br /> [https://www.dropbox.com/s/nd4u7tpe50n3noc/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]<br /> <br /> [https://www.dropbox.com/s/u7fms5ha752o7z2/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]<br /> <br /> [https://www.dropbox.com/s/v83f2101qzdhy18/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]<br /> <br /> === Проведённые семинары в группе 164 ===<br /> <br /> ====Семинар 1 (5 сентября)====<br /> Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.<br /> Решение задач линейного программирования методом исключения переменных.<br /> <br /> ==Конспекты лекций==<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''<br /> <br /> [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]<br /> <br /> ==Консультации ==<br /> 164 группа: <br /> вторник с 16:40 до 19:30 в ком. 623 (Верещагин).<br /> <br /> 166 группа:<br /> вторник с 16:30 до 17:00 в ком. 617 (Милованов)<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2017_2018&diff=23871 2017-09-05T13:20:11Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.<br /> <br /> ==Новости==<br /> <br /> * (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.<br /> <br /> * (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 163, 165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич msdiskin@edu.hse.ru<br /> <br /> 164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна<br /> lena97denisova@mail.ru<br /> <br /> 166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Денисова Елена Алексеевна lena97denisova@mail.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному<br /> программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов<br /> соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. <br /> Экзамен состоит из 8 задач с указанием количества баллов за каждую<br /> задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.<br /> <br /> Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 1/3 и 2/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. <br /> <br /> Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его <br /> сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ====Правила округления==== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки сдачи ДЗ для 164 и 166 группы:<br /> <br /> Первое домашнее задание 19 сентября (защита до 10 октября). <br /> Второе домашнее задание 3 октября (защита до 24 октября). <br /> Третье домашнее задание 17 октября (защита до 7 ноября).<br /> Четвертое домашнее задание 7 ноября (защита до 28 ноября). <br /> Пятое домашнее задание 21 ноября (защита до 12 декабря).<br /> Шестое домашнее задание 5 декабря (защита до 26 декабря).<br /> <br /> Коллоквиум пройдет с 11 по 15 декабря. <br /> <br /> Экзамен (письменный) с 21 по 31 декабря.<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 164)]'''<br /> <br /> '''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для группы 164).<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний (пропозициональной формулы).<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций для пропозициональных формул.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Исчисление резолюций для формул первого порядка.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (5 сентября). ====<br /> Определение задачи линейного программирования. Примеры: задача о составлении раствора,<br /> транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.<br /> <br /> ====Лекция 2 (15 сентября). ====<br /> <br /> Канонические формы задач линейного программирования. Как можно доказать несовместность ЛП и оптимальность решения задачи линейного программирования. Программа, двойственная к данной. Синтаксические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1.<br /> <br /> ====Лекция 3 (19 сентября). ====<br /> <br /> ====Лекция 4 (29 сентября). ====<br /> <br /> ====Лекция 5 (3 октября). ====<br /> <br /> ====Лекция 6 (10 октября). ====<br /> <br /> ====Лекция 7 (17 октября). ====<br /> <br /> ====Лекция 8 (31 октября). ====<br /> <br /> ====Лекция 9 (7 ноября). ====<br /> <br /> ====Лекция 10 (14 ноября). ====<br /> <br /> ====Лекция 11 (21 ноября). ====<br /> <br /> ====Лекция 12 (28 ноября). ====<br /> <br /> ====Лекция 13 (5 декабря). ====<br /> <br /> <br /> == Семинары ==<br /> <br /> === Листки с задачами для семинаров ===<br /> <br /> [https://www.dropbox.com/s/cd7bztnxy7d1gbx/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)]<br /> <br /> [https://www.dropbox.com/s/nd4u7tpe50n3noc/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]<br /> <br /> [https://www.dropbox.com/s/u7fms5ha752o7z2/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]<br /> <br /> [https://www.dropbox.com/s/v83f2101qzdhy18/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]<br /> <br /> === Проведённые семинары в группе 164 ===<br /> <br /> ====Семинар 1 (5 сентября)====<br /> Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.<br /> Решение задач линейного программирования методом исключения переменных.<br /> <br /> ==Конспекты лекций==<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''<br /> <br /> [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]<br /> <br /> ==Консультации ==<br /> 164 группа: <br /> вторник с 16:40 до 19:30 в ком. 623 (Верещагин).<br /> 166 группа:<br /> вторник с 16:30 до 17:00 в ком. 617 (Милованов)<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2017_2018&diff=23868 2017-09-05T12:15:17Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по вторникам в аудитории 622 в 10:30-11:50. Первая лекция 5 сентября.<br /> <br /> ==Новости==<br /> <br /> * (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.<br /> <br /> * (1 сентября) Выложено [https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 163, 165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич msdiskin@edu.hse.ru<br /> <br /> 164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна<br /> lena97denisova@mail.ru<br /> <br /> 166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Денисова Елена Алексеевна lena97denisova@mail.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному<br /> программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов<br /> соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. <br /> Экзамен состоит из 8 задач с указанием количества баллов за каждую<br /> задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.<br /> <br /> Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 1/3 и 2/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2. <br /> <br /> Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его <br /> сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной. <br /> <br /> ====Правила округления==== <br /> <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки сдачи ДЗ для 164 и 166 группы:<br /> <br /> Первое домашнее задание 19 сентября (защита до 10 октября). <br /> Второе домашнее задание 3 октября (защита до 24 октября). <br /> Третье домашнее задание 17 октября (защита до 7 ноября).<br /> Четвертое домашнее задание 7 ноября (защита до 28 ноября). <br /> Пятое домашнее задание 21 ноября (защита до 12 декабря).<br /> Шестое домашнее задание 5 декабря (защита до 26 декабря).<br /> <br /> Коллоквиум пройдет с 11 по 15 декабря. <br /> <br /> Экзамен (письменный) с 21 по 31 декабря.<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 164)]'''<br /> <br /> '''[https://www.dropbox.com/s/wapy36llq2ykdsl/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для группы 164).<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний (пропозициональной формулы).<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций для пропозициональных формул.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Исчисление резолюций для формул первого порядка.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (5 сентября). ====<br /> Определение задачи линейного программирования. Примеры: задача о составлении раствора,<br /> транспортная задача. Решение двумерных задач ЛП графическим методом. Метод исключения переменных: определение совместности, поиск оптимума.<br /> <br /> ====Лекция 2 (15 сентября). ====<br /> <br /> Канонические формы задач линейного программирования. Как можно доказать несовместность ЛП и оптимальность решения задачи линейного программирования. Программа, двойственная к данной. Синтаксические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1.<br /> <br /> ====Лекция 3 (19 сентября). ====<br /> <br /> ====Лекция 4 (29 сентября). ====<br /> <br /> ====Лекция 5 (3 октября). ====<br /> <br /> ====Лекция 6 (10 октября). ====<br /> <br /> ====Лекция 7 (17 октября). ====<br /> <br /> ====Лекция 8 (31 октября). ====<br /> <br /> ====Лекция 9 (7 ноября). ====<br /> <br /> ====Лекция 10 (14 ноября). ====<br /> <br /> ====Лекция 11 (21 ноября). ====<br /> <br /> ====Лекция 12 (28 ноября). ====<br /> <br /> ====Лекция 13 (5 декабря). ====<br /> <br /> <br /> == Семинары ==<br /> <br /> === Листки с задачами для семинаров ===<br /> <br /> [https://www.dropbox.com/s/cd7bztnxy7d1gbx/listok1.pdf?dl=0 Листок 1 (определение задач ЛП и их решение графическим методом)]<br /> <br /> [https://www.dropbox.com/s/nd4u7tpe50n3noc/listok2.pdf?dl=0 Листок 2 (решение ЛП методом исключения переменных)]<br /> <br /> [https://www.dropbox.com/s/u7fms5ha752o7z2/listok3.pdf?dl=0 Листок 3 (двойственность в ЛП)]<br /> <br /> [https://www.dropbox.com/s/v83f2101qzdhy18/listok4.pdf?dl=0 Листок 4 (интересные задачи, сводящиеся к ЛП)]<br /> <br /> === Проведённые семинары в группе 164 ===<br /> <br /> ====Семинар 1 (5 сентября)====<br /> Графическое решение задач линейного программирования с двумя переменными и сводящихся к таким.<br /> Решение задач линейного программирования методом исключения переменных.<br /> <br /> ==Конспекты лекций==<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''<br /> <br /> [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций]<br /> <br /> ==Консультации ==<br /> 164 группа: <br /> вторник с 16:40 до 19:30 в ком. 623 (Верещагин).<br /> <br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=22141 2016-12-09T17:24:58Z

<p>Алексей Милованов: /* Домашние задания */</p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> <br /> * Отодвинут срок сдачи последнего ДЗ для 153 группы. Новый дедлайн сдачи: понедельник 12 декабря в 15:00 (и вторник 13 для тех, у кого военная кафедра - работы нужно послать по электронной почте). Работы надо сдать Федору Когану на его консультации (ауд. 623). Крайний срок защиты не изменен.<br /> <br /> * Коллоквиум состоится в ауд. 509 13 декабря. Получить билет для ответа нужно в начале указанного периода, но при невозможности прийти вовремя можно и в любое время в интервале 9-11 и 13:40-16. Приоритет будет отдан тем, кто пришел в свое время (группа 153 в 15-16:20, группа 154 в 10:30-11:50, группа 155 в 13:40-15, группа 156 в 9-10:20).<br /> <br /> * Выложено [https://www.dropbox.com/s/arpstg9oypen94e/hw6.pdf?dl=0 Домашнее задание №6]<br /> <br /> * Выложены [https://www.dropbox.com/s/du2suujppow3rfm/colloq.pdf?dl=0 вопросы к коллоквиуму].<br /> <br /> * Определена дата коллоквиума: вторник 13 декабря. Группа 153 в 15-16:20, Группа 154 в 10:30-11:50, Группа 155 в 13:40-15, Группа 156 в 9-10:20.<br /> <br /> * Напоминание: консультации Фёдора Когана для группы 153 проходят в понедельник с 13-40 до 16-30 (ауд. 623 и 432). Приходите защищать ДЗ и консультироваться по содержанию лекций!<br /> <br /> * Экзамен (письменный) состоится 22 декабря в 13:40 ауд. 509 (основной поток) и 622 (пилотный), показ работ 24 декабря в 16:40 ауд. 509. <br /> <br /> * Выложен [https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 конспект] лекций о линейном программировании.<br /> <br /> <br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 5 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4.<br /> <br /> ====Правила округления==== <br /> В вычислениях текущие оценки и промежуточные величины не округляются. Результат<br /> вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок.<br /> Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной<br /> оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6<br /> округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3,<br /> 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.<br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 18 ноября (защита до 7 декабря). <br /> Пятое домашнее задание 2 декабря (защита до 14 декабря).<br /> Шестое домашнее задание 9 декабря (защита до 21 декабря).<br /> <br /> Коллоквиум пройдет 13 декабря. [https://www.dropbox.com/s/du2suujppow3rfm/colloq.pdf?dl=0 Вопросы к коллоквиуму].<br /> <br /> Экзамен (письменный) - 22 декабря в 13:40 ауд. 509 (основной поток) и 622 (пилотный), показ работ 24 декабря в 16:40 ауд. 509.<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1zFLHjan1qJhu2o0veFnXO-izZra2Di49ImJU6rONEGA/edit#gid=94199443 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://www.dropbox.com/s/n4tily98sgy7pk0/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 16 сентября, для защиты 21 октября (для пятничных групп), 19 сентября и 24 октября(для групп по понедельникам) и 20 сентября, 25 октября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайны: 30 сентября и 4 ноября (для пятничных групп), 3 октября и 7 ноября (для групп по понедельникам) и 4 октября и 8 ноября(для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/ojd7ffp6jq3kuyu/hw3.pdf?dl=0 Домашнее задание №3]''' -- дедлайны: 14 октября и 18 ноября для групп 153,155, 17 октября и 21 ноября для группы 156, 18 октября и 22 ноября для группы 154.<br /> Студенты группы 153 могут сдать домашнее задание семинаристу группы 155 А. Милованову.<br /> <br /> '''[https://www.dropbox.com/s/v0e3tepzz3zb2vl/hw4.pdf?dl=0 Домашнее задание №4]''' -- дедлайны: 18 ноября (сдача) и 2 декабря (защита) для групп 153,155, 14 ноября и 28 ноября для группы 156, 15 ноября и 29 ноября для группы 154.<br /> <br /> '''[https://www.dropbox.com/s/3p0lpqbc0kmacsw/hw5.pdf?dl=0 Домашнее задание №5]''' дедлайны: 2 декабря (сдача) и 14 декабря (защита) для групп 153, 155, 28 ноября и 10 декабря для группы 156, 29 ноября и 11 декабря для группы 154.<br /> <br /> '''[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 декабря по электронной почте.<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Игры с нулевой суммой, теорема фон Ноймана.<br /> Задача об узелках и задача о минимальной стоимости единичного потока (кратко и без доказательства).<br /> <br /> ====Лекция 6 (7 октября). ====<br /> <br /> Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> Алгоритм для леммы Фаркаша и завершение описания алгоритма симплекс метода. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, дистрибутивности, контрапозиции. (Все это было довольно кратко.)<br /> <br /> Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности и полноты, опровержение произвольных формул в исчислении резолюций.<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> Определение формулы первого порядка в данной сигнатуре. <br /> Запись утверждений формулами первого порядка. Модели (интепретации) сигнатуры. <br /> <br /> Изоморфные и элементарно эквивалентные модели. Теорема об элементарной эквивалентности изоморфных моделей.<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> Выразимые (определимые отношения). Сохранение отношений при автоморфизмах. Доказательства <br /> невыразимости. Общезначимые и выполнимые формулы. Равносильные формулы. Основные равносильности.<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> Нормальные модели. Теории и их модели. Семантическое следование. Теорема Черча об алгоритмической неразрешимости общезначимости (а значит и семантического следования). Совместные и полные теории. Критерий полноты в терминах элементарной эквивалентности. Элементарная теория данной модели. Задача аксиоматизации элементарной теории модели. Аксиоматизация элементарных теорий следующих моделей: упорядоченные множества целых и натуральных чисел (без доказательства полноты).<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> Доказательство элементарной эквивалентности с помощью игры Эренфойхта. <br /> Аксиоматизация элементарной теории упорядоченного множества действительных чисел.<br /> Доказательства полноты аксиоматизаций для упорядоченных множеств натуральных, целых и действительных чисел.<br /> <br /> Не удалось рассказать: Аксиоматизация элементарных теорий поля комплексных чисел и упорядоченного поля действительных чисел. Теорема Эрбрана. Исчисление резолюций для опровержения формул первого порядка.<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы. '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> Изучение синтаксических следствий, применение критерия совместности.<br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> ===Семинар 4 (23 сентября)===<br /> Двойственные задачи.<br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ===Семинар 5 (30 сентября)===<br /> Двойственные задачи и игры с нулевой суммой. Применение соотношений <br /> дополняющей нежесткости для поиска оптимального решения двойственной задачи<br /> при известном оптимальном решении прямой.<br /> '''[https://www.dropbox.com/s/qg7350m1voy1bzd/cw5.pdf?dl=0 Задачи пятого семинара]'''<br /> <br /> ===Семинары 6 (7 октября)===<br /> <br /> Решение с помощью симплекс метода различных задач, в частности, на игры с нулевой<br /> суммой и потоки.<br /> <br /> '''[https://www.dropbox.com/s/7eu2de7gl5uz9ot/cw6-7.pdf?dl=0 Задачи шестого семинара]'''<br /> <br /> ===14 октября семинара в 153 группе не будет===<br /> <br /> ===Семинар 7 (21 октября)===<br /> Эквивалентные формулы, тавтологии, выполнимые формулы. Записывание рассуждений формулами. <br /> Приведение к КНФ и ДНФ.<br /> <br /> '''[https://www.dropbox.com/s/bnqnq0upwtxwwk4/cw8.pdf?dl=0 Задачи седьмого семинара]'''<br /> <br /> ===Семинар 8 (11 ноября)===<br /> <br /> Составление формул.<br /> Приведение формул к КНФ. Доказательство невыполнимости и тавтологичности <br /> в исчислении резолюций (для набора дизъюнктов и для произвольных формул).<br /> '''[https://www.dropbox.com/s/dv1v29vg1rymo4r/cw9.pdf?dl=0 Задачи]'''<br /> <br /> ===Семинар 9 (18 ноября)===<br /> <br /> Выражение формулами первого порядка утверждений и отношений.<br /> '''[https://www.dropbox.com/s/lmin1nfpemgas2h/cw10.pdf?dl=0 Задачи по логике на ноябрь.]'''<br /> <br /> ===Семинар 10 (25 ноября)===<br /> Приведение к предварённой нормальной форме. Выяснение общезначимости.<br /> Элементарная эквивалентность и изоморфность.<br /> <br /> ===Семинар 11 (2 декабря)===<br /> Задачи на выразимость. '''[https://www.dropbox.com/s/7zwricggx1xza8d/cw11.pdf?dl=0 Задачи по логике на декабрь.]'''<br /> <br /> ===Семинар 12 (9 декабря)===<br /> ===Семинар 13 (16 декабря)===<br /> <br /> ==Конспекты лекций==<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''<br /> <br /> ==Консультации ==<br /> 153 группа: понедельник с 13-40 до 15 в ком. 623 и с 15:10 до 16-30 в ауд. 432 (Коган), <br /> среда 16:40-18 в каб. 617 и пятница 15:10-16:30 в каб. 617 (Верещагин).<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313 (также с 10:30 до семинара в 617).<br /> <br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 15:00 в 617 или в 623.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=21912 2016-11-25T22:03:39Z

<p>Алексей Милованов: /* Домашние задания */</p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> * Определена дата коллоквиума: вторник 13 декабря. Группа 153 в 15-16:20, Группа 154 в 10:30-11:50, Группа 155 в 13:40-15, Группа 156 в 9-10:20.<br /> Вопросы к коллоквиуму будут выложены 26 ноября.<br /> <br /> * Напоминание: консультации Фёдора Когана для группы 153 проходят в понедельник с 13-40 до 16-30 (ауд. 623 и 432). Приходите защищать ДЗ и консультироваться по содержанию лекций!<br /> <br /> * Экзамен (письменный) состоится 22 декабря в 13:40 ауд. 509 (основной поток) и 622 (пилотный), показ работ 24 декабря. <br /> <br /> * Выложен [https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 конспект] лекций о линейном программировании.<br /> <br /> <br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 5 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 18 ноября (защита до 7 декабря). <br /> Пятое домашнее задание 2 декабря (защита до 14 декабря).<br /> Шестое домашнее задание 9 декабря (защита до 21 декабря).<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен (письменный) - 22 декабря в 13:40 ауд. 509 (основной поток) и 622 (пилотный), показ работ 24 декабря.<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1zFLHjan1qJhu2o0veFnXO-izZra2Di49ImJU6rONEGA/edit#gid=94199443 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://www.dropbox.com/s/n4tily98sgy7pk0/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 16 сентября, для защиты 21 октября (для пятничных групп), 19 сентября и 24 октября(для групп по понедельникам) и 20 сентября, 25 октября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайны: 30 сентября и 4 ноября (для пятничных групп), 3 октября и 7 ноября (для групп по понедельникам) и 4 октября и 8 ноября(для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/ojd7ffp6jq3kuyu/hw3.pdf?dl=0 Домашнее задание №3]''' -- дедлайны: 14 октября и 18 ноября для групп 153,155, 17 октября и 21 ноября для группы 156, 18 октября и 22 ноября для группы 154.<br /> Студенты группы 153 могут сдать домашнее задание семинаристу группы 155 А. Милованову.<br /> <br /> '''[https://www.dropbox.com/s/v0e3tepzz3zb2vl/hw4.pdf?dl=0 Домашнее задание №4]''' -- дедлайны: 18 ноября (сдача) и 2 декабря (защита) для групп 153,155, 14 ноября и 28 ноября для группы 156, 15 ноября и 29 ноября для группы 154.<br /> <br /> '''[https://www.dropbox.com/s/3p0lpqbc0kmacsw/hw5.pdf?dl=0 Домашнее задание №5]''' дедлайны: 2 декабря (сдача) и 14 декабря (защита) для групп 153, 155, 28 ноября и 10 декабря для группы 156, 29 ноября и 11 декабря для группы 154.<br /> <br /> Домашнее задание 6 дедлайны: 9 декабря и 21 декабря для групп 153,155, 5 декабря и 17 декабря для группы 156, 6 декабря и 18 декабря для группы 154.<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Игры с нулевой суммой, теорема фон Ноймана.<br /> Задача об узелках и задача о минимальной стоимости единичного потока (кратко и без доказательства).<br /> <br /> ====Лекция 6 (7 октября). ====<br /> <br /> Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> Алгоритм для леммы Фаркаша и завершение описания алгоритма симплекс метода. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> Формулы логики высказываний. Тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, дистрибутивности, контрапозиции. (Все это было довольно кратко.)<br /> <br /> Исчисление резолюций: дизъюнкты, правило резолюции, опровержение КНФ в исчислении резолюций, доказательство корректности и полноты, опровержение произвольных формул в исчислении резолюций.<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> Определение формулы первого порядка в данной сигнатуре. <br /> Запись утверждений формулами первого порядка. Модели (интепретации) сигнатуры. <br /> <br /> Изоморфные и элементарно эквивалентные модели. Теорема об элементарной эквивалентности изоморфных моделей.<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> Выразимые (определимые отношения). Сохранение отношений при автоморфизмах. Доказательства <br /> невыразимости. Общезначимые и выполнимые формулы. Равносильные формулы. Основные равносильности.<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы. '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> Изучение синтаксических следствий, применение критерия совместности.<br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> ===Семинар 4 (23 сентября)===<br /> Двойственные задачи.<br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ===Семинар 5 (30 сентября)===<br /> Двойственные задачи и игры с нулевой суммой. Применение соотношений <br /> дополняющей нежесткости для поиска оптимального решения двойственной задачи<br /> при известном оптимальном решении прямой.<br /> '''[https://www.dropbox.com/s/qg7350m1voy1bzd/cw5.pdf?dl=0 Задачи пятого семинара]'''<br /> <br /> ===Семинары 6 (7 октября)===<br /> <br /> Решение с помощью симплекс метода различных задач, в частности, на игры с нулевой<br /> суммой и потоки.<br /> <br /> '''[https://www.dropbox.com/s/7eu2de7gl5uz9ot/cw6-7.pdf?dl=0 Задачи шестого семинара]'''<br /> <br /> ===14 октября семинара в 153 группе не будет===<br /> <br /> ===Семинар 7 (21 октября)===<br /> Эквивалентные формулы, тавтологии, выполнимые формулы. Записывание рассуждений формулами. <br /> Приведение к КНФ и ДНФ.<br /> <br /> '''[https://www.dropbox.com/s/bnqnq0upwtxwwk4/cw8.pdf?dl=0 Задачи седьмого семинара]'''<br /> <br /> ===Семинар 8 (11 ноября)===<br /> <br /> Составление формул.<br /> Приведение формул к КНФ. Доказательство невыполнимости и тавтологичности <br /> в исчислении резолюций (для набора дизъюнктов и для произвольных формул).<br /> '''[https://www.dropbox.com/s/dv1v29vg1rymo4r/cw9.pdf?dl=0 Задачи]'''<br /> <br /> ===Семинар 9 (18 ноября)===<br /> <br /> Выражение формулами первого порядка утверждений и отношений.<br /> '''[https://www.dropbox.com/s/lmin1nfpemgas2h/cw10.pdf?dl=0 Задачи по логике на ноябрь.]'''<br /> <br /> ===Семинар 10 (25 ноября)===<br /> Приведение к предварённой нормальной форме. Выяснение общезначимости.<br /> Элементарная эквивалентность и изоморфность.<br /> <br /> ===Семинар 11 (2 декабря)===<br /> ===Семинар 12 (9 декабря)===<br /> ===Семинар 13 (16 декабря)===<br /> <br /> ==Конспекты лекций==<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''<br /> <br /> ==Консультации ==<br /> 153 группа: понедельник с 13-40 до 15 в ком. 623 и с 15:10 до 16-30 в ауд. 432 (Коган), <br /> среда 16:40-18 в каб. 617 и пятница 15:10-16:30 в каб. 617 (Верещагин).<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313 (также с 10:30 до семинара в 617).<br /> <br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 15:00 в 617 или в 623.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=21510 2016-11-01T09:38:02Z

<p>Алексей Милованов: /* Консультации */</p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> <br /> * Выложен [https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 конспект] лекций о линейном программировании.<br /> <br /> * Назначены консультации Фёдора Когана для группы 153 в понедельник с 13-40 до 16-30 (ауд. 623 и 432).<br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 5 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 18 ноября (защита до 7 декабря). <br /> Пятое домашнее задание 2 декабря (защита до 14 декабря).<br /> Шестое домашнее задание 9 декабря (защита до 21 декабря).<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен (письменный) - 22 декабря, показ работ 24 декабря (даты предварительные).<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1zFLHjan1qJhu2o0veFnXO-izZra2Di49ImJU6rONEGA/edit#gid=94199443 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://www.dropbox.com/s/n4tily98sgy7pk0/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 16 сентября, для защиты 21 октября (для пятничных групп), 19 сентября и 24 октября(для групп по понедельникам) и 20 сентября, 25 октября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайны: 30 сентября и 4 ноября (для пятничных групп), 3 октября и 7 ноября (для групп по понедельникам) и 4 октября и 8 ноября(для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/ojd7ffp6jq3kuyu/hw3.pdf?dl=0 Домашнее задание №3]''' -- дедлайны: 14 октября и 18 ноября для групп 153,155, 17 октября и 21 ноября для группы 156, 18 октября и 22 ноября для группы 154.<br /> Студенты группы 153 могут сдать домашнее задание семинаристу группы 155 А. Милованову.<br /> <br /> '''[https://www.dropbox.com/s/v0e3tepzz3zb2vl/hw4.pdf?dl=0 Домашнее задание №4]''' -- дедлайны: 18 ноября (сдача) и 2 декабря (защита) для групп 153,155, 14 ноября и 28 ноября для группы 156, 15 ноября и 29 ноября для группы 154.<br /> <br /> Домашнее задание 5 дедлайны: 2 декабря (сдача) и 14 декабря (защита) для групп 153,155, 28 ноября и 10 декабря для группы 156, 29 ноября и 11 декабря для группы 154.<br /> <br /> Домашнее задание 6 дедлайны: 9 декабря и 21 декабря для групп 153,155, 5 декабря и 17 декабря для группы 156, 6 декабря и 18 декабря для группы 154.<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Игры с нулевой суммой, теорема фон Ноймана.<br /> Задача об узелках и задача о минимальной стоимости единичного потока (кратко и без доказательства).<br /> <br /> ====Лекция 6 (7 октября). ====<br /> <br /> Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> Алгоритм для леммы Фаркаша и завершение описания алгоритма симплекс метода. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> Формулы логики высказываний. Равносильные формулы, тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, поглощения, дистрибутивности, снятия двойного отрицания, контрапозиции. <br /> ДНФ и КНФ. Приведение формул к КНФ и ДНФ. (Все это можно пропустить, поскольку студенты и так знают с первого курса.<br /> <br /> Метод резолюций<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы. '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> Изучение синтаксических следствий, применение критерия совместности.<br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> ===Семинар 4 (23 сентября)===<br /> Двойственные задачи.<br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ===Семинар 5 (30 сентября)===<br /> Двойственные задачи и игры с нулевой суммой. Применение соотношений <br /> дополняющей нежесткости для поиска оптимального решения двойственной задачи<br /> при известном оптимальном решении прямой.<br /> '''[https://www.dropbox.com/s/qg7350m1voy1bzd/cw5.pdf?dl=0 Задачи пятого семинара]'''<br /> <br /> ===Семинары 6 (7 октября)===<br /> <br /> Решение с помощью симплекс метода различных задач, в частности, на игры с нулевой<br /> суммой и потоки.<br /> <br /> '''[https://www.dropbox.com/s/7eu2de7gl5uz9ot/cw6-7.pdf?dl=0 Задачи шестого семинара]'''<br /> <br /> ===14 октября семинара в 153 группе не будет===<br /> <br /> ===Семинар 7 (21 октября)===<br /> Эквивалентные формулы, тавтологии, выполнимые формулы. Записывание рассуждений формулами. <br /> Приведение к КНФ и ДНФ.<br /> <br /> '''[https://www.dropbox.com/s/bnqnq0upwtxwwk4/cw8.pdf?dl=0 Задачи седьмого семинара]'''<br /> <br /> ===Семинар 8 (11 ноября)===<br /> <br /> Составление формул.<br /> Приведение формул к КНФ. Доказательство невыполнимости и тавтологичности <br /> в исчислении резолюций (для набора дизъюнктов и для произвольных формул).<br /> '''[https://www.dropbox.com/s/dv1v29vg1rymo4r/cw9.pdf?dl=0 Задачи]'''<br /> <br /> ==Конспекты лекций==<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''<br /> <br /> ==Консультации ==<br /> 153 группа: понедельник с 13-40 до 15 в ком. 623 и с 15:10 до 16-30 в ауд. 432 (Коган), <br /> среда 16:40-18 в каб. 617 и пятница 15:10-16:30 в каб. 617 (Верещагин).<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313<br /> <br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 15:00 в 617 или в 623.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=21500 2016-10-31T07:30:05Z

<p>Алексей Милованов: /* Консультации */</p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> <br /> * Выложен [https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 конспект] лекций о линейном программировании.<br /> <br /> * Назначены консультации Фёдора Когана для группы 153 в понедельник с 13-40 до 16-30 (ауд. 623 и 432).<br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 5 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 18 ноября (защита до 7 декабря). <br /> Пятое домашнее задание 2 декабря (защита до 14 декабря).<br /> Шестое домашнее задание 9 декабря (защита до 21 декабря).<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен (письменный) - 22 декабря, показ работ 24 декабря (даты предварительные).<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/muquy5ohykx50hs/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1zFLHjan1qJhu2o0veFnXO-izZra2Di49ImJU6rONEGA/edit#gid=94199443 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://www.dropbox.com/s/n4tily98sgy7pk0/hw1.pdf?dl=0 Домашнее задание №1]''' -- дедлайны: для сдачи 16 сентября, для защиты 21 октября (для пятничных групп), 19 сентября и 24 октября(для групп по понедельникам) и 20 сентября, 25 октября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайны: 30 сентября и 4 ноября (для пятничных групп), 3 октября и 7 ноября (для групп по понедельникам) и 4 октября и 8 ноября(для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/ojd7ffp6jq3kuyu/hw3.pdf?dl=0 Домашнее задание №3]''' -- дедлайны: 14 октября и 18 ноября для групп 153,155, 17 октября и 21 ноября для группы 156, 18 октября и 22 ноября для группы 154.<br /> Студенты группы 153 могут сдать домашнее задание семинаристу группы 155 А. Милованову.<br /> <br /> '''[https://www.dropbox.com/s/v0e3tepzz3zb2vl/hw4.pdf?dl=0 Домашнее задание №4]''' -- дедлайны: 18 ноября (сдача) и 2 декабря (защита) для групп 153,155, 14 ноября и 28 ноября для группы 156, 15 ноября и 29 ноября для группы 154.<br /> <br /> Домашнее задание 5 дедлайны: 2 декабря (сдача) и 14 декабря (защита) для групп 153,155, 28 ноября и 10 декабря для группы 156, 29 ноября и 11 декабря для группы 154.<br /> <br /> Домашнее задание 6 дедлайны: 9 декабря и 21 декабря для групп 153,155, 5 декабря и 17 декабря для группы 156, 6 декабря и 18 декабря для группы 154.<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Игры с нулевой суммой, теорема фон Ноймана.<br /> Задача об узелках и задача о минимальной стоимости единичного потока (кратко и без доказательства).<br /> <br /> ====Лекция 6 (7 октября). ====<br /> <br /> Симплекс метод: общая схема алгоритма с данным начальным допустимым решением, оценка количества шагов.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> Алгоритм для леммы Фаркаша и завершение описания алгоритма симплекс метода. Алгоритм нахождения начального допустимого решения.<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> Формулы логики высказываний. Равносильные формулы, тавтологии, выполнимые формулы. Связь между тавтологиями и выполнимыми формулами. Примеры тавтологий, выражающие важные логические законы: законы де Моргана, поглощения, дистрибутивности, снятия двойного отрицания, контрапозиции. <br /> ДНФ и КНФ. Приведение формул к КНФ и ДНФ. (Все это можно пропустить, поскольку студенты и так знают с первого курса.<br /> <br /> Метод резолюций<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы. '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> Изучение синтаксических следствий, применение критерия совместности.<br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> ===Семинар 4 (23 сентября)===<br /> Двойственные задачи.<br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ===Семинар 5 (30 сентября)===<br /> Двойственные задачи и игры с нулевой суммой. Применение соотношений <br /> дополняющей нежесткости для поиска оптимального решения двойственной задачи<br /> при известном оптимальном решении прямой.<br /> '''[https://www.dropbox.com/s/qg7350m1voy1bzd/cw5.pdf?dl=0 Задачи пятого семинара]'''<br /> <br /> ===Семинары 6 (7 октября)===<br /> <br /> Решение с помощью симплекс метода различных задач, в частности, на игры с нулевой<br /> суммой и потоки.<br /> <br /> '''[https://www.dropbox.com/s/7eu2de7gl5uz9ot/cw6-7.pdf?dl=0 Задачи шестого семинара]'''<br /> <br /> ===14 октября семинара в 153 группе не будет===<br /> <br /> ===Семинар 7 (21 октября)===<br /> Эквивалентные формулы, тавтологии, выполнимые формулы. Записывание рассуждений формулами. <br /> Приведение к КНФ и ДНФ.<br /> <br /> '''[https://www.dropbox.com/s/bnqnq0upwtxwwk4/cw8.pdf?dl=0 Задачи седьмого семинара]'''<br /> <br /> ===Семинар 8 (11 ноября)===<br /> <br /> Составление формул.<br /> Приведение формул к КНФ. Доказательство невыполнимости и тавтологичности <br /> в исчислении резолюций (для набора дизъюнктов и для произвольных формул).<br /> '''[https://www.dropbox.com/s/dv1v29vg1rymo4r/cw9.pdf?dl=0 Задачи]'''<br /> <br /> ==Конспекты лекций==<br /> <br /> '''[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Конспект лекций о линейном программировании.]'''<br /> <br /> ==Консультации ==<br /> 153 группа: понедельник с 13-40 до 15 в ком. 623 и с 15:10 до 16-30 в ауд. 432 (Коган), <br /> среда 16:40-18 в каб. 617 и пятница 15:10-16:30 в каб. 617 (Верещагин).<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313<br /> <br /> Для 155 группы консультации будут проходить по пятницам с 13:40 до 15:00 в 617 или в 623.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=21051 2016-10-07T12:30:13Z

<p>Алексей Милованов: /* Домашние задания */</p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> <br /> * Назначены консультации Фёдора Когана для группы 153 в понедельник с 13-40 до 16-30 (ауд. 623 и 432).<br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 5 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 1 ноября. <br /> Пятое домашнее задание 18 ноября.<br /> Шестое домашнее задание 2 декабря.<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен - 24 декабря (дата предварительная).<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/vpuoicoqwc3nip8/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1zFLHjan1qJhu2o0veFnXO-izZra2Di49ImJU6rONEGA/edit#gid=94199443 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1V0qw93a1JUsb_hTDFajt9FVapM7MeHwr28N4vmXcf_c/edit?usp=sharing Домашнее задание №1]''' -- дедлайн 16 сентября (для пятничных групп), 19 сентября (для групп по понедельникам) и 20 сентября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайн 30 сентября (для пятничных групп), 3 октября (для групп по понедельникам) и 4 октября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/ojd7ffp6jq3kuyu/hw3.pdf?dl=0 Домашнее задание №3]''' -- дедлайн 14 октября для групп 153,155, 17 октября для группы 156, 18 октября для группы 154.<br /> Студенты группы 153 могут сдать домашнее задание семинаристу группы 155 А. Милованову.<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Игры с нулевой суммой, теорема фон Ноймана.<br /> Задача об узелках и задача о минимальной стоимости единичного потока (кратко и без доказательства).<br /> <br /> ====Лекция 6 (7 октября). ====<br /> <br /> Алгоритм для леммы Фаркаша. Симплекс метод.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы. '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> Изучение синтаксических следствий, применение критерия совместности.<br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> ===Семинар 4 (23 сентября)===<br /> Двойственные задачи.<br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ===Семинар 5 (30 сентября)===<br /> Двойственные задачи и игры с нулевой суммой. Применение соотношений <br /> дополняющей нежесткости для поиска оптимального решения двойственной задачи<br /> при известном оптимальном решении прямой.<br /> '''[https://www.dropbox.com/s/qg7350m1voy1bzd/cw5.pdf?dl=0 Задачи пятого семинара]'''<br /> <br /> ===Семинары 6-7 (7 и 14 октября)===<br /> <br /> Решение с помощью симплекс метода различных задач, в частности, на игры с нулевой<br /> суммой и потоки.<br /> <br /> '''[https://www.dropbox.com/s/7eu2de7gl5uz9ot/cw6-7.pdf?dl=0 Задачи шестого и седьмого семинаров]'''<br /> <br /> ===14 октября семинара в 153 группе не будет===<br /> <br /> ==Конспекты лекций==<br /> <br /> Эта черновик конспектов лекций М.Н.Вялого для пилотного потока. Он покрывает весь материал первых шести лекций. https://drive.google.com/file/d/0By-nGAT52Ee3cHo1c1lPNlpsSkE/view?usp=sharing<br /> <br /> ==Консультации ==<br /> 153 группа: понедельник с 13-40 до 15 в ком. 623 и с 15:10 до 16-30 в ауд. 432 (Коган), <br /> среда 16:40-18 в каб. 617 и пятница 15:10-16:30 в каб. 617 (Верещагин).<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313<br /> <br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 14:30<br /> и по пятницам с 11:00 до 11:50 в 617 или в 623.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=20850 2016-09-30T13:52:19Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> <br /> * Назначены консультации Фёдора Когана для группы 153 в понедельник с 13-40 до 16-30 (ауд. 623 и 432).<br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru,ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 5 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> ==Сроки контрольных мероприятий==<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 1 ноября. <br /> Пятое домашнее задание 18 ноября.<br /> Шестое домашнее задание 2 декабря.<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен - 27 декабря (дата предварительная).<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/vpuoicoqwc3nip8/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1V0qw93a1JUsb_hTDFajt9FVapM7MeHwr28N4vmXcf_c/edit#gid=1258935881 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1V0qw93a1JUsb_hTDFajt9FVapM7MeHwr28N4vmXcf_c/edit?usp=sharing Домашнее задание №1]''' -- дедлайн 16 сентября (для пятничных групп), 19 сентября (для групп по понедельникам) и 20 сентября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайн 30 сентября (для пятничных групп), 3 октября (для групп по понедельникам) и 4 октября (для вторничных групп)<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Другие примеры применения принципа двойственности: игры с нулевой суммой,<br /> задача об узелках и задача о кратчайшем пути.<br /> <br /> ====Лекция 6 (7 октября). ====<br /> Симплекс метод.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы. '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> Изучение синтаксических следствий, применение критерия совместности.<br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> ===Семинар 4 (23 сентября)===<br /> Двойственные задачи.<br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ===Семинар 5 (30 сентября)===<br /> Двойственные задачи и игры с нулевой суммой. Применение соотношений <br /> дополняющей нежесткости для поиска оптимального решения двойственной задачи<br /> при известном оптимальном решении прямой.<br /> '''[https://www.dropbox.com/s/qg7350m1voy1bzd/cw5.pdf?dl=0 Задачи пятого семинара]'''<br /> <br /> ===14 октября семинара не будет===<br /> <br /> ==Конспекты лекций==<br /> <br /> Эта черновик конспектов лекций М.Н.Вялого для пилотного потока. Он покрывает весь материал первых шести лекций. https://drive.google.com/file/d/0By-nGAT52Ee3cHo1c1lPNlpsSkE/view?usp=sharing<br /> <br /> ==Консультации ==<br /> 153 группа: понедельник с 13-40 до 15 в ком. 623 и с 15:10 до 16-30 в ауд. 432 (Коган), <br /> среда 16:40-18 в каб. 617 и пятница 15:10-16:30 в каб. 617 (Верещагин).<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313<br /> <br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 14:30<br /> и по пятницам с 11:00 до 11:50 в 617 или в 623.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)<br /> <br /> 7. Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. (Для курса важен раздел про метод резолюций в главе 5.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=20779 2016-09-27T19:46:13Z

<p>Алексей Милованов: /* Домашние задания */</p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru,ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. После проверки домашнее задание должно быть защищено в течение не более месяца. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> ===Сроки контрольных мероприятий===<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 1 ноября. <br /> Пятое домашнее задание 18 ноября.<br /> Шестое домашнее задание 2 декабря.<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен - 27 декабря (дата предварительная).<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/vpuoicoqwc3nip8/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1V0qw93a1JUsb_hTDFajt9FVapM7MeHwr28N4vmXcf_c/edit#gid=1258935881 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1V0qw93a1JUsb_hTDFajt9FVapM7MeHwr28N4vmXcf_c/edit?usp=sharing Домашнее задание №1]''' -- дедлайн 16 сентября (для пятничных групп), 19 сентября (для групп по понедельникам) и 20 сентября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайн 30 сентября (для пятничных групп), 3 октября (для групп по понедельникам) и 4 октября (для вторничных групп)<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Другие примеры применения принципа двойственности: задача об узелках и задача о кратчайшем пути, игры с нулевой суммой.<br /> <br /> ====Лекция 6 (7 октября). ====<br /> Симплекс метод.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> <br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> <br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы.<br /> <br /> '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> <br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> <br /> Изучение синтаксических следствий, применение критерия совместности.<br /> <br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> <br /> <br /> ===Семинар 4 (23 сентября)===<br /> <br /> Двойственные задачи.<br /> <br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ==Конспекты лекций==<br /> <br /> Эта черновик конспектов лекций М.Н.Вялого для пилотного потока. Он покрывает весь материал первых шести лекций. https://drive.google.com/file/d/0By-nGAT52Ee3cHo1c1lPNlpsSkE/view?usp=sharing<br /> <br /> ==Консультации ==<br /> 153 группа: среда 16:40-18 и пятница 15:10-16:30 в каб. 617.<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313<br /> <br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 14:30 в преподавательской<br /> и по пятницам с 11:00 до 11:50 в ауд. 304.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=20778 2016-09-27T19:41:47Z

<p>Алексей Милованов: /* Домашние задания */</p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ (основной поток)=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> ==Новости==<br /> <br /> * Консультации в 153 группе переносятся со вторника 16:40-18 на среду 16:40-18 (каб. 617). Консультации по пятницам в прежнее время (15:10-16:30).<br /> <br /> * 14 октября лекции не будет! В этот день также не будет семинара в группе 153.<br /> <br /> ==Лектор== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ==Семинаристы== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru,ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ==Краткое описание==<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ==Отчётность по курсу и критерии оценки==<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> <br /> Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Сдача домашних заданий после их срока невозможна.<br /> <br /> Каждое ДЗ будут проверено в течение 10 дней после дедлайна. После проверки домашнее задание должно быть защищено в течение не более месяца. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.<br /> <br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> ===Сроки контрольных мероприятий===<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). <br /> <br /> Сроки для 153 группы:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 1 ноября. <br /> Пятое домашнее задание 18 ноября.<br /> Шестое домашнее задание 2 декабря.<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен - 27 декабря (дата предварительная).<br /> <br /> ==Домашние задания ==<br /> <br /> '''[https://www.dropbox.com/s/vpuoicoqwc3nip8/DM%20153.xls?dl=0 Оценки за домашние задания (группа 153)]'''<br /> <br /> '''[https://www.dropbox.com/s/w4tuaawuvvpwis2/DM%20154.xls?dl=0 Оценки за домашние задания (группа 154)]'''<br /> <br /> '''[https://docs.google.com/spreadsheets/d/1V0qw93a1JUsb_hTDFajt9FVapM7MeHwr28N4vmXcf_c/edit#gid=1258935881 Оценки за домашние задания (группа 155)]'''<br /> <br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3NnFiN0IxeWdMb1E/view?usp=sharing Домашнее задание №1]''' -- дедлайн 16 сентября (для пятничных групп), 19 сентября (для групп по понедельникам) и 20 сентября (для вторничных групп)<br /> <br /> '''[https://www.dropbox.com/s/q29zaxmuvcijgs5/hw2.pdf?dl=0 Домашнее задание №2]''' -- дедлайн 30 сентября (для пятничных групп), 3 октября (для групп по понедельникам) и 4 октября (для вторничных групп)<br /> <br /> ==Примерное содержание лекций==<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ====Лекция 2 (9 сентября). ====<br /> Синтаксические и семантические следствия системы неравенств. Критерий совместности: система линейных неравенств несовместна тогда и только тогда, когда из нее синтаксически следует неравенство 0&lt;-1. Лемма Фаркаша и ее вывод из критерия совместности.<br /> <br /> ====Лекция 3 (16 сентября). ====<br /> Проекция полиэдра является полиэдром. Достижение максимума целевой функцией.<br /> Геометрическое доказательство леммы Фаркаша. Вывод критерия совместности из леммы Фаркаша. Принцип двойственности в самой простой форме: неравенство семантически следует из системы неравенств тогда и только тогда, когда оно следует синтаксически (формулировка и объяснение смысла).<br /> <br /> ====Лекция 4 (23 сентября). ====<br /> Доказательство принципа двойственности. <br /> ЛП, двойственная к данной и вторая формулировка принципа двойственности. Задача, двойственная<br /> к задаче о максимальном потоке.<br /> <br /> ====Лекция 5 (30 сентября). ====<br /> Соотношения дополняющей нежесткости. Доказательство теоремы Форда-Фалкерсона о потоках и разрезах.<br /> Другие примеры применения принципа двойственности: задача об узелках и задача о кратчайшем пути, игры с нулевой суммой.<br /> <br /> ====Лекция 6 (7 октября). ====<br /> Симплекс метод.<br /> <br /> ====14 октября лекции не будет (лектор в командировке)====<br /> <br /> ====Лекция 7 (21 октября). ====<br /> <br /> ====28 октября лекции не будет (сессия)====<br /> <br /> ====4 ноября лекции не будет (праздник)====<br /> <br /> ====Лекция 8 (11 ноября). ====<br /> <br /> ====Лекция 9 (18 ноября). ====<br /> <br /> ====Лекция 10 (25 ноября). ====<br /> <br /> ====Лекция 11 (2 декабря). ====<br /> <br /> ====Лекция 12 (9 декабря). ====<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> <br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> '''[https://drive.google.com/file/d/0By-nGAT52Ee3QW1BWG4ycDN6Ymc/view?usp=sharing Задачи первого семинара]'''<br /> <br /> ===Семинар 2 (9 сентября)===<br /> <br /> Графическое изображении полуплоскостей, линий уровня, двумерных полиэдров. Задачи на синтаксическое<br /> следствие, нахождения оптимума в транспортной задаче, несовместность систем л.у. Задача на потоки и разрезы.<br /> <br /> '''[https://www.dropbox.com/s/auozud7pkr052fh/cw2.pdf Задачи второго семинара.]'''<br /> <br /> '''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи ко второму семинару пилотного потока (для тех, кто решил все задачи задания основного потока)]'''<br /> <br /> ===Семинар 3 (16 сентября)===<br /> <br /> Изучение синтаксических следствий, применение критерия совместности.<br /> <br /> '''[https://www.dropbox.com/s/hjtd7umhcvp71o6/cw3.pdf?dl=0 Задачи третьего семинара]'''<br /> <br /> <br /> <br /> ===Семинар 4 (23 сентября)===<br /> <br /> Двойственные задачи.<br /> <br /> '''[https://www.dropbox.com/s/od1w267y1rgbjlu/cw4.pdf?dl=0 Задачи четвертого семинара]'''<br /> <br /> ==Конспекты лекций==<br /> <br /> Эта черновик конспектов лекций М.Н.Вялого для пилотного потока. Он покрывает весь материал первых шести лекций. https://drive.google.com/file/d/0By-nGAT52Ee3cHo1c1lPNlpsSkE/view?usp=sharing<br /> <br /> ==Консультации ==<br /> 153 группа: среда 16:40-18 и пятница 15:10-16:30 в каб. 617.<br /> <br /> Для группы 154 консультации будут проходить по вторникам с 9:00 до 10:20 в ауд. 313<br /> <br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 14:30 в преподавательской<br /> и по пятницам с 11:00 до 11:50 в ауд. 304.<br /> <br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)</div>

Алексей Милованов https://wiki.cs.hse.ru/index.php?title=DM_2_2016_2017&diff=20155 2016-09-05T22:42:02Z

<p>Алексей Милованов: </p> <hr /> <div>= Дискретная математика на 2-ом курсе ПМИ=<br /> <br /> Лекции проходят по пятницам в аудитории 509 в 12:10-13:30. Первая лекция 2 сентября.<br /> <br /> <br /> <br /> ===Лектор:=== <br /> <br /> Н.К. Верещагин nikolay.vereshchagin@gmail.com<br /> <br /> ===Семинаристы:=== <br /> <br /> 153 Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, ассистент Федор Андреевич Коган, taskmage@inbox.ru,<br /> <br /> 154 Козачинский Александр Николаевич, kozlach@mail.ru,ассистент Гущенко-Чеверда Иван, vania1997qwerty@gmail.com,<br /> <br /> 155 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Пособин Глеб Игоревич posobin@gmail.com,<br /> <br /> 156 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Акимова Дина Александровна, akidina14@yandex.ru<br /> <br /> ===Краткое описание===<br /> <br /> Курс состоит из двух частей. В первом модуле будет рассказан о линейном программировании:<br /> что это такое, в каких областях оно применяется, двойственность в линейном программировании и<br /> симплекс метод решения линейных программ. Во втором модуле будет изучаться математическая логика:<br /> формулы логики высказываний и логики предикатов, определение истинности, выразимость средствами<br /> логики предикатов, исчисление резолюций.<br /> <br /> ===Отчётность по курсу и критерии оценки===<br /> <br /> 6 домашних заданий, коллоквиум и экзамен.<br /> Всего будет 6 заданий и каждое оценивается по десятибальной системе (10 означает решение всех задач ДЗ). Оценка за домашние задания равна доле решенных задач, умноженной на 10. <br /> На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.<br /> Оценки за каждое ДЗ будут выставляться примерно через неделю после дедлайна.<br /> Сдача домашних заданий после их срока невозможна.<br /> Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме и<br /> экзамене можно<br /> пользоваться своими рукописными конспектами (не копиями чужих).<br /> <br /> Оценки за коллоквиум и экзамен входят в общую оценку с коэффициентами 0.3, а оценка за домашние задания - с коэффициентом 0.4. <br /> <br /> <br /> <br /> <br /> <br /> ====Контрольные мероприятия и их сроки====<br /> <br /> Эти сроки немного различаются для разных групп (поскольку семинары в разные дни). Сроки для групп, в которых семинары по пятницам следующие:<br /> <br /> Первое домашнее задание 16 сентября.<br /> Второе домашнее задание 30 сентября. <br /> Третье домашнее задание 14 октября.<br /> Четвертое домашнее задание 28 октября.<br /> Пятое домашнее задание 18 ноября.<br /> Шестое домашнее задание 2 декабря.<br /> <br /> Коллоквиум пройдет с 12 по 16 декабря (скорей всего 13 декабря).<br /> <br /> Экзамен - 27 декабря (дата предварительная).<br /> <br /> ===Домашние задания ===<br /> <br /> Домашнее задание №1 https://drive.google.com/file/d/0By-nGAT52Ee3NnFiN0IxeWdMb1E/view?usp=sharing -- дедлайн 16 сентября (для пятничных групп) и 20 сентября (для вторничных групп)<br /> <br /> ===Примерное содержание лекций===<br /> <br /> * Общая задача линейного программирования.<br /> <br /> * Примеры линейных программ: смешивание растворов, транспортная задача, потоки в сетях<br /> <br /> * Метод исключения переменных.<br /> <br /> * Способы докательства оптимальности линейных программ.<br /> <br /> * Общая теория двойственности. Двойственная линейная программа. Лемма Фаркаша и теорема <br /> двойственности<br /> <br /> * Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.<br /> <br /> * Полиэдры и политопы. <br /> <br /> * Симплекс метод.<br /> <br /> * Определение формулы логики высказываний.<br /> <br /> * Тавтологии, выполнимые, общезначимые и равносильные формулы.<br /> <br /> * Исчисление резолюций.<br /> <br /> * Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.<br /> <br /> * Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.<br /> <br /> * Логическое следование и аксиоматические теории.<br /> <br /> <br /> ==Прочитанные лекции==<br /> <br /> ====Лекция 1 (2 сентября). ====<br /> <br /> Определение вид задачи линейного программирования. Пример: задача о составлении раствора,<br /> задача о потоке в сети, транспортная задача. Представление произвольной линейной программы в виде <br /> системы равенств на неотрицательные переменные. Как доказывать оптимальность решения<br /> задачи линейного программирования. Общее представление о двойственности.<br /> <br /> ==Проведённые семинары (153 группа) ==<br /> <br /> ===Семинар 1 (2 сентября)===<br /> <br /> Графическое решение задач линейного программирования с двумя переменными и сводящиеся к таким.<br /> <br /> ==Консультации ==<br /> Для 155 группы консультации будут проходить по вторникам с 13:40 до 14:30 в преподавательской<br /> и по пятницам с 11:00 до 11:50 в ауд. 304.<br /> ==Рекомендуемая литература ==<br /> <br /> 1. Alexander Schrijver. Theory of linear and integer programming. John Wiley and Sons. 1998 <br /> <br /> 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 446 с.<br /> <br /> 3. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012. (Для курса будут наиболее важны главы 1, 3 и 4. Глава 1 содержит материал, который практически полностью входил в программу курса &quot;Дискретная математика -1&quot;. Материал главы 4 в курсе будет затронут очень незначительно.)<br /> <br /> 5. А. Схрейвер. Теория линейного и целочисленного программирования. М.: Мир, 1991. Тт.1-2. (Классический учебник. Для курса наиболее важна глава 7 тома 1, а также (частично) гл. 8 и 11.)<br /> <br /> 6. Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015. (Современный учебник по комбинаторной оптимизации. Включает главы с описанием линейного программирования и алгоритмов для задач линейного программирования.)</div>

Алексей Милованов