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

2023/2024

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

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

Статус:

Курс обязательный

Когда читается:

3-й курс, 3, 4 модуль

Преподаватели

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

Корнеев Сергей Александрович

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

Аннотация

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

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

• Целями освоения дисциплины «Сложность вычислений и логика в теоретической информатике» являются овладение студентами основными концепциями и результатами сложности вычислений и математической логики, применяемыми в теоретической информатике.

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

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

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

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

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

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

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

• 2023/2024 учебный год 4 модуль
  0.2 * Домашние задания + 0.4 * Коллоквиум + 0.4 * Экзамен

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

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

• Верещагин, Н. К. Языки и исчисления : учебное пособие / Н. К. Верещагин, А. Х. Шень. — 2-е изд. — Москва : ИНТУИТ, 2016. — 278 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100547 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Лекции по математической логике и теории алгоритмов. Ч.2: Языки и исчисления, Верещагин, Н. К., 2008

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

• MOSER, R. A., & TARDOS, G. (2010). A Constructive Proof of the General Lovász Local Lemma. Journal of the ACM, 57(2), 11–11:15. https://doi.org/10.1145/1667053.1667060