Дискретная математика 2 2016/2017 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м
(не показано 14 промежуточных версии этого же участника)
Строка 2: Строка 2:
  
 
Лекции проходят по понедельникам в аудитории 205 в 10:30-11:50. Первая лекция 5 сентября.
 
Лекции проходят по понедельникам в аудитории 205 в 10:30-11:50. Первая лекция 5 сентября.
 +
 +
'''Объявление''' 19 декабря занятий не будет. Курс закончен. Остался только экзамен 22 декабря (см. ниже более подробную информацию).
  
 
===Лектор:===  
 
===Лектор:===  
Строка 15: Строка 17:
 
===Коллоквиум===
 
===Коллоквиум===
  
[https://dl.dropboxusercontent.com/u/33029521/colloq-pilot.pdf Программа коллоквиума.]
+
Коллоквиум будет 16 декабря, 311 ауд. Начало для 151 группы 12:10, для 152 группы 13:40.
 +
 
 +
12 декабря, 10:30, будет консультация перед коллоквиумом. Предварительно, в ауд. 205 (там же, где и лекции). С аудиторией возможны изменения, следите за информацией!
 +
 
 +
[https://www.dropbox.com/s/ziw491t1m939x8x/colloq-pilot.pdf?dl=0 Программа коллоквиума.]
 +
 
 +
'''Важное уточнение:''' на коллоквиуме при подготовке ответа не разрешается пользоваться никакими записями.
 +
 
 +
 
 +
===Экзамен (письменный)===
 +
 
 +
состоится 22 декабря в 13:40 ауд. 622, показ работ 24 декабря.
 +
 
 +
На экзамене разрешается пользоваться письменными источниками и не разрешается пользоваться электронными приборами.
 +
 
 +
[https://www.dropbox.com/s/nowtdj7agri2cw8/exam161222_pilot.pdf?dl=0 Задачи экзамена 22.12.2016]
 +
 
 +
[https://www.dropbox.com/s/j279gfhi1pg3g8q/sol161222pilot.pdf?dl=0 Решения задач экзамена 22.12.2016]
 +
 
 +
[https://www.dropbox.com/s/84ny95hstwmx5q0/exam-pilot-170118.pdf?dl=0 Задачи переэкзаменовки 18.01.2017]
 +
 
 +
[https://www.dropbox.com/s/2n5ann0qoo4c855/sol-pilot-170118.pdf?dl=0 Решения задач переэкзаменовки 18.01.2017]
 +
 
 +
[https://www.dropbox.com/s/l4rjbb1slpsgx3v/exam-pilot-170124.pdf?dl=0 Задачи переэкзаменовки 24.01.2017]
 +
 
 +
[https://www.dropbox.com/s/oyo94r994gzy6je/sol-pilot-170124.pdf?dl=0 Решения задач переэкзаменовки 24.01.2017]  
  
 
===Ссылки===  
 
===Ссылки===  
Строка 25: Строка 52:
 
[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://dl.dropboxusercontent.com/u/33029521/Res-lect.pdf Записки про метод резолюций.]
+
  
 
===Материалы занятий===  
 
===Материалы занятий===  
  
 
====Консультации М.Н.Вялого====
 
====Консультации М.Н.Вялого====
 +
 +
'''6 декабря''' Крайний срок защиты домашних заданий 3-4 в группе 152. 15:10-16:30. Встречаемся возле 617 ауд. (Можно попробовать найти меня после лекции Макарычева (заканчивается в 18:00), которая будет в 509 ауд.)
  
 
'''29 ноября''' Начало 15:10. Встречаемся возле 617 ауд.  
 
'''29 ноября''' Начало 15:10. Встречаемся возле 617 ауд.  
Строка 46: Строка 74:
 
====Домашние задания====
 
====Домашние задания====
  
'''[https://dl.dropboxusercontent.com/u/33029521/hw06DM2-pilot.pdf Домашнее задание 6]''' Срок выполнения: к 5 декабря. '''Обратите внимание!''' Срок выполнения этого домашнего задания '''одна неделя''', а не две!
 
  
'''[https://dl.dropboxusercontent.com/u/33029521/hw05DM2-pilot.pdf Домашнее задание 5]''' Срок выполнения: к 28 ноября.
+
'''[https://www.dropbox.com/s/462mhg9vmky2srj/hw06DM2-pilot.pdf?dl=0 Домашнее задание 6]''' Срок выполнения: к 5 декабря. '''Обратите внимание!''' Срок выполнения этого домашнего задания '''одна неделя''', а не две!
  
'''[https://dl.dropboxusercontent.com/u/33029521/hw04DM2-pilot.pdf Домашнее задание 4]''' Срок выполнения: к 14 ноября.
 
  
'''[https://dl.dropboxusercontent.com/u/33029521/hw03DM2-pilot.pdf Домашнее задание 3]''' Срок выполнения: к 17 октября. <big>'''(по многочисленным просьбам) Определение невырожденного полиэдра:'''</big> Полиэдр в n-мерном пространстве называется ''невырожденным'', если все минимальные грани - точки (вершины), и в каждой вершине обращается в равенство ровно n ограничений, задающих полиэдр (каждое равенство в системе ограничений считается  один раз).  
+
'''[https://www.dropbox.com/s/nt9kali0ok23ctw/hw05DM2-pilot.pdf?dl=0 Домашнее задание 5]''' Срок выполнения: к 28 ноября.
  
'''[https://dl.dropboxusercontent.com/u/33029521/hw02DM2-pilot.pdf Домашнее задание 2]''' Срок выполнения: к 3 октября.
+
'''[https://www.dropbox.com/s/es90rfooblegwqv/hw04DM2-pilot.pdf?dl=0 Домашнее задание 4]''' Срок выполнения: к 14 ноября.
  
'''[https://dl.dropboxusercontent.com/u/33029521/hw01DM2-pilot.pdf Домашнее задание 1]''' Срок выполнения: к 19 сентября.
+
'''[https://www.dropbox.com/s/jye28z475kdx4q4/hw03DM2-pilot.pdf?dl=0 Домашнее задание 3]''' Срок выполнения: к 17 октября. <big>'''(по многочисленным просьбам) Определение невырожденного полиэдра:'''</big> Полиэдр в n-мерном пространстве называется ''невырожденным'', если все минимальные грани - точки (вершины), и в каждой вершине обращается в равенство ровно n ограничений, задающих полиэдр (каждое равенство в системе ограничений считается  один раз).
 +
 
 +
'''[https://www.dropbox.com/s/xb9lkzzvkduy33i/hw02DM2-pilot.pdf?dl=0 Домашнее задание 2]''' Срок выполнения: к 3 октября.
 +
 
 +
'''[https://www.dropbox.com/s/4hskvd7e4g4vqqn/hw01DM2-pilot.pdf?dl=0 Домашнее задание 1]''' Срок выполнения: к 19 сентября.
  
 
====Лекции  ====
 
====Лекции  ====
 +
 +
'''5 декабря''' Элементарная эквивалентность моделей. Изоморфные модели. Игры Эренфойхта.
  
 
'''28 ноября''' Доказательства невыразимости предикатов с помощью автоморфизмов. Элиминация кванторов. Приложения к доказательствам невыразимости.
 
'''28 ноября''' Доказательства невыразимости предикатов с помощью автоморфизмов. Элиминация кванторов. Приложения к доказательствам невыразимости.
Строка 80: Строка 112:
 
'''12 сентября''' Метод исключения переменных для систем линейных неравенств. Проекции полиэдров и достижимость максимума в задача ЛП. Синтаксическиее и семантические следствия. Критерий совместности систем линейных неравенств. Лемма Фаркаша и ее геометрический смысл.
 
'''12 сентября''' Метод исключения переменных для систем линейных неравенств. Проекции полиэдров и достижимость максимума в задача ЛП. Синтаксическиее и семантические следствия. Критерий совместности систем линейных неравенств. Лемма Фаркаша и ее геометрический смысл.
  
'''[https://dl.dropboxusercontent.com/u/33029521/ToLect1.pdf 5 сентября]''' Примеры задач линейного программирования: задача о составлении раствора,
+
'''[https://www.dropbox.com/s/y2brdob6xe8wwv8/ToLect1.pdf?dl=0 5 сентября]''' Примеры задач линейного программирования: задача о составлении раствора,
 
задача о потоке в сети, транспортная задача. Виды ЛП задач: общий, только с неравенствами, равенства на неотрицательные переменные. Дробно-линейное программирование и сводимость к ЛП.
 
задача о потоке в сети, транспортная задача. Виды ЛП задач: общий, только с неравенствами, равенства на неотрицательные переменные. Дробно-линейное программирование и сводимость к ЛП.
  
 
==== Семинары ====
 
==== Семинары ====
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw11DM2-pilot.pdf Задачи к семинару 28 ноября]'''
+
'''[https://www.dropbox.com/s/iq6o9chaoxp2fov/cw12DM2-pilot.pdf?dl=0 Задачи к семинару 5 декабря]'''
 +
 
 +
'''[https://www.dropbox.com/s/ofygpumnx5ssy42/cw11DM2-pilot.pdf?dl=0 Задачи к семинару 28 ноября]'''
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw10DM2-pilot.pdf Задачи к семинару 21 ноября]''' Задача 3 будет разбираться в следующий раз. Очень рекомендуется попробовать ее решить к следующему занятию на основе тех идей, которые обсуждались в этот раз.
+
'''[https://www.dropbox.com/s/co8yzyj1udfejq4/cw10DM2-pilot.pdf?dl=0 Задачи к семинару 21 ноября]''' Задача 3 будет разбираться в следующий раз. Очень рекомендуется попробовать ее решить к следующему занятию на основе тех идей, которые обсуждались в этот раз.
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw09DM2-pilot.pdf Задачи к семинару 14 ноября]''' Часть задач будет разобрана на следующем семинаре.
+
'''[https://www.dropbox.com/s/oqnovkrrek8k7gw/cw09DM2-pilot.pdf?dl=0 Задачи к семинару 14 ноября]''' Часть задач будет разобрана на следующем семинаре.
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw08DM2-pilot.pdf Задачи к семинару 7 ноября]''' Задачи 5 и 6 переносятся на следующий раз.
+
'''[https://www.dropbox.com/s/9lmbg0dd30pjjlm/cw08DM2-pilot.pdf?dl=0 Задачи к семинару 7 ноября]''' Задачи 5 и 6 переносятся на следующий раз.
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw07DM2-pilot.pdf Задачи к семинару 31 октября]'''  
+
'''[https://www.dropbox.com/s/bj0ok0jd1k3h5kg/cw07DM2-pilot.pdf?dl=0 Задачи к семинару 31 октября]'''  
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw06DM2-pilot.pdf Задачи к семинару 10 октября]'''  
+
'''[https://www.dropbox.com/s/s3dxyba4d8w7pra/cw06DM2-pilot.pdf?dl=0 Задачи к семинару 10 октября]'''  
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw05DM2-pilot.pdf Задачи к семинару 3 октября]'''  
+
'''[https://www.dropbox.com/s/hy1syywm0cs5l6s/cw05DM2-pilot.pdf?dl=0 Задачи к семинару 3 октября]'''  
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw04DM2-pilot.pdf Задачи к семинару 26 сентября]'''  
+
'''[https://www.dropbox.com/s/cauy20clq99ule8/cw04DM2-pilot.pdf?dl=0 Задачи к семинару 26 сентября]'''  
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw03DM2-dos.pdf Задачи к семинару 19 сентября]''' Последние две задачи не разобраны до конца, будут обсуждаться в следующий раз.
+
'''[https://www.dropbox.com/s/vtbrr8lr818tuh0/cw03DM2-dos.pdf?dl=0 Задачи к семинару 19 сентября]''' Последние две задачи не разобраны до конца, будут обсуждаться в следующий раз.
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw02DM2-pilot.pdf Задачи к семинару 12 сентября]''' Задача 5 на семинаре не разбиралась, отложена на следующее занятие.
+
'''[https://www.dropbox.com/s/an4aaj3baneh4r3/cw02DM2-pilot.pdf?dl=0 Задачи к семинару 12 сентября]''' Задача 5 на семинаре не разбиралась, отложена на следующее занятие.
  
'''[https://dl.dropboxusercontent.com/u/33029521/cw01DM2-pilot.pdf Задачи к семинару 5 сентября]'''
+
'''[https://www.dropbox.com/s/ong91v3reh5gd5n/cw01DM2-pilot.pdf?dl=0 Задачи к семинару 5 сентября]'''

Версия 20:33, 10 декабря 2018

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

Лекции проходят по понедельникам в аудитории 205 в 10:30-11:50. Первая лекция 5 сентября.

Объявление 19 декабря занятий не будет. Курс закончен. Остался только экзамен 22 декабря (см. ниже более подробную информацию).

Лектор:

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

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

151 Таламбуца Алексей Леонидович, alexey.talambutsa@gmail.com, ассистент Волгин Андрей Денисович, andrewvlg@yandex.ru

152 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Святокум Полина Олеговна, pola_sv@mail.ru

Коллоквиум

Коллоквиум будет 16 декабря, 311 ауд. Начало для 151 группы 12:10, для 152 группы 13:40.

12 декабря, 10:30, будет консультация перед коллоквиумом. Предварительно, в ауд. 205 (там же, где и лекции). С аудиторией возможны изменения, следите за информацией!

Программа коллоквиума.

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


Экзамен (письменный)

состоится 22 декабря в 13:40 ауд. 622, показ работ 24 декабря.

На экзамене разрешается пользоваться письменными источниками и не разрешается пользоваться электронными приборами.

Задачи экзамена 22.12.2016

Решения задач экзамена 22.12.2016

Задачи переэкзаменовки 18.01.2017

Решения задач переэкзаменовки 18.01.2017

Задачи переэкзаменовки 24.01.2017

Решения задач переэкзаменовки 24.01.2017

Ссылки

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

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

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

Записки про метод резолюций.

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

Консультации М.Н.Вялого

6 декабря Крайний срок защиты домашних заданий 3-4 в группе 152. 15:10-16:30. Встречаемся возле 617 ауд. (Можно попробовать найти меня после лекции Макарычева (заканчивается в 18:00), которая будет в 509 ауд.)

29 ноября Начало 15:10. Встречаемся возле 617 ауд.

22 ноября Начало 15:10. Встречаемся возле 617 ауд.

10 октября Начало 16:40 (если будут желающие). Встречаемся возле 617 ауд.

04 октября Начало 15:10. Искать возле 513 ауд.

30 сентября Начало 16:40. Искать возле 503 ауд.

23 сентября Начало 16:40. Искать возле 503 ауд.

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

Домашнее задание 6 Срок выполнения: к 5 декабря. Обратите внимание! Срок выполнения этого домашнего задания одна неделя, а не две!


Домашнее задание 5 Срок выполнения: к 28 ноября.

Домашнее задание 4 Срок выполнения: к 14 ноября.

Домашнее задание 3 Срок выполнения: к 17 октября. (по многочисленным просьбам) Определение невырожденного полиэдра: Полиэдр в n-мерном пространстве называется невырожденным, если все минимальные грани - точки (вершины), и в каждой вершине обращается в равенство ровно n ограничений, задающих полиэдр (каждое равенство в системе ограничений считается один раз).

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

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

Лекции

5 декабря Элементарная эквивалентность моделей. Изоморфные модели. Игры Эренфойхта.

28 ноября Доказательства невыразимости предикатов с помощью автоморфизмов. Элиминация кванторов. Приложения к доказательствам невыразимости.

21 ноября Перестановки кванторов. Перестановки связок и кванторов. Приведенная нормальная форма. Существование ПНФ, эквивалентной данной формуле. Выразимость в теории множеств и арифметике. Арифметическое кодирования конечных подмножеств множества натуральных чисел.

14 ноября Определение формул первого порядка. Параметры, сводобные и связанные вхождения. Интерпретации. Значение формулы в заданной интерпретации при заданной оценке переменных. Общезначимые формулы, выполнимые формулы. Эквивалентные формулы. Примеры эквивалентных и неэквивалентных формул. Замена переменной в кванторе.

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

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

10 октября Конструктивная лемма Фаркаша. Алгоритм замены базисов с правилом Бленда и его сходимость. Конечно порожденные конусы поиэдральны, полиэдральные конусы конечно порождены. Политоп - выпуклая оболочка своих вершин. Выпуклая оболочка конечного числа точек - полиэдр.

3 октября Геометрическая идея симплекс-метода. Грани полиэдров. Минимальные грани. Вершины (0-мерные грани), ребра (1-мерные грани). Политопы - ограниченные полиэдры. Задача локального улучшения целевой функции. Критерий оптимальности. Увеличение целевой функции при сдвиге по ребру. Конструктивная лемма Фаркаша. Невырожденный случай, количество ребер равно размерности.

26 сентября Приложения двойственности в линейном программировании. Вывод теоремы Форда-Фалкерсона из анализа пары двойственных задач линейного программирования. Матричные игры двух игроков с нулевой суммой. Существование равновесия в смешанных стратегиях.

19 сентября Двойственность в линейном программировании. Критерий того, что неравенство является семантическим следствием совместной системы неравенств. Двойственная задача ЛП. Виды пар прямой и двойственной задачи. Теорема двойственности. Соотношения дополняющей нежесткости.

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

5 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о потоке в сети, транспортная задача. Виды ЛП задач: общий, только с неравенствами, равенства на неотрицательные переменные. Дробно-линейное программирование и сводимость к ЛП.

Семинары

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

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

Задачи к семинару 21 ноября Задача 3 будет разбираться в следующий раз. Очень рекомендуется попробовать ее решить к следующему занятию на основе тех идей, которые обсуждались в этот раз.

Задачи к семинару 14 ноября Часть задач будет разобрана на следующем семинаре.

Задачи к семинару 7 ноября Задачи 5 и 6 переносятся на следующий раз.

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

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

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

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

Задачи к семинару 19 сентября Последние две задачи не разобраны до конца, будут обсуждаться в следующий раз.

Задачи к семинару 12 сентября Задача 5 на семинаре не разбиралась, отложена на следующее занятие.

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