Комбинаторные конструкции в теоретической информатике

Бакалавриат 2026/2027

Статус: Курс по выбору (Прикладная математика и информатика)

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 3-й курс, 3, 4 модуль

Охват аудитории: для своего кампуса

Язык: русский

Кредиты: 6

Контактные часы: 80

Дополнительные материалы в LMS Задать вопрос

Аннотация

Графы-экспандеры являются одним из самых важных инструментов в теоретической информатики. Они используются при построении множества современных эффективных алгоритмов (например, алгоритма Рейнгольда поиска пути в графе), а также в доказательстве теорем (например, PCP-теорема). То же самое относится к кодам с исправлением ошибок - они используются при передаче информации по ненадежному каналу и, например, в построении односторонних функций. Овладение этими двумя техниками является необходимым умением современных специалистов в теоретической информатике.

Цель освоения дисциплины

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

Планируемые результаты обучения

Знание: • основные понятия и теоремы сложности вычислений; • основные понятия и теоремы математической логики; • методы доказательства разрешимости логических теорий; • основные понятия дискретной математики, линейной алгебры и математического анализа. • способы построения графов-экспандеров и их применения в сложности вычислений.
Умение: • пользоваться основными методами построения экспандеров; • пользоваться методами элиминации кванторов и игр Эренфойхта; • пользоваться понятиями чуствительности и блочной чуствительности; владеть: • навыками доказательства нижних оценок в сложности вычислений; • навыками доказательства верхних оценок в сложности вычислений; • методом дерандомизации вероятностных алгоритмов с попощью графов-экспандеров.
• Знание: • основные понятия и теоремы про экспандеры и коды с исправлением ошибок • способы построения графов экспандеров и их применения в теоретической информатике • способы построения кодов с исправлением ошибок и их применения в теоретической информатике • классические семейства экспандеров • классические коды с исправлением ошибок
Умение: • пользоваться основными методами построения экспандеров • пользоваться методом дерандомизации вероятностных алгоритмов с помощью графов-экспандеров • пользоваться методами построения кодов с исправление ошибок: конктатенаций кодов и суммой кодов

Содержание учебной дисциплины

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением.
Матрица графа и ее собственные числа. Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному. Лемма о перемешивании.
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.Нижняя оценка 2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами(начало).
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (завершение).Степень графа и тензорное произведение графов и их собственные числа.Зигзаг-произведение графов и первая оценка его собственных чисел(начало).
Первая оценка собственных чисел зигзаг произведения (окончание).Первая и вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин. Вторая оценка для спектрального зазора зигзаг-произведения.
Второе собственное число связного недвудольного графа. Алгоритм Рейнгольда.
Применение экспандеров для дерандомизации.
Экспандер Маргулиса.
Экспандер Маргулиса (окончание доказательства). Двудольные экспандеры: определение и вероятностное доказательство существования.
Экспандер Варди - Парвареша.
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время. Линейные коды. Оценка Хэмминга.
Проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга. Оценка Гиблерта. Функция Шеннона и графики оценок Хэмминга и Гилберта для произвольного алфавита. Оценка Варшамова - Гилберта.
Cлучайные линейные коды. Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.
Коды Форни. Экспандерные коды: определение, последовательный алгоритм декодирования.
Первая оценка Плоткина для двоичного алфавита.
Оценки Плоткина и коды Адамара. Улучшение оценки Синглтона для обычного декодирования с исправлением ошибок.
Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта. Кодовое расстояние и декодирование списком. Оценки Джонсона и Элайеса - Бассалыго. Декодирование списком кода Адамара.
Декодирование списком кодов Рида - Соломона. Композиция кодов Рида - Соломона и Адамара.

Элементы контроля

Экзамен
Коллоквиум
Домашние задания

Промежуточная аттестация

2026/2027 4th module
0.2 * Домашние задания + 0.4 * Коллоквиум + 0.4 * Экзамен

Список литературы

Авторы

Верещагин Николай Константинович

Программа дисциплины