KKTI-22-23 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показаны 73 промежуточные версии 2 участников)
Строка 5: Строка 5:
 
zoom: https://us02web.zoom.us/j/82025733297?pwd=Znd2enF2S080Sk5LbjM0dndLWEFOdz09
 
zoom: https://us02web.zoom.us/j/82025733297?pwd=Znd2enF2S080Sk5LbjM0dndLWEFOdz09
  
−
Первая лекция и семинар 17 января!
+
[https://disk.yandex.com/d/8bXDWDka4x1Pnw Видео]
−
 
+
−
==Новости==
+
  
 
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com
 
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com
Строка 14: Строка 12:
  
 
Группа в Телеграм: https://t.me/+KV_zm22fF8FjMGYy
 
Группа в Телеграм: https://t.me/+KV_zm22fF8FjMGYy
 +
 +
[https://docs.google.com/spreadsheets/d/1oRNuNLUHtnQrhsHqVaQUxGfxZKkOSRctCgQkP7dqWJg/edit?usp=sharing Результаты]
 +
 +
==Новости==
 +
 +
 +
Экзамен (письменный) состоится 21 июня с 11 до 12:30 в ауд. D502.
 +
Для тех, кто не сможет присутствовать на экзамене очно ссылка на zoom: https://us02web.zoom.us/j/86147063668?pwd=cDVxRDVRY2xkeXF0K2NHZ2xiN2VGdz09.
 +
 +
Выложена [https://www.dropbox.com/s/6t64gokz0095o2d/colloq2023.pdf?dl=0 программа] коллоквиума 13 июня с 9:30 до 15:30 в ауд. G103. Для сдачи необходимо записаться в [https://docs.google.com/spreadsheets/d/1zaWfn-Xu4Lm8WW-LWbYrQBrlePJh54KzP5lTVhnb6ng/edit?usp=sharing таблицу].
 +
 +
Ссылка на zoom для сдающих онлайн: https://us02web.zoom.us/j/82025733297
 +
 +
Выложено первое домашнее задание.
 +
 +
Первая лекция и семинар 17 января!
  
 
==Краткое описание==
 
==Краткое описание==
Строка 23: Строка 37:
 
==Отчётность по курсу и критерии оценки==
 
==Отчётность по курсу и критерии оценки==
  
−
Итоговая оценка складывается из оценок за домашние задания и оценок за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентом 0.4, а оценка за домашние задания - с коэффициентом 0.2. Если произойдет очередной переход на он-лайн занятия и это случится до 1 апреля 2022 (включительно), то на лекциях, проводимых через Zoom, будут даваться тесты. В этом случае результаты тестов будут учитываться с коэффициентом 0.2, а доли коллоквиума и экзамена будут уменьшены до 0.3. 
+
Итоговая оценка складывается из оценок за домашние задания и оценок за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентом 0.4, а оценка за домашние задания - с коэффициентом 0.2.  
  
 
В домашних заданиях иногда будут бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.   
 
В домашних заданиях иногда будут бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.   
Строка 42: Строка 56:
 
====Коллоквиум====   
 
====Коллоквиум====   
  
−
Предварительная дата: 13 июня
+
Коллоквиум состоится 13 июня с 9:30 до 15:30 в ауд. G103.
−
[https://www.dropbox.com/s/z6k1vf2xwfr7jv8/colloq2022.pdf?dl=0 Программа коллоквиума.]
+
[https://www.dropbox.com/s/6t64gokz0095o2d/colloq2023.pdf?dl=0 Программа коллоквиума.]
 +
 
 +
Для сдачи коллоквиума нужно записаться в следующую [https://docs.google.com/spreadsheets/d/1zaWfn-Xu4Lm8WW-LWbYrQBrlePJh54KzP5lTVhnb6ng/edit?usp=sharing  таблицу], в которой указано время получения билета. В билете будет два теоретических вопроса,
 один про экспандеры, другой про коды, и вопрос на определение или формулировку теоремы. 
На подготовку ответа у Вас будет ровно час, во время которого можно пользоваться любыми бумажными источниками. 
Коллоквиум Вы 
сдаёте устно одному из преподавателей.
 Для уточнения оценки 
преподаватель может задавать дополнительные вопросы на знание определений и
 основных фактов курса.
 Оценка за коллоквиум формируется следующим образом.
 Полный ответ на каждый из теоретических 
вопросов оценивается в 4 балла, вопрос на определение --- в два балла.
 +
Во всех теоретических вопросах, содержащих формулировки теорем,
  надо знать и рассказать и их 
  доказательства.
  
 
====Экзамен====
 
====Экзамен====
  
−
Предварительная дата: 21 июня (сессия с 21 по 30 июня)
+
Экзамен (письменный) состоится 21 июня с 11 до 12:30 в ауд. D502. Можно пользоваться любыми бумажными материалами.
 +
 
 +
Студенты, сдающие экзамен он-лайн, решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
 Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
 Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен.
  
 
====Пересдачи====
 
====Пересдачи====
Строка 66: Строка 85:
  
 
==Домашние задания  ==
 
==Домашние задания  ==
 +
 +
[https://disk.yandex.com/i/kRJr4IPn3x_wXQ Домашнее задание 1] Срок сдачи: 7.03.2023
 +
 +
[https://disk.yandex.com/i/gmwszzOhy13w3Q Домашнее задание 2] Срок сдачи: 15.04.2023
 +
 +
[https://disk.yandex.com/i/gqiY0M__BQ6Oag Домашнее задание 3] Срок сдачи: 14.05.2023
 +
 +
[https://disk.yandex.com/i/2y_5ZWkpv-0jEg Домашнее задание 4] Срок сдачи: 18.06.2023
  
 
==Результаты ==
 
==Результаты ==
 +
[https://docs.google.com/spreadsheets/d/1oRNuNLUHtnQrhsHqVaQUxGfxZKkOSRctCgQkP7dqWJg Оценки за домашние задания, коллоквиум и экзамен]
  
−
==Планируемые лекции==
+
==Прочитанные лекции==
  
 
====Лекция 1 (17 января).  ====
 
====Лекция 1 (17 января).  ====
−
 
 
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
 
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
 
Реберное расширение и его связь с вершинным расширением.
 
Реберное расширение и его связь с вершинным расширением.
  
 
====Лекция 2 (24 января).  ====
 
====Лекция 2 (24 января).  ====
−
 
 
Матрица графа и ее собственные числа.
 
Матрица графа и ее собственные числа.
 
Максимальное по абсолютной величине собственное число регулярного графа.  От спектрального экспандера к комбинаторному.
 
Максимальное по абсолютной величине собственное число регулярного графа.  От спектрального экспандера к комбинаторному.
 
Лемма о перемешивании.  
 
Лемма о перемешивании.  
−
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.
 
  
 
====Лекция 3 (31 января).  ====
 
====Лекция 3 (31 января).  ====
 +
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.
 
Нижняя оценка  2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.  
 
Нижняя оценка  2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.  
  
−
Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами.
+
Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами (начало).
  
 
====Лекция 4 (7 февраля). ====
 
====Лекция 4 (7 февраля). ====
 +
Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами (завершение).
 
Степень графа и тензорное произведение графов и их собственные числа.  
 
Степень графа и тензорное произведение графов и их собственные числа.  
−
Зигзаг-произведение графов и первая оценка его собственных чисел.
+
Зигзаг-произведение графов и первая оценка его собственных чисел (начало). Видеозапись лекции: https://www.youtube.com/watch?v=0sKCkrV0jeY
  
 
====Лекция 5 (14 февраля). ====
 
====Лекция 5 (14 февраля). ====
 +
Первая оценка собственных чисел зигзаг произведения (окончание).
 
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
 
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
 
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
 
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
−
Вторая оценка для спектрального зазора зигзаг-произведения.  
+
Вторая оценка для спектрального зазора зигзаг-произведения.
  
 
====Лекция 6 (21 февраля). ====
 
====Лекция 6 (21 февраля). ====
Строка 109: Строка 137:
  
 
====Лекция 9 (14 марта). ====
 
====Лекция 9 (14 марта). ====
 +
Экспандер Маргулиса (окончание доказательства).
 
Двудольные экспандеры: определение и вероятностное доказательство существования.  
 
Двудольные экспандеры: определение и вероятностное доказательство существования.  
  
 
====Лекция 10 (21 марта). ====
 
====Лекция 10 (21 марта). ====
−
 
 
Экспандер Варди - Парвареша.
 
Экспандер Варди - Парвареша.
  
 
====Лекция 11 (4 апреля). ====
 
====Лекция 11 (4 апреля). ====
 
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.  
 
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.  
 +
Линейные коды. Оценка Хэмминга.
  
 
====Лекция 12 (11 апреля).  ====
 
====Лекция 12 (11 апреля).  ====
−
Оценка Хэмминга.
+
Проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. Оценка Гиблерта.
−
Линейные коды, проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.
+
Функция Шеннона и графики оценок Хэмминга и Гилберта
−
 
+
для произвольного алфавита. Оценка Варшамова - Гилберта.
  
 
====Лекция 13 (18 апреля) ====
 
====Лекция 13 (18 апреля) ====
−
 
+
Cлучайные линейные коды. Коды Возенкрафта.
−
Функция Шеннона и графики оценок Хэмминга и Гилберта
+
−
для произвольного алфавита. Оценка Варшамова - Гилберта. Случайные линейные коды. Коды Возенкрафта.
+
 
   
 
   
−
Каскадные коды.
+
Каскадные коды. Декодирование каскадного кода.  
  
 
====Лекция 14 (25 апреля) ====
 
====Лекция 14 (25 апреля) ====
−
Каскадные коды. Декодирование каскадного кода. Коды Форни.  
+
Коды Форни. Экспандерные коды: определение, последовательный алгоритм декодирования.  
  
 
====Лекция 15.  (16 мая) ====
 
====Лекция 15.  (16 мая) ====
−
Экспандерные коды: определение, последовательный алгоритм декодирования.
 
 
Первая оценка Плоткина для двоичного алфавита.
 
Первая оценка Плоткина для двоичного алфавита.
  
 
====Лекция 16  (23 мая) ====
 
====Лекция 16  (23 мая) ====
−
Оценки Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.
+
Оценки Плоткина и коды Адамара. Улучшение оценки Синглтона для обычного декодирования с исправлением ошибок.
  
 
====Лекция 17 (30 мая ) ====
 
====Лекция 17 (30 мая ) ====
−
Доказательство оценки Гилберта для декодирования списком.
+
Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.
−
Улучшение оценки Синглтона для обычного декодирования с исправлением ошибок.  
+
Кодовое расстояние и декодирование
−
Оценки Джонсона и Элайеса - Бассалыго.  
+
списком.
 +
Оценки Джонсона и Элайеса - Бассалыго. Декодирование списком кода Адамара.
  
 
====Лекция 18 (6 июня). ====
 
====Лекция 18 (6 июня). ====
 +
Декодирование списком кодов Рида - Соломона.
 +
Композиция кодов Рида - Соломона и Адамара.
 +
[https://www.youtube.com/playlist?list=PLo3cgfsnO72dlgkmUSZARDGY0hpjBRiy9 Видеозапись лекции]
  
−
Композиция кодов Рида - Соломона и Адамара и его декодирование списком.
+
==Планируемые лекции==
  
 
==Семинары  ==
 
==Семинары  ==
Строка 153: Строка 183:
 
=== Семинар 1 (17 января) ===
 
=== Семинар 1 (17 января) ===
 
[https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]
 
[https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]
 +
 +
=== Семинар 2 (24 января) ===
 +
[https://www.dropbox.com/s/pu34evbm8y2maqe/cw_2.pdf?dl=0 Листок 2  (спектр графов)]
 +
 +
=== Семинар 3 (31 января) ===
 +
[https://disk.yandex.com/i/uDwJFLoHoTX7yA Листок 3]
 +
 +
=== Семинар 4 (7 февраля) ===
 +
[https://drive.google.com/file/d/13-msSbArI1hB9OZaWm-r8IZFphJg5cw6/view?usp=sharing Листок 4]
 +
 +
=== Семинар 5 (14 февраля) ===
 +
[https://disk.yandex.com/i/knXdYXuxQveTpw Листок 5]
 +
 +
=== Семинар 6 (21 февраля) ===
 +
[https://disk.yandex.com/i/TwcqCNKj7r3LMw Листок 6]
 +
 +
=== Семинар 7 (28 февраля) ===
 +
[https://disk.yandex.com/i/PWpellxNlUqCaw Листок 7]
 +
 +
=== Семинар 8 (7 марта) ===
 +
[https://drive.google.com/file/d/1vEA8LpabEkZJVlxmHIsKghoN4eYwli9m/view?usp=sharing Листок 8]
 +
 +
=== Семинар 9 (14 марта) ===
 +
[https://disk.yandex.com/i/wVj1SU8049__lw Листок 9]
 +
 +
 +
=== Семинар 10 (21 марта) ===
 +
[https://disk.yandex.com/i/KIr9jV6_XkiNmw Листок 10]
 +
 +
=== Семинар 11 (4 апреля) ===
 +
[https://disk.yandex.com/i/2TujLV1mw2clIg Листок 11]
 +
 +
 +
=== Семинар 12 (11 апреля) ===
 +
[https://disk.yandex.com/i/48vcnsi2rjBN8w Листок 12]
 +
 +
=== Семинар 13 (18 апреля) ===
 +
[https://drive.google.com/file/d/1kqITKuAUsKmgyOwS_kwb7Ae4JrEXCqau/view?usp=sharing Листок 13]
 +
 +
=== Семинар 14 (25 апреля) ===
 +
[https://drive.google.com/file/d/1YVacYsaI-y-rpRW1pt6ZnSBqCwq8xkkr/view?usp=sharing Листок 14]
 +
 +
=== Семинар 15 (16 мая) ===
 +
[https://drive.google.com/file/d/141RLRmbm4DabrnS2ksrOWaRehOM7HBaN/view?usp=sharing Листок 15]
 +
 +
=== Семинар 16 (23 мая) ===
 +
[https://disk.yandex.com.ge/i/cZdb9GKKihxUGA Листок 16]
 +
 +
=== Семинар 17 (30 мая) ===
 +
[https://disk.yandex.com/i/BmLdOH21GRBp2w Листок 17]
 +
 +
=== Семинар 18 (6 июня) ===
 +
[https://disk.yandex.com/i/J534wZHs5xKZWA Листок 18]
  
 
==Конспекты лекций==
 
==Конспекты лекций==

Текущая версия на 22:41, 20 июня 2023

Содержание

Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2023 год

Лекции проходят по вторникам 11:10-12:30 ауд. N507, семинары также по вторникам 13:00-14:20 ауд. N507

zoom: https://us02web.zoom.us/j/82025733297?pwd=Znd2enF2S080Sk5LbjM0dndLWEFOdz09

Видео

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

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

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

Результаты

Новости

Экзамен (письменный) состоится 21 июня с 11 до 12:30 в ауд. D502. Для тех, кто не сможет присутствовать на экзамене очно ссылка на zoom: https://us02web.zoom.us/j/86147063668?pwd=cDVxRDVRY2xkeXF0K2NHZ2xiN2VGdz09.

Выложена программа коллоквиума 13 июня с 9:30 до 15:30 в ауд. G103. Для сдачи необходимо записаться в таблицу.

Ссылка на zoom для сдающих онлайн: https://us02web.zoom.us/j/82025733297

Выложено первое домашнее задание.

Первая лекция и семинар 17 января!

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

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

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

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

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

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

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

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

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

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

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

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

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

Коллоквиум

Коллоквиум состоится 13 июня с 9:30 до 15:30 в ауд. G103. Программа коллоквиума.

Для сдачи коллоквиума нужно записаться в следующую таблицу, в которой указано время получения билета. В билете будет два теоретических вопроса,
 один про экспандеры, другой про коды, и вопрос на определение или формулировку теоремы. 
На подготовку ответа у Вас будет ровно час, во время которого можно пользоваться любыми бумажными источниками. 
Коллоквиум Вы 
сдаёте устно одному из преподавателей.
 Для уточнения оценки 
преподаватель может задавать дополнительные вопросы на знание определений и
 основных фактов курса.
 Оценка за коллоквиум формируется следующим образом.
 Полный ответ на каждый из теоретических 
вопросов оценивается в 4 балла, вопрос на определение --- в два балла. Во всех теоретических вопросах, содержащих формулировки теорем,
 надо знать и рассказать и их 
 доказательства.

Экзамен

Экзамен (письменный) состоится 21 июня с 11 до 12:30 в ауд. D502. Можно пользоваться любыми бумажными материалами.

Студенты, сдающие экзамен он-лайн, решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
 Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
 Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен.

Пересдачи

Пересдачи состоятся ... . Пересдача комиссии ... .

Пересдать можно коллоквиум и/или письменный экзамен (ранее полученная оценка при этом аннулируется).

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

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

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

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

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

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

Домашнее задание 1 Срок сдачи: 7.03.2023

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

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

Домашнее задание 4 Срок сдачи: 18.06.2023

Результаты

Оценки за домашние задания, коллоквиум и экзамен

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

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

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

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

Матрица графа и ее собственные числа. Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному. Лемма о перемешивании.

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

Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа. Нижняя оценка 2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.

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

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

Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (завершение). Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов и первая оценка его собственных чисел (начало). Видеозапись лекции: https://www.youtube.com/watch?v=0sKCkrV0jeY

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

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

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

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

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

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

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

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

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

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

Экспандер Маргулиса (окончание доказательства). Двудольные экспандеры: определение и вероятностное доказательство существования.

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

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

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

Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. Линейные коды. Оценка Хэмминга.

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

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

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

Cлучайные линейные коды. Коды Возенкрафта.

Каскадные коды. Декодирование каскадного кода.

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

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

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

Первая оценка Плоткина для двоичного алфавита.

Лекция 16 (23 мая)

Оценки Плоткина и коды Адамара. Улучшение оценки Синглтона для обычного декодирования с исправлением ошибок.

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

Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта. Кодовое расстояние и декодирование списком. Оценки Джонсона и Элайеса - Бассалыго. Декодирование списком кода Адамара.

Лекция 18 (6 июня).

Декодирование списком кодов Рида - Соломона. Композиция кодов Рида - Соломона и Адамара. Видеозапись лекции

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

Семинары

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

Листок 1 (комбинаторные экспандеры)

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

Листок 2 (спектр графов)

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

Листок 3

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

Листок 4

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

Листок 5

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

Листок 6

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

Листок 7

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

Листок 8

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

Листок 9


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

Листок 10

Семинар 11 (4 апреля)

Листок 11


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

Листок 12

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

Листок 13

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

Листок 14

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

Листок 15

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

Листок 16

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

Листок 17

Семинар 18 (6 июня)

Листок 18

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

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

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

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

А.Е. Ромащенко. Экспандеры: конструкции и приложения.

Источник — «http://wiki.cs.hse.ru/index.php?title=KKTI-22-23&oldid=78538»