Содержание

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

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

Лекции проходят по вторникам 15:10-16:30, семинары 16:40-18:00

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

Новости

Ссылка на лекцию и семинар 31 марта: https://zoom.us/j/974201240 Начало лекции 15:10, начало семинара 16:40.

Лекция 24 марта (вторник) в 15:10-16:30 состоится в виде вебинара. Вот ссылка на вебинар: https://zoom.us/j/912901893 Преимущество вебинара перед Ютуб трансляцией в том, что удобнее задавать вопросы по ходу лекции (это можно делать и устно, и письменно).

Весенняя сессия отменяется, поэтому лекция и семинар 31 марта состоятся.

C 17 марта 2020 года ВШЭ перешла на дистанционное обучение (карантинная мера, вызванная распостранением коронавируса). Лекции курса будут транслироваться и записываться в обычное время (по вторникам с 15:10 до 16:30) на Ютуб канале https://www.youtube.com/channel/UCQpMy-jk_5qdi91U9NsBVdQ?view_as=subscriber

Во время трансляции можно задавать вопросы в чате, на которые лектор сможет отвечать примерно с полминутной задержкой. Очередная трансляция состоится 17 марта.

Лекция 17 марта

Лектор

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

Семинарист

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

Консультации (защиты): по вторникам 14-15, 18-19 и по средам 15.10-16 в S832.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Коллоквиум

Экзамен

Пересдачи

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

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

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

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

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

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

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

Домашнее задание 2 Срок сдачи 31.3.2020 в 16.40 MSK.

Результаты

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

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

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

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

Максимальное по абсолютной величине собственное число регулярного графа. От чего зависит кратность собственного числа d. Второе по абсолютной величине собственное число двудольного графа.

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

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

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

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

Формула для числа Каталана. Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами.

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

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

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

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

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

Второе собственное число связного недвудольного графа.

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

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

Применение экспандеров для дерандомизации.

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

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

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

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

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

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

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

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

Лекция 12 (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 (спектр графов)

Семинары

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

Разобраны задачи 1-6 из первого листка.

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

Разобраны задачи 1--5 из второго листка.

Семинар 3 (11 февраля)

Разобраны задачи 1--2 из третьего листка

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

Разобраны задачи 1--2 из четвёртого листка

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

Разобраны задачи 1--3 из пятого листка

Семинар 6 (3 марта)

Разобраны задачи 1--3 из шестого листка

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

Разобраны задачи 1--3 из седьмого листка

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

Разобраны задачи 1--4 из восьмого листка https://www.youtube.com/watch?v=3Kg6yDvRnt0&feature=youtu.be PDF доски

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

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

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

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

CCTI 2020