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

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

Сложность вычислений и логика в теоретической информатике (3-ий курс ТИ) 2018 год

Лекции проходят по вторникам в аудитории 306 в 15:10-16:30. Семинары по вторникам 16:40-18:00. Первая лекция и семинар 9 января.

Новости

4 апреля выложены конспекты лекций об экспандеров, полученные переработкой книги Ромащенко.

Лектор

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

Семинарист

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


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

Теоремы Геделя о неполноте для формальной арифметики и теории множеств. Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и поля комплексных чисел. Экспандеры и теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти. Лемма Ловаса и быстрые алгоритмы для SAT. Сложность пропозициональных доказательств.


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

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

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

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

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

Сумма оценки за коллоквиум и оценки за домашние задания с коэффициентами 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.

Экзамен

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

Первое домашнее выложено 6.2.2018, срок сдачи 20.2.2018.

Второе домашнее будет выложено 6.3.2018, срок сдачи 20.3.2018.

Третье домашнее будет выложено 24.4.2018, срок сдачи 8.5.2018.

Четвертое домашнее будет выложено 5.6.2018, срок сдачи 19.6.2018.

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

Оценки

Домашнее задание 1. Cрок сдачи 20.2.2018 в 15:10 MSK.

Домашнее задание 2. Cрок сдачи 20.3.2018 в 15:10 MSK.

Домашнее задание 3. Cрок сдачи 15.5.2018 в 15:10 MSK. ==== В этом ДЗ есть две бонусные задачи. Каждая из них дает +1 к оценке коллоквиума (но больше 10 за коллоквиум получить все равно нельзя, так что эти задачи можно воспринимать как подстраховку). Чтобы бонус засчитался, нужно за основную часть ДЗ получить не менее половины от максимально возможного балла). ====

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

Лекция 1 (9 января).

Формулировки первой и второй теоремы Гёделя для формальной арифметики и теории множеств. Понятие финитного и сугубо финитного доказательства. Программа Гильберта обоснования математики.

Лекция 2 (16 января).

Нефинитное доказательство существования сколь угодно больших чисел. Нефинитное доказательство непротиворечивости PA.

Тезис арифметичности (любая арифметическая формула, имеющая финитное доказательство, выводима в PA). Принцип свертывания (без доказательства).

Принцип отражения в PA. Первая теорема Геделя о неполноте для PA. Вторая теорема Геделя о неполноте для PA.

Лекция 3 (23 января).

Аксиомы Бернайса и вывод из них второй теоремы о неполноте. Первая теорема Геделя в форме Россера для PA.

Лекция 4 (30 января).

Разрешимость элементарной теории поля комплексных чисел.

Разрешимость элементарной теории упорядоченного поля действительных чисел (теорема Тарского-Зайденберга) (начало).

Лекция 5 (6 февраля).

Разрешимость элементарной теории упорядоченного поля действительных чисел (теорема Тарского-Зайденберга) (окончание).

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).

Лекция 6 (13 февраля).

Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа. Expander mixing lemma.

Лекция 7 (20 февраля).

L_2-расстояние до равномерного распределения при одном шаге случайного блуждания. Лапласиан графа. От спектрального экспадера к комбинаторному.

Лекция 8 (27 февраля).

Нижняя оценка на второе собственное числа d-регулярного графа. Вероятностное доказательство существования спектрального экспандера.

Лекция 9 (6 марта).

Тензорное произведение и зигзаг-произведение двух графов и их собственные числа. Построение спектрального экспандера с использованием первой оценки для зигзаг-произведения (слабо и сильно эффективные конструкции).

Лекция 10 (13 марта).

Уменьшение вероятности ошибки с помощью экспандеров без использования дополнительной случайности.

Уменьшение вероятности ошибки с помощью экспандеров путем t шагов случайного блуждания с использованием O(t) дополнительных случайных битов.

Вторая спектральная оценка для зигзаг-произведения.

Лекция 11 (20 марта).

Алгоритм Рейнголда.


27 марта лекции нет (сессия).

Лекция 12 (3 апреля).

Экспандер Маргулиса.

Лекция 13 (10 апреля).

Двудольные экспандеры: необходимое и достаточное условие существования. Экспандер с коэффициентом увеличения близким к степени.

Экспандер Варди-Парвареша (конструкция).

Проведённые семинары

Семинар 1 (9 января)

Beta-функция Геделя. Задачи на выразимость предикатов в арифметике ("x --- совершенное число", "x равно целой части e^y"). Построение формулы, выражающей непротиворечивость PA. Некоторые простые свойства ZF (почему множество не может принадлежать самому себе, почему существует декартово произведение).

Семинар 2 (16 января)

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

Семинар 3 (23 января)

Ложность аксиом Бернайса при неестественном определении выводимости. Определение натуральных чисел в ZF (если ZF непротиворечива, то PA непротиворечива). Вывод транзитивности и коммутативности сложения из PA. Сугубо финитное доказательство принципа свертывания (не до конца).


Семинар 4. Задачи (30 января)

Семинар 5. Задачи (6 февраля)

Семинар 6. Задачи (13 февраля)

Семинар 7. Задачи (20 февраля)

Семинар 8. Задачи (27 февраля)

Семинар 9. Задачи (6 марта)

Семинар 10. Задачи (13 марта)

Семинар 11. Задачи (20 марта)

Семинар 12. Задачи (3 апреля)

Семинар 13. Задачи (10 апреля)

Семинар 14. Задачи (17 апреля)

Семинар 15. Задачи (24 апреля)

Конспекты лекций

Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко

Конспекты лекций о теоремах Геделя для арифметики Пеано

Конспекты лекций об аксиоматической теории множеств

Конспекты лекций о теоремах Геделя для аксиоматической теории множеств

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

Козачинский вт. 13:30-15:00, ср 16:00-18:00 в 617

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

А.Е. Ромащенко. Экспандеры: конструкции и приложения.