DM2-pilot2018/2019 — различия между версиями
Vyalyi (обсуждение | вклад) |
Vyalyi (обсуждение | вклад) |
||
| (не показано 29 промежуточных версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
= Дискретная математика на 2-ом курсе ПМИ (пилотный поток)= | = Дискретная математика на 2-ом курсе ПМИ (пилотный поток)= | ||
| − | Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября. | + | Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября. Последняя лекция 10 декабря. |
| + | |||
| + | '''17 декабря занятий не будет (ни лекции, ни семинара в 171 группе)''' | ||
| + | |||
| + | Результаты коллоквиума и накопленные оценки можно посмотреть в тех же таблицах, что и результаты проверки домашних заданий. | ||
===Лектор:=== | ===Лектор:=== | ||
| Строка 19: | Строка 23: | ||
[[ Литература по курсу ДМ-2 | Литература по курсу ДМ-2 ]] | [[ Литература по курсу ДМ-2 | Литература по курсу ДМ-2 ]] | ||
| − | [https://www.dropbox.com/s/ | + | [https://www.dropbox.com/s/vp4q6uro9v1fcvk/main-ver.pdf?dl=0 Записки по материалам курса.] |
[https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока. Содержит только то, что рассказывалось или будет рассказано на лекциях основного потока. Зато в этом конспекте изложение по возможности упрощено и улучшено.] | [https://www.dropbox.com/s/bxpbt7eq5oyknut/KonspektyOsnovnojPotok.pdf?dl=0 Конспект лекций о линейном программировании для основного потока. Содержит только то, что рассказывалось или будет рассказано на лекциях основного потока. Зато в этом конспекте изложение по возможности упрощено и улучшено.] | ||
[https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций] | [https://www.dropbox.com/s/uwdsbj5xymnqqbt/res-lect-revised.pdf?dl=0 Конспект лекций о методе резолюций] | ||
| + | |||
| + | ===Экзамен=== | ||
| + | |||
| + | Дата и время экзамена: 21 декабря (пятница), начало 16:40, ауд. 622, 317 | ||
| + | |||
| + | '''Важно:''' основная аудитория для пилотного потока - 317. Приходите туда, кто не поместится, пойдёт в 622. | ||
| + | |||
| + | [https://www.dropbox.com/s/ettojx4erkby68e/sol181221pilot.pdf?dl=0 Решения задач, критерии проверки, правило выставления оценки.] | ||
| + | |||
| + | [https://www.dropbox.com/s/orspx50ul78jtf9/exam-results-pilot.xls?dl=0 Результаты экзамена] (с оценками по задачам). | ||
| + | |||
| + | '''Обратите внимание!''' Время и место показа работ ЕЩЕ РАЗ ИЗМЕНИЛОСЬ! | ||
| + | |||
| + | Показ работ, 25 декабря, 16:40, ауд.402 | ||
| + | |||
| + | ===Коллоквиум=== | ||
| + | |||
| + | Дата и время: 15 декабря, ауд. 622. | ||
| + | |||
| + | 171 группа приглашается к 12:10. | ||
| + | |||
| + | 172 группа приглашается к 13:40. | ||
| + | |||
| + | [[https://www.dropbox.com/s/342jujkz4ec5fnr/colloq-pilot.pdf?dl=0 Программа коллоквиума.]] Обратите внимание: | ||
| + | |||
| + | # В теоретические вопросы по логике '''входят''' игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть. | ||
| + | # На коллоквиуме не разрешается пользоваться '''никакими''' записями - ни в электронной, ни в бумажной форме. | ||
| + | |||
| + | 10 декабря, 9:00, ауд. 205: консультация перед коллоквиумом. | ||
=== Консультации === | === Консультации === | ||
| − | 171 группа: М.Вялый по вторникам 15:10-16:40, ком. | + | 171 группа: М.Вялый по вторникам 15:10-16:40, ком. 617. |
| − | 172 группа: Козачинский по понедельникам | + | 172 группа: Козачинский по понедельникам 12:10-13:30, ком. 617. |
===Материалы занятий=== | ===Материалы занятий=== | ||
| Строка 35: | Строка 68: | ||
====Домашние задания==== | ====Домашние задания==== | ||
| − | '''[https://www.dropbox.com/s/ | + | '''[https://www.dropbox.com/s/p7soc0qvu1g1twk/hw06DM2-pilot.pdf?dl=0 Домашнее задание 6]''' 171 группа - 3 декабря; 172 группа - 7 декабря. |
| − | '''[https://www.dropbox.com/s/ | + | '''[https://www.dropbox.com/s/8067nkp6l8u50tt/hw05DM2-pilot.pdf?dl=0 Домашнее задание 5]''' 171 группа - 26 ноября; 172 группа - 30 ноября, защита до коллоквиума. |
| + | '''[https://www.dropbox.com/s/9wc9wklc5swmd8d/hw04DM2-pilot.pdf?dl=0 Домашнее задание 4]''' 171 группа - 12 ноября; 172 группа - 16 ноября, защита до коллоквиума. | ||
| + | '''[https://www.dropbox.com/s/r6tr70f61qk98nm/hw03DM2-pilot.pdf?dl=0 Домашнее задание 3]''' 171 группа - 15 октября; 172 группа - 19 октября, защита к 3 декабря. | ||
| − | '''[https://www.dropbox.com/s/ | + | '''[https://www.dropbox.com/s/bbtlhaqxykagxz5/hw02DM2-pilot.pdf?dl=0 Домашнее задание 2]''' 171 группа - 1 октября; 172 группа - 5 октября, защита к 26 ноября |
| + | |||
| + | '''[https://www.dropbox.com/s/b8z57369cuwt95i/hw01DM2-pilot.pdf?dl=0 Домашнее задание 1]''' Сроки выполнения: 171 группа - к 17 сентября, 172 группа - к 21 сентября, защита к 12 ноября. | ||
| + | |||
| + | |||
| + | {| class="wikitable" style="text-align:center" | ||
| + | |- | ||
| + | ! [https://docs.google.com/spreadsheets/d/1AanoJxVuqYlH1YKxGIGP6ZFisAIup5J2I1ptKjny98g/edit#gid=0 Оценки (171 группа)] !! [https://www.dropbox.com/s/146l3peu4jmvr96/172_results-n-ekzamen.xls?dl=0 Оценки (172 группа)] | ||
| + | |} | ||
====Лекции ==== | ====Лекции ==== | ||
| + | |||
| + | '''3 декабря''' Выразимость предикатов формулами первого порядка. Доказательства невыразимости: метод авоморфизмов, игры Эренфойхта, элиминация кванторов. Выразимость в арифметике. Лемма о бета-функции Гёделя. | ||
| + | |||
| + | '''26 ноября''' Элементарно эквивалентные модели. Игры Эренфойхта. | ||
| + | |||
| + | '''19 ноября''' Теории и модели. Изоморфизмы моделей, сохранение значения замкнутой формулы при изоморфизме. | ||
| + | |||
| + | '''12 ноября''' Проверка общезначимости формул первого порядка. Исчисление резолюций для универсальных дизъюнктов. Предваренная и сколемовская нормальные формы. | ||
| + | |||
| + | '''29 октября''' Сводимость проверки выполнимости булевых формул к проверке выполнимости КНФ. Формулы первого порядка: определение, семантика. Модели заданной сигнатуры. Общезначимые формулы. | ||
| + | |||
| + | '''15 октября''' Булевы формулы. Тавтологии и выполнимые формулы. КНФ. Исчисление резолюций: корректность и полнота. | ||
| + | |||
| + | '''8 октября''' Симплекс метод. Действия в невырожденном случае. Алгоритм замены базисов в вырожденном случае. Правило Бленда. Корректность алгоритма замены базисов при соблюдении правила Бленда. Сходимость симплекс метода. Поиск начального допустимого решения с помощью вспомогательной задачи ЛП. | ||
| + | |||
| + | '''1 октября''' Введение в симплекс-метод. Грани полиэдров, размерности граней. Грани - множества оптитмальных решений задач ЛП на полиэдре. Общая схема симплекс-метода. Локальное улучшение целевой функции. Критерий оптимальности текущего решения. | ||
'''24 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях. | '''24 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях. | ||
| Строка 56: | Строка 115: | ||
==== Семинары ==== | ==== Семинары ==== | ||
| − | '''[https://www.dropbox.com/s/ionttln4a8d1d0e/cw04DM2-pilot.pdf?dl=0 Задачи | + | '''[https://www.dropbox.com/s/mpyleg4j3gtf42z/cw13DM2-pilot.pdf?dl=0 Задачи к 13 семинару]''' |
| + | |||
| + | '''[https://www.dropbox.com/s/n0l099gocw0k6qi/cw12DM2-pilot.pdf?dl=0 Задачи к 12 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/fdcvxftoy2nctcy/cw11DM2-pilot.pdf?dl=0 Задачи к 11 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/yqxun1lq12trzos/cw10DM2-pilot.pdf?dl=0 Задачи к 10 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/b5tkuh1whi13o7o/cw09DM2-pilot.pdf?dl=0 Задачи к 9 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/9meryr8b636w3pg/cw08DM2-pilot.pdf?dl=0 Задачи к 8 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/zsdykijlyp1suuy/cw07DM2-pilot.pdf?dl=0 Задачи к 7 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/s9agt9yl87bgb14/cw06DM2-pilot.pdf?dl=0 Задачи к 6 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/rf0lzj34plglplo/cw05DM2-pilot.pdf?dl=0 Задачи к 5 семинару]''' | ||
| + | |||
| + | '''[https://www.dropbox.com/s/ionttln4a8d1d0e/cw04DM2-pilot.pdf?dl=0 Задачи к 4 семинару]''' | ||
'''[https://www.dropbox.com/s/comqfj5ezfzri7a/cw03DM2-pilot.pdf?dl=0 Задачи ко третьему семинару]''' | '''[https://www.dropbox.com/s/comqfj5ezfzri7a/cw03DM2-pilot.pdf?dl=0 Задачи ко третьему семинару]''' | ||
Текущая версия на 20:45, 20 декабря 2019
Содержание
Дискретная математика на 2-ом курсе ПМИ (пилотный поток)
Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября. Последняя лекция 10 декабря.
17 декабря занятий не будет (ни лекции, ни семинара в 171 группе)
Результаты коллоквиума и накопленные оценки можно посмотреть в тех же таблицах, что и результаты проверки домашних заданий.
Лектор:
М.Н. Вялый vyalyi@gmail.com
Семинаристы:
171 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Гайдамашко Даниил Олегович, dogaydamashko@edu.hse.ru
172 Козачинский Александр Николаевич, kozlach@mail.ru, группа в телеграме для вопросов, ассистент Ракитин Денис Романович, drrakitin@edu.hse.ru
Ссылки
Информация о курсе ДМ-2 (правила оценивания)
Конспект лекций о методе резолюций
Экзамен
Дата и время экзамена: 21 декабря (пятница), начало 16:40, ауд. 622, 317
Важно: основная аудитория для пилотного потока - 317. Приходите туда, кто не поместится, пойдёт в 622.
Решения задач, критерии проверки, правило выставления оценки.
Результаты экзамена (с оценками по задачам).
Обратите внимание! Время и место показа работ ЕЩЕ РАЗ ИЗМЕНИЛОСЬ!
Показ работ, 25 декабря, 16:40, ауд.402
Коллоквиум
Дата и время: 15 декабря, ауд. 622.
171 группа приглашается к 12:10.
172 группа приглашается к 13:40.
[Программа коллоквиума.] Обратите внимание:
- В теоретические вопросы по логике входят игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
- На коллоквиуме не разрешается пользоваться никакими записями - ни в электронной, ни в бумажной форме.
10 декабря, 9:00, ауд. 205: консультация перед коллоквиумом.
Консультации
171 группа: М.Вялый по вторникам 15:10-16:40, ком. 617.
172 группа: Козачинский по понедельникам 12:10-13:30, ком. 617.
Материалы занятий
Домашние задания
Домашнее задание 6 171 группа - 3 декабря; 172 группа - 7 декабря.
Домашнее задание 5 171 группа - 26 ноября; 172 группа - 30 ноября, защита до коллоквиума.
Домашнее задание 4 171 группа - 12 ноября; 172 группа - 16 ноября, защита до коллоквиума.
Домашнее задание 3 171 группа - 15 октября; 172 группа - 19 октября, защита к 3 декабря.
Домашнее задание 2 171 группа - 1 октября; 172 группа - 5 октября, защита к 26 ноября
Домашнее задание 1 Сроки выполнения: 171 группа - к 17 сентября, 172 группа - к 21 сентября, защита к 12 ноября.
| Оценки (171 группа) | Оценки (172 группа) |
|---|
Лекции
3 декабря Выразимость предикатов формулами первого порядка. Доказательства невыразимости: метод авоморфизмов, игры Эренфойхта, элиминация кванторов. Выразимость в арифметике. Лемма о бета-функции Гёделя.
26 ноября Элементарно эквивалентные модели. Игры Эренфойхта.
19 ноября Теории и модели. Изоморфизмы моделей, сохранение значения замкнутой формулы при изоморфизме.
12 ноября Проверка общезначимости формул первого порядка. Исчисление резолюций для универсальных дизъюнктов. Предваренная и сколемовская нормальные формы.
29 октября Сводимость проверки выполнимости булевых формул к проверке выполнимости КНФ. Формулы первого порядка: определение, семантика. Модели заданной сигнатуры. Общезначимые формулы.
15 октября Булевы формулы. Тавтологии и выполнимые формулы. КНФ. Исчисление резолюций: корректность и полнота.
8 октября Симплекс метод. Действия в невырожденном случае. Алгоритм замены базисов в вырожденном случае. Правило Бленда. Корректность алгоритма замены базисов при соблюдении правила Бленда. Сходимость симплекс метода. Поиск начального допустимого решения с помощью вспомогательной задачи ЛП.
1 октября Введение в симплекс-метод. Грани полиэдров, размерности граней. Грани - множества оптитмальных решений задач ЛП на полиэдре. Общая схема симплекс-метода. Локальное улучшение целевой функции. Критерий оптимальности текущего решения.
24 сентября Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях.
17 сентября Критерий совместности систем линейных неравенств и двойственность. Лемма Фаркаша и ее геометрический смысл. Конечно порожденные и полиэдральные конусы. Двойственная задача ЛП. Теорема двойственности в ЛП.
10 сентября Системы линейных неравенств. Метод исключения переменных Фурье-Моцкина. Геометрические приложения: проекция полиэдра - полиэдр, политоп (выпуклая оболочка конечного числа точек) - полиэдр. Критерий совместности системы линейных неравенств.
3 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о назначениях, транспортная задача. Семантические и синтаксические следствия из систем линейных неравенств. Полиэдры и задача ЛП. Преобразования задач ЛП и систем неравенств. Канонические виды задач ЛП.
