Сложность и логика

Материал из Wiki - Факультет компьютерных наук
Версия от 17:03, 9 января 2018; Nvereshagin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

Новости

  • (22 декабря) Проверены экзаменационные работы. Баллы за задачи и критерии их оценки (на последнем листе) находятся здесь. Показ работ 23 декабря в 16:40 в ауд. 402. Решения задач здесь
  • (18 декабря) Экзамен состоится в четверг 21 декабря с 15 до 18 в ауд. 622. Объявление для группы 164: После сдачи экзаменационной работы можно будет защитить шестое ДЗ.
  • (14 декабря) Объявление для группы 164: в пятницу 15 декабря после коллоквиума (до 17:15) можно защитить пятое домашнее задание Н.К. Верещагину (ауд. 617). Другого дня для защиты пятого ДЗ лектору не будет.
  • (5 декабря) Выложено расписание коллоквиума:

12 декабря (вторник)

Группа 161 13:40-16:30 (первая пара 300, затем 622)

Группа 162 15:10-18:00 (первая пара 622, затем 435)

Группа 163 16:40-18:00 (и до победного конца) (ауд. 311).

Подгруппы 164-2, 165-1: 12:10 - 15:00 (первая пара 622, потом 505)

Группа 166 12:10 - 15:00 (первая пара 622, потом 219)

15 декабря (Пятница) Подгруппы 164-1 и 165-2: время 13:40-16:30 -- ауд.205.

  • (19 октября) Дедлайн защиты второго домашнего задания для группы 164 сдвинут на 31 октября (из-за сессии)
  • (12 октября) Внимание! По ошибке в третьем домашнем задании первые две задачи совпадали с некоторыми задачами из второго домашнего задания. Они заменены на новые задачи.
  • (10 октября) Крайний срок сдачи третьего домашнего задания для групп 164, 166 сдвинут на 24 октября (поскольку 24 октября каникулы, при сдаче 24 октября задание надо послать по компьютерной почте).
  • (1 сентября) Лекции 12 и 26 сентября переносятся на 15 и 29 сентября, соответственно (на то же время) в ауд. 509. Это относится и к семинарам в группе 164, переносящимся в ауд. 301.

Лектор

Н.К. Верещагин nikolay.vereshchagin@gmail.com

Семинаристы

163 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Дискин Михаил Сергеевич, yhn1124@gmail.com, t.me/yhn112

164 Верещагин Николай Константинович nikolay.vereshchagin@gmail.com, ассистент Денисова Елена Алексеевна, lena97denisova@mail.ru

165 Дашков Евгений Владимирович edashkov@gmail.com, ассистент Моисеев Андрей Андреевич, andrei.moiseev213@yandex.ru

166 Милованов Алексей Сергеевич, almas239@gmail.com, ассистент Ребенко Ярослав Алексеевич, yarebenko@gmail.com

Краткое описание

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

Отчётность по курсу и критерии оценки

6 домашних заданий, коллоквиум и экзамен.

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

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

Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными. Коллоквиум состоит из двух теоретических вопросов (один по линейному программированию, другой по логике) и одной задачи, которые оцениваются в 3, 3 и 4 баллов соответственно. Эти задачи берутся из заранее опубликованного списка задач (с точностью до выбора конкретных чисел), подобных тем, что были в домашних заданиях. Экзамен состоит из 8 задач с указанием количества баллов за каждую задачу. Эти баллы в сумме дают 10 баллов. Задачи нужно решить за две пары.

Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 2/3 и 1/3, соответственно, составляют накопленную оценку. Накопленная оценка и оценка за экзамен с коэффициентами 3/5 и 2/5 дают итоговую оценку. Таким образом, оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.

Те, кто не смог прийти на экзамен и коллоквиум по болезни, могут его сдать отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.

Правила округления

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления накопленной и итоговой оценок. Округление при выставлении итоговой оценки арифметическое, а при выставлении накопленной оценки используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7.12 – до 8.

Экзамен

Баллы за задачи и критерии их оценки (на последнем листе) находятся здесь. Показ работ 23 декабря в 16:40 в ауд. 402. Решения задач [ https://www.dropbox.com/s/vgj8vcm2yyx63rg/main-17-12-21-sol.pdf?dl=0 здесь]

Сроки контрольных мероприятий

Эти сроки немного различаются для разных групп (поскольку семинары в разные дни).

Сроки сдачи ДЗ для 164 и 166 группы:

Первое домашнее задание 19 сентября (защита до 10 октября [для 166 группы до 17 октября]) . Второе домашнее задание 3 октября (защита до 24 октября). Третье домашнее задание 24 октября (защита до 14 ноября). Четвертое домашнее задание 7 ноября (защита до 28 ноября). Пятое домашнее задание 21 ноября (защита до 12 декабря). Шестое домашнее задание 5 декабря (защита до 26 декабря).

Сроки сдачи ДЗ для 163 и 165 группы:

Первое домашнее задание 22 сентября (защита до 13 октября). Второе домашнее задание 6 октября (защита до 27 октября). Третье домашнее задание 3 ноября (защита до 17 ноября). Четвертое домашнее задание 17 ноября (защита до 1 декабря). Пятое домашнее задание 1 декабря (защита до 15 декабря). Шестое домашнее задание 15 декабря (защита до 29 декабря).


Коллоквиум пройдет с 11 по 15 декабря. Вопросы к коллоквиуму

Экзамен (письменный) с 21 по 31 декабря.

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

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

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

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

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

Домашнее задание №1 -- дедлайны: для сдачи 19 сентября, для защиты 10 октября (для групп 164 и 166).

Домашнее задание №2 -- дедлайны: для сдачи 3 октября, для защиты 24 октября (для группы 166) и 31 октября (для группы 164).

Домашнее задание №3 -- дедлайны: для сдачи 17 или 24 октября, для защиты 7 ноября (для групп 164 и 166).

Домашнее задание №4. Срок сдачи для 164 и 166 групп - 7 ноября. Защита до 28 ноября.

Домашнее задание №5. Срок сдачи для 164 и 166 групп - 21 ноября. Защита до 12 декабря.

Домашнее задание №6. Срок сдачи для 164 и 166 групп - 5 декабря. Защита до 26 декабря.

Примерное содержание лекций

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

двойственности

  • Применения двойственности: потоки и разрезы в сетях, игры с нулевой суммой.
  • Симплекс метод.
  • Исчисление резолюций для пропозициональных формул.
  • Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели. Доказательства элементарной эквивалентности с помощью игр Эренфойхта
  • Исчисление резолюций для формул первого порядка.
  • Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.
  • Логическое следование и аксиоматические теории.

Прочитанные лекции

Лекция 1 (5 сентября).

Источник — «http://wiki.cs.hse.ru/index.php?title=Сложность_и_логика&oldid=26385»