DM2-pilot2018/2019 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия 3 участников)
Строка 1: Строка 1:
 
= Дискретная математика на 2-ом курсе ПМИ (пилотный поток)=
 
= Дискретная математика на 2-ом курсе ПМИ (пилотный поток)=
  
−
Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября.
+
Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября. Последняя лекция 10 декабря.
 +
 
 +
'''17 декабря занятий не будет (ни лекции, ни семинара в 171 группе)'''
 +
 
 +
Результаты коллоквиума и накопленные оценки можно посмотреть в тех же таблицах, что и результаты проверки домашних заданий.
  
 
===Лектор:===  
 
===Лектор:===  
Строка 11: Строка 15:
 
171 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Гайдамашко Даниил Олегович, dogaydamashko@edu.hse.ru
 
171 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Гайдамашко Даниил Олегович, dogaydamashko@edu.hse.ru
  
−
172 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Ракитин Денис Романович, drrakitin@edu.hse.ru
+
172 Козачинский Александр Николаевич, kozlach@mail.ru, '''[https://t.me/joinchat/GQufoAxIyP9j-KerqpkDgg группа в телеграме для вопросов]''', ассистент Ракитин Денис Романович, drrakitin@edu.hse.ru
  
 
===Ссылки===  
 
===Ссылки===  
Строка 19: Строка 23:
 
[[ Литература по курсу ДМ-2 | Литература по курсу ДМ-2 ]]
 
[[ Литература по курсу ДМ-2 | Литература по курсу ДМ-2 ]]
  
−
[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Записки по материалам курса.]  
+
[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, ком. 219. Первая консультация 11 сентября.
+
171 группа: М.Вялый по вторникам 15:10-16:40, ком. 617.
  
−
172 группа: Козачинский (предварительно) по понедельникам 13:40-15:00, ком. 617.
+
172 группа: Козачинский по понедельникам 12:10-13:30, ком. 617.
  
 
===Материалы занятий===  
 
===Материалы занятий===  
Строка 35: Строка 68:
 
====Домашние задания====
 
====Домашние задания====
  
−
'''[https://www.dropbox.com/s/b8z57369cuwt95i/hw01DM2-pilot.pdf?dl=0 Домашнее задание 1]''' Сроки выполнения: 171 группа - к 17 сентября, 172 группа - к 21 сентября.
+
'''[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 сентября''' Примеры задач линейного программирования: задача о составлении раствора,
 
'''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 Задачи к первому семинару]'''
 
'''[https://www.dropbox.com/s/i5rrcu7gojjwazb/cw01DM2-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 (правила оценивания)

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

Записки по материалам курса.

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

Конспект лекций о методе резолюций

Экзамен

Дата и время экзамена: 21 декабря (пятница), начало 16:40, ауд. 622, 317

Важно: основная аудитория для пилотного потока - 317. Приходите туда, кто не поместится, пойдёт в 622.

Решения задач, критерии проверки, правило выставления оценки.

Результаты экзамена (с оценками по задачам).

Обратите внимание! Время и место показа работ ЕЩЕ РАЗ ИЗМЕНИЛОСЬ!

Показ работ, 25 декабря, 16:40, ауд.402

Коллоквиум

Дата и время: 15 декабря, ауд. 622.

171 группа приглашается к 12:10.

172 группа приглашается к 13:40.

[Программа коллоквиума.] Обратите внимание:

  1. В теоретические вопросы по логике входят игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
  2. На коллоквиуме не разрешается пользоваться никакими записями - ни в электронной, ни в бумажной форме.

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 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о назначениях, транспортная задача. Семантические и синтаксические следствия из систем линейных неравенств. Полиэдры и задача ЛП. Преобразования задач ЛП и систем неравенств. Канонические виды задач ЛП.

Семинары

Задачи к 13 семинару

Задачи к 12 семинару

Задачи к 11 семинару

Задачи к 10 семинару

Задачи к 9 семинару

Задачи к 8 семинару

Задачи к 7 семинару

Задачи к 6 семинару

Задачи к 5 семинару

Задачи к 4 семинару

Задачи ко третьему семинару

Задачи ко второму семинару

Задачи к первому семинару

Источник — «http://wiki.cs.hse.ru/index.php?title=DM2-pilot2018/2019&oldid=37551»