KKTI-23-24
Содержание
- 1 Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2024 год
- 1.1 Новости
- 1.2 Краткое описание
- 1.3 Отчётность по курсу и критерии оценки
- 1.4 Примерные сроки контрольных мероприятий
- 1.5 Домашние задания
- 1.6 Результаты
- 1.7 Прочитанные лекции
- 1.7.1 Лекция 1 (13 февраля).
- 1.7.2 Лекция 2 (13 февраля).
- 1.7.3 Лекция 3 (20 февраля).
- 1.7.4 Лекция 4 (27 февраля).
- 1.7.5 Лекция 5 (5 марта).
- 1.7.6 Лекция 6 (5 марта).
- 1.7.7 Лекция 7 (12 марта).
- 1.7.8 Лекция 8 (12 марта).
- 1.7.9 Лекция 9 (19 марта).
- 1.7.10 Лекция 10 (19 марта).
- 1.7.11 Лекция 11 (2 апреля).
- 1.7.12 Лекция 12 (9 апреля).
- 1.7.13 Лекция 13 (16 апреля)
- 1.7.14 Лекция 14 (23 апреля)
- 1.7.15 Лекция 15. (30 апреля)
- 1.7.16 Лекция 16 (14 мая)
- 1.7.17 Лекция 17 (21 мая )
- 1.7.18 Лекция 18 (28 мая).
- 1.8 Планируемые лекции
- 1.9 Планируемые лекции
- 1.10 Семинары
- 1.10.1 Семинар 1 (17 января)
- 1.10.2 Семинар 2 (24 января)
- 1.10.3 Семинар 3 (31 января)
- 1.10.4 Семинар 4 (7 февраля)
- 1.10.5 Семинар 5 (14 февраля)
- 1.10.6 Семинар 6 (21 февраля)
- 1.10.7 Семинар 7 (28 февраля)
- 1.10.8 Семинар 8 (7 марта)
- 1.10.9 Семинар 9 (14 марта)
- 1.10.10 Семинар 10 (21 марта)
- 1.10.11 Семинар 11 (4 апреля)
- 1.10.12 Семинар 12 (11 апреля)
- 1.10.13 Семинар 13 (18 апреля)
- 1.10.14 Семинар 14 (25 апреля)
- 1.10.15 Семинар 15 (16 мая)
- 1.10.16 Семинар 16 (23 мая)
- 1.10.17 Семинар 17 (30 мая)
- 1.10.18 Семинар 18 (6 июня)
- 1.11 Конспекты лекций
- 1.12 Рекомендуемая литература
Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2024 год
Лекции проходят по вторникам на второй и третей парах в ауд. S326, семинары по пятницам онлайн (см. РУЗ) Первая лекция - 13 февраля
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com телеграм: https://t.me/nikolay_vereshchagin
Семинарист: Сергей Корнеев, SubjectNameHere4444@yandex.ru телеграм: https://t.me/SubjectNameHere4444
Группа в Телеграм: https://t.me/+KV_zm22fF8FjMGYy
Новости
Ссылки на экзаменационные варианты прошлых лет для подготовки к экзамену:
https://www.dropbox.com/s/120kgt6iyuzc1uz/exam_25_06_2021solutions.pdf?dl=0
https://www.dropbox.com/scl/fi/kn3mu8yhqb6t7v0knwvz7/exam.pdf?rlkey=rb95jnijdwk0i46h5tytmtdpi&dl=0
30 апреля и 14 мая лекции будут онлайн в обычное время. Ссылка для подключения: https://us06web.zoom.us/j/88978180287?pwd=HQfAHf1jtWGqtQup3YLLJf8RmcMbT3.1
Выложено Домашнее задание 1 Срок сдачи: 17 марта 2024
Выложено Домашнее задание 2 Срок сдачи: 7 апреля 2024
Выложено Домашнее задание 3 Срок сдачи: 3 мая 2024
Выложено Домашнее задание 4 Срок сдачи: 16 июня 2024
Обновление: первые две лекции будут в один день 13 февраля в ауд. D210 на 2 и 3 парах.
Первая лекция состоится 13 февраля в ауд. S222.
Краткое описание
Экспандеры и их применения: теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, построение генераторов псевдослучайных чисел, экспандерные коды.
Коды с исправлением ошибок для компьютерных наук.
Отчётность по курсу и критерии оценки
Итоговая оценка складывается из оценок за домашние задания, за колллоквиум, за экзамен и за дополнительные сложные задачи. Она вычисляется так, чтобы усердный студент, хорошо усвоивший курс, но не сделавший ни одной дополнительной задачи, получил 8 баллов. Оценки за домашние задания, за колллоквиум и за экзамен ставятся по десятибалльной системе. Дополнительные задачи входят в домашние задания и имеют специальные пометки, их будет всего четыре, по одной в каждом ДЗ. За каждую решеннную дополнительную задачу к итоговой оценке прибавляется 0.5 балла. Точнее, итоговая оценка выставляется по следующуй формуле MIN{8, 0.2*(оценка за домашние задания)+ 0.4*(оценка за коллоквиум)+ 0.4*(оценка за экзамен)} + (оценка за дополнительные задачи).
Домашние задания
В течение двух модулей студентам будет дано 4 домашних задания. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно сдавать семинаристу. Сдача домашних заданий после их срока невозможна.
Коллоквиум и письменный экзамен
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.
Правила округления
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.
Коллоквиум
Коллоквиум состоится 18 июня с 9:00 до 13:00 дистанционно. Программа коллоквиума.
Для сдачи коллоквиума нужно записаться в следующую таблицу, в которой указано время получения билета. В билете будет два теоретических вопроса, один про экспандеры, другой про коды, и вопрос на определение или формулировку теоремы. На подготовку ответа у Вас будет ровно час, во время которого можно пользоваться любыми бумажными источниками. Коллоквиум Вы сдаёте устно одному из преподавателей. Для уточнения оценки преподаватель может задавать дополнительные вопросы на знание определений и основных фактов курса. Оценка за коллоквиум формируется следующим образом. Полный ответ на каждый из теоретических вопросов оценивается в 4 балла, вопрос на определение --- в два балла. Во всех теоретических вопросах, содержащих формулировки теорем, надо знать и рассказать и их доказательства.
Экзамен
Экзамен (письменный) состоится 22 июня с 10 до 11:30 в ауд. T304. Можно пользоваться любыми бумажными материалами.
Студенты на дистанционном обучении решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Ссылка на подключение https://meet.google.com/hiq-otzf-sbx
Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ. Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен.
Ссылки на экзаменационные варианты прошлых лет для подготовки к экзамену:
https://www.dropbox.com/s/120kgt6iyuzc1uz/exam_25_06_2021solutions.pdf?dl=0
https://www.dropbox.com/scl/fi/kn3mu8yhqb6t7v0knwvz7/exam.pdf?rlkey=rb95jnijdwk0i46h5tytmtdpi&dl=0
Пересдачи
Пересдачи состоятся ... . Пересдача комиссии ... .
Пересдать можно коллоквиум и/или письменный экзамен (ранее полученная оценка при этом аннулируется).
Примерные сроки контрольных мероприятий
Первое домашнее задание будет выложено 3 марта, срок сдачи 17 марта.
Второе домашнее будет задание выложено 24 марта, срок сдачи 7 апреля.
Третье домашнее будет задание выложено 14 апреля, срок сдачи 28 апреля.
Четвертое домашнее задание будет выложено 2 июня, срок сдачи 16 июня.
Домашние задания
Домашнее задание 1 Срок сдачи: 17 марта 2024
Домашнее задание 2 Срок сдачи: 7 апреля 2024
Домашнее задание 3 Срок сдачи: 3 мая 2024
Домашнее задание 4 Срок сдачи: 16 июня 2024
Результаты
Оценки за домашние задания, коллоквиум и экзамен
Прочитанные лекции
Лекция 1 (13 февраля).
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением.
Лекция 2 (13 февраля).
Матрица графа и ее собственные числа. Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному. Лемма о перемешивании.
Лекция 3 (20 февраля).
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа. Нижняя оценка 2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (начало).
Лекция 4 (27 февраля).
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (завершение). Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов. Видеозапись лекции: https://www.youtube.com/watch?v=0sKCkrV0jeY
Лекция 5 (5 марта).
Первая оценка собственных чисел зигзаг произведения. Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. Вторая оценка для спектрального зазора зигзаг-произведения.
Лекция 6 (5 марта).
Второе собственное число связного недвудольного графа.
Алгоритм Рейнгольда (кратко).
Лекция 7 (12 марта).
Алгоритм Рейнгольда. Применение экспандеров для дерандомизации.
Лекция 8 (12 марта).
Экспандер Маргулиса.
Лекция 9 (19 марта).
Экспандер Маргулиса (окончание доказательства). Двудольные экспандеры: определение и вероятностное доказательство существования.
Лекция 10 (19 марта).
Экспандер Варди - Парвареша.
Лекция 11 (2 апреля).
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. Оценка Хэмминга.
Лекция 12 (9 апреля).
Линейные коды. Проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. Оценка Гилберта. Функция Шеннона и график оценки Хэмминга для произвольного алфавита. Оценка Варшамова - Гилберта.
Лекция 13 (16 апреля)
Оценка Гилберта. Ее график. Оценка Варшамова - Гилберта. Cлучайные линейные коды. Коды Возенкрафта.
Лекция 14 (23 апреля)
Каскадные коды. Декодирование каскадного кода. Коды Форни.
Лекция 15. (30 апреля)
Первая и вторая оценки Плоткина.
Лекция 16 (14 мая)
Улучшение оценки Синглтона с помощью оценки Плоткина. Коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.
Лекция 17 (21 мая )
Кодовое расстояние и декодирование списком. Декодирование списком кода Адамара. Оценка Джонсона. Видеозапись лекции
Лекция 18 (28 мая).
Оценка Элайеса - Бассалыго. Декодирование списком кодов Рида - Соломона. Видеозапись лекции
Планируемые лекции
Лекция 19 последняя (4 июня).
Экспандерные коды: определение, последовательный и параллельный алгоритмы декодирования.
Планируемые лекции
Семинары
Семинар 1 (17 января)
Листок 1 (комбинаторные экспандеры)
Семинар 2 (24 января)
Семинар 3 (31 января)
Семинар 4 (7 февраля)
Семинар 5 (14 февраля)
Семинар 6 (21 февраля)
Семинар 7 (28 февраля)
Семинар 8 (7 марта)
Семинар 9 (14 марта)
Семинар 10 (21 марта)
Семинар 11 (4 апреля)
Семинар 12 (11 апреля)
Семинар 13 (18 апреля)
Семинар 14 (25 апреля)
Семинар 15 (16 мая)
Семинар 16 (23 мая)
Семинар 17 (30 мая)
Семинар 18 (6 июня)
Конспекты лекций
Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко
Конспект лекций о кодах с исправлением ошибок (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."
