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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(не показана одна промежуточная версия 2 участников)
Строка 9: Строка 9:
 
===Семинаристы:===  
 
===Семинаристы:===  
 
   
 
   
161 Вялый Михаил Николаевич, vyalyi@gmail.com,  
+
161 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Умаров Рустам, rustam.umarov96@gmail.com
  
162 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Стороженко Андрей Андреевич, storozhenkoaa@yandex.ru
+
162 Козачинский Александр Николаевич, kozlach@mail.ru, +7(909)944 15 08 ассистент Стороженко Андрей Андреевич, storozhenkoaa@yandex.ru
  
 
===Ссылки===  
 
===Ссылки===  
Строка 19: Строка 19:
 
[[ Литература по курсу ДМ-2 | Литература по курсу ДМ-2 ]]
 
[[ Литература по курсу ДМ-2 | Литература по курсу ДМ-2 ]]
  
[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Записки по материалам курса.] Они лучше соответствуют тому, что было на лекциях, чем предварительные записки, которые выкладывались ранее. Как и предыдущий вариант, содержат также дополнительный материал, который не вошел в лекции.
+
[https://www.dropbox.com/s/q1xqbmlniw4u6an/main-ver.pdf?dl=0 Записки по материалам курса.]  
  
[https://www.dropbox.com/s/n9i76cnyr30ww6u/Res-lect.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 Конспект лекций о методе резолюций]
 +
 
 +
===Экзамен===
 +
 
 +
Показ работ, 23 декабря, 16:40, ауд.402
 +
 
 +
'''[https://www.dropbox.com/s/50vwvaovhupq1xr/sol171221pilot.pdf?dl=0 Условия, решения задач. Критерии проверки.]'''
 +
 
 +
'''[https://www.dropbox.com/s/3ty4ef0agb8lu80/exam-results-pilot.xls?dl=0 Результаты экзамена ]''' На одном листе результаты 161 группы, на втором - 162 группы.
 +
 
 +
'''[https://www.dropbox.com/s/t4uamj9l2wv8ann/162.xls?dl=0 Полная таблица оценок (группа 162)]''' Итоговая оценка за курс: лист Итог, колонка AH (название колонки O(итог)).
 +
 
 +
'''[https://www.dropbox.com/s/92zf1qsir9lk5qs/161.xls?dl=0 Полная таблица оценок (группа 161)]''' Итоговая оценка за курс: лист Итог, колонка AH (название колонки O(итог).
 +
 
 +
===Коллоквиум===
 +
 
 +
[[https://www.dropbox.com/s/unpcgt2lzhv34fx/colloq-pilot.pdf?dl=0  Программа коллоквиума.]] Обратите внимание: в теоретические вопросы по логике '''входят''' игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.
 +
 
 +
'''Расписание коллоквиума:'''
 +
 
 +
161 группа: 12 декабря (вторник), начало в 13:40, завершение (предположительно) в 16:30. Место: первая пара ауд. 300, вторая пара ауд. 622.
 +
 
 +
162 группа: 12 декабря (вторник), начало в 15:10, завершение (предположительно) в 18:00. Место: первая пара ауд. 622, вторая пара ауд. 435.
 +
 
 +
 
 +
=== Консультации ===
 +
 
 +
161 группа: М.Вялый по пятницам 15:10-16:40, ком. 617. Возможны изменения! Следите за объявлениями.
 +
 
 +
161 группа: Р. Умаров по понедельникам, 15:10-16:30, ауд. 311.
 +
 
 +
162 группа: по вторникам на первой паре в ауд. 219 (где семинар) (Козачинский)
 +
 
 +
===Материалы занятий===
 +
 
 +
====Домашние задания====
 +
 
 +
'''[https://www.dropbox.com/s/t4uamj9l2wv8ann/162.xls?dl=0 Оценки за домашние задания (группа 162)]'''
 +
 
 +
'''[https://www.dropbox.com/s/92zf1qsir9lk5qs/161.xls?dl=0 Оценки за домашние задания (группа 161)]'''
 +
 
 +
 
 +
'''Внимание:''' домашние задания нужно сдавать преподавателю перед началом семинара. Поэтому сроки сдачи домашних заданий теперь различаются в разных группах.
 +
 
 +
'''[https://www.dropbox.com/s/srnmgp4nfciog87/hw06DM2-pilot.pdf?dl=0 Домашнее задание 6]''' Срок выполнения: 161 группа к 4 декабря; 162 группа к 5 декабря.
 +
'''Обратите внимание:''' на выполнение 6 задания даётся одна неделя, а не две, как обычно.
 +
 
 +
'''[https://www.dropbox.com/s/4iv8m16cagoeum0/hw05DM2-pilot.pdf?dl=0 Домашнее задание 5]''' Срок выполнения: 161 группа к 27 ноября; 162 группа к 28 ноября
 +
 
 +
'''[https://www.dropbox.com/s/rki7za6m6rkf8rh/hw04DM2-pilot.pdf?dl=0 Домашнее задание 4]''' Срок выполнения: 161 группа к 13 ноября; 162 группа к 14 ноября
 +
 
 +
'''[https://www.dropbox.com/s/7szmx2uq3iu5fx0/hw03DM2-pilot.pdf?dl=0 Домашнее задание 3]''' Срок выполнения: 161 группа к 16 октября; 162 группа к 17 октября (на листке написано неверно)
 +
 
 +
'''[https://www.dropbox.com/s/ri97ejxo4zbm7qe/hw02DM2-pilot.pdf?dl=0 Домашнее задание 2]''' Срок выполнения: 161 группа ко 2 октября; 162 группа к 3 октября
 +
 
 +
'''[https://www.dropbox.com/s/ajybn9ybh5soq05/hw01DM2-pilot.pdf?dl=0 Домашнее задание 1]''' Срок выполнения: к 18 сентября.
 +
 
 +
====Лекции  ====
 +
 
 +
'''27 ноября''' Теории и модели. Пример полной теории: плотные линейные порядки без наибольшего и наименьшего элементов. Изоморфизм моделей. Сохранение значений формул при изоморфизме. Элементарная эквивалентность. Игры Эренфойхта.
 +
 
 +
'''20 ноября''' Корректность и полнота для исчисления резолюций с универсальными дизъюнктами. Применение метода резолюций для общих формул первого порядка. Разделение переменных, предварённая нормальная форма, сколемизация, построение универсальных дизъюнктов.
 +
 
 +
'''13 ноября''' Функциональные символы и константы. Правила оценки формулы. Общезначимые и эквивалентные формулы. Примеры. Выполнимость и общезначимость, совместные множества формул. Универсальные дизъюнкты. Исчисление резолюций для универсальных дизъюнктов. Примеры вывода противоречия.
 +
 
 +
'''6 ноября''' Полнота исчисления резолюций для КНФ. Преобразование булевой формулы в КНФ, сохраняющее выполнимость. Формулы первого порядка. Предикаты, кванторы. Модели, сигнатуры. Предикат, выражаемый формулой в сигнатуре из одних предикатных символов.
 +
 
 +
'''30 октября''' Булевы формулы. Тавтологии и выполнимые формулы. КНФ. Исчисление резолюций для КНФ. Корректность исчисления резолюций.
 +
 
 +
'''09 октября''' Выбор направления в вырожденном случае: алгоритм замены базисов. Правило Бленда. Корректность алгоритма замены базисов с правилом Бленда. Конечность итераций симплекс-метода. Поиск начального допустимого решения с помощью вспомогательной задачи ЛП с известным допустимым решением.
 +
 
 +
'''02 октября'''  Введение в симплекс-метод. Итерации, направление улучшения целевой функции. Грани, опорная грань. Улучшение целевой функции вдоль грани. Критерий того, что целевая функция постоянна на опорной грани. Выбор направления итерации, когда целевая функция постоянна на опорной грани: невырожденный случай.
 +
 
 +
'''25 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП: задача о максимальном потоке, двойственная к ней и теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесных стратегий и цены игры.
 +
 
 +
'''18 сентября''' Двойственность. Лемма Фаркаша. Конечно порожденные конусы и полиэдральные конусы - одно и то же. Двойственные задачи в ЛП. Теорема двойственности.
 +
 
 +
'''11 сентября''' Исключение переменной в системе линейных неравенств. Проекция полиэдра - полиэдр. Решение систем линейных неравенств и задачи ЛП методом исключения переменных. Достижимость максимума в задаче ЛП с ограниченной целевой функцией. Политопы. Политоп - это полиэдр. Синтаксические следствия линейных неравенств. Критерий совместности системы линейных неравенств.
 +
 
 +
'''4 сентября''' Примеры задач линейного программирования: задача о составлении раствора,
 +
задача о назначениях, транспортная задача. Полиэдры и задача ЛП. Преобразования задач ЛП и систем неравенств. Канонические виды задач ЛП.
 +
 
 +
==== Семинары ====
 +
 
 +
'''[https://www.dropbox.com/s/eqr5vp3d3qmx37m/cw12DM2-pilot.pdf?dl=0 Задачи к семинару 4 декабря]'''
 +
 
 +
'''[https://www.dropbox.com/s/wort1l3qpptndci/cw11DM2-pilot.pdf?dl=0 Задачи к семинару 27 ноября]'''
 +
 
 +
'''[https://www.dropbox.com/s/01dtkqvz3qoqfcq/cw10DM2-pilot.pdf?dl=0  Задачи к семинару 20 ноября]'''
 +
 
 +
'''[https://www.dropbox.com/s/mv661fpuxx6pkz2/cw09DM2-pilot.pdf?dl=0 Задачи к семинару 13 ноября]'''
 +
 
 +
'''[https://www.dropbox.com/s/0y8hok0znsthcz7/cw08DM2-pilot.pdf?dl=0 Задачи к семинару 6 ноября]'''
 +
 
 +
'''[https://www.dropbox.com/s/8klkeheuapbh7p5/cw07DM2-pilot.pdf?dl=0 Задачи к семинару 30 октября]'''
 +
 
 +
'''[https://www.dropbox.com/s/1o7xh6hmd53rcqn/cw06DM2-pilot.pdf?dl=0 Задачи к семинару 09 октября]'''
 +
 
 +
'''[https://www.dropbox.com/s/dsun5eja0wednkq/cw04DM2-pilot.pdf?dl=0 Задачи к семинарам 25 сентября и 2 октября]'''
 +
 
 +
'''[https://www.dropbox.com/s/016mtobg7dclctr/cw03DM2-pilot.pdf?dl=0 Задачи к семинару 18 сентября]'''
 +
 
 +
'''[https://www.dropbox.com/s/xlm20uvejyanix5/cw02DM2-pilot.pdf?dl=0 Задачи к семинару 11 сентября]'''
 +
 
 +
'''[https://www.dropbox.com/s/54wu0ln45s6c8jb/cw01DM2-pilot.pdf?dl=0 Задачи к семинару 4 сентября]'''

Версия 16:27, 23 декабря 2017

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

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

Лектор:

М.Н. Вялый vyalyi@gmail.com

Семинаристы:

161 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Умаров Рустам, rustam.umarov96@gmail.com

162 Козачинский Александр Николаевич, kozlach@mail.ru, +7(909)944 15 08 ассистент Стороженко Андрей Андреевич, storozhenkoaa@yandex.ru

Ссылки

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

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

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

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

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

Экзамен

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

Условия, решения задач. Критерии проверки.

Результаты экзамена На одном листе результаты 161 группы, на втором - 162 группы.

Полная таблица оценок (группа 162) Итоговая оценка за курс: лист Итог, колонка AH (название колонки O(итог)).

Полная таблица оценок (группа 161) Итоговая оценка за курс: лист Итог, колонка AH (название колонки O(итог).

Коллоквиум

[Программа коллоквиума.] Обратите внимание: в теоретические вопросы по логике входят игры Эренфойхта и метод автоморфизмов для доказательства невыразимости предикатов. Задач на эти темы на коллоквиуме не будет. Однако на экзамене задачи по этим темам вполне могут быть.

Расписание коллоквиума:

161 группа: 12 декабря (вторник), начало в 13:40, завершение (предположительно) в 16:30. Место: первая пара ауд. 300, вторая пара ауд. 622.

162 группа: 12 декабря (вторник), начало в 15:10, завершение (предположительно) в 18:00. Место: первая пара ауд. 622, вторая пара ауд. 435.


Консультации

161 группа: М.Вялый по пятницам 15:10-16:40, ком. 617. Возможны изменения! Следите за объявлениями.

161 группа: Р. Умаров по понедельникам, 15:10-16:30, ауд. 311.

162 группа: по вторникам на первой паре в ауд. 219 (где семинар) (Козачинский)

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

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

Оценки за домашние задания (группа 162)

Оценки за домашние задания (группа 161)


Внимание: домашние задания нужно сдавать преподавателю перед началом семинара. Поэтому сроки сдачи домашних заданий теперь различаются в разных группах.

Домашнее задание 6 Срок выполнения: 161 группа к 4 декабря; 162 группа к 5 декабря. Обратите внимание: на выполнение 6 задания даётся одна неделя, а не две, как обычно.

Домашнее задание 5 Срок выполнения: 161 группа к 27 ноября; 162 группа к 28 ноября

Домашнее задание 4 Срок выполнения: 161 группа к 13 ноября; 162 группа к 14 ноября

Домашнее задание 3 Срок выполнения: 161 группа к 16 октября; 162 группа к 17 октября (на листке написано неверно)

Домашнее задание 2 Срок выполнения: 161 группа ко 2 октября; 162 группа к 3 октября

Домашнее задание 1 Срок выполнения: к 18 сентября.

Лекции

27 ноября Теории и модели. Пример полной теории: плотные линейные порядки без наибольшего и наименьшего элементов. Изоморфизм моделей. Сохранение значений формул при изоморфизме. Элементарная эквивалентность. Игры Эренфойхта.

20 ноября Корректность и полнота для исчисления резолюций с универсальными дизъюнктами. Применение метода резолюций для общих формул первого порядка. Разделение переменных, предварённая нормальная форма, сколемизация, построение универсальных дизъюнктов.

13 ноября Функциональные символы и константы. Правила оценки формулы. Общезначимые и эквивалентные формулы. Примеры. Выполнимость и общезначимость, совместные множества формул. Универсальные дизъюнкты. Исчисление резолюций для универсальных дизъюнктов. Примеры вывода противоречия.

6 ноября Полнота исчисления резолюций для КНФ. Преобразование булевой формулы в КНФ, сохраняющее выполнимость. Формулы первого порядка. Предикаты, кванторы. Модели, сигнатуры. Предикат, выражаемый формулой в сигнатуре из одних предикатных символов.

30 октября Булевы формулы. Тавтологии и выполнимые формулы. КНФ. Исчисление резолюций для КНФ. Корректность исчисления резолюций.

09 октября Выбор направления в вырожденном случае: алгоритм замены базисов. Правило Бленда. Корректность алгоритма замены базисов с правилом Бленда. Конечность итераций симплекс-метода. Поиск начального допустимого решения с помощью вспомогательной задачи ЛП с известным допустимым решением.

02 октября Введение в симплекс-метод. Итерации, направление улучшения целевой функции. Грани, опорная грань. Улучшение целевой функции вдоль грани. Критерий того, что целевая функция постоянна на опорной грани. Выбор направления итерации, когда целевая функция постоянна на опорной грани: невырожденный случай.

25 сентября Соотношения дополняющей нежесткости. Приложения двойственности ЛП: задача о максимальном потоке, двойственная к ней и теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесных стратегий и цены игры.

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

11 сентября Исключение переменной в системе линейных неравенств. Проекция полиэдра - полиэдр. Решение систем линейных неравенств и задачи ЛП методом исключения переменных. Достижимость максимума в задаче ЛП с ограниченной целевой функцией. Политопы. Политоп - это полиэдр. Синтаксические следствия линейных неравенств. Критерий совместности системы линейных неравенств.

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

Семинары

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

Задачи к семинару 27 ноября

Задачи к семинару 20 ноября

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

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

Задачи к семинару 30 октября

Задачи к семинару 09 октября

Задачи к семинарам 25 сентября и 2 октября

Задачи к семинару 18 сентября

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

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