Содержание

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

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

Лекции проходят по вторникам в аудитории D506.

21 января лекция в 13:40-15:00, семинар в 15:10-16:30,

28 января лекция будет в 16:40, а семинара не будет,

В остальные дни лекции в 15:10-16:30, семинары 16:40-18:00

Первая лекция и семинар 21 января.

Новости

Лектор

Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com

Семинарист

Милованов Алексей Сергеевич almas239@gmail.com

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

Экспандеры и их применения:теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, экспандерные коды.

Коды с исправлением ошибок для компьютерных наук.

Представление булевых функций деревьями разрешения и многочленами.

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

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

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

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

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

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

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

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

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

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

Коллоквиум

Экзамен

Пересдачи

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

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

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

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

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

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

Оценки

[ Домашнее задание 1.] Cрок сдачи 12.2.2019 в 12:10 MSK.

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

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

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

Планируемые лекции

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

Лемма о перемешивании. От спектрального экспандера к комбинаторному.

Лекция 3 (4 февраля).

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

Лекция 4 (11 февраля).

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

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

Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.

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

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

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

Алгоритм Рейнгольда. Применение экспандеров для дерандомизации.

Лекция 7 (3 марта).

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

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

Экспандер Маргулиса (окончание доказательства).

Двудольные экспандеры: определение и вероятностное доказательство существования.

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

Экспандер Варди - Парвареша.

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

Коды с исправлением ошибок и их параметры. Линейные коды.

Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона.

Лекция 11 (7 апреля).

Оценка Хэмминга и коды Хэмминга. Оценки Гилберта и Варшамова - Гилберта. Случайные коды и случайные линейные коды.

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

Коды Возенкрафта. Функция Шеннона. Графики оценок Хэмминга и Гилберта.

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

Каскадные коды и коды Форни. Декодирование каскадного кода.

Коды Форни - Юстесена - Возенкрафта

Лекция 14 (28 апреля).

Экспандерные коды: определение, параллельный и последовательный алгоритмы декодирования.

Лекция 15 (5 мая).

Оценки Плоткина и коды Адамара. Декодирование списком и теорема Левина - Голдрайха.

Лекция 16 (12 мая).

Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность. Чувстительность и блочная чувствительность. Неравенства D < C_0 C_1, D< C_0 bs_1

Лекция 17 (19 мая).

Неравенство C_0< bs_0 s_1. Вероятностные деревья и неравенство bs = O(R)

Представление булевых функций многочленами с действительными коэффициентами. Теорема Маркова.

Лекция 18 (26 мая).

Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).

Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ

Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).

Лекция 19 (2 июня).

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

Лекция 20 (9 июня).

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

Задачи для семинаров

Листок 1 (комбинаторные экспандеры)

Листок 2 (еще комбинаторные экспандеры)

Листок 3 (спектр графов)

Листок 4 (спектр графов и спектральные экспандеры)

Листок 5 (случайные блуждания)

Листок 6 (log-space алгоритмы)

Листок 7 (продолжаем спектральные экспандеры)

Листок 8 (аффинная плоскость и другие экспандеры)

Листок 9 (двудольные экспандеры)

Листок 10 (болты и гайки)

Листок 11 (выразимость, элиминация кванторов)

Листок 12 (еще элиминация кванторов)

Листок 14 (еще деревья разрешения)

Листок 15 (деревья разрешения + немного схем)

Листок 16 (схемы)

Листок 17 (еще схемы)

Листок 18 (схемы + коды)

Листок 19 (коды)

Семинары

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

Разобраны задачи 1-5 из первого листка. Кроме этого, частично разобрана задача 7.

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

Решены задачи 1 и 4.

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

Решены задачи 1, 4 и 6а, а также 5 в одну сторону.

Семинар 4 (5 февраля)

Решили задачи 4 и 5. Для этого рассказал о графах Кели.

Семинар 5 (12 февраля)

Решена задача 4. Решали 5-ую, но не до конца.

Семинар 6 (19 февраля)

Решили все задачи из листка.

Семинар 7 (26 февраля)

Решили первую и часть четвертой задачи.

Семинар 8 (5 марта)

Решили первые три задачи.

Семинар 9 (12 марта)

Решена первая задача.

Семинар 10 (19 марта)

Решена первая задача. Остальное время обсуждали 2-ую задачу.

Семинар 11 (2 апреля)

Решены задачи 1, 2a, 4.

Семинар 12 (9 апреля)

Решены задачи 1, 2а, 2б, 3а, 6а.

Семинар 13 (16 апреля)

Решены задачи 1, 2, 4.

Семинар 14 (23 апреля)

Решены задачи 1 и 4а)

Семинар 15 (30 апреля)

Разобрали первую задачи + обсудили схемы, отношения Карчмера --- Видгерсона, как доказать, что для Majority нужна глубина хотя бы 2\log_2(n).

Семинар 16 (14 мая)

Решили задачи 1, 2 и 3а.

Семинар 17 (21 мая)

Решили задачи 1 и 2.

Семинар 18 (28 мая)

Решили 5 задачу и частично 6а)

Семинар 19 (4 июня)

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

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

Конспект лекций о деревьях разрешения.

Конспект лекций о кодах с исправлением ошибок (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."

CCTI 2020