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

2019-12-20T17:45:37Z

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

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

= Дискретная математика на 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, '''[https://t.me/joinchat/GQufoAxIyP9j-KerqpkDgg группа в телеграме для вопросов]''', ассистент Ракитин Денис Романович, drrakitin@edu.hse.ru

===Ссылки===

[[ Информация о курсе ДМ-2 (правила оценивания) | Информация о курсе ДМ-2 (правила оценивания) ]]

[[ Литература по курсу ДМ-2 | Литература по курсу ДМ-2 ]]

[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/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, ком. 617.

172 группа: Козачинский по понедельникам 12:10-13:30, ком. 617.

===Материалы занятий===

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

'''[https://www.dropbox.com/s/p7soc0qvu1g1twk/hw06DM2-pilot.pdf?dl=0 Домашнее задание 6]''' 171 группа - 3 декабря; 172 группа - 7 декабря.

'''[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/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 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях.

'''17 сентября''' Критерий совместности систем линейных неравенств и двойственность. Лемма Фаркаша и ее геометрический смысл. Конечно порожденные и полиэдральные конусы. Двойственная задача ЛП. Теорема двойственности в ЛП.

'''10 сентября''' Системы линейных неравенств. Метод исключения переменных Фурье-Моцкина. Геометрические приложения: проекция полиэдра - полиэдр, политоп (выпуклая оболочка конечного числа точек) - полиэдр. Критерий совместности системы линейных неравенств.

'''3 сентября''' Примеры задач линейного программирования: задача о составлении раствора,
задача о назначениях, транспортная задача. Семантические и синтаксические следствия из систем линейных неравенств. Полиэдры и задача ЛП. Преобразования задач ЛП и систем неравенств. Канонические виды задач ЛП.

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

'''[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/tgrhegllheirq9z/cw02DM2-pilot.pdf?dl=0 Задачи ко второму семинару]'''

'''[https://www.dropbox.com/s/i5rrcu7gojjwazb/cw01DM2-pilot.pdf?dl=0 Задачи к первому семинару]'''

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

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