KKTI-25-26: различия между версиями
Нет описания правки |
Нет описания правки |
||
| (не показаны 44 промежуточные версии 2 участников) | |||
| Строка 10: | Строка 10: | ||
Группа в Телеграм: https://t.me/+KV_zm22fF8FjMGYy | Группа в Телеграм: https://t.me/+KV_zm22fF8FjMGYy | ||
[ Результаты] | [https://docs.google.com/spreadsheets/d/1Yy_D3LUCmW0EOhpoX-VpZuzpdCIvmZBT/edit?usp=sharing&ouid=114867075298197812676&rtpof=true&sd=true Результаты] | ||
==Новости== | ==Новости== | ||
| Строка 44: | Строка 44: | ||
====Коллоквиум==== | ====Коллоквиум==== | ||
Коллоквиум состоится | Коллоквиум состоится 15 июня дистанционно. | ||
[https://www.dropbox.com/scl/fi/ | [https://www.dropbox.com/scl/fi/nyf1pk04js8op1zux02yw/colloq.pdf?rlkey=69whwpzuq3e7ngo172phq6t6f&st=q4nwam8w&dl=0 Программа коллоквиума.] | ||
Для сдачи коллоквиума нужно записаться в следующую | Для сдачи коллоквиума нужно записаться в следующую | ||
[таблицу], в которой указано время получения билета. В билете будет два теоретических вопроса,
один про экспандеры, другой про коды, и вопрос на определение или формулировку теоремы.
На подготовку ответа у Вас будет ровно час, во время которого можно пользоваться любыми бумажными источниками.
Коллоквиум Вы
сдаёте устно одному из преподавателей.
Для уточнения оценки
преподаватель может задавать дополнительные вопросы на знание определений и
основных фактов курса.
Оценка за коллоквиум формируется следующим образом.
Полный ответ на каждый из теоретических
вопросов оценивается в 4 балла, вопрос на определение --- в два балла. | [https://docs.google.com/spreadsheets/d/1vbVNb8XlrtPNlRnGlTI8zU-09uHQVIBtb0hgCJnqHtA/edit?usp=sharing таблицу], в которой указано время получения билета. В билете будет два теоретических вопроса,
один про экспандеры, другой про коды, и вопрос на определение или формулировку теоремы.
На подготовку ответа у Вас будет ровно час, во время которого можно пользоваться любыми бумажными источниками.
Коллоквиум Вы
сдаёте устно одному из преподавателей.
Для уточнения оценки
преподаватель может задавать дополнительные вопросы на знание определений и
основных фактов курса.
Оценка за коллоквиум формируется следующим образом.
Полный ответ на каждый из теоретических
вопросов оценивается в 4 балла, вопрос на определение --- в два балла. | ||
Во всех теоретических вопросах, содержащих формулировки теорем,
надо знать и рассказать и их
доказательства. | Во всех теоретических вопросах, содержащих формулировки теорем,
надо знать и рассказать и их
доказательства. | ||
====Экзамен==== | ====Экзамен==== | ||
Экзамен (письменный) состоится | Экзамен (письменный) состоится 20 июня с 11 до 12:30 в ауд. R308. Можно пользоваться любыми бумажными материалами. | ||
Студенты на дистанционном обучении решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Ссылка на подключение | Студенты на дистанционном обучении решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Ссылка на подключение | ||
| Строка 60: | Строка 60: | ||
Ссылки на экзаменационные варианты прошлых лет для подготовки к экзамену: | Ссылки на экзаменационные варианты прошлых лет для подготовки к экзамену: | ||
https://www.dropbox.com/scl/fi/yj9ut0k03pn5r59yifxh8/250925.pdf?rlkey=w9zwf95sct1vt9y5egb1jci4k&st=vnmo6sxi&dl=0 | |||
https://www.dropbox.com/scl/fi/nvy2aors2otwsn2pieqk4/250620.pdf?rlkey=cosb5ibfaafgy9332ewphk3hj&st=wmppvudb&dl=0 | |||
https://www.dropbox.com/scl/fi/cue6a9g5agi69fu61lcjo/240622.pdf?rlkey=95ujffdi17igi1ql5w6drdl8t&st=rm1fv8jv&dl=0 | |||
https://www.dropbox.com/s/120kgt6iyuzc1uz/exam_25_06_2021solutions.pdf?dl=0 | https://www.dropbox.com/s/120kgt6iyuzc1uz/exam_25_06_2021solutions.pdf?dl=0 | ||
| Строка 85: | Строка 91: | ||
====Пересдачи==== | ====Пересдачи==== | ||
Первая пересдача состоится | Первая пересдача состоится ... . Пересдача комиссии ... . | ||
Пересдать можно только письменный экзамен (ранее полученная оценка при этом аннулируется). | Пересдать можно только письменный экзамен (ранее полученная оценка при этом аннулируется). | ||
| Строка 91: | Строка 97: | ||
==Примерные сроки контрольных мероприятий== | ==Примерные сроки контрольных мероприятий== | ||
Первое домашнее задание будет выложено | Первое домашнее задание будет выложено 27 февраля, срок сдачи 13 марта. | ||
Второе домашнее будет задание выложено | Второе домашнее будет задание выложено 20 марта, срок сдачи 3 апреля. | ||
Третье домашнее будет задание выложено | Третье домашнее будет задание выложено 24 апреля, срок сдачи 10 мая. | ||
Четвёртое домашнее будет задание выложено | Четвёртое домашнее будет задание выложено 31 мая, срок сдачи 14 июня. | ||
==Домашние задания == | ==Домашние задания == | ||
[Домашнее задание 1] Срок сдачи: ... | [https://www.dropbox.com/scl/fi/14a1hzpq89vfy00gh8v19/hw1-3.pdf?rlkey=m0a3h4qasgya27h1pbvqt09l3&st=sdhxo859&dl=0 Домашнее задание 1] Срок сдачи: 13 марта. | ||
[https://www.dropbox.com/scl/fi/j2gcpth7zsehbbpemjz5y/hw2.pdf?rlkey=lv0js7vz8bf0yx4wcqski9v2j&st=rsn2cg50&dl=0 Домашнее задание 2] Срок сдачи: 3 апреля. | |||
[https://www.dropbox.com/scl/fi/5gws1e9dkuhqusc87ifeb/hw3.pdf?rlkey=go8fd6ojhnls0ut6hvir2uk60&st=10eu7quu&dl=0 Домашнее задание 3] Срок сдачи: 10 мая. | |||
[https://www.dropbox.com/scl/fi/v6u9yrsvqxdau9orn46g3/hw4.pdf?rlkey=rpnd6wxj5z7fbg7ie84p835fa&st=pgnmivwt&dl=0 Домашнее задание 4] Срок сдачи: 14 июня. | |||
==Результаты == | ==Результаты == | ||
[Оценки за домашние задания, коллоквиум и экзамен] | [https://docs.google.com/spreadsheets/d/1Yy_D3LUCmW0EOhpoX-VpZuzpdCIvmZBT/edit?usp=sharing&ouid=114867075298197812676&rtpof=true&sd=true Оценки за домашние задания, коллоквиум и экзамен] | ||
== | ==Прочитанные лекции== | ||
====Лекция 1 (19 января). ==== | ====Лекция 1 (19 января). ==== | ||
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). | Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). | ||
====Лекция 2 (26 января). ==== | |||
Реберное расширение и его связь с вершинным расширением. | Реберное расширение и его связь с вершинным расширением. | ||
Матрица графа и ее собственные числа. | Матрица графа и ее собственные числа. | ||
Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному. | Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному. | ||
Лемма о перемешивании. | Лемма о перемешивании. | ||
====Лекция 3 (2 февраля). ==== | ====Лекция 3 (2 февраля). ==== | ||
| Строка 122: | Строка 134: | ||
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (начало). | Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (начало). | ||
====Лекция 4 (9 февраля). ==== | |||
====Лекция 4 ( | |||
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (завершение). | Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (завершение). | ||
Степень графа и тензорное произведение графов и их собственные числа. | Степень графа и тензорное произведение графов и их собственные числа. | ||
Зигзаг-произведение графов. Видеозапись лекции: https://www.youtube.com/watch?v=0sKCkrV0jeY | Зигзаг-произведение графов. Видеозапись лекции: https://www.youtube.com/watch?v=0sKCkrV0jeY | ||
====Лекция 5 ( | |||
====Лекция 5 (16 февраля). ==== | |||
Первая оценка собственных чисел зигзаг произведения. | Первая оценка собственных чисел зигзаг произведения. | ||
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. | Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. | ||
====Лекция 6 (25 февраля). ==== | |||
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. | Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. | ||
Вторая оценка для спектрального зазора зигзаг-произведения. | Вторая оценка для спектрального зазора зигзаг-произведения. | ||
====Лекция | ====Лекция 7 (2 марта). ==== | ||
Второе собственное число связного недвудольного графа. | Второе собственное число связного недвудольного графа. | ||
Алгоритм Рейнгольда. | |||
====Лекция 9 (11 марта). ==== | |||
====Лекция | Экспандер Маргулиса. | ||
====Лекция 8 (16 марта). ==== | |||
Применение экспандеров для дерандомизации. | Экспандер Маргулиса (окончание доказательства). | ||
Применение экспандеров для дерандомизации (без дополнительной случайности). | |||
====Лекция | ====Лекция 9 (23 марта). ==== | ||
Применение экспандеров для дерандомизации (случайное блуждание). | |||
Двудольные экспандеры: определение и вероятностное доказательство существования. | Двудольные экспандеры: определение и вероятностное доказательство существования. | ||
====Лекция 10 ( | ====Лекция 10 (6 апреля). ==== | ||
Экспандер Варди - Парвареша. | Экспандер Варди - Парвареша. | ||
====Лекция 11 ( | ====Лекция 11 (13 апреля). ==== | ||
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. | Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. | ||
====Лекция 12 ( | ====Лекция 12 (20 апреля). ==== | ||
Оценка Хэмминга. | Оценка Хэмминга. | ||
Линейные коды. Проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. Оценка Гилберта. | Линейные коды. Проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. | ||
Функция Шеннона для двоичного алфавита. | |||
====Лекция 13 (27 апреля) ==== | |||
График оценки Хэмминга для произвольного алфавита. | |||
Оценка Гилберта. | |||
Оценка Варшамова - Гилберта. | Оценка Варшамова - Гилберта. | ||
Cлучайные линейные коды. | |||
====Лекция 14 (18 мая) ==== | |||
Коды Возенкрафта. | |||
Каскадные коды. | |||
Коды Форни. | |||
====Лекция 15. (25 мая) ==== | |||
Декодирование каскадного кода. | |||
Геометрические факты к первой оценке Плоткина. | |||
====Лекция | ====Лекция 16 (27 мая) ==== | ||
Первая | Первая оценка Плоткина. Геометрический факт для второй оценки Плоткина и сама оценка. | ||
Улучшение оценки Синглтона с помощью оценки Плоткина. | Улучшение оценки Синглтона с помощью оценки Плоткина. | ||
Коды Адамара. | Коды Адамара. | ||
====Лекция 17 (1 июня ) ==== | |||
Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта. | |||
Кодовое расстояние и декодирование списком. Декодирование списком кода Адамара. | Кодовое расстояние и декодирование списком. Декодирование списком кода Адамара. | ||
[https://youtu.be/XQghOUCsQRs Видеозапись лекции] | |||
====Лекция 18 ( | ==Планируемые лекции== | ||
====Лекция 18 (8 июня). ==== | |||
Оценка Джонсона. | |||
Оценка Элайеса - Бассалыго. | Оценка Элайеса - Бассалыго. | ||
Декодирование списком кодов Рида - Соломона. | Декодирование списком кодов Рида - Соломона. | ||
[https://www.youtube.com/watch?v=-WxESbNqy_Y Видеозапись лекции] | [https://www.youtube.com/watch?v=-WxESbNqy_Y Видеозапись лекции] | ||
==Семинары == | ==Семинары == | ||
=== Семинар 1 ( | === Семинар 1 (19 января) === | ||
[https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1 (комбинаторные экспандеры)] | [https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1 (комбинаторные экспандеры)] | ||
=== Семинар 2 ( | === Семинар 2 (26 января) === | ||
[https://www.dropbox.com/s/pu34evbm8y2maqe/cw_2.pdf?dl=0 Листок 2 (спектр графов)] | [https://www.dropbox.com/s/pu34evbm8y2maqe/cw_2.pdf?dl=0 Листок 2 (спектр графов)] | ||
=== Семинар 3 ( | === Семинар 3 (2 февраля) === | ||
[https://disk.yandex.com/i/uDwJFLoHoTX7yA Листок 3] | [https://disk.yandex.com/i/uDwJFLoHoTX7yA Листок 3] | ||
=== Семинар 4 ( | === Семинар 4 (9 февраля) === | ||
[https://drive.google.com/file/d/13-msSbArI1hB9OZaWm-r8IZFphJg5cw6/view?usp=sharing Листок 4] | [https://drive.google.com/file/d/13-msSbArI1hB9OZaWm-r8IZFphJg5cw6/view?usp=sharing Листок 4] | ||
=== Семинар 5 ( | === Семинар 5 (16 февраля) === | ||
[https://disk.yandex.com/i/knXdYXuxQveTpw Листок 5] | [https://disk.yandex.com/i/knXdYXuxQveTpw Листок 5] | ||
=== Семинар 6 ( | === Семинар 6 (25 февраля) === | ||
[https://disk.yandex.com/i/TwcqCNKj7r3LMw Листок 6] | [https://disk.yandex.com/i/TwcqCNKj7r3LMw Листок 6] | ||
=== Семинар 7 ( | === Семинар 7 (2 марта) === | ||
[https://disk.yandex.com/i/PWpellxNlUqCaw Листок 7] | [https://disk.yandex.com/i/PWpellxNlUqCaw Листок 7] | ||
=== Семинар 8 ( | === Семинар 8 (11 марта) === | ||
[https://drive.google.com/file/d/1vEA8LpabEkZJVlxmHIsKghoN4eYwli9m/view?usp=sharing Листок 8] | [https://drive.google.com/file/d/1vEA8LpabEkZJVlxmHIsKghoN4eYwli9m/view?usp=sharing Листок 8] | ||
=== Семинар 9 ( | === Семинар 9 (16 марта) === | ||
[https://disk.yandex.com/i/wVj1SU8049__lw Листок 9] | [https://disk.yandex.com/i/wVj1SU8049__lw Листок 9] | ||
=== Семинар 10 ( | === Семинар 10 () === | ||
[https://disk.yandex.com/i/KIr9jV6_XkiNmw Листок 10] | [https://disk.yandex.com/i/KIr9jV6_XkiNmw Листок 10] | ||
=== Семинар 11 ( | === Семинар 11 () === | ||
[https://disk.yandex.com/i/2TujLV1mw2clIg Листок 11] | [https://disk.yandex.com/i/2TujLV1mw2clIg Листок 11] | ||
=== Семинар 12 ( | === Семинар 12 () === | ||
[https://disk.yandex.com/i/48vcnsi2rjBN8w Листок 12] | [https://disk.yandex.com/i/48vcnsi2rjBN8w Листок 12] | ||
=== Семинар 13 ( | === Семинар 13 () === | ||
[https://drive.google.com/file/d/1kqITKuAUsKmgyOwS_kwb7Ae4JrEXCqau/view?usp=sharing Листок 13] | [https://drive.google.com/file/d/1kqITKuAUsKmgyOwS_kwb7Ae4JrEXCqau/view?usp=sharing Листок 13] | ||
=== Семинар 14 ( | === Семинар 14 () === | ||
[https://drive.google.com/file/d/1YVacYsaI-y-rpRW1pt6ZnSBqCwq8xkkr/view?usp=sharing Листок 14] | [https://drive.google.com/file/d/1YVacYsaI-y-rpRW1pt6ZnSBqCwq8xkkr/view?usp=sharing Листок 14] | ||
=== Семинар 15 ( | === Семинар 15 () === | ||
[https://drive.google.com/file/d/141RLRmbm4DabrnS2ksrOWaRehOM7HBaN/view?usp=sharing Листок 15] | [https://drive.google.com/file/d/141RLRmbm4DabrnS2ksrOWaRehOM7HBaN/view?usp=sharing Листок 15] | ||
=== Семинар 16 ( | === Семинар 16 () === | ||
[https://disk.yandex.com.ge/i/cZdb9GKKihxUGA Листок 16] | [https://disk.yandex.com.ge/i/cZdb9GKKihxUGA Листок 16] | ||
=== Семинар 17 ( | === Семинар 17 () === | ||
[https://disk.yandex.com/i/BmLdOH21GRBp2w Листок 17] | [https://disk.yandex.com/i/BmLdOH21GRBp2w Листок 17] | ||
=== Семинар 18 ( | === Семинар 18 () === | ||
[https://disk.yandex.com/i/J534wZHs5xKZWA Листок 18] | [https://disk.yandex.com/i/J534wZHs5xKZWA Листок 18] | ||
Текущая версия от 09:04, 10 июня 2026
Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2026 год
Лекции проходят по понедельникам на четвертой паре в ауд. S328, семинары по понедельникам на пятой паре в S330. Первая лекция - 19 января, первый семинар 19 января.
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com телеграм: https://t.me/nikolay_vereshchagin
Семинарист: Сергей Корнеев, SubjectNameHere4444@yandex.ru телеграм: https://t.me/SubjectNameHere4444
Группа в Телеграм: https://t.me/+KV_zm22fF8FjMGYy
Новости
Краткое описание
Экспандеры и их применения: теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, построение генераторов псевдослучайных чисел, экспандерные коды.
Коды с исправлением ошибок для компьютерных наук.
Отчётность по курсу и критерии оценки
Итоговая оценка складывается из оценок за домашние задания, за колллоквиум, за экзамен и за дополнительные сложные задачи. Она вычисляется так, чтобы усердный студент, хорошо усвоивший курс, но не сделавший ни одной дополнительной задачи, получил 8 баллов. Оценки за домашние задания, за колллоквиум и за экзамен ставятся по десятибалльной системе. Дополнительные задачи входят в домашние задания и имеют специальные пометки, их будет всего четыре, по одной в каждом ДЗ. За каждую решеннную дополнительную задачу к итоговой оценке прибавляется 0.5 балла, при условии, что эта оценка равна 8. Точнее, итоговая оценка выставляется по следующуй формуле MIN{8, 0.2*(оценка за домашние задания)+ 0.4*(оценка за коллоквиум)+ 0.4*(оценка за экзамен)} + (оценка за дополнительные задачи, если этот минимум равен 8).
Домашние задания
В течение двух модулей студентам будет дано 4 домашних задания. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно сдавать семинаристу. Сдача домашних заданий после их срока невозможна.
Коллоквиум и письменный экзамен
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.
Правила округления
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.
Коллоквиум
Коллоквиум состоится 15 июня дистанционно. Программа коллоквиума.
Для сдачи коллоквиума нужно записаться в следующую таблицу, в которой указано время получения билета. В билете будет два теоретических вопроса, один про экспандеры, другой про коды, и вопрос на определение или формулировку теоремы. На подготовку ответа у Вас будет ровно час, во время которого можно пользоваться любыми бумажными источниками. Коллоквиум Вы сдаёте устно одному из преподавателей. Для уточнения оценки преподаватель может задавать дополнительные вопросы на знание определений и основных фактов курса. Оценка за коллоквиум формируется следующим образом. Полный ответ на каждый из теоретических вопросов оценивается в 4 балла, вопрос на определение --- в два балла. Во всех теоретических вопросах, содержащих формулировки теорем, надо знать и рассказать и их доказательства.
Экзамен
Экзамен (письменный) состоится 20 июня с 11 до 12:30 в ауд. R308. Можно пользоваться любыми бумажными материалами.
Студенты на дистанционном обучении решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Ссылка на подключение
Черновики отсылать не надо. Крайний срок посылки - 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
https://www.dropbox.com/scl/fi/kn3mu8yhqb6t7v0knwvz7/200622.pdf?rlkey=rb95jnijdwk0i46h5tytmtdpi&dl=0
Пересдачи
Первая пересдача состоится ... . Пересдача комиссии ... .
Пересдать можно только письменный экзамен (ранее полученная оценка при этом аннулируется).
Примерные сроки контрольных мероприятий
Первое домашнее задание будет выложено 27 февраля, срок сдачи 13 марта.
Второе домашнее будет задание выложено 20 марта, срок сдачи 3 апреля.
Третье домашнее будет задание выложено 24 апреля, срок сдачи 10 мая.
Четвёртое домашнее будет задание выложено 31 мая, срок сдачи 14 июня.
Домашние задания
Домашнее задание 1 Срок сдачи: 13 марта.
Домашнее задание 2 Срок сдачи: 3 апреля.
Домашнее задание 3 Срок сдачи: 10 мая.
Домашнее задание 4 Срок сдачи: 14 июня.
Результаты
Оценки за домашние задания, коллоквиум и экзамен
Прочитанные лекции
Лекция 1 (19 января).
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
Лекция 2 (26 января).
Реберное расширение и его связь с вершинным расширением.
Матрица графа и ее собственные числа. Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному. Лемма о перемешивании.
Лекция 3 (2 февраля).
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа. Нижняя оценка 2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (начало).
Лекция 4 (9 февраля).
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (завершение). Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов. Видеозапись лекции: https://www.youtube.com/watch?v=0sKCkrV0jeY
Лекция 5 (16 февраля).
Первая оценка собственных чисел зигзаг произведения. Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
Лекция 6 (25 февраля).
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
Вторая оценка для спектрального зазора зигзаг-произведения.
Лекция 7 (2 марта).
Второе собственное число связного недвудольного графа. Алгоритм Рейнгольда.
Лекция 9 (11 марта).
Экспандер Маргулиса.
Лекция 8 (16 марта).
Экспандер Маргулиса (окончание доказательства). Применение экспандеров для дерандомизации (без дополнительной случайности).
Лекция 9 (23 марта).
Применение экспандеров для дерандомизации (случайное блуждание).
Двудольные экспандеры: определение и вероятностное доказательство существования.
Лекция 10 (6 апреля).
Экспандер Варди - Парвареша.
Лекция 11 (13 апреля).
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.
Лекция 12 (20 апреля).
Оценка Хэмминга. Линейные коды. Проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. Функция Шеннона для двоичного алфавита.
Лекция 13 (27 апреля)
График оценки Хэмминга для произвольного алфавита.
Оценка Гилберта. Оценка Варшамова - Гилберта.
Cлучайные линейные коды.
Лекция 14 (18 мая)
Коды Возенкрафта.
Каскадные коды. Коды Форни.
Лекция 15. (25 мая)
Декодирование каскадного кода. Геометрические факты к первой оценке Плоткина.
Лекция 16 (27 мая)
Первая оценка Плоткина. Геометрический факт для второй оценки Плоткина и сама оценка.
Улучшение оценки Синглтона с помощью оценки Плоткина. Коды Адамара.
Лекция 17 (1 июня )
Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта. Кодовое расстояние и декодирование списком. Декодирование списком кода Адамара. Видеозапись лекции
Планируемые лекции
Лекция 18 (8 июня).
Оценка Джонсона. Оценка Элайеса - Бассалыго. Декодирование списком кодов Рида - Соломона. Видеозапись лекции
Семинары
Семинар 1 (19 января)
Листок 1 (комбинаторные экспандеры)
Семинар 2 (26 января)
Семинар 3 (2 февраля)
Семинар 4 (9 февраля)
Семинар 5 (16 февраля)
Семинар 6 (25 февраля)
Семинар 7 (2 марта)
Семинар 8 (11 марта)
Семинар 9 (16 марта)
Семинар 10 ()
Семинар 11 ()
Семинар 12 ()
Семинар 13 ()
Семинар 14 ()
Семинар 15 ()
Семинар 16 ()
Семинар 17 ()
Семинар 18 ()
Конспекты лекций
Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко
Конспект лекций о кодах с исправлением ошибок (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."