Версия 15:21, 14 января 2020

Содержание

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

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

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

Группа в телеграме для вопросов

Новости

Лектор

Верещагин Николай Константинович, 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 (22 января).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Листок 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 июня)

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

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

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

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

@@ Строка 79: / Строка 79: @@
 [ Домашнее задание 1.] Cрок сдачи 12.2.2019 в 12:10 MSK.
-==Прочитанные лекции==
+==Планируемые лекции==
+====Лекция 1 (22 января).  ====
-====Лекция 1 (15 января).  ====
 Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
 Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа.
-====Лекция 2 (22 января).  ====
+====Лекция 2 (29 января).  ====
 Лемма о перемешивании. От спектрального экспандера к комбинаторному.
-====Лекция 3 (29 января).  ====
+====Лекция 3 (5 февраля).  ====
 Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.
 Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами.
-====Лекция 4 (5 февраля). ====
+====Лекция 4 (12 февраля). ====
 Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов и первая оценка его собственных чисел. Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
-====Лекция 5 (12 февраля). ====
+====Лекция 5 (19 февраля). ====
 Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
@@ Строка 109: / Строка 107: @@
 Алгоритм Рейнгольда.
-====Лекция 6 (19 февраля). ====
+====Лекция 6 (26 февраля). ====
 Алгоритм Рейнгольда.
 Применение экспандеров для дерандомизации.
-====Лекция 7 (26 февраля). ====
+====Лекция 7 (5 марта). ====
 Экспандер Маргулиса.
-====Лекция 8 (5 марта). ====
+====Лекция 8 (12 марта). ====
 Экспандер Маргулиса (окончание доказательства).
@@ Строка 123: / Строка 122: @@
 Двудольные экспандеры: определение и вероятностное доказательство существования.
-====Лекция 9 (12 марта). ====
+====Лекция 9 (19 марта). ====
 Экспандер Варди - Парвареша.
-====Лекция 10 (19 марта). ====
+====Лекция 10 (2 апреля). ====
-Экспандерные коды: определение, параллельный и последовательный алгоритмы декодирования.
+Коды с исправлением ошибок и их параметры. Линейные коды.
-====Лекция 11 (2 апреля). ====
-Разрешимость элементарной теории поля комплексных чисел.
+Оценка Синглтона и коды Рида - Соломона.
+Декодирование кодов Рида - Соломона.
-====Лекция 12 (9 апреля). ====
+====Лекция 11 (9 апреля). ====
-Разрешимость элементарной теории упорядоченного поля
+Оценка Хэмминга и коды Хэмминга.
-действительных чисел.
+Оценки Гилберта и  Варшамова - Гилберта.
+Случайные коды и случайные линейные коды.
-====Лекция 13 (16 апреля). ====
+====Лекция 12 (16 апреля). ====
-Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность.
+Коды Возенкрафта.
-Чувстительность и блочная чувствительность.
+Функция Шеннона. Графики оценок Хэмминга и Гилберта.
-Неравенства D < C_0 C_1, D< C_0 bs_1
-====Лекция 14 (23 апреля). ====
+====Лекция 13 (23 апреля). ====
-Неравенство C_0< bs_0 s_1. Вероятностные деревья и неравенство bs = O(R)
+Каскадные коды и коды Форни. Декодирование каскадного кода.
-Представление булевых функций многочленами с действительными коэффициентами.
+Коды Форни - Юстесена - Возенкрафта
-Теорема Маркова.
+====Лекция 14 (30 апреля). ====
-====Лекция 15 (30 апреля). ====
+Экспандерные коды: определение, параллельный и последовательный алгоритмы декодирования.
-Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
+====Лекция 15 (7 мая). ====
-Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ
+Оценки Плоткина и коды Адамара. Декодирование списком и теорема Левина - Голдрайха.
-Связь между размером дерева и представлением функции в виде m,*-ДНФ и m,*-КНФ (Эренфойхт - Хауслер).
 ====Лекция 16 (14 мая). ====
+Деревья разрешения, метод противника. Сертификатная и недетерминированная сложность.
+Чувстительность и блочная чувствительность.
+Неравенства D < C_0 C_1, D< C_0 bs_1
-Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).
+====Лекция 17 (21 мая). ====
-Метод Храпченко доказательства нижних оценок формульной сложности.
+Неравенство C_0< bs_0 s_1. Вероятностные деревья и неравенство bs = O(R)
-====Лекция 17 (21 мая). ====
+Представление булевых функций многочленами с действительными коэффициентами.
+Теорема Маркова.
-Ограничения булевой функции. Нижняя оценка формульной сложности функции Андреева.
-Теорема Разборова - Смоленского о нижней оценке размера формул ограниченной глубины.
 ====Лекция 18 (28 мая). ====
-Коды с исправлением ошибок и их параметры. Линейные коды.
+Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
-Оценка Синглтона и коды Рида - Соломона.
+Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ
-Декодирование кодов Рида - Соломона.
+Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).
 ====Лекция 19 (4 июня). ====
-Оценка Хэмминга и коды Хэмминга (без доказательства и построения)
-Случайные коды и оценка Варшамова - Гилберта.
+Разрешимость элементарной теории поля комплексных чисел.
-Коды Возенкрафта.
 ====Лекция 20 (11 июня). ====
-Каскадные коды и коды Форни. Декодирование каскадного кода.
+Разрешимость элементарной теории упорядоченного поля
+действительных чисел.
 ==Задачи для семинаров  ==

CCTI 2020 — различия между версиями