Сложность вычислений и логика в теоретической информатике

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

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

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

Лекции проходят по вторникам в аудитории 501 в 10:30-11:50. Семинары по вторникам в аудитории 501 в 12:10-13:30. Первая лекция и семинар 15 января.

Канал в telegram

Новости

Лектор

Верещагин Николай Константинович, 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) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.

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

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется (арифметически) только в момент выставления накопленной и итоговой оценок.

Коллоквиум

Коллоквиум состоится в июне.

Экзамен

Письменный состоится в июне.

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

Первое домашнее будет выложено 29.1.2019, срок сдачи 12.2.2019.

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

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

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

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

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

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

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа. Expander mixing lemma.


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

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

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


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

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


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

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

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

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

Moser R.A., Tardos G., A constructive proof of the general Lovasz Local Lemma,Journal of the ACM, 2010, 57(2), 11.1–11.15.

Статья Румянцева и Шеня с изложением алгоритма Мозера-Тардоша

Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995

N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.