Дополнительные главы дискретной математики

Целью курса является изучение вероятностных, комбинаторных и алгебраических конструкций и методов, используемых в теоретической информатике
Возможные темы курса: экспандеры, коды, k-независимые множества, множества с малым смещением, энтропия, дизайны, мартингалы, конечные проективные плоскости и др.

Программа экзамена 2011

  1. Матрица графа, комбинаторный смысл ее собственных чисел. Алгебраический экспандер. Лемма о перемешивании.
  2. Свойство реберного расширения алгебраического экспандера.
  3. Нижняя оценка на второе собственное число.
  4. Существование алгебраических экспандеров: большинство $d$-регулярных графов являются экспандерами.
  5. Произведения графов: матричное произведение, тензорное произведение, простой и сбалансированный варианты подстановочного произведения, зигзаг-произведение.
    Оценка второго собственного числа в графе зигзаг-произведения. Явное построение экспандеров (рекурсивная конструкция с зигзаг-произведением).
  6. Оценка второго собственного числа для сбалансированного подстановочного произведения. Вторая явная конструкция экспандера (рекурсивная конструкция с подстановочным произведением).
  7. Вычисление спектра для графа аффинной плоскости. Использование графа аффинной плоскости в явных конструкцих экспандеров.
  8. Графы Кэли. Спектр графа Кэли для конечных абелевых групп. Примеры. Построение экспандера из кодов, исправляющих ошибки. Графы Рамунаджана (без доказательства).
  9. Понижение ошибки в $\rm RP$ и $\rm BPP$ : в полиномиальное число раз без использования дополнительных случайных битов. В экспоненциальное число раз с использованием случайных битов.
  10. Алгоритм Рейнголда: решение задачи UPATH детерминированным алгоритмом с логарифмической памятью.
  11. Коды, исправляющие ошибки. Границы Хемминга, Гилберта. Случайные коды. Линейные коды: граница Варшамова-Гилберта. Проверочная матрица, код Хемминга.
  12. Оценка Синглетона. Код Рида-Соломона. Алгоритм Берлекампа-Велча.
  13. Каскадные коды. Декодирующий алгоритм, позволяющий исправлять $d_1e_2$ ошибок.
  14. Теорема Форни. Код Форни-Возенкрафта-Юстенсена.
  15. Коды с большими расстояними. Оценка Плоткина.
  16. Код Адамара и его локальное декодирование. Каскадный код из кода Адамара и Рида-Соломона.
  17. Код Рида-Маллера и его локальное декодирование.
  18. Декодирование списоком при выполнении оценки Хемминга. Кодовое расстояние и декодирование списком.
  19. Декодирование списком кодов Адамара. Оценка Джонсона. Оценка Элайеса-Бассалыго.
  20. Декодирование списком кода Рида-Соломона. Декодирование списком каскадного года из Рида-Соломона и Адамара.
  21. Локальное декодирование списком для кодов Адамара.
  22. Локальное декодирование списком для кодов Рида-Маллера.
  23. Коды, основанные на экспандерах: коды Земора.
  24. Энтропия и ее свойства. Полуаддитивность. Оценка для $C_n^1+C_n^2+\dots+C_n^k$.
  25. Условная энтропия и ее свойства. Обобщенная полуаддитивность. Пересекающиеся множества и графы.
  26. Энтропия и однозначно декодируемые коды.
  27. Дизайны и их свойства. Семейство регулярных подмножеств. Разностные множества и дизайны. Разностное множество из квадратичных вычетов.
  28. Конечные геометрии. Конечные проективные и афинные плоскости, их свойства. Построение проективных плоскостей порядка $p^k$.
  29. Мартингалы. Мартингал проявления вершин и ребер. Неравенство Ацумы, пример о плотной концентрации хроматических чисел.
  30. Пример применения неравенства Ацумы: хроматическое число $G(n,p)$ сконцентрированно в четырех значениях.

Литература



  • Н. Алон, Дж. Спенсер. Вероятностный метод. БИНОМ, Лаборатория знаний, 2007.
  • S. Hoory, N. Linial, A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, vol. 43, Number 4, Oct. 2006, pp.439-561.
  • S. Arora, B. Barak. Computational Complexity: A modern Approach
  • S. Jukna. Exremal combinatorics.