DM2-pilot2019/2020

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

Лекции проходят по пятницам в 13:40-15:00 в аудитории R406

Новости

Лектор

Вялый Михаил Николаевич vyalyi@gmail.com

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

181 Козачинский Александр Николаевич kozlach@mail.ru (учебный ассистент Агамов Раджаб Эльдар оглы agamov@phystech.edu)

182 Вялый Михаил Николаевич vyalyi@gmail.com

184 Козачинский Александр Николаевич kozlach@mail.ru

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

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

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

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

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

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

Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.

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

Экзамен состоит из 8 задач с указанием количества баллов за каждую задачу. Эти баллы в сумме дают 10 баллов или больше. Задачи нужно решить за две пары.

Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.

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

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

При вычислениях промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент, когда по внешним причинам требуется целочисленная оценка (скажем, при выставлении итоговой оценки). В этом случае используется арифметическое округление (то есть, 6.5 округляется до 7, а 6.49 - до 6).

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

Коллоквиум

Экзамен

Пересдачи

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

Оценки за домашние задания

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

  • Вычислимые функции. Разрешимые, перечислимые множества. Теорема Поста.
  • Универсальные функции. Неразрешимые и неперечислимые множества.
  • Главные нумерации. Теорема Райса-Успенского. Теорема о неподвижной точке.
  • Машины Тьюринга. Неразрешимость проблемы остановки МТ.
  • Сводимости. Неразрешимость задачи достижимости в ассоциативных исчислениях.
  • Полугруппы, двусторонние исчисления, неразрешимость проверки равенства слов.
  • Логические формулы: булевы формулы, формулы первого порядка.
  • Общезначимые формулы. Предваренная нормальная форма.
  • Исчисление резолюций для пропозициональных формул.
  • Исчисление резолюций для формул первого порядка.
  • Неразрешимость проверки общезначимости. Перечислимость множества общезначимых формул.
  • Языки первого порядка и их модели. Изоморфные и элементарно эквивалентные модели.
  • Выразимые в данной модели отношения. Метод автоморфизмов доказательства невыразимости.
  • Выразимость в арифметике. Бета-функция Гёделя. Неперечислимость формул, истинных в арифметике.

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

Семинары

Рекомендуемая литература

1. Н.К.Верещагин, А. Шень. Вычислимые функции. М.:МЦНМО, 2012.

2. Н.К.Верещагин, А. Шень. Языки и исчисления. М.:МЦНМО, 2012.

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

4. Черновик учебника "Лекции по дискретной математике" М.Вялый, В. Подольский, А. Рубцов, Д. Шварц, А Шень Главы 14-16 посвящены вычислимости.