Содержание

1 Односторонние функции и их применения (4-ий курс ТИ) 2021 год

Односторонние функции и их применения (4-ий курс ТИ) 2021 год

Лекции проходят по четвергам 14:40 - 16:00 в ауд. D201, семинары по средам 13:00-14:20 в ауд. D109. Первая лекция 2 сентября, первый семинар 8 сентября.

Новости

Контакты

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

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

Группа в Телеграм: https://t.me/joinchat/seYgH4TaKrsxY2Yy

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

Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону,  по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел,  схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации. 

Необходимы предварительные знания: знакомство с основными вычислительными  моделями: машинами Тьюринга, вероятностными машинами Тьюринга  и схемами из функциональных элементов.

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

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

В домашних заданиях иногда будут даваться бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.

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

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

Сдать ДЗ лектору можно с помощью Google Meet https://meet.google.com/noy-cait-jph

Сдать ДЗ семинаристу можно ... .

Коллоквиум и письменный экзамен

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

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

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

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

Коллоквиум

Коллоквиум будет ... .

[ Программа коллоквиума.]

Экзамен

Пересдачи

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

Первое домашнее будет выложено 11 февраля, срок сдачи 4 марта.

Второе домашнее будет выложено 25 марта, крайний срок сдачи 15 апреля.

Третье домашнее будет выложено 22 апреля, крайний срок сдачи 13 мая.

Четвертое домашнее будет выложено 27 мая, крайний срок сдачи - 17 июня.

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

Домашнее задание 1 Cрок сдачи 4.03.2021

Домашнее задание 2 Срок сдачи 15.04.2021

Домашнее задание 3 Срок сдачи 13.05.2021

Домашнее задание 4 Срок сдачи 17.06.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 апреля).

Оценка Хэмминга. Линейные коды, проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. Оценка Гилберта.

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

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

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

Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.

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

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

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

Оценка Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.

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

Доказательство оценок Хэмминга и Гилберта. Деревья разрешения, метод противника. Сертификатная сложность. Чувстительность и блочная чувствительность. Неравенствo D < C^2

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

Вероятностные деревья и неравенство bs = O(R). Неравенствo D < C*bs. Неравенство C< bs*s.

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

Представление булевых функций многочленами с действительными коэффициентами. Теорема Маркова. Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди). Связь между чувствительностью и степенью многочлена (Hao Huang), без доказательства.

Семинары

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

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

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

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

Sensitivity for dummies (решение Sensitivity conjecture).

OWF2021

Содержание

Односторонние функции и их применения (4-ий курс ТИ) 2021 год

Новости

Контакты

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

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

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

Коллоквиум и письменный экзамен

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

Коллоквиум

Экзамен

Пересдачи

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

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

Результаты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Семинары

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

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

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

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

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

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

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

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

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

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

Семинар 11 (26 марта)

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

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

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

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

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

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

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

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

Семинар 20 (11 июня)

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

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

Навигация

Поиск