Список алгоритмів
Матеріал з Вікіпедії — вільної енциклопедії.
Зміст |
Комбінаторні алгоритми [ред.]
Алгоритми на графах [ред.]
- Алгоритм Беллмана-Форда — знаходить найкоротші шляхи у зваженому графі (де деякі ваги ребер можуть бути негативними)
- Алгоритм Борувки — знаходить мінімальне основне дерево в графі
- Алгоритм Брона-Кербоша — знаходження найбільших максимальних незалежних по включенню множин вершин графа.
- Алгоритм Воршала — обчислює всі найкоротші шляхи в підвішеному графі
- Алгоритм Дейкстри — обчислює найкоротший шлях у графі з невід'ємними вагами ребер
- Алгоритм Крускала — знаходить остовний ліс мінімальної ваги в графі
- Алгоритм заснований на джерелі (англ.) — алгоритм для малювання графа
- Алгоритм Прима — знаходить остовне дерево мінімальної ваги у зв'язному графі
- Алгоритм Флойда-Воршала — розв'язує проблему знаходження всіх пар найкоротших шляхів в підвішеному направленому графі
- Алгоритм Форда-Фалкерсона (англ.) — обчислює максимальний потік у графі
- Алгоритм Кристофідеса — евристичний наближений алгоритм для вирішення метричного завдання комівояжера на графі.
- Алгоритм Едмонса-Карпа (англ.) — модифікація алгоритму Форда-Фалкерсона
- Метод найближчого сусіда
- Неблокуючий мінімальний охоплюючий перемикач наприклад, для телефонного зв'язку
Алгоритми пошуку [ред.]
- Лінійний пошук (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
Стиснення даних [ред.]
Стиснення без втрат [ред.]
Стиснення з втратами [ред.]
Обчислювальна геометрія [ред.]
Побудова опуклої оболонки множини точок [ред.]
- Алгоритм Грехема — трудомісткість
. - Алгоритм швидкої оболонки QuickHull — трудомісткість
, в середньому —
. - Алгоритм загортання подарунка (Джарвіса) — трудомісткість
,
— кількість точок опуклої оболонки. - Алгоритм Киркпатріка — Зейделя Kirkpatrick–Seidel algorithm — трудомісткість
,
— кількість точок опуклої оболонки. - Алгоритм Чана Chan's algorithm — трудомісткість
,
— кількість точок опуклої оболонки. - Динамічна підтримка опуклої оболонки
Тріангуляція [ред.]
- Жадібна тріангуляція — трудомісткість
.
Тріангуляція Делоне [ред.]
Псевдотріангуляція [ред.]
Діаграма Вороного [ред.]
- Алгоритм побудови діаграми Вороного через замітаючу пряму Fortune's algorithm — трудомісткість
.
Криптографічні алгоритми [ред.]
- Асиметричні алгоритми (алгоритми з відкритим ключем):
- Криптографічні хешувальні функції:
- Криптографічні генератори псевдовипадкових чисел
- Алгоритм Блум Блум Шуба — базується на складності факторизації цілих чисел
- Fortuna, розглядався в якості покращення у порівнянні з алгоритмом Яроу
- Лінійний зсувний регістр зі зворотнім зв'язком
- Алгоритм Яроу
- Обмін ключами
- Поділ секрету
- Схема Блекі
- Схема Шаміра
- Симетричні алгоритми (алгоритми з секретним ключем):
- Advanced Encryption Standard (AES), переможець на конкурсі NIST, також відомий як «Алгоритм Рейндайля»
- Blowfish
- Twofish
- Threefish
- Serpent
- Data Encryption Standard (DES), інколи DE Algorithm, переможець конкурсу NBS, замінений AES для більшості застосувань
- Triple DES, особливий режим шифрування алгоритмом DES.
- IDEA
- RC4
- Tiny Encryption Algorithm
Розробка програмного забезпечення [ред.]
Алгоритми для баз даних [ред.]
Розподілені обчислення [ред.]
Алгоритми виділення/звільнення пам'яті [ред.]
Операційні системи [ред.]
- Алгоритм банкіра: Алгоритм уникнення взаємних блокувань.
- Алгоритм хулігана: Вибір нового лідера із багатьох ком'ютерів.
- Алгоритми заміни сторінок (англ.): Вибір сторінки для заміни в умовах браку пам'яті.
- Адаптивний кеш замін (англ.): швидкодія краща за попередній алгоритм.


.
, в середньому —
,
— кількість точок опуклої оболонки.
,
.