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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 43: Строка 43:
 
#  В теоретические вопросы по логике '''входят''' игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
 
#  В теоретические вопросы по логике '''входят''' игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
 
# На коллоквиуме не разрешается пользоваться '''никакими''' записями - ни в электронной, ни в бумажной форме.
 
# На коллоквиуме не разрешается пользоваться '''никакими''' записями - ни в электронной, ни в бумажной форме.
 +
 +
10 декабря, 9:00, ауд. 205: консультация перед коллоквиумом.
  
 
=== Консультации ===
 
=== Консультации ===

Версия 20:48, 3 декабря 2018

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

Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября.

Лектор:

М.Н. Вялый 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

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

Коллоквиум

Дата и время: 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 семинару

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

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

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