Алгебра и алгоритмы

Аннотация

Основная цель курса: показать взаимное влияние алгебры и computer science, по дороге напомнив/познакомив слушателей с важными понятиями теории сложности вычислений. С одной стороны, алгебраические подходы помогают в создании быстрых алгоритмов решения задач, изначально в алгебраических терминах не формулируемых. С другой стороны, есть важные алгебраические операции, которые сами по себе хотелось бы выполнять быстро. В курсе нам встретятся различные модели вычислений: самая популярная RAM-модель, известные схемы из функциональных элементов, а также двоичные решающие диаграммы, схемы параллельных процессоров и др.

Прочитанное на лекциях в осеннем семестре 2019–2020 учебного года

• Напоминания некоторых понятий из теории сложности. Задачи с битовым ответом («да-нетки»). Классы \(\mathrm{P}\) и \(\mathrm{NP}\). Определение класса \(\mathrm{NP}\) как класса задач, разрешимых за полиномиальное время на компьютере с неограниченным числом параллельно работающих процессоров. Классы \(\mathrm{NC}^{k}\) и \(\mathrm{NC}\). Параллельное вычисление префиксов «произведения» \(n\) элементов для ассоциативной операции. [Kozen, §28.3] Суммирование чисел в двоичной записи в классе \(\mathrm{NC}^1\). Умножение чисел в двоичной записи в классе \(\mathrm{NC}^1\). [Kozen, §30]
• Деление с остатком (алгоритм на основе метода Ньютона). [Kozen, §30]
• Обсуждение размера схем для арифметических операций. Схема субквадратичного размера для умножения чисел: алгоритм Карацубы—Офмана [Верещагин—Шень, §1.3, Теорема 13]. Оценки сложности «самой сложной функции». Асимптотически оптимальная схема для дешифратора (индукция → трюк meet-in-the-middle). Оптимальная схема для универсального многополюсника (произвольная схема → топологическая сортировка → устранение дублирования). Формула разложения булевой функции по нескольким переменным. Верхняя оценка сложности самой сложной функции \(10\cdot\frac{2^n}{n}\). [Wegener, §4.1, §4.2] [Верещагин—Шень, §1.3, Задача 13]
• Замечание о явной конструкции оптимального универсального многополюсника: сначала строим все ЭК, затем уже используем только элементы дизъюнкции для построения функций в порядке роста количества единиц в столбце значений. [??] Нижняя асимптотическая оценка функции Шеннона \(\const\cdot\frac{2^n}{n}\) (мощностной метод — если сложность маленькая, то схем не хватит): переходим от схем к помеченным деревьям; оцениваем число корневых непомеченных деревьев с помощью обхода в глубину, домножаем на число помечиваний. Эффект Шеннона: почти все функции сложны. Замечание о гигантской разнице между известными оценками для почти всех функций и нижними оценками для конкретных функций. [Wegener, §4.1, §4.2]
• Алгоритм Чанского (Csansky) вычисления определителя матрицы в классе \(\mathrm{NC}\) (сведение задачи об определителе к вычислению следов степеней матрицы и последующему решению «нижнетреугольной» СЛАУ). Замечание о разрешимости СЛАУ общего вида в \(\mathrm{NC}\). [Kozen, §31]
• Теорема Липтона—ДеМилло—Шварца—Зиппеля (лемма Шварца—Зиппеля). [Wikipedia] Применение леммы Шварца—Зиппеля к задаче о существовании совершенного паросочетания (вычисление определителя матрицы смежности двудольного графа) и задаче изоморфизма корневых деревьев. [Kozen, §40]
• Задача DLS (оптимизация аддитивной функции на семействе подмножеств конечного множества). Лемма об изолировании (теорема Малмали—Вазирани—Вазирани). [Ta-Shma] Вероятностный параллельный алгоритм нахождения совершенного паросочетания в двудольном графе [Motwani—Raghavan, §12.4.2]
• Применение подхода «разделяй и властвуй» в умножении матриц: алгоритм Штрассена. [Ахо—Хопкрофт—Ульман, §6.2]
• Задача построения транзитивного замыкания графа (отношения) и связь с умножением матриц. Метод Арлазарова—Диница—Кронрода—Фараджева для ускорения булева умножения матриц («алгоритм четырёх русских», Four Russians’ Algorithm). [Ахо—Хопкрофт—Ульман, §6.6]
• Связь сложности умножения матриц и ранга трилинейных форм. Вычислительная эквивалентность задач умножения матриц разного размера. [Алексеев (Обзор), §4–5]
• Алгоритм Тоома умножения чисел со сложностью \( O(n^{1+\epsilon}) \) для сколь угодно малого \( \epsilon \). [Алексеев, §2.4] Константа матричного умножения. НВП-разложение матрицы. Вычислительная эквивалентность задач обращения и умножения матриц. Быстрое вычисление определителя при наличии быстрого алгоритма умножения матриц. [Ахо—Хопкрофт—Ульман, §§6.3–6.5]
• Вероятностный алгоритм Фрейвалдса верификации умножения матриц с квадратичной сложностью. [Wikipedia] Теорема Татта: «физический» алгоритм укладки трёхсвязных планарных графов — без доказательства корректности. [Lovász], [слайды]
• Алгоритм PageRank: основная идея (интерпретации с «перераспределением репутационного веса» и «блужданием по графу интернета»), проблемы (с вершинами-стоками). Введение «телепортации» в качестве решения проблемы. [Büttcher—Clarke—Cormack, §15.3]
• Дискретное преобразование Фурье. Связь с задачей умножения многочленов и преобразованием сигналов в инвариантных по времени линейных системах. Алгоритм быстрого преобразования Фурье. [Дасгупта—Пападимитриу—Вазирани, §2.6]
• Линейное программирование. Двойственность в линейном программировании как существование сертификатов оптимальности. [Дасгупта—Пападимитриу—Вазирани, §7.4] Применение линейного программирования в задаче о вершинном покрытии графа. Простое округление в задаче о взвешенном вершинном покрытии графа. 2-приближённый алгоритм для вершинного покрытия, не использующий решение задачи линейного программирования. [Trevisan, §7]
• Задача о построении наименее плотного разреза (sparsest cut) в графе. Приближённый алгоритм решения задачи, основанный на собственных значениях лапласиана графа. [Matoušek, §31]
• Теорема Адамара, матрицы Адамара, гипотеза Адамара. Коды, исправляющие ошибки. Блочное кодирование. Коды Боуза—Шриханде на основе матриц Адамара (два вида). Граница Плоткина, её достижимость на кодах Боуза—Шриханде. Поле вычетов по простому модулю, примитивный элемент, квадратичные вычеты, символ Лежандра и его мультипликативность. Построение матрицы Адамара порядка \( p+1 \) при \( 4\mid (p+1)\) с помощью конструкции Пэли. [конспект лекций по теории кодирования], [Ромащенко—Румянцев—Шень]
• Теорема Баррингтона о построении BDD константной ширины и полиномиального размера по схеме из \(\mathrm{NC}^1\). [Wikipedia], [Lecture notes]

Некоторые темы лекций прошлых лет

• Решение дискретной задачи как вычисление набора булевых функций. Схемы из функциональных элементов (алгоритм → последовательность схем). Базисы \(B_0\) и \(B_2\). Меры сложности схем: размер и глубина. [Верещагин—Шень, §1.3, Теоремы 7 и 16] Сложность «самых сложных функций» от \(n\) аргументов. Верхняя оценка числа схем с данным числом входов и данной сложностью. Нижняя асимптотическая оценка \(\frac{2^n}{n}\) (мощностной метод — если сложность маленькая, то схем не хватит). Эффект Шеннона: почти все функции сложны. Замечание о гигантской разнице между известными оценками для почти всех функций и нижними оценками для конкретных функций. Нижняя оценка вида \(2n-3\) для функций-счётчиков \(\bmod 3\). [Wegener, §5.2] Асимптотически оптимальная схема для дешифратора (индукция → трюк meet-in-the-middle). Оптимальная схема для универсального многополюсника (произвольная схема → топологическая сортировка → устранение дублирования). Формула разложения булевой функции по нескольким переменным. Верхняя оценка сложности самой сложной функции \(10\cdot\frac{2^n}{n}\). [Wegener, §4.1, §4.2] Классы \(\mathrm{NC}\) и \(\mathrm{AC}\).
• Связь глубины и времени вычисления ответа схемой. Эквивалентность базисов с точки зрения порядка роста размера и глубины схем. Оценки глубины схем, построенных по формулам, через их размер. [Верещагин—Шень, §1.3, Теоремы 7 и 16]
• Теорема о рекуррентном неравенстве. [Cormen, §4.5]
• Теорема Вигдерсона о моделировании контактных схем схемами чётности. [Jukna 1st edition, Theorem 12.6]
• Классы \(\mathrm{RP}\), \(\mathrm{co‑RP}\) и \(\mathrm{ZPP}\). Равенство \(\mathrm{RP} \cap \mathrm{co‑RP} = \mathrm{ZPP}\). [Cai, §5.4] Теорема Липтона—ДеМилло—Шварца—Зиппеля (лемма Шварца—Зиппеля). Применение леммы Шварца—Зиппеля в задаче о существовании совершенного паросочетания (вычисление определителя матрицы смежности двудольного графа). [Kozen, §40]
• Вероятностный параллельный алгоритм нахождения совершенного паросочетания в двудольном графе [Motwani—Raghavan, §12.4.2]
• Задача построения транзитивного замыкания графа и связь с умножением матриц. Метод Арлазарова—Диница—Кронрода—Фараджева для ускорения булева умножения матриц («алгоритм четырёх русских», Four Russians’ Algorithm). [Ахо—Хопкрофт—Ульман, §6.6]
• Дискретное преобразование Фурье. Связь с задачей умножения многочленов. Замечание о применении в обработке сигналов. Алгоритм быстрого преобразования Фурье. [Дасгупта, §2.6] [Опционально: алгоритм Шёнхаге—Штрассена. [Ахо—Хопкрофт—Ульман, гл. 7]
• Понятие о задаче ранжирования в поисковых системах. Случайное блуждание по веб-графу: PageRank. Система линейных уравнений для его вычисления.
• Линейное программирование. Двойственность в линейном программировании как существование сертификатов оптимальности. Пример: задача о кратчайшем пути как задача о «растягивании графа из нитей» и двойственная к ней задача — задача о потоке наименьшей стоимости. [Дасгупта—Пападимитриу—Вазирани, §7.4]
• Применение линейного программирования в задаче о покрытии. Простое округление в задаче о взвешенном вершинном покрытии графа. Вероятностное округление в задаче о покрытии множеств. Основанный на двойственности комбинаторный алгоритм для задачи о взвешенном вершинном покрытии. [Trevisan, §7]
• Коды, исправляющие ошибки. Границы Хемминга и Плоткина. Матрицы Адамара. Набросок доказательства теоремы Адамара. Использование матриц Адамара для построения кодов, на которых достигается граница Плоткина. [Ромащенко—Румянцев—Шень]
• Однородные множества двоичных наборов. Построение однородных множеств на основе кодов Рида—Маллера. Применение \(3\)-однородных множеств для решения ослабленной задачи 3-выполнимости. [Дайняк, §9.3]
• Применение теории групп в информатике. Теорема Баррингтона о построении BDD константной ширины по булевой формуле с полиномиальным ростом сложности. [Wikipedia]

Литература

• В. Б. Алексеев. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002, 82 с.
• В. Б. Алексеев. Сложность умножения матриц. Обзор. // Кибернетический сборник, вып. 25. 1988.
• А. Ахо, Дж. Ульман, Дж. Хопкрофт. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. [Гл. 6,7]
• Н. К. Верещагин, А. Шень. Языки и исчисления. 4-е изд., испр., М.: МЦНМО, 2012, 240 с.
• А. Б. Дайняк. Конспект лекций по теории кодирования
• С. Дасгупта, Х. Пападимитриу, В. Вазирани. Алгоритмы. М.: МЦНМО, 2014.
• П. Ноден, К. Китте. Алгебраическая алгоритмика. М.: Мир, 1999.
• А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. М.: МЦНМО, 2011.
• А. Шень. Введение в теоретическую информатику, курс на платформе Stepik.
• S. Büttcher, C. L. A. Clarke, G. V. Cormack. Information Retrieval. Implementing and Evaluating Search Engines. MIT Press, 2010.
• J.-Y. Cai. Lectures in Computational Complexity. (Lecture notes).
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.
• S. Jukna. Extremal Combinatorics with Applications to Computer Science (1st edition). Springer, 2001.
• S. Jukna. Extremal Combinatorics with Applications to Computer Science (2nd edition). Springer, 2011.
• D. Kozen. Design and Analysis of Algorithms. Springer, 1991.
• L. Lovász. Geometric Representations of Graphs. Institute of Mathematics Eötvös Loránd University, Budapest. 2009.
• J. Matoušek. Thirty-three miniatures: mathematical and algorithmic applications of linear algebra. Springer, 2010.
• R. Motwani, P. Raghavan. Randomized algorithms. Cambridge University Press, 1995.
• M. Sudan. Algorithmic Introduction to Coding Theory. Lecture notes. MIT, 2001.
• N. Ta-Shma. A simple proof of the Isolation Lemma // ECCC Report TR15-080.
• L. Trevisan. Combinatorial Optimization: Exact and Approximate Algorithms. 2011.
• I. Wegener. The Complexity of Boolean Functions. Wiley, 1987.