Comb2020 2021
Содержание
- 1 Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2021 год
- 1.1 Новости
- 1.2 Контакты
- 1.3 Краткое описание
- 1.4 Отчётность по курсу и критерии оценки
- 1.5 Примерные сроки контрольных мероприятий
- 1.6 Домашние задания
- 1.7 Результаты
- 1.8 Прочитанные лекции
- 1.8.1 Лекция 1 (15 января).
- 1.8.2 Лекция 2 (22 января).
- 1.8.3 Лекция 3 (29 января).
- 1.8.4 Лекция 4 (5 февраля).
- 1.8.5 Лекция 5 (12 февраля).
- 1.8.6 Лекция 6 (19 февраля).
- 1.8.7 Лекция 7 (26 февраля).
- 1.8.8 Лекция 8 (5 марта).
- 1.8.9 Лекция 9 (12 марта).
- 1.8.10 Лекция 10 (19 марта).
- 1.8.11 Лекция 11 (26 марта).
- 1.8.12 Лекция 12 (9 апреля).
- 1.9 Планируемые лекции
- 1.10 Задачи для семинаров
- 1.11 Семинары
- 1.11.1 Семинар 1 (15 января)
- 1.11.2 Семинар 2 (22 января)
- 1.11.3 Семинар 3 (29 января)
- 1.11.4 Семинар 4 (5 февраля)
- 1.11.5 Семинар 5 (12 февраля)
- 1.11.6 Семинар 6 (19 февраля)
- 1.11.7 Семинар 7 (26 февраля)
- 1.11.8 Семинар 8 (5 марта)
- 1.11.9 Семинар 9 (12 марта)
- 1.11.10 Семинар 10 (19 марта)
- 1.11.11 Семинар 11 (26 марта)
- 1.11.12 Семинар 12 (9 апреля)
- 1.12 Конспекты лекций
- 1.13 Рекомендуемая литература
Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2021 год
Лекции проходят по пятницам 13:00-14:20, семинары также по пятницам 14:40-16:00 через Zoom по ссылке https://zoom.us/j/97847376308?pwd=NTQ2ZnZVdldHZ2xtTHlYTUdNM24xdz09С Идентификатор конференции: 97847376308 пароль 557552
Ссылка на доску: https://drive.google.com/drive/folders/1JwrAZgF8NXajZvnXuUG_6NFEv7vWjlqs?usp=sharing
Если Zoom виснет, лекции переносятся в Google Meet https://meet.google.com/noy-cait-jph
Первая лекция и семинар 15 января.
Новости
25 марта
Выложено второе домашнее задание
11 февраля
Выложено первое домашнее задание
15 января
Добавлена Ссылка на записи на доске, сделанные во время лекции
Контакты
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com
Семинарист: Милованов Алексей Сергеевич almas239@gmail.com, телеграм: AlexeySMilovanov
Группа в Телеграм: https://t.me/joinchat/RXhbmrjQzig8QLiw
Краткое описание
Экспандеры и их применения: теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, построение генераторов псевдослучайных чисел, экспандерные коды.
Коды с исправлением ошибок для компьютерных наук.
Представление булевых функций деревьями разрешения и многочленами.
Отчётность по курсу и критерии оценки
Итоговая оценка складывается из оценок за домашние задания, оценок за тесты, и оценки за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.3, а оценки за домашние задания и тесты - с коэффициентом 0.2.
В домашних заданиях иногда будут бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.
Тесты
В конце каждой лекции будет предлагаться десятиминутный тест с простыми задачами. Целью тестов является контроль за тем, чтобы студенты внимательно слушали лекцию. К написанию теста допускаются только присутствовавшие на лекции (разрешается десятиминутное опоздание к началу лекции). За каждый тест выставляется оценка, равная доле правильных ответов, умноженной на 10. Общая оценка за тесты равняется среднему арифметическому оценок за все тесты.
Домашние задания
В течение двух модулей студентам будет дано 4 домашних задания. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно сдавать семинаристу или лектору устно (онлайн). Сдача домашних заданий после их срока невозможна.
Сдать ДЗ лектору можно по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью Google Meet https://meet.google.com/noy-cait-jph
Сдать ДЗ семинаристу можно в понедельник, субботу или воскресение по предварительной договорённости.
Коллоквиум и письменный экзамен
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.
Правила округления
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.
Коллоквиум
Коллоквиум состоится 18 июня с 9:30. Записываться в таблицу: ...
[ Программа коллоквиума.]
Экзамен
Экзамен состоится ...
Экзамен проходит с прокторингом. Студенты загружают задание по ссылке ... , решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке ... . Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
Экзамен длится 90 минут. Во время экзамена студенты должны включить камеры. Во время экзамена разрешено смотреть на любые материалы, загруженные на компьютер до начала экзамена, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать загруженные материалы и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
Пересдачи
Примерные сроки контрольных мероприятий
Первое домашнее будет выложено 11 февраля, срок сдачи 4 марта.
Второе домашнее будет выложено 25 марта, крайний срок сдачи 15 апреля.
Третье домашнее будет выложено 22 апреля, крайний срок сдачи 13 мая.
Четвертое домашнее будет выложено 27 мая, крайний срок сдачи - 17 июня.
Домашние задания
Домашнее задание 1 Cрок сдачи 4.03.2021
Домашнее задание 2 Срок сдачи 15.04.2021
Результаты
Общая ведомость оценок (в нее вносятся и результаты тестов)
Прочитанные лекции
Ссылка на записи на доске, сделанные во время лекции
Лекция 1 (15 января).
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением.
Лекция 2 (22 января).
Матрица графа и ее собственные числа. Максимальное по абсолютной величине собственное число регулярного графа. Лемма о перемешивании. От спектрального экспандера к комбинаторному.
Лекция 3 (29 января).
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа. Формула для числа Каталана (без доказательства).
Лекция 4 (5 февраля).
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами.
Лекция 5 (12 февраля).
Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов и первая оценка его собственных чисел.
Лекция 6 (19 февраля).
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. Вторая оценка для спектрального зазора зигзаг-произведения.
Лекция 7 (26 февраля).
Второе собственное число связного недвудольного графа.
Алгоритм Рейнгольда.
Лекция 8 (5 марта).
Применение экспандеров для дерандомизации.
Лекция 9 (12 марта).
Лекция 10 (19 марта).
Двудольные экспандеры: определение и вероятностное доказательство существования.
Лекция 11 (26 марта).
Лекция 12 (9 апреля).
Планируемые лекции
Лекция 13 (16 апреля).
Линейные коды, проверочная матрица. Оценка Хэмминга и коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. https://events.webinar.ru/event/4301788/4390364
Лекция 14 (23 апреля)
Лекция 15 (30 апреля)
Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.
Лекция 16. (7 мая)
Лекция 17 (14 мая)
Лекция 18 (21 мая )
Лекция 19 (28 мая).
Неравенствo D < C*bs Неравенство C< bs*s. Вероятностные деревья и неравенство bs = O(R)
Лекция 20 (4 июня).
Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ Связь между глубиной дерева и представлением функции в виде m,k-ДНФ и m,k-КНФ (Эренфойхт - Хауслер).
Лекция 21 (11 июня).
Теорема Маркова. Представление булевых функций многочленами с действительными коэффициентами. Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди). Связь между чувствительностью и блочной чувствительностью (Hao Huang).
Задачи для семинаров
Листок 1 (комбинаторные экспандеры)
Семинары
Семинар 1 (15 января)
Доска Листок 1 (комбинаторные экспандеры)
Семинар 2 (22 января)
Доска Листок 2 (спектр графов)
Семинар 3 (29 января)
Семинар 4 (5 февраля)
Семинар 5 (12 февраля)
Семинар 6 (19 февраля)
Семинар 7 (26 февраля)
Семинар 8 (5 марта)
Семинар 9 (12 марта)
Семинар 10 (19 марта)
Семинар 11 (26 марта)
Семинар 12 (9 апреля)
Конспекты лекций
Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко
Конспект лекций о деревьях разрешения.
Конспект лекций о кодах с исправлением ошибок (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."
Sensitivity for dummies (решение Sensitivity conjecture).
Рекомендуемая литература
А.Е. Ромащенко. Экспандеры: конструкции и приложения.
N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.
Alexander Razborov, Nikolay Vereshchagin. One Property of Cross-Intersecting Families. ECCC TR99-014. https://eccc.weizmann.ac.il/report/1999/014/