algorithms.tex

\documentclass[a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[english, russian]{babel}
\usepackage[fleqn]{amsmath}
\usepackage{amsfonts, amssymb, amsthm, mathtools}

\usepackage{mathtools}
\usepackage{fullpage}
\usepackage[colorinlistoftodos]{todonotes}


\title{Алгоритмы и структуры данных}
\author{MIPT DIHT}
\begin{document}
\maketitle

\section{Сортировки}
\subsection{Quick Sort}
\subsubsection{Шаги}
\begin{itemize}
	\item  Выбираем в массиве некоторый элемент, который будем называть опорным элементом. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом. Часто хороший результат даёт выбор в качестве опорного элемента среднего арифметического между минимальным и максимальным элементами массива.
	\item Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
	\begin{enumerate}
		\item Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
		\item Вычисляется индекс опорного элемента m.
		\item Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
		\item Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
		\item Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
		\item Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
	\end{enumerate}
	\item Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
\subsubsection{Оценка сложности}
Разделение массива: O(n). \\
\textbf{Лучший случай} \\
Массив делится на две почти одинаковые части, максимальная глубина рекурсии $\log_2 n$. Количество сравнений: $C_n = 2 \cdot C_{n/2} + n$, что даёт общую сложность $O(n \cdot \log_2 n)$. \\
\textbf{Среднее} \\
Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно.
Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 процентов и 25 процентов от исходного, глубина рекурсии будет равна $\log_{4/3} n$, а это по-прежнему даёт сложность $O(n \log n)$. Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами. \\
Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 процентов элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 процентов и не более 75 процентов от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива. \\
Удачное разделение даёт глубину рекурсии не более $\log_{4/3} n$. Поскольку вероятность удачи равна 0,5, для получения k удачных разделений в среднем потребуется $2 \cdot k$ рекурсивных вызовов, чтобы опорный элемент k раз оказался среди центральных 50 процентов массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит $2 \cdot \log_{4/3} n$, что равно $O(\log n)$ А поскольку на каждом уровне рекурсии по-прежнему выполняется не более O(n) операций, средняя сложность составит $O(n \log n)$. \\
\textbf{Худший случай} \\
В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и n-1, то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента — первого или последнего в массиве, — такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется n-1 операций разделения, а общее время работы составит $\sum_{i=0}^n (n-i) = O(n^2)$ операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.

\end{itemize}


\subsection{Merge Sort}
Пример использования принципа «разделяй и властвуй»
\begin{enumerate}
	\item Рекурсивное разбиение задачи на меньшие до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным)
	\begin{itemize}
		\item Сортируемый массив разбивается на две части примерно одинакового размера;
		\item Два упорядоченных массива половинного размера соединяются в один.
	\end{itemize}
	\item Слияние. Пусть мы имеем два уже отсортированных по возрастанию подмассива. Тогда
	\begin{itemize}
		\item На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.
		\item «Прицепление» остатка.
		\item Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.
	\end{itemize}
\end{enumerate}
Время работы алгоритма порядка $O(n \log n)$ при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка $O(n \log n)$, но только для среднего случая).

\subsection{Heap Sort}
Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:
\begin{enumerate}
	\item Каждый лист имеет глубину либо $d$, либо $d-1$, $d$ — максимальная глубина дерева.
	\item Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.
\end{enumerate}
Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] являются Array[2i] и Array[2i+1].
Алгоритм:
\begin{enumerate}
	\item Выстраиваем элементы массива в виде сортирующего дерева(O(n) операций.)
		$\text{Array}[i]\geq \text{Array}[2i]$
		$\text{Array}[i]\geq \text{Array}[2i+1]$
		при $1\leq i<n/2$.
	\item Удалять элементы из корня по одному за раз и перестраивать дерево ($O(n \log n)$ операций.)
	То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент
\end{enumerate}
Достоинства
\begin{enumerate}
	\item Имеет доказанную оценку худшего случая $O(n\log n)$.
	\item Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).
\end{enumerate}

Недостатки
\begin{enumerate}
	\item Сложен в реализации.
	\item Неустойчив — для обеспечения устойчивости нужно расширять ключ.
	\item На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
	\item На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
	\item Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.
\end{enumerate}

\section{Hash-table and hash-function}

\section{Динамическое программирование: общая идея. Линейная и матричная динамика. Динамика на отрезках}

\section{Амортизационный анализ}
\textbf{Амортизационный анализ} — метод подсчета времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае. Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счѐт низкой частоты встречаемости. Подчеркнѐм, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая. \\
\textbf{Средняя амортизационная стоимость операций} — величина $a$, находящаяся по формуле:
$$ a= \frac{\sum_{\substack{i=1}}^n t_i}{n} $$
где $t_1, \ldots, t_n$ - время выполнения операций $1, \ldots, n$ совершѐнных над структурой данных.\\
Амортизационный анализ использует следующие методы:
\begin{enumerate}
	\item Метод усреднения (метод группового анализа).
	\item Метод потенциалов.
	\item Метод предоплаты (метод бухгалтерского учета).
\end{enumerate}
\textbf{Метод усреднения} \\
В методе усреднения амортизационная стоимость операций определяется напрямую по формуле, указанной выше: суммарная стоимость всех операций алгоритма делится на их количество.\\
Пример\\
Рассмотрим стек с операцией $multipop(a)$— извлечение из стека элементов. В худшем случае она работает за $O(n)$ времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более элементов, то в худшем случае с каждым из них могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было операций $push$- добавление в стек, стоимость каждой $O(1)$, и одна операция $multipop(n)$, то суммарное время всех операций — $O(2n)$, всего операций $n+1$, а значит, амортизационная стоимость операции — $O(1)$. \\
Математическое обоснование:
Пусть $n$ — количество операций, $m$ — количество элементов, задействованных в этих операциях. Очевидно $m ]leq n$. Тогда:
$$ a = \frac{\sum_{\substack{i=1}}^n t_i}{n} = a= \frac{\sum_{\substack{i=1}}^n \sum_{\substack{j=1}}^m t_{ij}}{n} $$
где $t_{ij}$ — стоимость $i$-ой операции над $j$-ым элементом. Величина $\sum_{\substack{i=1}}^n t_{ij}$ не превосходит 2, т. к. над элементом можно совершить только 2 операции, стоимость которых равна 1 — добавление и удаление. Тогда:
$$ a \leq \frac{2m}{n} \leq 2 $$
Таким образом, cредняя амортизационная стоимость операций $a=O(1)$. \\

\textbf{Метод потенциалов}
Теорема (О методе потенциалов): Введѐм для каждого состояния структуры данных величину $\Phi$ — потенциал. Изначально потенциал равен $\Phi_0$, а после выполнения $i$-ой операции — $\Phi_i$. Стоимость $i$-ой операции обозначим $a_i = t_i + \Phi_i - \Phi_{i-1}$. Пусть $n$ — количество операций, $m$ — размер структуры данных. Тогда средняя амортизационная стоимость операций $a=O(f(n,m))$ если выполнены два условия:
\begin{enumerate}
	\item $\forall i \rightarrow a_i = O(f(n,m))$
	\item $\forall i \rightarrow \Phi_i = O(nf(n,m))$
\end{enumerate}
Доказательство: 
$$ a_i = \frac{\sum_{\substack{i=1}}^n t_i}{n} = \frac{\sum_{\substack{i=1}}^n a_i + \sum_{\substack{i=0}}^{n-1} \Phi_i - \sum_{\substack{i=1}}^n \Phi_i}{n} = \frac{nO(f(n,m)) + \Phi_0 - \Phi_n}{n} = O(nf(n,m)) $$

\textbf{Метод предоплаты} \\
Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учѐтная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости $O(f(n,m))$ нужно построить учѐтные стоимости так, что для каждой операции она будет составлять $O(f(n,m))$. Тогда для последовательности из операций суммарно будет затрачено $O(f(n,m))$ монет, следовательно, cредняя амортизационная стоимость операций будет $a_ = \frac{\sum_{\substack{i=1}}^n t_i}{n} = \frac{nO(f(n,m))}{n} = O(f(n,m))$. \\
Пример \\
Опять же рассмотрим стек с операцией $multipop(a)$. При выполнении операции $push$ будем использовать две монеты — одну для самой операции, а вторую — в качестве резерва. Тогда для операций $pop$ и $multipop$ учѐтную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции $push$. Таким образом, для каждой операции требуется $O(1)$ монет, а значит, cредняя амортизационная стоимость операций $a=O(1))$.

\section{RMQ and LCA}
\subsection{RQM}
Запрос минимума на отрезке \\
Вход: массив чисел, два числа (начало и конец отрезка в массиве) \\
Выход: минимальное значение на данном отрезке\\
Алгоритм:\\
Динамика (дерево отрезков)
\begin{enumerate}
	\item Дополняем исходный массив до степени двойки бесконечно большими элементами.
	\item  Строим дерево отрезков (двоичное дерево: листья - значения элементов массива;вершины - минимум из дочерних листьев)
	\item (Фундаментальный отрезок - такой отрезок, что существует вершина в дереве, которой он соответсвует) 
	\begin{itemize}
		\item Заведем два указателя l и r, и установим указывающими на концы исходного отрезка (если l ( r ) указывает на правый ( левый ) дочерний элемент, то эта вершина принадлежит разбиению на фундаментальные отрезки)
		\item сдвигаем указатели на уровень вверх.
		\item повторяем до тех пор пока указатели не совпадут.
		\item Находя очередной фундоментальные отрезок, сравниваем его значение с имеющимся минимум, при необходимости обновляем минимум.
	\end{itemize}  
\end{enumerate}
Оценка: препроцессинг O(n); запрос $O(\log_n)$.

\subsection{LCA: сведение к RQM}
Задача LCA (наименьший общий предок) для двух вершин u и v в корневом дереве T называется узел w, который среди всех узлов, являющихся предками как узла u, так и v, имеет наибольшую глубину. Пусть дано корневое дерево T. На вход подаются запросы вида (u,v), для каждого запроса требуется найти их наименьшего общего предка.
Три основных алгоритма:
\begin{enumerate}
	\item Алгоритм с препроцессингом \\
	Для каждой вершины определим глубину с помощью следующей рекурсивной формулы:
	$$ depth(u) = \begin{cases}
		0, & u=root(T)\\
		depth(v)+1, &u=son(v)
	\end{cases} $$
	Ясно, что глубина вершины элементарным образом поддерживается во время обхода в глубину. Запустим обход в глубину из корня, который будет вычислять значения следующих величин:
	\begin{enumerate}
		\item Cписок глубин посещенных вершин $d$. Глубина текущей вершины добавляется в конец списка при входе в данную вершину, а также после каждого возвращения из еѐ сына.
		\item Список посещений узлов $vtx$, строящийся аналогично предыдущему, только добавляется не глубина а сама вершина.
		\item Значение функции $I[u]$, возвращающей любой индекс в списке глубин $d$, по которому была записана глубина вершины $u$ (например на момент входа в вершину).
	\end{enumerate}
	Будем считать, что $rmq(d,l,r)$ возвращает индекс минимального элемента в $d$ на отрезке $[l..r]$. Тогда ответом на запрос $lca(u,v)$, где $I[u] \leq I[v]$, будет $vtx\big[rmq(d, I[u], I[v])\big]$.

	\item Метод двоичного подъема \\
	Данный алгоритм является on-line (то есть сначала делается препроцессинг, затем алгоритм работает в формате запрос-ответ). \\ 
	Препроцессинг заключается в том, чтобы посчитать функцию $dp[v][i]$ — номер вершины, в которую мы придем если пройдем из вершины $v$ вверх по подвешенному дереву $2^i$ шагов, причем если мы пришли в корень, то мы там и останемся. Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее родителя $p[v]$ и глубину вершины в подвешенном дереве $d[v]$. Если $v$ — корень, то $p[v]=v$. Тогда для функции $dp$ есть рекуррентная формула: 
	$$ dp[v][i] = \begin{cases}
		p[v], &\i=0\\
		dp\big[dp[v[i-1]] \big]\big[i-1 \big]
	\end{cases}$$
	Для того чтобы отвечать на запросы нам нужны будут только те значения $dp[v][i]$, где $i \leq \log_2 n$, ведь при больших $i$ значение $dp[v][i]$ будет номером корня. \\
	Всего состояний динамики $O(n \log n)$, где $n$ - это количество вершин в дереве. Каждое состояние считается за $O(1)$. Поэтому суммарная сложность времени и памяти препроцессинга — $O(n \log n)$.
	Ответы на запросы будут происходить за время $O(\log n)$. Для ответа на запрос заметим сначала, что если $c=LCA(v,u)$, для некоторых $v$ и $u$, то $d[c] \leq \min (d[v], d[u])$. Поэтому если $d[v] < d[u]$, то пройдем от вершины $u$ на $d[u]-d[v]$ шагов вверх, это и будет новое значение $u$ и это можно сделать за $O(\log n)$. Можно записать число в двоичной системе, это представление этого число в виде суммы степеней двоек$2^{i_1} + \ldots + 2^{i_t}$, и для всех $j$ пройти вверх последовательно из вершины $u$ в $d[u][i_j]$. \\
	Дальше считаем, что $d[v]=d[u]$. Если $v=u$, то ответ на запрос $v$. Иначе найдем такие вершины $x$ и $y$, такие что $x \neq y$, $x$ — предок $v$, $y$ — предок $u$ и $p[x]=p[y]$. Тогда ответом на запрос будет $p[x]$.\\
	Научимся находить эти вершины $x$ и $y$. Для этого сначала инициализируем $x=v$ и $y=u$. Дальше на каждом шаге находим такое максимальное $k$, что $dp[x][k] \neq dp[y][k]$. И проходим из вершин $x$ и $y$ на $2^k$ шагов вверх. Если такого $k$ найти нельзя, то значения $x$ и $y$, это те самые вершины, которые нам требуется найти, ведь $p[x]=dp[x][0]=dp[y][0]=p[y]$.\\
	Оценим время работы. Заметим, что найденные $k$ строго убывают. Во-первых, потому что мы находим на каждом шаге максимальное значение $k$, а во-вторых, два раза подряд мы одно и то же получить не можем, так как тогда получилось бы, что можно пройти $2^{k+1}$ шагов, а значит вместо первого $k$, мы бы нашли $k+1$. А значит всего значений $k$ $O(\log n)$, их можно перебирать в порядке убывания. Сложность ответа на запрос $O(\log n)$.

	\item Сведение задачи RMQ к задаче LCA \\
	Если у нас уже есть решение задачи задачи RMQ на отрезке, до построив декартово дерево по неявному ключу на массиве$A[1..N]$ по правилам:
	\begin{itemize}
		\item Корнем дерева является элемент массива, имеющий минимальное значение $A$, скажем $A[i]$. Если минимальных элементов несколько, можно взять любой
		\item Левым поддеревом является декартово дерево на массиве $A[1..i-1]$.
		\item Правым поддеревом является декартово дерево на массиве $A[i+1..N]$.
	\end{itemize}
\end{enumerate}
Тогда $RMQ(i,j) = LCA(A[i],A[j])$. Со сложностью $O(n)$. Доказательство: \\
Положим $w=LCA(A[i],A[j])$. Заметим, что $A[i]$ и $A[j]$ не принадлежат одновременно либо правому, либо левому поддереву $w$, потому как тогда бы соответствующий сын находился на большей глубине, чем $w$, и также являлся предком как $A[i]$ так и $A[j]$, что противоречит определению LCA. Из этого замечанию следует, что $w$ лежит между $A[i]$ и $A[j]$ и, следовательно, принадлежит отрезку $A[i..j]$. По построению мы также знаем, что:
\begin{enumerate}
	\item Любая вершина дерева имеет свое значение меньшим либо равным значению еѐ детей.
	\item Поддерево с корнем в содержит в себе подмассив $A[i..j]$.
\end{enumerate}
Суммируя, получаем, что $w$ имеет минимальное значение на отрезке, покрывающем $A[i..j]$, и принадлежит отрезку $A[i..j]$, отсюда $RMQ(i,j)=w$.
\subsection{Метод двоичного подъема}

\section{Алгоритмы на деревьях}
\subsection{Декартовы деревья}
Декартово дерево — это двоичное дерево, в узлах которого хранятся:
\begin{itemize}
	\item ссылки на правое и левое поддерево;
	\item ссылка на родительский узел (необязательно);
	\item ключи $x$ и $y$, которые являются двоичным деревом поиска по ключу $x$ и двоичной кучей по ключу $y$; а именно, для любого узла дерева $n$:
	\begin{itemize}
		\item ключи $x$ узлов правого (левого) поддерева больше (меньше либо равны) ключа $x$ узла $n$;
		\item ключи $y$ узлов правого и левого детей больше либо равны ключу $y$ узла $n$.
	\end{itemize}
\end{itemize}
Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева.По сути, декартово дерево - это структура данных, объединяющая в себе бинарное кучу и двоичное дерево поиска. Декартово дерево не является самобалансирующемся деревом в обычном смысле (в
отличие от красно-черных деревьев). \\
Преимущества:\begin{enumerate}
	\item Легко и быстро реализуется, в отличие от красно-черных деревьев.
	\item Для случайного набора ключей y (относительно кучи) хорошо строится.
	\item Операция разделить по ключу х выполняется за линейное время.
\end{enumerate}
Недостатки: \begin{enumerate}
	\item Большие расходы памяти: в каждой вершине нужно хранить два-три указателя и два ключа.
	\item Скорость доступа в худшем случае - O(n), поэтому декартово дерево не применяется в ядрах ОС.
\end{enumerate}
\subsubsection{Операции на декартовых деревьях}
\begin{enumerate}
	\item Split
	Операция Split позволяет разрезать декартово дерево $T$ по ключу $k$ и получить два других декартовых дерева: $T_1$ и $T_2$, причем в $T_1$ находятся
все ключи дерева $T$, не большие $k$, а в $T_2$ — большие $k$. \\
Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня. Посмотрим, как будут устроены результирующие деревья $T_1$ и $T_2$:
\begin{itemize}
	\item $T_1$ : левое поддерево $T_1$ совпадѐт с левым поддеревом $T$. Для нахождения правого поддерева $T_1$, нужно разрезать правое поддерево $T$ на $T_1^R$ и $T_2^R$ по ключу $k$ и взять $T_1^R$
	\item $T_2$ совпадѐт с $T_2^R$.
\end{itemize}
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично. \\
Псевдокод: \\
Split(Treap t, int k, Treap \&t1, Treap \&t2) \\
if t == NULL\\
	t1 = t2 = NULL;\\
else \\
     if k > t.x\\
 		Split(t.right, k, t.right, t2);\\
 		t1 = t;\\
 	 else\\
 		Split(t.left, k, t1, t.left);\\
 t2 = t;\\
 \todo{fix spacing}
Оценим время работы операции. Во время выполнения вызывается одна операция для дерева хотя бы на один меньшей высоты и делается ещѐ $O(1)$ операция. Тогда итоговая трудоѐмкость этой операции равна $O(h)$, где $h$ — высота дерева

\item Merge

\end{enumerate}
\subsubsection{Декартово дерево по неявному ключу}

\subsection{Минимальное основное дерево}
\subsubsection{Алгоритм Прима}
Алгоритм построения минимального остовного дерева (дерево, сумма весов ребер которого минимальна) \\
Вход: взвешенный граф (неориентированный) \\
Алгоритм:
\begin{enumerate}
	\item Выбираем некоторую стартовую вершину
	\item Из этой вершины строим самый дешевый путь
	\item Берем связанные вершины и строим самые дешевые пути из них (не рассматриваем те, которые образуют цикл)
	\item Продолжаем до тех пор, пока не свяжем все вершины
\end{enumerate}
Примечания: \\
$\bullet$ Для быстрого нахождения минимальных путей рекомендуется использовать биномиальную кучу. \\
$\bullet$ Интерпретация задачи: есть некое множество городов (и расстояний между ними) - нужно построить самую дешевую сеть дорого (самую короткую) \\
Сложность зависит от способа представления графа и приоритетной очереди:
\begin{itemize}
	\item Массив d, списки смежности (матрица смежности): $O(|V|^2)$
	\item Бинарная пирамида, списки смежности: $O(E \log V)$
	\item Фибоначчиева пирамида, списки смежности: $O(E + V \log V)$
\end{itemize}
\subsubsection{Алгоритм Крускала}
Качественный алгоритм для топологической сортировки \\
Условия: имеем ацикличный ориентированный граф. Упорядочиваем согласно частичному порядку. \\
Алгоритм:
\begin{enumerate}
	\item Берем случайную вершину
	\item Выполняем из нее DFS со следующей особенностью: черные вершины автоматически заносятся в стек, и помечаются использованными
	\item Повторяем п.2 для неиспользованных вершин
	\item Извлекаем ответ из стека
\end{enumerate} 
Сложность: $O(|E| + |V|)$

\section{Минимальные потоки в сети}
\subsection{Метод Форда-Фалкерсона}
Решает задачу нахождения максимального потока транспортной сети. \\
Алгоритм:
\begin{enumerate}
	\item Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
	\item В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
	\item 3 Пускаем через найденный путь (он называется увеличивающим путѐм или увеличивающей цепью) максимально возможный поток:
	\begin{itemize}
	 	\item На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью $c_{min}$.
		\item Для каждого ребра на найденном пути увеличиваем поток на $c_{min}$, а в противоположном ему — уменьшаем на $c_{min}$.
		\item Модифицируем остаточную сеть. Для всех рѐбер на найденном пути, а также для противоположных им рѐбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
	\end{itemize}
	\item Возвращаемся на шаг 2.
\end{enumerate}
Алгоритм (формально):\\
Вход: Граф с пропускной способностью, источник и сток\\
Выход: Максимальный поток $f$ из $s$ в $t$\\
\begin{enumerate}
	\item $f(u,v) \leftarrow 0 \forall (u,v)$
	\item Пока есть путь $p$ из $s$ в $t$ в $G_f$, такой что $c_f(u,v)>0 \forall (u,v) \in p$:
	\begin{enumerate}
		\item Найти $c_f(p) = \min\{c_f(u,v)|(u,v) \in p\}$
		\item $\forall (u,v) \in p$:
		\begin{itemize}
			\item $f(u,v) \leftarrow f(u,v) + c_f(p)$
			\item $f(v,u) \leftarrow f(v,u) - c_f(p)$
		\end{itemize}
	\end{enumerate}
\end{enumerate}
Сложность: $O(E*f)$
\subsection{Метод Эдмондса-Карпа (б/д)}

\section{Алгоритмы на графах}
\subsection{Обход в ширину и глубину}
\subsubsection{Обход в глубину}
Сложность: $O(|E| + |V|)$
\begin{enumerate}
	\item Присваиваем всем вершинам белый цвет
	\item Берем произвольную белую вершину
	\item Красим в серый
	\begin{itemize}
		\item Если есть белый потомок, переходим в него и goto 3
		\item Если нет, красим в черный, переходим к родителю и goto 3a
		\item Если нет родителя и есть белые вершины goto 2
		\item Не осталось белых – конец алгоритма
	\end{itemize}
\end{enumerate}

\subsubsection{Обход в ширину}
Сложность: $O(|E| + |V|)$
\begin{enumerate}
	\item Берем произвольную вергину
	\item Добавляем в очередь (пометив как пройденную)
	\item Пока очередь не пуста
	\begin{itemize}
		\item Достаем первую вершин
		\item Добавляем в очередь все непройденные потомки
		\item goto 3
	\end{itemize}
\end{enumerate}

\subsection{Поиск кратчайших путей в графе}
\subsubsection{Алгоритм Дейкстры}
Вход: взвешенный граф (веса положительны), стартовая вершина\\
Выход: ветор расстояний до стартовой вершины (опционально - вектор предков, чтобы восстановить кратчайший путь)\\
Алгоритм:
\begin{enumerate}
	\item Проставляем расстояния: для стартовой 0, для остальных inf
	\item Пусть S - множество вершин, до которых ихзвестны кратчайшие пути
	\item Добавляем в S вершину с минимальным расстоянием из вектора расстояний и еще не находящуюся в множестве. Помечаем ее, как добавленную.
	\item Для всех соседей обновляем оценку:
	\begin{itemize}
		\item  Сосед ib 
		\item Вершина v
		\item Новая оценка для i = min(старая, d(start, v)+d(v,i))
	\end{itemize}
	\item Если еще остались неиспользованные goto 2
\end{enumerate}
Сложность: $O(|E| + |V|^2)$

\subsubsection{Алгоритм Форда-Беллмана}
Алгоритм поиска кратчайшего пути во взвешенном графе\\
Условие: взвешенный граф, можно с отрицательными весами и циклами (с добавлением дополнительной проверки), стартовая вершина.\\
Алгоритм (без отрицательных циклов):
\begin{enumerate}
	\item Для всех вершин проставляем расстояние = $\inf$
	\item Для начальной вершины расстояние = 0
	\item for i = 1 to (V - 1)
			$\forall (u ,v)$
				if $d[v] >  d[u] + w(u,v)$
					$d[v] = d[u] + w(u,v)$
	\item Возвращаем вектор расстояний
\end{enumerate}
Алгоритм (c отрицательными циклами):\\
Алгоритм Беллмана–Форда позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не $|V|-1$ , a ровно $|V|$ раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию: отслеживать изменения в графе и, как только они закончатся, сделать выход из цикла (дальнейшие итерации будут бессмысленны).\\
Сложность: $O(|E|^*|V|)$

\subsubsection{Алгоритм Флойда-Уоршелла}
Вход: взвешенный орграф\\
Выход: матрица длин кратчайших путей.\\
Алгоритм:\\
for v = 1 to V\\
	for i = 1 to V\\
		for j = 1 to V\\
			Table[i][j] = min (Table[i][j], Table[i][v] + Table[v][j]); \\
Сложность: $O(|V|^3)$

\subsection{Поиск сильносвязных компонент в графе}
ССК - максимальный по включению сильно связанный подграф. Сильно связный граф - орграф, т. ч. из любой вершины можно попасть в любую.\\
Алгоритм находит ССК по данному графу.\\
Условия: дается орграф.\\
Алгоритм (Косарайю):
\begin{enumerate}
	\item Инвертируем граф (меняем направление всех ребер)
	\item Запускаем DFS на транспонированном (инвертированном) графе DFS.
	\item Для каждой вершины запоминаем время выхода (шаги), т. е. когда выходим из вершины окончательно (она становится черной)
	\item Запускаем DFS на исходном графе, в очередной раз выбирая вершину с максимальным номером (временем выхода)
	\item Полученные деревья в п.4 и есть искомые ССК (появляются, когда мы переходим к новой белой вершине в DFS)
\end{enumerate}
Сложность: $O(|E| + |V|)$ для разреженного и $O(|V|^2)$ для плотного графа. 
\subsection{Мосты и точки сочленения в графе}

\section{STL и стандартные контейнеры}
\subsection{vector, deque, queue, priority\_queue, set, map}
Я не знаю, что тут писать. Кто-то не знает, что такое дек или очередь с приоритетами?
\subsection{Итераторы и компараторы}

\end{document}