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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 1: Строка 1:
= Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2022 год =
+
= Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2023 год =
 
+
 
+
  
 
Лекции проходят по вторникам 11:10-12:30 ауд. N507, семинары также по вторникам 13:00-14:20 ауд. N507
 
Лекции проходят по вторникам 11:10-12:30 ауд. N507, семинары также по вторникам 13:00-14:20 ауд. N507
 
  
 
Первая лекция и семинар 17 января!
 
Первая лекция и семинар 17 января!
Строка 43: Строка 40:
 
====Коллоквиум====   
 
====Коллоквиум====   
  
 +
Предварительная дата: 13 июня
 
[https://www.dropbox.com/s/z6k1vf2xwfr7jv8/colloq2022.pdf?dl=0 Программа коллоквиума.]
 
[https://www.dropbox.com/s/z6k1vf2xwfr7jv8/colloq2022.pdf?dl=0 Программа коллоквиума.]
  
 
====Экзамен====
 
====Экзамен====
 +
 +
Предварительная дата: 21 июня (сессия с 21 по 30 июня)
  
 
====Пересдачи====
 
====Пересдачи====
Строка 67: Строка 67:
 
==Результаты ==
 
==Результаты ==
  
 +
==Планируемые лекции==
 +
 +
====Лекция 1 (17 января).  ====
 +
 +
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
 +
Реберное расширение и его связь с вершинным расширением.
 +
 +
====Лекция 2 (24 января).  ====
 +
 +
Матрица графа и ее собственные числа.
 +
Максимальное по абсолютной величине собственное число регулярного графа.  От спектрального экспандера к комбинаторному.
 +
Лемма о перемешивании.
 +
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.
 +
 +
====Лекция 3 (31 января).  ====
 +
Нижняя оценка  2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.
 +
 +
Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами.
 +
 +
====Лекция 4 (7 февраля). ====
 +
Степень графа и тензорное произведение графов и их собственные числа.
 +
Зигзаг-произведение графов и первая оценка его собственных чисел. https://zoom.us/rec/share/w2v90UsyP37UWW9gKdWiPyfIf_GSJSuG2pfqKNgfamWV8M24JVprbICyRHNob2r2.B9WF7cLBqode6WgN?startTime=1644573389000 (Passcode: 3.&CeGk&)
 +
 +
====Лекция 5 (14 февраля). ====
 +
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
 +
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
 +
Вторая оценка для спектрального зазора зигзаг-произведения.
 +
 +
====Лекция 6 (21 февраля). ====
 +
Второе собственное число связного недвудольного графа.
 +
 +
Алгоритм Рейнгольда.
 +
 +
====Лекция 7 (28 февраля). ====
 +
Применение экспандеров для дерандомизации.
 +
 +
====Лекция 8 (7 марта). ====
 +
Экспандер Маргулиса. https://us06web.zoom.us/rec/share/-aCtmQApQVyS0ba-762NYPsrGCPVm7AVOPuRgDRH-NnLmbn060f649Is2PrkXXPC.y48bojzyHWHkqPCB?startTime=1646992575000 (Код доступа: ^3YntU!t)
 +
 +
====Лекция 9 (14 марта). ====
 +
Двудольные экспандеры: определение и вероятностное доказательство существования. https://us06web.zoom.us/rec/share/lRohEAegryfNOxh9a6SuON9EKnoBoezJUtQuFyQjJ46mgGWSJbX3hUfM4N_e63BF.Sv-fP_hTizo9OIRX?startTime=1647597560000 (Код доступа: D*s+3!%K)
 +
 +
====Лекция 10 (21 марта). ====
 +
 +
Экспандер Варди - Парвареша. https://us06web.zoom.us/rec/share/S3TpwT6-nRuuL-OIKYpddFdNtNvvmRiOPdqs0fwXiuD2MbZ9E4Bgd3DsNDgmNh6e.H9ZywqG8i7ICkWIf?startTime=1648202267000 (Код доступа: 5P?UVs5z)
 +
 +
====Лекция 11 (4 апреля). ====
 +
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. https://us06web.zoom.us/rec/share/39A1_AduE88WzSIa5-QwBMlDozywjXMij1Q6_LGFf-cXUoMR1L9E_YO_zuyrs6At.Rdik0wA-JUqf90Tn?startTime=1649411730000 (Код доступа: 17!!K@TZ)
 +
https://us06web.zoom.us/rec/share/h6hTzwAc_2U3nPCm9t1554_GXXi8_NAI-_caGjx2gtDDUcOehuCangEENXf5uMI.52NW_PS9x0quz3ue?startTime=1649419086000
 +
 +
====Лекция 12 (11 апреля).  ====
 +
Оценка Хэмминга.
 +
Линейные коды, проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.
 +
Оценка Гилберта. Функция Шеннона. Графики оценок Хэмминга и Гилберта для двоичного алфавита. https://us06web.zoom.us/rec/share/24fS1mP-6LF46tQn9G4iP0EywiyMGBCXbHWfSHyZLC4MzNQNmMXfmm1Zdy6NIMA.TUOyTocg_q49eWud?startTime=1650627047000
 +
Код доступа: t^g85Y!A
 +
 +
====Лекция 13 (18 апреля) ====
 +
 +
Функция Шеннона и графики оценок Хэмминга и Гилберта
 +
для произвольного алфавита. Оценка Варшамова - Гилберта. Случайные линейные коды. Коды Возенкрафта.
 +
 +
Каскадные коды.
 +
 +
====Лекция 14 (25 апреля) ====
 +
Каскадные коды. Декодирование каскадного кода. Коды Форни. https://www.youtube.com/watch?v=6NXJVcnO-5k и https://www.youtube.com/watch?v=NE7dtzZOlWc
 +
 +
====Лекция 15.  (16 мая) ====
 +
Экспандерные коды: определение, последовательный алгоритм декодирования.
 +
Первая оценка Плоткина для двоичного алфавита.
 +
https://www.youtube.com/playlist?list=PLo3cgfsnO72ctaL2aza8xQ0ZA2S9SqW-c
 +
 +
====Лекция 16  (23 мая) ====
 +
Оценки Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.
 +
[https://drive.google.com/file/d/1BA5LJsAwV4-CjLhPn5-HFf9PhIU81WfF/view?usp=sharing Video]
 +
 +
====Лекция 17 (30 мая ) ====
 +
Доказательство оценки Гилберта для декодирования списком.
 +
Улучшение оценки Синглтона для обычного декодирования с исправлением ошибок.
 +
Оценки Джонсона и Элайеса - Бассалыго. [https://drive.google.com/file/d/1bxXB2I_5PrqQQzmISllWH3HSxm4DclIM/view?usp=sharing video]
 +
 +
====Лекция 18 (6 июня). ====
 +
 +
Композиция кодов Рида - Соломона и Адамара и его декодирование списком. [https://drive.google.com/file/d/1wHUig8m4Odjdh1JcxzF5K8-EZS-Sc_TU/view?usp=sharing видео]
  
 
==Семинары  ==
 
==Семинары  ==

Версия 12:15, 10 января 2023

Содержание

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

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

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

Новости

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

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

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

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

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

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

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

Итоговая оценка складывается из оценок за домашние задания и оценок за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентом 0.4, а оценка за домашние задания - с коэффициентом 0.2. Если произойдет очередной переход на он-лайн занятия и это случится до 1 апреля 2022 (включительно), то на лекциях, проводимых через Zoom, будут даваться тесты. В этом случае результаты тестов будут учитываться с коэффициентом 0.2, а доли коллоквиума и экзамена будут уменьшены до 0.3.

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

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

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

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

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

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

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

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

Коллоквиум

Предварительная дата: 13 июня Программа коллоквиума.

Экзамен

Предварительная дата: 21 июня (сессия с 21 по 30 июня)

Пересдачи

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

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

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

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

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

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

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

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

Результаты

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

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

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

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

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

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

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

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

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

Степень графа и тензорное произведение графов и их собственные числа. Зигзаг-произведение графов и первая оценка его собственных чисел. https://zoom.us/rec/share/w2v90UsyP37UWW9gKdWiPyfIf_GSJSuG2pfqKNgfamWV8M24JVprbICyRHNob2r2.B9WF7cLBqode6WgN?startTime=1644573389000 (Passcode: 3.&CeGk&)

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

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

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

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

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

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

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

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

Экспандер Маргулиса. https://us06web.zoom.us/rec/share/-aCtmQApQVyS0ba-762NYPsrGCPVm7AVOPuRgDRH-NnLmbn060f649Is2PrkXXPC.y48bojzyHWHkqPCB?startTime=1646992575000 (Код доступа: ^3YntU!t)

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

Двудольные экспандеры: определение и вероятностное доказательство существования. https://us06web.zoom.us/rec/share/lRohEAegryfNOxh9a6SuON9EKnoBoezJUtQuFyQjJ46mgGWSJbX3hUfM4N_e63BF.Sv-fP_hTizo9OIRX?startTime=1647597560000 (Код доступа: D*s+3!%K)

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

Экспандер Варди - Парвареша. https://us06web.zoom.us/rec/share/S3TpwT6-nRuuL-OIKYpddFdNtNvvmRiOPdqs0fwXiuD2MbZ9E4Bgd3DsNDgmNh6e.H9ZywqG8i7ICkWIf?startTime=1648202267000 (Код доступа: 5P?UVs5z)

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

Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. https://us06web.zoom.us/rec/share/39A1_AduE88WzSIa5-QwBMlDozywjXMij1Q6_LGFf-cXUoMR1L9E_YO_zuyrs6At.Rdik0wA-JUqf90Tn?startTime=1649411730000 (Код доступа: 17!!K@TZ) https://us06web.zoom.us/rec/share/h6hTzwAc_2U3nPCm9t1554_GXXi8_NAI-_caGjx2gtDDUcOehuCangEENXf5uMI.52NW_PS9x0quz3ue?startTime=1649419086000

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

Оценка Хэмминга. Линейные коды, проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. Оценка Гилберта. Функция Шеннона. Графики оценок Хэмминга и Гилберта для двоичного алфавита. https://us06web.zoom.us/rec/share/24fS1mP-6LF46tQn9G4iP0EywiyMGBCXbHWfSHyZLC4MzNQNmMXfmm1Zdy6NIMA.TUOyTocg_q49eWud?startTime=1650627047000 Код доступа: t^g85Y!A

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

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

Каскадные коды.

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

Каскадные коды. Декодирование каскадного кода. Коды Форни. https://www.youtube.com/watch?v=6NXJVcnO-5k и https://www.youtube.com/watch?v=NE7dtzZOlWc

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

Экспандерные коды: определение, последовательный алгоритм декодирования. Первая оценка Плоткина для двоичного алфавита. https://www.youtube.com/playlist?list=PLo3cgfsnO72ctaL2aza8xQ0ZA2S9SqW-c

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

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

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

Доказательство оценки Гилберта для декодирования списком. Улучшение оценки Синглтона для обычного декодирования с исправлением ошибок. Оценки Джонсона и Элайеса - Бассалыго. video

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

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

Семинары

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

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

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

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

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

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

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

Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995

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/