Список алгоритмів

Зміст

1 Комбінаторні алгоритми
2 Стиснення даних
- 2.1 Стиснення без втрат
- 2.2 Стиснення з втратами
3 Обчислювальна геометрія
- 3.1 Побудова опуклої оболонки множини точок
- 3.2 Тріангуляція
4 Криптографічні алгоритми
5 Розробка програмного забезпечення
6 Дивіться також

Комбінаторні алгоритми [ред.]

Алгоритми на графах [ред.]

Алгоритм Беллмана-Форда — знаходить найкоротші шляхи у зваженому графі (де деякі ваги ребер можуть бути негативними)
Алгоритм Борувки — знаходить мінімальне основне дерево в графі
Алгоритм Брона-Кербоша — знаходження найбільших максимальних незалежних по включенню множин вершин графа.
Алгоритм Воршала — обчислює всі найкоротші шляхи в підвішеному графі
Алгоритм Дейкстри — обчислює найкоротший шлях у графі з невід'ємними вагами ребер
Алгоритм Крускала — знаходить остовний ліс мінімальної ваги в графі
Алгоритм заснований на джерелі (англ.) — алгоритм для малювання графа
Алгоритм Прима — знаходить остовне дерево мінімальної ваги у зв'язному графі
Алгоритм Флойда-Воршала — розв'язує проблему знаходження всіх пар найкоротших шляхів в підвішеному направленому графі
Алгоритм Форда-Фалкерсона (англ.) — обчислює максимальний потік у графі
Алгоритм Кристофідеса — евристичний наближений алгоритм для вирішення метричного завдання комівояжера на графі.
Алгоритм Едмонса-Карпа (англ.) — модифікація алгоритму Форда-Фалкерсона
Метод найближчого сусіда
Неблокуючий мінімальний охоплюючий перемикач наприклад, для телефонного зв'язку

Алгоритми пошуку [ред.]

Докладніше: Алгоритми пошуку

Лінійний пошук (Linear search): шукає елемент у не відсортованому списку
Алгоритм вибору (Selection algorithm): знаходить k-ий найбільший елемент
Двійковий пошук (Binary search algorithm): шукає елемен у впорядкованому списку
Бінарне дерево пошуку (Binary search tree): використовує бінарне дерево для збереження елементів
Пошук в ширину (Breadth-first search): обходить граф рівень за рівнем
Пошук в глибину (Depth-first search): обходить граф гілка за гілкою
Пошук в глибину з ітеративним заглибленням (Iterative deepening depth-first search): обходить граф гілка за гілкою щоразу збільшуючи глибину обходу
Пошук за першим кращим збігом (Best-first search): обходить граф в порядку важливості елементів, використовуєтсья черга з пріоритетами
Алгоритм пошуку A* (A-star search algorithm): окремий випадок пошуку за найкращим шляхом, що використовує евристику для покращення швидкодії
Алгоритм пошуку SMA* (en:Simplified Memory-Bounded A-star search algorithm) : модифікація алгоритму А* з обмеженим використанням пам'яті
Алгоритм пошуку D* (en:D*): вдосконалений варіант А*, враховує нову інформацію про середовище
Пошук за критерієм вартості (Uniform-cost search): алгоритм пошуку на деревах, що знаходить найдешевший шлях
Інтерполяційний алгоритм пошуку (Interpolation search): подібний до алгоритму двійкового пошуку
Хеш-таблиця (Hash table): шукає елемент у невпорядкованій множині за час O(1)

Рядкові алгоритми [ред.]

Пошук на рядках [ред.]

Докладніше: Алгоритм пошуку рядка

Алгоритм Аха-Карасіка (Aho-Corasick algorithm): алгоритм оснований на дереві префіксів (trie) що знаходить всі збіги в словнику
Алгоритм Бітап: нечіткий алгоритм, що з'ясовує приблизну рівність рядків
Алгоритм Бояра-Мура
Алгоритм Кнута-Моріса-Прата: не проводить повторної перевірки рівних літер
Алгоритм Рабіна-Карпа: ефективний пошук за багатьма шаблонами
Пошук найдовшої спільної підпослідовності: динамічний алгоритм Хаскеля
Longest increasing subsequence problem
Пошук найкоротшої спільної надпослідовності (Shortest common supersequence )
Пошук найдовшого спільного рядка (longest common substring problem)
Алгоритм Кадана (Kadane's Algorithm): знаходить максимальний підмасив довільного розміру
Алгоритм Бояра-Мура-Горспула (Boyer-Moore-Horspool algorithm)

Приблизний збіг [ред.]

Алгоритм Гіршберга (Hirschberg's algorithm): алгоритм знаходження відстані редагувань
Відстань Левенштейна
Метафон (Metaphone): алгоритм індексування слів за їх вимовою в англійській мові
Алгоритм Нідлмана-Вунша (Needleman-Wunsch algorithm)
NYSIIS (NYSIIS): фонетичний алгоритм
Алгоритм Сміта-Вотермана (Smith-Waterman algorithm)
Саундекс (Soundex)

Алгоритми сортування [ред.]

Докладніше: Алгоритми сортування

Сортування бінарним деревом
Сортування Бого
Сортування стандартним обміном (сортування бульбашкою): для кожної пари індексів, поміняти місцями невпорядковані елементи
Сортування комірками
Сортування змішуванням Cocktail sort
Сортування гребінцем Comb sort (модифікація сортування бульбашкою)
Сортування підрахунком
Сортування гнома Gnome sort
Flashsort
Сортування купою: занести список у купу, видаляти найбільший елемент купи та записувати його у кінець списку
Сортування вставкою: з'ясувати місце, на яке слід поставити поточний елемент, та вставити його туди
Сортування вставкою з проміжками en:Library sort
Сортування злиттям: відсортувати першу та другу половину списку окремо, а потім об'єднати їх в один список
Pancake sorting
Цифрове сортування Pigeonhole sort
Швидке сортування: розділити список на дві частини, так, щоб всі елементи першої частини не перевищували елементи з іншої, відсортувати обидві частини
Сортування за розрядами: сортування рядків літера за літерою
Сортування вибором: обрати найменший елемент із решти списку, та перенести його в кінець відсортованої частини
Сортування Шелла: спроба покращити сортування вставкою
Пірамідальне сортування Smoothsort
Топологічне сортування Topological sorting

Стиснення даних [ред.]

Стиснення без втрат [ред.]

Стиснення з втратами [ред.]

Обчислювальна геометрія [ред.]

Побудова опуклої оболонки множини точок [ред.]

Алгоритм Грехема — трудомісткість $O(n\log n)$ .
Алгоритм швидкої оболонки QuickHull — трудомісткість $O(n^2)$ , в середньому — $O(n\log n)$ .
Алгоритм загортання подарунка (Джарвіса) — трудомісткість $O(nh)$ , $h$ — кількість точок опуклої оболонки.
Алгоритм Киркпатріка — Зейделя Kirkpatrick–Seidel algorithm — трудомісткість $O(n\log h)$ , $h$ — кількість точок опуклої оболонки.
Алгоритм Чана Chan's algorithm — трудомісткість $O(n\log h)$ , $h$ — кількість точок опуклої оболонки.
Динамічна підтримка опуклої оболонки