• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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 * Экзамен
Список литературы

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

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

  • Верещагин, Н. К. Языки и исчисления : учебное пособие / Н. К. Верещагин, А. Х. Шень. — 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

Авторы

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