Algorithms and datastructs

Datastructures - organize data so that it can be accessed quickly and usefully. There are so many because different datastructures support different sets of operations (Tim Roughgarden)

Выбор алгоритма

Если оценить сложность двух алгоритмов двумя функциями T1(n) и T2(n) и если один хуже другого ассимптотически, то на практике следует предпочитать алгоритм посредством анализа n>N0 относительно точки N0 где происходит "перелом" сложности. Если известно что на вход поступает N0 достаточно малое - то вопрос об эффективности не является первостепенным и можно использовать простой алгоритм.

При доказательстве ассимпотической сложности алгоритма при использовании мат.индукции следует делать так, чтобы спрятанные константы в O(n) не росли с n, т.к. иначе такой ход рассуждения просто неправильный и приводит к казусам. [3,5]

Материалы

[1] - Лекции по алгоритмам Р.Седжвика из Принстона "Algorithms - Robert Sedgewick, Kevin Wayne"

[2] - Лекции по алгоритмам Tim Roughgarden из Стенфорда

[3] - Т.Кормен, Ч.Лейзерсон,Р.Ривест,К.Штайн - Алгоритмы Построение и Анализ, второе издание.

[4] - М.Курносов, Структуры и алгоритмы обработки данных (http://www.mkurnosov.net/teaching/index.php/DSA/Fall2015)

[5] - MIT, Introduction to Algorithms

[6] - "XIX Белоусов А.И., Ткачев СБ. Дискретная математика"

"K" - сокращение от Konstantin, выражает моё личное мнение.

"__" - желтым маркером я помечаю что-то "очень" интересное.

Сортировки

Internal Sort -- сортируемые элементы помещаются в память компьютера

External Sort -- элементы размещены на внешней памяти. Один из алгоритмов k-way merge sort

- Разбиение на блоки массива данных

- Сортировка блоков в памяти ЭВМ

- Сброс их на диск

- Вычитывание кусочков блоков с диска и выполнения merge на эти кусочки

In place Sort -- сортировка без использования дополнительной памяти

Stable Sort -- не меняется относительный порядок равных элементов.

Поиск элемента

Словари

Binary Search Tree

Red-Black(RB) Tree, 1972 (Rudolf Bayer,1972, Germany)

1978, R. Sedgewick

Splay tree. (Tarjan,1985)

AVL-tree

Георгий Максимович

Адельсон-Вельский,

Ландис Евгений Михайлович, 1962, СССР

2-3 tree, Hopcroft, 1970

2-3-4 tree

B-trees, 1972

Van Emde Boas tree, 1975

Hash Table via chaining, IBM 1953

Hash Table via open addressing, IBM 1953

Skip List (Pugh,1990)

Sorted Array

Unsorted Array

R-way trie

Ternary trie (TST)

Hybrid R-way and Ternary trie

Patricia or radix tree

Bitwise tree

Suffix tree

Find min/max

O(h) i.e. O(lg(n))

O(lg(n))

O(lg_t((n+1)/2))

O(log(log(N)))

O(n+h)

O(lg(n))

O(1)

O(n)

Add(k,v)

O(lg(n))

O(lg_t((n+1)/2))

O(log(log(N)))

O(1)

O(lg(n))

O(n)

O(1)

O(L)

O(L + ln(N))

But it is character access

GetValue(k) (lookup)

O(lg(n))

O(lg_t((n+1)/2))

O(log(log(N)))

O(1+n/h) - best

O(1+n) - worst

O(lg(n))

via binary search

O(n)

O(L)

and can be faster for unsuccessfull search

O(L + ln(N))

But it is character access

Remove(k)

best: O(lg(n))

average: O(n^0.5)

O(lg(n))

O(lg_t((n+1)/2))

O(log(log(N)))

O(1+n/h) - best

O(1+n) - worst

O(lg(n))

O(n)

O(L)

O(L + ln(N))

But it is character access.

Extra

Binary tree for symmetric order.

Tree shape depends on order of insertion. Worst case - no tree at all, just chain.

Можно сделать lazy-delete - ставить значение в null, без фактического удаления узла.

If store in X node extra "nodes count" in tree rooted by X, i.e. size[x]=size[left[x]] + size[right[x]] + 1

Then it's possible to define rank of the element in O(lg(N)) time.

Inorder traversal - travers left subtree, enqueue element, travers right subtree.

Hibbard deletion - algorithm for delete node in BST. It consist of different cases, depend on what we're deleting. Most complicated - if two child then in right subtree find min, exchange it with current node. And remove previously min node.

For long runs of insert,delete it lead to delete time equal to O(N^0.5). Nobody know how to efficiently remove element from usual BST.

RB self balanced tree

GNU libstdc++, LLVM libc++, Java, .NET 4.5, Linux Kernel - ext3, scheduler,etc.

0. Root and leafs are read or black

1. Root is black. Leafs are black and NULLs

2. Every red node has black parent

3. For any node black-length to the any leaf is the same fot this node

Black-Heigh of the tree - is the length of the black height from the root.

Garantee that h<=2lg(n+1)

В 1979 R.Sedjvik имел статью про rb-tree, но в в 2007 он обнаружил более простой алгоритм для имплементации.

Любой 2-3 tree можно перегнать в left-leaning RB-tree.

3-node from 2-3 tree are represented with "small tree" with 3 leafs, and 2 internal nodes. 2 internal nodes are connected via lef leaning red edge.

Properties (LLRB-tree):

1. red link lean left

2. no node has two red link

3. every path from root to null link has the same number of black links

If draw red link together horizontally then we will see a shape of 2-3 tree. RB-tree is eqialent to 2-3 tree.

Названы т.к. в то время из цветных чернил были только красные -

https://youtu.be/4slgC3UOXc0?t=307

Имеем обычный BST. Ищем куда вставить, вставляем. Затем делаем над втсавленным элементом операцию splay.

Удаление - удаляем элемент и делаем splay для его родителя.

Поиск - находим элемент и выполняем splay для него.

splay:

zig - правый поворот относительно родителя

zig-zig- правый поворот относительно родителя, правый поворот родителя относительно деда

zig-zag

GNU libavl, libdict, python avllib

Высота левого и правого поддерева отличаются не больше чем на 1.

Коэффициент сбалансированности (balance factro) - разность высот левого и правого поддерева.

В AVL balance factor всегда {-1,0,1}

Каждый узел отслеживает свой balance factor, если баланс нарушем после вставки то балансируемся за счёт поворотов.

Это дерево имеет perfect balance.

2-node - узел из ключа и двух детей

Для 2-node: всё по обычному

3-node - узел из двух ключей! и троих детей. Для него левое поддерево состоит из всех "<key_l". Правое поддерево состоит из всех ">key_r". Среднее дерево состоит из всех между [key_l, key_r].

Поиск как делать - следовать правилу дерева рекурсивно, почти так же как в BST.

Вставка - трассируемся по дереву и если ключа раньше в дереве не было то мы дойдём до листа. Если попали в 2-node то добавить элемент к узлу сделав из него 3-node. Попали в 3 node - вставляем в него делая из него 4 node (временно). Потом берём средний ключ его передаем в родителя а сам 4 node бьём на 2 обычных 2-node. И так рекурсивно. Если же родителя нет то этот выпихиваемый элемент "на верх" становится новым корнем.

Perfect balance - every path from root to null link has same length.

Height: worst -- lgN, best -- log3(N).

B дерево с t=2.

Иногда нужно хранить данные во внешней памяти.

Количество пользователей Facebook (лето 2014): 1 350 000 000

Количество пользователей Google Gmail (май 2015): 900 000 000

Загрузка с external storage очень большая.

По сути B tree есть обобщение 2-3 tree. Накачать столько ключей K, сколько поместиться в страницу.

Все узлы по крайней мере на половину заполнены. Это правило не распространяется только на корень.

Узел с K элементами содержит K+1 дочерних элементов.

Все листья находятся на одной глубине.

Узел максимум содержит (2t-1) ключей. Когда при вставке видим, что узел уже накачался до (2t-1)- бъём его на два по (t-1) и пушим на медиану на верх. Вставка как и в 2-3 дереве делается за счёт трасировки максимум до листьев. А затем вставки элемента в node и возможно дробёшки node-ы и propagation элемента на верх.

B-дерево минимизирует обращение к оперативной памяти.

Можно ускорить поиск узла в ключе за счёт binary search.

Модификация B-дерево когда информация хранится только в листьях называется - "B+" дерево.

Если поставить ограничение узлам быть заполненными как минимум на 2/3, а не на 1/2 то такая модификация называется "B*" дерево

Ключи есть целые неотрицательные числа из m бит.

Асимпотитески лучше чем любые сбалансированные деревья.

В целом если не важен порядок, лучше чем деревья на основе сравнений.

Хеш-таблицы можно использовать для реализации sparse матриц.

load factor=Items/Bucket

hash code - is value returned bu hash function uniform distribution

Хеш для строк может быть целое число показывающее, что строка это разложение целого числа по модулю алфавита.

Если хочется для подсчёта хеша структуры использовать поля, то как правило делают:

hash = 31*hash + fieldA.hash()

hash = 31*hash + fieldB.hash()

Варианты прокачки

1. Использовать криптостойкую хеш-функцию, если хочется не боятся угроз "атак"

2. Использовать две хеш-функции. Вставлять в chain-list с меньшим кол-ом элементов.

No list per bucket, if not find element=>just try next cell.

Linear probing - sequntially check following

Применение:

QMap (Qt 4.7)

Redis persistent kv store

Несколько отсортированных параллельных списков. Бинарный поиск для связанных списков. Нижний уровень содержит всегда все элементы.

We can improve search - to do better then hash table. If not look through whole key string for define that such key is not present => it will make improvement.

Each node store

1. Value (or NULL)

2. "R" reference to child nodes. For Ascii R=256

L is length of the key.

R is radix of the symbols in the "string".

Need space is very large - (R+1)N

Tries beside usual container operations support others:

1. Find all string keys with some prefix (autocomplete)

2.Find key that has longer common preifx with some specified word

(route tables)

В отличие от хеш-таблиц, можно обойти ключи в упорядоченном виде и никогда не возникает коллизий.

Every node has 3 children:

"less" - link to the all keys that start from "char" which less then current

"equal" - link to the all keys that start from "char" which equal to current. Nodes after link with this type are actually formed "trie", other is only to supprt traverse structure.

"greater" - link to the all keys that start from "char" which greater then current. Such links also as "left" only "helps" to navigate. Space is now O(4N)

R^2 root nodes point for TST for strings which begin from different two letters.

In practice faster then Hashing in some applications.

Patricia - Practical Algorithm to Retrieve Information Coded in Alphanumeric.

Idea

1. Allow to strore string in node, not only symbol

2. Remove one-way branching by collapsing all chars into one string

Ключи - последовательность бит, т.е. разрядность (radix) букв равна двум.

Название для trie, который хранит все суфиксы строки. После построения можно использовать при операциях поиска подстроки в строке за линейное время.

Priority queues (min heap)

* - amortized time

O - means theta.

Application:

1. Find the largest M items in a stream of N items. Use prioirity queue to insert elements into PQ, if exceed limit, then deleteMin.

Graph algorithms

Множество путей ведущих из одной вершины в другую не более чем счётно ([6], стр.329)

A^l - если A матрица размеченная ад полукольцом R. И длина пути есть произведение в полукольце. Стоимость прохождения есть сумма в R. То A^l есть матрица с путями длины l. A* есть матрица стоимости по всевозможным путям.

DFS traversal

BFS traversal

Dejkstra, 1959

Shortest paths in DAG

Bellman-Ford

Кратчайшие пути на основе замкнутого полукольца R+(min, sum)

Флойда-Уоршелла

Транзитивное замыкание отношения достижимости

Джонсона

Алгоритм Ли (волновой алгоритм)

MST via J. Kruskal, 1956

MST R.Prim,1957

MST O. Boruvki, 1926

MST Chazelle, 2000

Union Find

Graph isomorphism

Is Graph Biparated?

Is Graph planar?

Topological sort

Find Oriented Cycles

Job Scheduling in parallel

Digraph Strong Component.

Kosaraju algo

ST-cut

Max Flow. Ford-Fulkerson.

MinCut. Contraction Algorithm

Compexity

O(|V|+|E|)

Fib. heap -

O(E+Vlg(V))

Binary hep-

O( (E+V)lg(V))

O(V+E)

O( |V-1| * |E|)

O(E lg(V))

Fib. heap -

O(E+Vlg(V))

Binary heap-

O( (E+V)lg(V))

V*Time of extract min+

E*Time to decrease key

O(E lg(V))

O(E inv.ackerman(|E|,|V|)))

Union(set with a, set with b)

- O(lg(N))

IsInOneSet(a,b)

- O(lg(N))

Find_In_which_set(a)

Hopcroft,Ulman, Tarjan.

M union-find for N objects with path compression and weights takes:

O(N + Mlg*(N) )

Nobody knows how to solve

O(E+V)

Производительность зависит от длины augemented path.

shortest path O(EV)

Dfs path O(EU).

Description

Applications:

1. Find all verticies connected to S.

2. Image-based pixel processing to find components.

vertex -- pixel

edge -- pixels are neighboors and change in intensity is small

3. Find connected components in undirectedf graph

4. Perform topological sort

5. Поиск числа компонент

6. Поиск древесных и обратных ребёр(неор граф). Поиск древ., прямых, обратных, поперечных дуг орграфа

7. Поиск вершин составляющих фундаментальный цикл и поиск фундаментальных циклов

Algo:

1. Mark vertex v as visited

2. Recursively visit all unmarked vertices adjacent to v

Альтернативная реализация использовать "стек" не для рекурсивных вызовов, а для хранения текущего накопленного пути. В этом случае можно обойтись как-бы без рекурсии.

Замечания:

1. Результат работы - остовный подграф, результат зависит от порядка в котором вершины перечислены в списках смежности

2. Не всякий оставный подграф может найден поиском в глубину. Контрпример - граф в виде снежинки

Applications:

1. Find all verticies connected to S and shorted paths in terms of fewest number of edges.

2. Can be used for multisource shortest path. Usual BFS but at the start queue contains all potenional source vertices.

3. Compated to DFS it is more space consuming, but also if the target is somewhere near the source then BFS will not go into infitnitely deep paths

4. Compute shortest path in edges terminology

5. Explore "environment" by "layers"

6. Crawl the web from the root page. DFS is not a good strategy for it, because you will go far away from your nearest neighboors.

Algo

1. Remove vertex from the queue

2. Append all adjacent & nmarked verticies to the queue

Кратчайший путь из source ко всем другим. Работает для графов без отрицательных весов. Алгоритм очень похож по своей сути на алгоритм Прима построения минимального остовного дерева.

"Лучше использовать 4-way heap для критичных по времени ситуациям. Фибоначевские Кучи хороши только в Теории."

- (R. Sedjvik)

Алгоритм Дейкстры ищет кратчайший путь из source во все другие вершины для размеченного графа с неотрицательными весами.

В A* дополнительная эвристика для расстояния до цели. Она должна быть недооценкой стоимости пути. Т.е. это должна быть нижняя оценка, например длина пути в отсутствии препятствий. Реальная может быть больше, и это не ломает алгоритм.

Алгоритм аналогичен Дейкстры, но вынимания происходит по критерию минимальности:

(пройденное расстояние от s до v) + (оценка расстояния снизу пути от v до цели)

Алгоритм ищет кратчайший путь из source к dest.

Когда мы начинаем двигаться мы ощущаем наше окружение по иному, т.к. оно меняется со временем.

Идея использовать A* с предыдущего шага. И важно то, что задача определения пути из source в dst на самом для этого алгоритма видоизменяется тем, что source и dst меняются ролями. Ну и судя по всему направления рёбер так же меняется на противоположные.

Если имеется безконрут. орграф (DAG) то можно сделать Topological Sort за O(V+E) а потом сделать один шаг алгоритма Беллмана-Форда за O(E) - просто порелаксировать все рёбра. Этим достигнется очень быстрая скорость поиска кратчайших путей. Этому алгоритму без разницы есть или нет отрицательные веса. Таким образом его можно использовать и для поиска самых длинных путей, если поменять веса на противоположные по знаку.

Кратчайший путь из source ко всем другим. Работает для графов с отрицательными весами без отрицательных циклов.

Этот алгоритм также может детектировать наличие контуров с суммарным отрицательным весом. Так же для таких графов данный алгоритм после V-1 внешний итераций не сходится, а именно - стоимость будет уменьшаться даже после V-1 шагов.

Одно из приложений поиска negative-weight-edge cycles заключается в поиски возможности честной махинации на финансовом рынке (arbitrage)

https://www.facebook.com/permalink.php?story_fbid=314255878963818&id=100011382256381

Convert weight to "w = -ln(w)" и поиск путей в которых сумма весов меньше нуля.

Можно сказать так

1. рассматриваем рассотяние от i до j (на первом шаге это 0 если i=i, и +inf иначе)

2. на шаге m мы будем рассматривать минимальное расстояние от i до j с использованием кол-ва ребёр меньше или равно m

3. внешний цикл по m, внутренний по i, ещё внутренний по j, и ещё внутренний по k т.к. нужно найти минимум с шага 2

Сложность ~V^4. Если использовать матричное умножение не в лоб, а с помощью рекурсвиного возведения в квадрат то можно прокачать до ~V^3 lg(V)

Интересное замечаение, что умными алгоритмами матричного умножения из теоретической информатики воспользоваться не получится, по той причине что сложение в нашей алгебре не имеет обратного элемента.

Кратчайшие пути между всеми парами вершин.

Все вершины пронумерованы целыми числами от 1.

Концептуально рассматриваем расстояние между вершинами i,j.

И используем только один внешний цикл по k. K означает что мы можем на этой итерации рассматривать промежуточные вершины из {1,2,...,K}

Сложность ~V^3

cij(k)=min(cij(k-1), cik(k-1)+kj(k-1))

1. V*BFS сложность ~V(V+E)

2. Флойд-Уоршелл ~V^3

3. Флойд-Уоршелл с заменой min на OR, и "+" на AND. Это позволяет немного прокачать Флойд-Уоршелла.

Кратчайшие пути между всеми парами вершин.

1. Идея сначала имзенить веса дуг применив h() на вершины.

wh(u,v)=w(u,v)+h(u)-h(v)

Такая конструкция изменяет все пути между u и v на одинаковое число. "Все" в том числе и кратчайший.

2. Сделать так что wh(u,v)>=0 <=> w(u,v)+h(u)-h(v) >= 0. Это difference constraint и для решения этого специального случая вместо general LP можно использовать Bellman-Ford ~(EV)

3. Запустить Дейкстры из каждой вершины V(E+VlgV)

4. обновить кратчащие пути из u в v на число h(v)-h(u)

Сложность O(VE+V*V*lg(V))

Путь с минимальным количеством промежуточных узлов.

Minimum Spanning Tree - остовное дерево с минимальной суммой весов его рёбер. Apps: Формирование дерева при широковещательной рассылки информации, прокладка тв кабеля.

Осортировали рёбра O(Elg(E)),

назначали всем вершинам свои индексы компонент.

Вытаксиваем ребро за ребром.

1. Соединяет разные компоненты => компоненты сливают,

2. Иначе => игнорируем ребро.

При использовании 1,2 --- O(Elg(E))

(1) эквивалентно критерию "вводит ли новое ребро цикл?"

Этот алгоритм можно использовать для кластериации - при уменьшении количества кластеров остановиться когда получили K компонент связности.

Greedy MST algorithm still correct if equal weights are present.

If graph is not connected then compute minimum spanning forest is MST of each component.

Жадно наращивать дерево T.

Требуется накачать V-1 рёбер в это дерево.

На каждом шаге добавлять новое ребро в T, так что одна из вершин уже лежит в дереве T.

1. Каждая вершина своя компонента связности

2. Для каждого дерева найти минимальное инцидентное ребро и добавить его к формируемому дереву.

3. Пересчитать новые компоненты связности

4. Повторять шаг 2 пока не останется две компоненты

5. При наличии двух компонент соединить их минимальным ребром/путём

Может использоваться для алгоритма Краскала.

Под капотом массив из целых чисел размером на кол-во элементов в массиве. Каждый элемент содержит индекс родителя. Корень хранит "индекс-указатель" на себя.

А так же массив содержащий для каждой компоненты её размер в элементах.

IsInOneSet - по сути проверяет что у "a" и "b" один и тот же родитель/корень.

Union - находим два корня. И родителям одного из корней делается другой корень. Лучше балансировать куда добавлять на основе массива с размерами.

Так же можно ввиду не обязательности бинарности дерева сделать трюк под названием "path compression" - во время траверса до корня мы проходим все эти вершины и ставим им родителя корень напрямую. Это подразумевает два прохода. Можно сделать приближенно похожую схему - до прыга в родителя, поставить индекс родителя в индекс деда. Это сократит пути в два.

Изумительно, но [Fredman-Saks] показали, что для этой задачи вообще не существует алгоритма с линейной сложностью

Tim Roughgarden:

Ackerman function растёт ещё медленее чем lg*(N)

A(k=0, r)=r+1

For k,r>=1

A(k,r)=A(k-1, A(k-1, A(k-1, ....A(k-1, r)....)) apply A(k-1,X) r times to r

It is possible to show that

A(1,r)=2r

A(2,r)=r*2^r

In general A(4,r) ~ iterate tower function. Ackerman function increase ridiculous fast.

Inverse Ackerman function

Let's fix r=2.

Alpha(n) -- is be def. minimum valueof k, s.t. A(k,2) >= n

Alpha(4)=1

Alpha(5)=2, Alpha(6)=2, Alpha(7)=2, Alpha(8)=2

Alpha(9 - 2048)=3

Alpha(2048-....vey big number)=4

Euler cycle/tour - cycle which use every edge once. In 1736 Euler setup problem where edge=bridge, vertex=island.

Theorem: Such cycle exist iff graph is connected and each vertex has even degree. This problem can be solved efficiently based. E.g. modify DFS search and mark passed edges, not vertices. But seems need more modification for DFS.

Hamilton cycle - cycle that use every vertex once.

This is NP-complete problem. This problem is intractable

Graph isomorphism - are two graphs are isomorphed (the same, if not take in mind naming of verticies)

[6].Гомоморфизм - отображение множества вершин одного графа в вершины другого при котором сохраняется отношение смежности задаваемое рёбрами.

Изоморфизм - биективный гомоморфизм.

Способы, которыми можно анализировать ситуацию:

1. Распознавать изоморфизм не оригинальных графов, а графов у которых множества рёбер заменены на дополнение до универсального мн-ва рёбер т.е. VxV

2. [6], стр. 366. В изоморфных графах должны совпадать "тонкие" структуры циклов-утверждение о структуре циклов должны совпадать в изначальном и изоморфном ему графе

DFS based solution

Layout graph in plane without crossing edge. To solve it you should hire an expert. Linear-Time DFS algorithm was discovered by Tarjan in 1970. Too complicated algorithm for most people.

Draw directed acyclic graph(digraph) (DAG) with edges only in "up" direction. In some sense "edges" define precedence contraint. The most simplest discovered algorithm:

1. Run DFS. After Recursive call DFS for children push processed current vertex to Stack. Such order garantee implementation of "precedence" constraint.

2. Return vertices in postorder

Use DFS

Есть работы, которые требуют времени. Изображаем их как вершина-начало работы, дуга длинной время выполнения, и финишная вершина.

Есть precedence constraint - из конца работы A ведёт дуга в начало работы B iff если B не может быть начато, пока не закончено A.

Critical path method - создаем вершину sink и source, проводим из source дуги весом ноль во все начала работ, и добавляем дуги из end работ в sink.

Процесс поиска на этом DAG графе longest path эквивалентен планированию работ, параллельно на неограниченно количестве процессоров.

Longest Path поиск является NP только на произвольных графах.

Постановка задачи - https://en.wikipedia.org/wiki/Longest_path_problem

найти простой путь максимальной длины.

На DAG можно обойтись заменой весов на противоположные по знаку, и пройтись одним шагом Белмана Форда, посещая вершины в порядке топологической сортировки.

R. Sedkvik explanation:

Kosaraju-Sharir. "In 1980 - Forgot notes for lecture and developed algorithm in order to teach it. Later found in Russian scientific literature (1972)" - R. Sedkvik.

1. Reverse digraph. (Reverse graph and original have similar strong connected components)

2. Run Topological sort for graph from previous step and receive reverse postorder of vertices from

3. Now using sequence of vertices from step2 run usual DFS in original graph. All vertices which can be visited from current vertex and which are still unmarked at current iteration are in one strong component.

This algorithm is a bit mysterious, but run in time proportional to O(E+V), because it just run DFS twice.

Из лекций Tim Roughgarden:

Если брать вершины unexplored и из них строить посредством DFS компоненты, то тогда мы будем находить:

1. Реальные SCC

2. Объединение SCC, соединённые дугами ведущих в одну только сторону

Идея алгоритма Kosrtaju найти такую последовательность запусков DFS, чтобы только получать только вариант 1.

Сложность алгоритма Kosrtaju O(E+V) и он шокирующий своей простотой (в формулировке).

pass-1: reverse graph with reverse edges Grev

pass-2: DFS on Grev. This step give magical order finishing time. Это счётчик обработанных вершин. Когда выходим из рекурсивного DFS задаём каждой вершине ft[v] = finishing_time++; (самый внешний цикл толкающий DFS обрабатывает вершины от последней к первой)

Доп. работа этого шага - составление ft[] который даёт магическую последовательность запусков DFS для следующего шага.

pass-3: DFS on G. Точнее почти на G. Берём веришны графа и им задаём новые номера из массива ft[]

(самый внешний цикл толкающий DFS обрабатывает вершины от последней к первой)

Доп. работа этого шага - при запуске DFS от корня запись номера корня в массив leaders[v] = start_vertex

Док-во корректности.

1. Предположим мы знаем SCC(Strong connected components) графа G.

Мета граф - вершины эти SCC компоненты. Для двух вершин C1 и C2 вводится дуга из C1 в C2 если если хотя бы одна дуга (i,j) в графе G. где i вершина из C1 и j вершина из C2.

Мета граф этот ациклический, т.к. SCC если и соединены то только дугами в одно направление.

2. Если построить метаграф то его вершины для Grev (графа полученного из оригинального переворачиванием дуг) останутся такими же (если оценивать SCC номерами вершин которые входят в SCC)

Размеченный орграф с весами дуг. Разделить вершины на два не пересекающихся подмножества A,B. Так чтобы capacity была минимальной.

capacity в данном контексте - сумма стоимостей дуг ведущих из A в B.

Приложения:

1. США в 1950 решало какие пути, соединящие СССР и Восточную Европу требуется ликвидировать в случае если холодная война станет настоящей. Рассекречено в 1999 году - Р.Седжвик.

new flow across a cut(A,B) - сумма стоимостей дуг ведущих из A в B за вычетом стоимостей ведущих из B в A.

Flow-value lemma: new flow одинаков для любого cut-а. Можно доказать по индукции. В целом из-за local equilibrium.

Maxflow-mincut theorem. Value of the maxflow = capacity of mincut.

Алгоритм.

1. Найти Max Flow.

2. Потраверсить вершины по undirected paths из (s), для которых:

-- forward edge не полный

--backward edge не пуст

A - это все найденные таким образом вершины

Есть размеченный граф с весами дуг, которые показывают максимально возможную "нагрузку" на дуги (capacity). Есть один источник(s) и один сток(t), требуется нагрузить сеть, чтобы максимизировать кол-во приходимое в сток.

Есть два ограничения

1. Нельзя нагружать ребро больше чем в capacity единиц

2. Для всех вершин кроме s и t выполнено, что сумма весов входящих дуг в вершину равна сумме весов выходящих дуг из вершины

Алгоритм Форда-Фалкерсона поиска максимального потока.

В графе есть один исход, и один сток. Задача найти максимальный поток "жидкости" по ребрам графа, с ограничением на capacity каждого ребра.

Augmented path in directed flow graph - undirected path from s to t for which we can increase flow on forward edges (they're not full) && can decrease flow on backward edges (they're not empty)

1. Начать с потока равному нулю по всем рёбрам.

2. Найти Augmented path

3. Посчитать bootleneck capacity

4. Пересчитать поток (увеличить на forward edge) уменьшить на backward edge. Таким образом всегда сохраняется local equilibrium.

Когда все Augmented path из (s) в (t) включают по крайней мере одно ребро forward edge с заполненным полностью capacity ИЛИ одно ребро с backward edge из которого уже нельзя вычесть, т.к. там уже ноль -

то алгоритм завершается.

Augmenting path theorem. A flow f is a maxflow iff no augmenting paths.

Чтобы обойти все пути можно использовать DFS-based подход.

Задан неор. граф.

Задача разбить вершины на два множества (а это можно сделать 2^N способами). Найти такую разбивку которая приводит к минимальному количеству crossing edge, i.e. рёбра соединяющие вершины разного типа.

Stanford, Karger, ~1990, Contraction Algorithm (алгоритм сжатия)

Выбрать случайно ребро. Схлопнуть две вершины в одну супервершину. Убирать петли, но оставлять параллельные рёбра.

Продолжать пока не останется две супервешины. Вершины в этих супервершинах определяют множества A,B.

Вероятность того, что будет получено минимальное разбибение - 1/C(2,n).

Это достаточно маленькое число, хотя и большее нежели чем выбор произвольного разбинения. (1/2^N)

Алгоритм улучшается посредством Repeated Trials.

Прогонка алгоритма несколько раз у выбрать наилучшее минимальное разбиение среди них.

Можно показать, что если алгоритм прогнать N^2 раз, вероятность того что мы не найдём лучшее разбибение 1/e

Если алгоритм прогнать N^2 lg(N) раз, вероятность того что мы не найдём лучшее разбибение 1/N

[Algorithm-design-analysis-1, Tim Roughgarden, Random Contraction Algorithm]

В отличие от min-cut, аналогичная проблема max-cut уже является NP.

Но иногда бывает special case с bipartite graph (существует разбивка вершин такая что всё рёбра являются crossing). Чтобы определить это можно заиспользовать BFS. И разукрашивать вершины в разные цвета в зависимости от слоя (чётный или нечётный). В таком типе виде графа max-cut уже не является NP.

How to solve Hard Problems

Backtracking (bruteforce for combinatoric problems)

1. if solution found => print solution

2. enumerate over all possible future steps (e.g. color adjacent vertex)

3.a apply step

3.b if step is valid recursive call backtracking

3.c if step is invalid revert application of step

Кучи (min-heap)

Minimum api: insert(), extractMin().

Если хочется одновременно делать extractMin, extractMax то лучше использовать self-balanced tree.

HeapSort -- insert all in heap, extract-min, extract-min. O(n lg(n))

n - кол-во объектов в куче

для заполнения кучи требуется O(log(n)n) - максимально, но можно сделать специальный батч со сложностью в O(n)

Примеры использования кучи

-- Быстрый способ для повторного извлечения минимума

-- Selection Sort (n**2), может быть улучшен с помощью Heap. Фактически selection sort с забиранием элемента из Heap, а не из массива называется HeapSort. Сложность O(n lgN)

-- Можно вынимать события из priority queue. Например key-время

-- Можно поставить задачи физической симуляции поведение частиц, эластически сталкивающиеся между собой. Один из подходов дискретизировать время на кванты "dt". Продвигать время, и на каждом этапе времени искать всевозможные пары коллизий за ~N*N. Альтернатива сделать event-driven simulation. Берутся все частицы проводятся лучи прямолинейных траекторий, по которым двигаться будут частички. Считаем время столкновения, засовываем в Priority Queue.

Вынимаем элемент из PQ. Если имеет место сталкивание, то пересчитываем скорости, считаем новые потенциальные коллизии с другими объектами и засовываем в PQ.

-- Выдавать медиану последовательности. Создать два heap max-heap, min-heap. и играться с поочередной вставкой + возможной перегруппировкой.

-- улучшение других алгоритмов, например алгоритм Дейкстры поиска на графе V*TExtractMin + E*DecreazeKey

-- получение M самых больших чисел из потока.

Куча есть дерево со специальными свойствами:

(I) Дерево для кучи полно "насколько это возможно"

(II) key(i)<=key({all i's child})

Преобразование кучи в массив и навигация по массиву

1. выделяются уровни дерева например с помощью топологической сортировки. level0..levelN

И в рамках одного уровня элементы перечисляются left 2 right)

2. элементы толкаются в массив

3. Возможно такое представление дерева как массива с шага 2, т.к. дерево полного "насколько это возможно"

4. i - индексы идут от 1

parent(i) = i/2, если i % 2 == 0

parent(i) = floor(i/2), если i % 2 == 1

сhild(i)=2i, 2i+1

Запихивание в кучу

1. stick. пихаем новый элемент в последний не заполненный уровень слева направо

2. bubble-up, heapify. если мы нарушили свойство кучи, то свопим с родителем, и так до корня.

Процесс оканчивается, когда не нарушаем никакие свойства кучи

ExtractMin

1. Возвращаем значение из корня

2. Берём из последнего уровня дереве самое правое значение и засовываем в корень, удаляя старый лист

3. bubble-down. Свопим корень c min child, если root > min child. и рекурсивно в ребёнке делаем аналогчиную операцию.

Подумать: может с последнего уровня вынимать элементы по умному.

Хеш таблицы

Пока идёт оперирование малым количеством целочисленных индексов - проблем нет вообще. Массивы подходят идеально. Однако когда индексов много, то хеш таблицы становятся необходимы, если требуется быстрый просмотр элементов.

Примеры использования хеш-таблиц:

-- устранения дубликатов

-- 2summ problem. найти из массива int-ов два которые в сумме дают Значение T. Naive way даёт n**2.

с предсортировкой можно улучшить до N lgN.(сортировка+binary search). Но подход можно улучшить с hashmap-ом

-- компиляторы

-- во время изучения допустимых выводимых конфигурация во время игры использовать хеш-таблицу для неизучения уже изученного

-- Одно из приложений использоание хем-мапов - хранение sparse matrix. Хранить только ненулевые элементы в матрице

Load Balancing

"Если случайно кидать шары в урну, то после M бросков - наиболее загруженная корзина будет иметь ~(logM/log(logM))

шаров." - R. Sedjvik

Подумать: может изучить получаемое распределения, чтобы подобрать параметры хеш-функции.

Два основных метода для реализации

resolve collision - chaining - списки для коллизий

open addressing - модель про то, что требуется иметь хеш функцию для первого тыка, и вторую для вычисления оффсетов.

Для chain-list перф зависит от распределения данных по бакетам.

Хорошая хеш-функция

-- должна иметь хорошую скорость

-- распределять данные равномерно на сколько это возможно. стандарт - полностью рандомная функция

Хеш-функция должна быть шустрая. Так же хеш-функции делят на две функции:

hash code -- U=>INTEGERS (возможно c модулем, чтобы избежать overflow)

compression code -- INTEGERS=>N BUCKETS

Как выбрать кол-во бакетов. Эвристики:

1. выбрать n как простое. Чтобы не было общих делителей.

2. не так близко к степени 2 и к степени 10

Проблема не только в возможно плохой хеш-функции, но и в плохих данных для этой хеш-функции.

Load Factor

Load Factor = кол-во объектов в хеше / кол-во бакетов

Load Factor > 1 -- имеет смысл только для chaining. для Open Addressing смысла говорить про это нет, т.к. это невозможно.

Советы:

1. Для chaining лучше Load Factor <= 1, если хочется всё таки выполнять быстрый поиск

2. Load Factor должен быть контролируемым. Например должен быть < 0.5, < 0.75, иначе во время следующей вставки следует удвоить кол-во бакетов. Во время удаления уменьшить кол-во бакетов (сделать shrink бакетов)

В любом случае есть патологические данные. т.к. по pigeonhole priciple |U| > |n| существует набор ключей и бакет такой, что |U|/n ключей идут в него.

Выходы. В следующих 1,2 методах можно публиковать код, и ничего плохого не будет:

1. использовать криптографические функции для хеширования sha-2 например. Как найти патологический набор данных для этой хеш-функции - пока никто не знает.

2. Использовать рандомизацию и использовать uniform hashing. Замечание при реализации семейства функций полиномом c суммой как modN, требуется чтобы коэффициенты были меньше чем N.

ExpectedNumberOfCollisionWithX[uniform hashing + chaining] = num of objects-1/size of table = (approx.) = load factor

ExpectedNumberOfCollisionWithX[uniform hashing + open addressing] ~ rather hard to analyze. But if all probes equally likely, then it is 1/(1-alpha)

Для linear probing - 1/(1-alpha) выполняется плохо. Время приблизительно 1/(1-alpha)**2 показано Кнутом в 1962 году.

linear probing теоретически очень плохая, однако она хороша ложится на memory hierarchy.

Bloom filtering

Приблизительно придумано в 1970 году. Супербыстрая вставка, супербыстрый lookup. Чем-то похож на hash table, но требует гораздо меньше размера. Очень space efficient.

1. Не может хранить объект ассоциировнный с ключом.

2. Удаление элемента требует большой работы над алгоритмом

3. Алгоритм может ошибаться! И в этом его отличие от классических контейнеров.

false negative. Ошибка такого рода отсутствует. Произошла вставка, произошёл вопрос есть ли объект в контейнере? - и алгоритм скажет что есть.

false postives. Такая ошибка есть. Но она небольшая. Вы не вставили элемент, есть ли объект в контейнере ? и алгоритм говорит, что есть.

примеры приложений:

-- проверка синтаксиса над большим кол-ом слов

-- список запрещённых паролей

-- роутеры для интернета для каких-то алгоритмов

Описание:

A - массив n битов.

b=n/|S| -- кол-во битов на объект.

массив хеш функций H - из K функций.

Вставка: for i=1,k {A[H[i](x)]=1}

Просмотр: for i=1,k {A[H[i](x)] should be equal to 1}

Чем больше бит используется, тем false postives уменьшается.

Анализ вероятности false postives

Применение хеш функции - бросание дротика. (K штук)

Биты в массиве бит - мишени для дротика. (n штук)

(1/n) -- вероятность того, что дротик попал в конкретную мишень

(1-1/n) -- вероятность того, что дротик не попал в конкретную мишень

(1-1/n)**k -- вероятность того, что дротик не попал в конкретную мишень k раз.

1-(1-1/n)**k -- вероятность того, что дротик попал в конкретную мишень хотя бы один раз из k раз.

1-(1-1/n)**((-n/1)(-k/n) ~ 1-exp(-k/n)

Вероятность, того что после заполнения фильтра блума из n бит |S| объектами, имеется ситуация такая что произвольный бит имеет значение 1.

1-exp(-k|S|/n)=1-exp(-k/b)

Вероятность ошибки false postives, после вставки нового объекта есть по сути ситуация что все биты и так были установлены в 1.

{1-exp(-k/b)}**k -- error rate

как поставить k?

d{{1-exp(-k/b)}**k}/dk =0

k ~ ln(2)*n/|S|~ ln(2)*b

error rate ~ 0.5**(ln2 * b)

Сбалансированные деревья

По сути сбалансированные бинарные деревья это динамическая версия статического отсортированного массива, но только на нём можно отлично выполнять модификацию. В некотором смысле лучшая структура данных для статических данных - это массив. Для сбалансированных деревьев большая часть операций выполняется в логарифмическое время в зависимости от кол-ва элементов.

Вывод отсортированных данных - O(n)

Хеш таблицы - не хороши для сортировки и навигации между элементами, т.к. по сути между ними нет отношения порядка.

Как правило используют one node per key. Но реализация указателей отличается. Например можно сделать на node три указателя - left, right child, and parent. Если кого-то из перечисленных у узла нет, то указатель ставится в null.

Этот способ позволяет искать Predesessor, successor текущего узла. Позволяет реализовать удаление элемента из bst.

Правило для кучи: key(i)<=key({all i's child})

Правило для search tree: left SubrteeNodes's Keys < KEY < right SubrteeNodes's Keys

Если хочется обрабатывать хранить несколько одинаковых ключей, то < или > следует заменить на <=, или >= соответственно.

высота дерева - максимальное кол-во хопов, чтобы добраться от рута до листа

глубина вершины дерева - длина пути из корня в эту вершины

поискать предшественника - max в левом поддереве. Если левое поддерево отсутствует, то идти рекурсивно в родителя до тех пор пока он не станет меньше узла для которого ищется предшественник. если дойдём до нул родителя, то предшественника не существует.

удаление элемента - нуль или 1 ребёнок - без проблем элемент просто удаляется из дерева с поправкой указателей.

если два ребёнка - надо свопнуть элемент с его предшественником. и потом удалить элемент из засвопленной позиции.

для операции select, rank - надо добавить кроме указателей доп. инфу о размере дерева с корнем в текущем узле.

Приложения бинарных деревьев:

1. Поиск всех точек на R, которые попадают в отрезок [low, high]

2. Поиск пересечений вертикальных и горизонатльных линий. h-segment. left point=>добавить в BST, right point=>remove. Если встретился v-segment то выполняем range search в интервалах с y-points.

3. Часто для геометрических данных наблюдается такая вещь как кластеризация поэтому если и оптимизировать поиск за счёт регулярных сеток, он как равило не эффективен. Лучше бить адаптивно выстраивая дерево (2d-tree, BSP-tree, QuadTree)

3.1 2d tree - поочерёдное биение то прямой параллельно OX, то OY при чётном/нечётном уровне вершины. Как правило поиск R точек в таком дереве занимает R+log(N)

3.2 Обощение 2d tree есть KD-tree

Lossless Compression

отосланное данное = принятое данное. используется для текстов, бинарников.

RUN LENGTH ENCODING (RLE)

AAABB=3A2B

Плохо работает с данными в которых большая "вариация" символов.

DIFFERENTIAL PULSE CODE MODULATION (DPCM)

AABBCCDD=A00112233

Менять Reference символ, когда дельта становится слишком большой. Работает лучше чем RLE для многих цифровых сообщений.

АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ

Каждому символу назначается подинтервал [0,1). Так что объединение этих интервалов есть [0,1). Попарно

полуинтервалы для символов не пересекаются. Закодированное данное передаётся как набор рациональных чисел.

Лучше чем Хаффман, но используется реже в том числе из-за патентов.

СЖАТИЕ ДЕВИДА ХАФФМАНА

Есть частоты букв из алфавита. Цель получить префиксные коды так чтобы получить малый размер конечного сообщения.

Хаффман предложил взять буквы, и считать их листами дерева. Затем рекурсивно, жадно, мержить от листов до рута, генеря промежуточные ноды. Жадность - мержить узлы с двумя меньшими частотами. И результирующими узлу назначить суммарную частоту. Часто символы берут из маленького алфавита, например байты. Коды для кодировки являются строками бит, такие что каждый из кодов не является префиксом какого-либо другого кода (prefix-free code).

Вообще добиться variable-length code можно добиться так

1. Использовать fixed-length-code

2. Использовать специальный стоповый символ разделитель или использовать передающую среду для этого если в ней можно ввести такое понятие.

3. Использовать prefix-free коды. Хаффман в 1950 году показал, что код генерируемый его алгоритмом в некотором смысле оптимальный.

СЖАТИЕ LZW (как правило сжатие 2:1 для текстов)

Фиксируем длину слова. Пихаем в trie все символы алфавита.

Просматриваем поток данных, ищем максимально совпадающих элемент в trie-е, находим, и пихаем код этой строки в выход.

Добавляем в трай прочитанный только что "набор символов" + 1 ин следующий символ.

trie контейнер будет восстановлен стороной которая производит раскодировку. Она сама создаст его из потока. Вовремя разжатия требуется работать очень аккуратно.

Для строки ABABABA - делается достаточно большой трюк т.к., мы одновременно выполнили на прошлом шаге пихание кода строки, которой делаем на след. шаге expansion. Этот пример нужно обрабатывать аккуратно.

Эвристики

-- иногда после долгого использования Symbol Table (ST) чиститься

Построенные алгоритмы сжатия на основе LZW могут иметь разные эвристики, а иногда даже прибегать к кодам Хаффмана для сжатия.

LZ77, LZ78, LZW, DEFLATE/zlib = LZW+HAFFMAN

unix compress, TIFF, GIF = LZW

zip, gzip, jar, png, pdf = DEFLATE/zlib

GZIP (LZ77)

Ключевая идея - делать бек-ссылки на данные из прошлого. (оффсет, длинна).

Lossy Compression

отосланное данное != принятое данное. используется для аудио, видео, картинок

JPEG

- бьем данные на куски 8x8, переводим сигнал в frequency домен.

- квантизация результата

- RLE+Huffman

- Перевод цвета в YUV

Попробовать идею сжатия:

Читаем и копим байты, пока не встретили разных 2**4 чисел. Заполнили. Затем пилим остаток файла на чанки такого же размера, ищем похожие чанки.

Создаём таблицу перекодировки с fixed bit length encoding. Вырываем чанки из потока. Над остатком выполняем тоже самое.

в каждый чанк добавляется указатель на таблицу. A(16,256) = 256! / (256-16)! -- кол-во которым можно выбрать 16 чисел без повторений из 256. Цифра большая.

Графы

Самый короткий путь в Directed Acyclic Graph (DAG)

Отсортировать вершины в topological order и затем в этом порядке обработать все вершины выполнив relax для всех исходящих дуг. Для этого алгоритма веса могут быть отрицательными на рёбрах. Сложность алгоритим O(E+V).

Т.к. алгоритм позволяет иметь отрицательные веса, то его можно использовать для поиска самого длинного пути. Для этого надо поменять знак весов всех дуг. Одно из приложений это поиск самого длинного пути (критического пути) в расписании с параллельными работами.

Lg*(N) -- iterate log function. Кол-во раз сколько раз надо взять log2 чтобы получить 1. Можно считать, что на практике это просто число от 0 до 5.

Линейное программирование

Simplex algorithm (G. Dantzig, 1947, Stanford). Developed after WW II due to logistical problems.

Ranked as one of the top 10 scientific algorithms of 20th century.

1. Convvert constraint AX<B into linear equation via append extra slack variable in lhs => A'X'=B

2. Set n-m variables into zeros (non-basis variables).

Solve m equations with m unknowns. At first step setup all non-slack variables to zero.

3. If unique and feasible => extreme point

4. Select pivot -- take some non-bais variable from some equation, solve w.r.t. to this variable. Basis should replace some variable.

Purpose -- increase objection function

5. Stop selecting pivot when no objective coefficient is positive

Nobody knows choose pivot rule to garantee that algorithm will be polynomial.

People try to understand why it is consume polynomial time.

It is exist Ellipsoid algorithm which works in poly-time. But problem was open for decades. - R.Sedjvick

Строки

Поиск подстроки длинной M в строке длинной N. Количество символов в алфавите R.

Регулярные выражения

Активно исследуются с 1930 года.

1. Теорема Клини об эквивалентности регулярных выражений и детерм. конечных автоматов сформулирована и доказана Стефаном Клини из Принстона в 1934 году.

2. Плохая новость - построение DFA по регулярному выражению потенциально может иметь экспотенциальное кол-во стейтов.

3. Иногда разумнее использовать Non Deterministic finite state automate (NFA) отличие от DFA:

- там есть лямба (или эпсилон в зависимости от терминологии) переходы

- из некоторых состояний не ведут дуги и мы стопоримся

4. NFA допускает строчку если есть какая-та последовательность переходов в final state.

Алгоритм - поддерживать множество всех возможных состояний где может находиться автомат после прочтения i символов.

На каждом шаге мы смотрим где автомат может находиться. Смотрим куда мы теоретичеки можем попасть по пустым дугам. После поступления нового символа отбрасываем "некорректные" состояния.

Таким образом мы поддерживаем по сути все возможные пути прыганья по автомату.

Скорость в худшем случае O(MN)

Вычисления

linearithmic называют алгоритмы со сложностью O(Nlg(N)). Например построение convex hull точек на плоскости.

intractable - проблемы которые не могут быть решены за полиноминальное время.

np - решения проверяется за полиноминальное время. Никакого ограничения на сложность самого поиска решения мы не делаем. Также этот класс задач/проблем называется проблема поиска (search problems) у людей занимающимися алгоритмами.

NP это все те задачи, которые мы хотим решить. Что-то мы знаем как решать (например LP), что-то нет (например ILP мы пока не знаем как решить за полиноминальное время).

В общем кажется, что для np алгоритма решающего задачу за полиноминальное время кажется может не существовать. Т.е. быстрая проверка того, что решение верное ничего не гарантирует о сложности самого решения.

p - класс проблем для которых известны алгоритмы решения за полиноминальное время. полином определён от N, где N размер описания задачки. Например люди долгое время не знали есть ли алгоритм который решает задачу линейного программирования гарнатировано за полиноминальное время.

Решение проблемы нашёл Хачинян Л.Г. с предложенным методом эллипосидов в 1979 году. Иногда под P понимают алгоритмы которые решаются за полиноминальное время в живой припроде. Например в живой природе можно посроить дерево Штейнера.

Что такое задача SAT(Boolean satisfiability problem or SATISFIABILITY)

Дано n булевых переменных.

Есть m булевых выражений, каждое выражение содержит литерал X(i) (само X(i) или его отрицание).

В 3-SAT понимается что каждое выражение содержит только три литерала.

np-complete - Если любая NP проблема (вообще любая) редуцируется в вызову алгоритму решающему эту проблему, причём кол-во вызовов есть полином от объёма данных. Кажется очень абстрактным, однако! [Cook 1971, Levin 1973] доказали, что SAT np-complete! np-complete лежит внутри np. А более конкретно 3-SAT является NP-complete. Метод перебора O(2^n), где n-количество независимых переменных в булевом уравнении.

2-SAT не является np задачей, и например может быть сведена к поиску компонент в графе.

Tim Roughgarden: Cook жив и преподаёт до сих пор в университет Торонто, Левин был за железным зановесом из СССР и заняло время, то чтобы его результаты узнали на западе.Сейчас Левин является проффесором в Бостоновском университете.

Они показали, что Np-complete проблемы(задачи) существуют!

There is no exist more powerfull model of computation then Turing machine (Turing, Prinstone, ~1936).

Can be observed like most important scientific result of 20th century. Tuning machine is simple and universal model of computations.

It is not like a math theorem, because Church-Turing thesis said that Turing machine can compute any function which can be computed by Natural World. But during 8 decades passed without any counterexamples.

In practice really people can use only polynomial algorithms on real data. So "efficient" means "polynomial".

E.g. if you need to iterate over N! => it's algorithm is not efficient.

Expotential grow usually means no problem in hardware, but in algorithms.

Number electrons in universe are limited. It's 10^79! So even computer can hold all electrons in universe it still can not solve exponential problems. - R.Sedjvik

Which problems have polynomial times algorithms? Not so easy to answer. Very few successes.

Задача Штейнера

поиска максимального остовного леса, но с разрешением вводить новые вершины и новые ребра для дополнительного уменьшение веса формируемого дерева. Для этой задачи не существует эффективного (полиноминального) алгоритма.

Not Polynomial problems, but answer for which we can check in polynomial time - NP problems.

Это конкретные проблемы, достаточно общие которые мы хотим решить на практике, но пока не знаем как.

Структура решения

1. Формируем возможное решение.

2. Проверяем полиноминальным алгоритмом является это решением.

TSP (travelling salesman problem) - задача коммивояжера. найти кртачайший цикл между заданными n городами. Через каждый город путь проходит один раз. Travel Search Problem need N! steps for brute force. But we don't know polymial algorithm.

Формируем случайную последовательность из N городов. Вычисляем длину пути.

Задача относится к классу Np.

Проверить что один из предложенных путей имеет длину меньше чем какое-то пороговое число решается просто просмотром всех его ребёр.

Игра в шашки. Доказано, что проблема требует экспотенциальное время. NxN checkers. Can first player win?

Halting problem (Turing, 1939) Есть алгоритм и входные данные. Сможет ли алгоритм завершиться когда-нибудь? Проблема не разрешима на машине Тюринга. Tim Roughgarden: Тюринг в 1936 показал, что алгоритма, не важно на сколько медленного просто не существует для этой задачи. Данный вид задачи, показывает что всё таки существуют задачи, даже более сложные нежели TSP.

SAT. System of boolean equation. Система уравнений в булевой алгебре (левая часть - переменные, скобки, or, and. правая часть константна). Можно привести в форму где в каждом уравнении только or, и увеличить количество уравнений.

Для решения например можно перебрать все возможные наборы которых 2^N (Exhaustive Search).

Для решения СЛАУ требуется O(N^3) - метод Гаусса.

Для решения задачи Линейного Программирования (LP) существует полиномиальный Эллиптический алгоритм, который долгое время не могли найти (десятками лет) (ellipsoid method, Khachiyan, 1979)

Для решения задачи линейного программирования в целых числах (ILP) нет пока полиноминального алгоритма.

Для решения SAT тоже нет полиноминального алгоритма.

Мы не можем пока доказать как что он есть, так что его и не существует. Но доказано, что SAT является NP-complete.

Если мы можем SAT редуцировать в другой алгорититм X. То этот X тоже не будет обладать полиноминальным временем выполнения. Если мы предполагаем, что SAT не имеет эффективного алгоритма.

Факторизация целого числа. Brute force алгоритм с проверкой всех возможных делителей займёт 2^N, где N длина числа в битах.

3-SAT - SAT с тремя пермененными. Т.е. есть три булевские переменные. Tim Roughgarden: Можно легко проверить что переменные удовлетворяют системе, однако поиск решение занимает экспотенциальное время.

3-COLOR - раскрасить каждую вершину графа в один из трёх цветов, так чтобы соседние вершины с общим ребром не имели общего цвета

HAM-CYCLE - есть ли цикл в графе такой, что посещает каждую вершину только один раз.

HAM-PATH - Найти путь в графе, такой что посещает каждую вершину один раз. Если хочется посетить каждое ребро один раз то это будет называться Эйлеровским путём. И эта задача уже не является NP. Алгоритм решения HAM-PATH - это DFS по сути по всем возможным путям. Единственное отличие - перед выходом из Рекурсивного вызовы сбрасываем marked. И это делает алгоритм экспотенциальным.

LONGEST-PATH - NP complete.

SUBSET-SUM - есть некоторое подмножество натуральных чисел. Среди чисел требуется найти подмножество в сумме дающих число k.

PARTITION - разделить множество чисел на две кучки так, что сумма чисел в одной была бы равна сумме чисел в другой.

KNAPSACK - задача о ранце. у каждого предмета есть вес и стоимость. задача запихнуть предметы в рюкзак, соблюдая весовое ограничение и максимизируя стоимость.

BIN-PACKING - задача упаковки корзин.Даны n предметов и их размеры - скаляры от 0.0 до 1.0. Требуется разместить в наименьшее количество корзин размером 1.

VERTEX COVER, CLIQUE, EXACT COVER - ещё другие NP проблемы.

VERTEX COVER - "дополнение" задачи о WIS. Т.е. теперь надо брать вершины такие, что минимизируется сумма весов, и для каждой вершины есть хотя бы одна смежная.

То, что невозможно создать алгоритм например факторизации числа за полиноминальное время можно использовать как основу для создания криптостойкой защиты.

Weight Independent Set (WIS)

Есть линейный список (граф) с вершинами. У каждой вершины свой вес. Найти подмножество вершин, такое что сумма весов максимальна и вершины в этом множестве не являются соседними. Данная задача решается с помощью динамического программирования за полиномиальное время.

Однако, если рассмотреть эту задачу для общего случая произвольного графа, то задача относится к классу NP.

Если столкнулись с NP проблемой

1) Посмотреть, может быть у вас специальный случай проблемы NP, когда сложность полиномиальная.

2) Может быть размер входных данных очень мал.

3) Может быть есть некоторые переменные "важные" а остальные формируют какой-то special case => можно скомбинировать (1) + (2) для решения задачи.

4) Отказаться от точного решения и использовать эвристику. Пример вероятностный алгоритм Karger-а поиска minimum cut на графе.

5) Возможно стоит построить алгоритм который делает не совсем brute-force, а немного дела поумнее. Например динамический вариант Knapsack работает за время O(nw), а не за O(2^n). Правда он требует чтобы веса w(i) были целыми числами, а не действительными.

TSP в лоб требует вообще перебора n!, однако можно построить алгоритм за O(2^n).

Как оценивать алгоритм

1. Измерить время как функцию от размера входа T=T(N), затем нарисовать lg(T) и lg(N). Для показательной зависимости с показателем "k" данная зависимость на log-log графике будет прямая с угловым коэффициентом k. Алгоритм и входные данные определяют в основном форму T(n). Скорость процессора, итерпретатора, скороть сети определяют коэффициента в зависимости T(n).

2. Если мы придумали алгоритм для решения проблемы. Чтобы доказать что какая-та функция не является "точным" lower bound - придумывают новый алгоритм который выполняется быстрее и lower bound сдвигается.

3. Обычно достаточно сложно доказать какие-либо утверждения про нетривиальные lower bound (как для union find). И таких мы узнаем очень мало.

4. Обычно мы не интересуемся худшим случаем, но иногда это очень важно чтобы иметь гарантии.

5. Big-O нотация очень плохая, лучше использовать нотацию из мат. анализа с помощью Тильды. Буквы "Тета" нет на клавиатуре, иногда люди не рисуют тильду внутри буквы O, это всё приводит к тому что статьи за статьей содержат ошибки (R. Sedjvik)

6. Если алгоритм X с гарантированной lower bound можно редуцировать до вызовов другого алгоритма Y. То это гарантирует lowe bound на Y. Т.к. иначе этот алгоритм будет служить моделью для более быстрой реализации X. Однако мы препдолагаем, что мы доказали lower bound на задачу X.

Таким образом можно доказать что решение задачи на поиск convex hull lower bound есть O(N lg(N)).

Сортировка может представлена как поиск conex hull точек (x[i], x[i]^2). Таким образом не стоит тратить время на поиск улучшения алгоритма Грекхема поиска convex hull.

Варианты решения некоторых проблем

1. 3-summ problem

Найти три элемента в сумме дающих ноль.

Naive -- O(N^3)

Sort за Nlg(N) и после этого перебрать все пары за N^2 и для каждой пары i,j попробовать найти -(a[i]+a[j]) через binary search

O(N^2 lg(N)). Кстати это метод будет работать в принципе и с приближенной float арифметикой.

Upper bound можно установить brute force алгоритмам, но очень тяжело установить lower bound для всех алгоритмов решающих задачу. Здесь имеется gap в сложности.

Можно решить эту задачу с использованием хеш-таблицы за O(N^2), но пока не известно:

1. Можно ли её решить быстрее чем за O(N^2)

2. Что является lower bound для всех решений этой задачи

2. Случайное перемешивание массива

* Для каждого элемента массива сгенерировать случайное число [0,1]

* Отсортировать элементы массива по сгенерированному ключу

Shuffle sort produces a uniformly random permutation of the input array, provided no duplicate values.

Алгоритм Кнута:

1. На итерации i выбрать случайное целое число r от [0, Size-1]

2. Переставить элемент i и элемент r

[Fisher-Yates 1938] Knuth shuffling algorithm produces a uniformly random permutation of the input array in linear time.

3. Shortest path with obstacle

Shortest path is either straight line from s to t or it is one of two polygonal chains of convex hull of (obstacle object, source, destination)

Graham Scan can be used to build convex hull of points in 2D.

3. Farthest two points

Farthest pair of points are extreme points on convex hull of points.

Доп. ссылки:

http://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/27/Small27.pdf

Page updated

Google Sites

Report abuse