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

Бакалавриат 2023/2024

Лучший по критерию «Новизна полученных знаний»

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

Направление: 01.03.02. Прикладная математика и информатика

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

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

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

Формат изучения: без онлайн-курса

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

Преподаватели: Верещагин Николай Константинович, Корнеев Сергей Александрович

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

Кредиты: 6

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

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

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

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

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

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

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

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением.
Матрица графа и ее собственные числа. Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному. Лемма о перемешивании.
Нижняя оценка 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 * Экзамен

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

Авторы

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

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