Нижче наведений не вичерпний список алгоритмів Комбінаторні алгоритмиАлгоритми на графах Обхід графа Пошук в ширину обхо

Нижче наведений не вичерпний список алгоритмів.

Комбінаторні алгоритми

Алгоритми на графах

Обхід графа

Пошук в ширину: обходить граф рівень за рівнем
Пошук в глибину: обходить граф гілка за гілкою
(Пошук в глибину з ітеративним заглибленням): обходить граф гілка за гілкою щоразу збільшуючи глибину обходу
(Пошук за першим найкращим збігом): обходить граф в порядку важливості елементів, використовується черга з пріоритетами

Сортування

Топологічне сортування — будується коректна послідовність виконання дій, будь-яка з яких може залежати від іншої

Компонента зв'язності графа

(Алгоритм Косараджу) (матриця суміжності $O(V^{2})$ , список суміжності $O(V+E)$ ) — алгоритм для знаходження компонент сильної зв'язності орієнтованого графа
Міст $O(|V|+|E|)$ — ребро, видалення якого збільшує кількість компонент зв'язності
(Двозв'язна компонента (Шарнір)) — вершина, видалення якого збільшує кількість компонент зв'язності
^[en] (Габова)
(Алгоритм Тар'яна)

Побудова кістякового дерева

(Алгоритм Борувки) ( $\mathop {O} (E\log V)$ ) — знаходить мінімальне кістякове дерево в графі
Алгоритм Крускала ( $\mathop {O} (E\log E)$ ) — знаходить мінімальне кістякове дерево в графі
Алгоритм Прима (списки суміжності (матриця суміжності) $O(V^{2})$ ) — знаходить кістякове дерево мінімальної ваги у зв'язному графі
нім. Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes

Пошук найкоротшого шляху

Алгоритм Дейкстри ( $O(|E|+|V|\log |V|)$ ) — обчислює найкоротший шлях у графі з невід'ємними вагами ребер
(Алгоритм Флойда — Воршелла) ( $O(|V|^{3})$ ) — розв'язує проблему знаходження всіх пар найкоротших шляхів в підвішеному направленому графі
(Алгоритм Джонсона) ( $O(V^{2}\log V+VE)$ ) — обчислює найкоротші шляхи між усіма парами вершин зваженого орієнтованого графа
(Алгоритм Беллмана — Форда) ( $O(|V||E|)$ ) — знаходить (найкоротші шляхи) у зваженому графі (де деякі ваги ребер можуть бути негативними)
(Алгоритм Левіта) — знаходження найкоротших шляхів до всіх вершин
(Алгоритм пошуку A*) ( $O(|V|\cdot \log |V|)$ ) — пошук найкоротшого шляху між двома вершинами з додатніми вагами ребер.
англ. Min-plus matrix multiplication
(Алгоритм Данцига) — знаходження найкоротших шляхів до всіх вершин планарний планарного спрямованого графа
(Алгоритм Лі)(Хвильовий алгоритм) — дозволяє знайти мінімальний шлях в графі з ребрами одиничної довжини.

Розфарбовування графів

Вершинне розфарбовування графів
- (Жадібна розмальовка)

Пошук найвигіднішого шляху

Задача комівояжера
- Метод найближчого сусіда
- ^[en]
- (Алгоритм інтелектуальних крапель) — алгоритм рою (колективного інтелекту) на основі алгоритму оптимізації

Потоки в мережах

Алгоритм Форда — Фалкерсона (1956) — обчислює максимальний потік у графі
(Алгоритм Едмондса — Карпа) (1969) — модифікація алгоритму Форда — Фалкерсона
(Алгоритм Дініца) (1970)
^[] (1972) — локально-максимального збільшення
(Алгоритм Дініца) 2 (1973)
(1974)
(1977)
(1977)
(1980)
(1980)
(1983)
(1985)
^[en] (1988)
(1989)
(1989)
1 (1992)
2 (1994)
(1996)
(1998)
(2010)
1 (2012)
2 (2012)

Кліки

(Алгоритм Брона-Кербоша) — пошуку всіх клік (знаходження найбільших максимальних незалежних по включенню множин вершин графа).

Цикли

Парування

(Алгоритм Гопкрофта — Карпа) ( $O(E{\sqrt {V}})$ ) — знаходить найбільше парування в двочастковому графі
(Угорський алгоритм (алгоритм Куна)) ( $O(n^{4})$ ) — знаходження парування мінімальної (або максимальної) ваги між елементами двох скінчених множин за поліноміальний час

Ізоморфізм

Ласло Бабай [ 16 серпня 2016 у Wayback Machine.]

Інше

(Алгоритм на основі пружин) — алгоритм для малювання графа
наприклад, для телефонного зв'язку
^[en] — алгоритм пошуку спільнот в складних системах (соціальних мережах).

Алгоритми пошуку в масиві (списку,...) даних

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

Елементи впорядковані (відсортовані)

Двійковий пошук: шукає елемент у впорядкованому списку
(Інтерполяційний алгоритм пошуку): подібний до алгоритму двійкового пошуку

Елементи не впорядковані (не відсортовані)

Лінійний пошук: шукає елемент у не відсортованому списку
(Алгоритм вибору): знаходить k-ий найбільший елемент
Хеш-таблиця: шукає елемент у невпорядкованій множині за час O(1)

Із створення нової структури

Бінарне дерево пошуку: використовує бінарне дерево для збереження елементів
(Алгоритм пошуку SMA*): модифікація алгоритму А* з обмеженим використанням пам'яті
(Алгоритм пошуку D*): вдосконалений варіант А*, враховує нову інформацію про середовище
(Пошук за критерієм вартості): алгоритм пошуку на деревах, що знаходить найдешевший шлях

Алгоритми пошуку в рядках

Пошук на рядках

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

(Алгоритм Ахо — Корасік): алгоритм оснований на (дереві префіксів), що знаходить всі збіги в словнику
^[en] - нечіткий алгоритм, що з'ясовує приблизну рівність рядків
^[en] - знаходить максимальний підмасив довільного розміру
(Алгоритм Кнута — Моріса — Прата): не проводить повторної перевірки рівних літер
: подібно до алгоритму Ахо — Корасік шукає всі збіги в словнику
(Алгоритм Рабіна — Карпа): ефективний пошук за багатьма шаблонами
Пошук найдовшої спільної підпослідовності: динамічний алгоритм Хаскеля
(Найдовша зростаюча підпослідовність)
^[en]
(Пошук найдовшого спільного рядка)

Приблизний збіг

^[en] - алгоритм знаходження відстані редагувань
(Відстань Левенштейна)
(Метафон): алгоритм індексування слів за їх вимовою в англійській мові
(Алгоритм Нідлмана — Вунша)
(NYSIIS): фонетичний алгоритм
^[en]
Саундекс

(Алгоритм сортування)

Сортування обміном

Сортування бульбашкою
(Сортування змішуванням)
(Парне-непарне сортування (сортування цеглинами))
(Сортування гребінцем)
(Сортування гнома)
Швидке сортування
(Stooge sort)
(Випадкове сортування)

Сортування вибором

(Сортування вибором)
(Пірамідальне сортування)
(Плавне сортування)
(Декартове дерево)
^[en]

Сортування включенням

(Сортування включенням)
(Сортування Шелла)
Двійкове дерево пошуку
^[en]
^[en]
(Сортування двійковим деревом)
^[en]
^[en]
^[en]

Сортування злиттям

(Сортування злиттям)
(Ниткоподібне сортування)
^[en]
^[en]
^[en]

Алгоритми без порівнянь

(Сортування за розрядами)
(Сортування комірками)
(Сортування підрахунком)
(Цифрове сортування)
^[en]
^[en]

Гібридні

(Timsort)
^[en]
^[en]
^[en]

Інші

Імовірнісні алгоритми

^[en]
(Лас-Вегас (алгоритм))
Алгоритм Монте-Карло

Інформатика

Докладніше: Інформатика

Архітектура комп'ютера

Докладніше: Архітектура комп'ютера

(Алгоритм Томасуло)

Комп'ютерна графіка

Докладніше: Комп'ютерна графіка

(Відсікання)
- Відсікання ліній
  - (Алгоритм Коена — Сазерленда)
  - (Алгоритм Кіруса — Бека)
  - (Алгоритм Ліангу–Барського)
Ізолінії та (Ізоповерхні)
- (Marching cubes)
- ^[en]
- ^[en]: альтернатива (Marching cubes)
(Заливка): заповнення зв'язної області багатовимірного масиву вказаним символом
(Глобальне освітлення): Враховується безпосереднє освітлення та віддзеркалені промені
- (Ambient occlusion)
- ^[en]
- ^[en]
- ^[en]
- ^[en]
- (Трасування шляху)
- (Метод фотонних карт)
- Освітлення
- Трасування променів
^[en]
- (Алгоритм Ньюелла): видалення зациклень полігонів при сортуванні у глибину при видаленні прихованої поверхні
- (Алгоритм художника): визначення видимих частин тривимірної сцени
- Алгоритм «Scanline»
- ^[en]
(Алгоритми побудови відрізка): апроксимація відрізка на дискретний графічний пристрій
- (Алгоритм Брезенхейма): зображення точок відрізка за заданими кінцями з використанням тільки цілих чисел
- (Алгоритм DDA-лінії): зображення точок відрізка за заданими кінцями з використанням чисел з рухомою комою
- Алгоритм Ву: використовується для екранного згладжування
(Растеризація кола): визначає точки необхідні для малювання кола
(Алгоритм Рамера — Дугласа — Пекера): дозволяє зменшити кількість точок для апроксимації кривої
Шейдинг
- (Затемнення за Гуро): імітує ефект освітлення поверхні в 3D графіці
- (Затемнення за Фонгом): використовує інтерполяцію векторів-нормалей до поверхні для обчислення затемнення
(Slerp) (сферична лінійна інтерполяція, англ. spherical linear interpolation): інтерполяція кватерніонами, використовується для анімації 3D обертання
(Інтегральне зображення): алгоритм для обчислення суми значень у прямокутній підмножині

Криптографічні алгоритми

Докладніше: Криптографія

Асиметричні алгоритми (алгоритми з відкритим ключем):
- (DSA)
- Схема Ель-Гамаля
- RSA
Криптографічні хешувальні функції:
- (BLAKE)
- (HMAC)
- (Keccak)
- (MD2)
- MD4
- (MD5) — слід зазначити, що існує метод генерації колізій для MD5
- (MD6)
- (RIPEMD-160)
- SHA-1
- SHA-2
- SHA-3
- Skein
- (Tiger) (TTH), зазвичай використовується в (геш-деревах)
Криптографічні генератори псевдовипадкових чисел
- (Алгоритм Блум Блум Шуба) — базується на складності факторизації цілих чисел
- (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)

Стиснення даних

Стиснення без втрат

Стиснення з втратами

Обчислювальна математика

Докладніше: Обчислювальна математика

Абстрактна алгебра

Докладніше: Абстрактна алгебра

Алгоритми оптимізації

Докладніше: Оптимізація (математика)

(Лінійний пошук)

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

Головна категорія:

Докладніше: Обчислювальна геометрія

Задачі геометричного пошуку (запиту)

(Локалізація точки)

(Належність точки многокутнику) — визначити чи точка знаходиться ззовні чи всередині даного многокутника. Трудомісткість — $O(n)$ .
(Найближча пара точок)

(Побудова) опуклої оболонки множини точок

Докладніше: (Алгоритми обчислення опуклої оболонки)

(Алгоритм Грехема) — трудомісткість $O(n\log n)$ .
(Алгоритм загортання подарунка) (Джарвіса) — трудомісткість $O(nh)$ , $h$ — кількість точок опуклої оболонки.
(Алгоритм Ендрю) — трудомісткість $O(n\log n)$ . Вдосконалений алгоритм Грехема.
(Алгоритм Кіркпатрика — Зейделя) — трудомісткість $O(n\log h)$ , $h$ — кількість точок опуклої оболонки.
(Алгоритм Чена) — трудомісткість $O(n\log h)$ , $h$ — кількість точок опуклої оболонки.
(Алгоритм швидкої оболонки) — трудомісткість $O(n^{2})$ , в середньому — $O(n\log n)$ .
(Задача динамічної підтримки опуклої оболонки)

Тріангуляція

Тріангуляція многокутника — розкладання простого многокутника на множину трикутників
Тріангуляція Делоне множини P, коли жодна точка множини P не знаходиться всередині кола описаного довкола трикутника з тріангуляції
(Псевдотріангуляція) — розбиття на псевдотрикутники

Діаграма Вороного

(Алгоритм Форчуна) — алгоритм побудови діаграми Вороного через замітаючу пряму. Трудомісткість $O(n\log n)$ .

(Перетин відрізків)

(Алгоритм Бентлі — Оттманна)

Символьні обчислення

Докладніше: Символьні обчислення

Ділення многочленів

Теорія чисел (алгоритми)

Докладніше: Теорія чисел

(Двійковий алгоритм обчислення найбільшого спільного дільника) — ефективний спосіб обчислення НСД.

Чисельні методи

Докладніше: Чисельні методи

Диференціальні рівняння

Докладніше: Диференціальні рівняння

Метод Ейлера

Елементарні та спеціальні функції

Докладніше: Спеціальні функції

Інтерполяція та екстраполяція

Докладніше: Інтерполяція і екстраполяція

Монте-Карло

Докладніше: Метод Монте-Карло

Пошук коренів

Докладніше: Методи розв'язання нелінійних рівнянь

Чисельне інтегрування

Докладніше: (Чисельне інтегрування)

Розробка програмного забезпечення

Алгоритми для баз даних

Розподілені обчислення

(Алгоритм вибору лідера) — позначення одного процесу як організатора завдання, розподіленого між декількома вузлами.

Алгоритми виділення/звільнення пам'яті

Операційні системи

(Алгоритм банкіра): Алгоритм уникнення взаємних блокувань.
(Алгоритм хулігана): Вибір нового лідера із багатьох комп'ютерів.
(Алгоритми заміни сторінок): Вибір сторінки для заміни в умовах браку пам'яті.
- ^[en]: швидкодія краща за попередній алгоритм.

Планування роботи з дисками

Комп'ютерні мережі

Алгоритми синхронизації процесів

(Алгоритм Декера)
(Алгоритм пекарні Лампорта)
Алгоритм Пітерсона

Алгоритми планування

Машинне навчання та статистична класифікація

Статистична класифікація

Машинне навчання

Кероване навчання

Прихована марковська модель
Баєсова мережа
- Наївний баєсів класифікатор
Метод найближчих k-сусідів
(Дисперсійний аналіз)
(Випадковий ліс)
Метод опорних векторів
(Мінімальна довжина повідомлення)
Ледаче навчання
(Навчання на прикладах)
(Метод групового урахування аргументів)
(Кригінг)
(Умовне випадкове поле)
- (Bootstrap aggregating)
- (Підсилювання (машинне навчання))
^[en]
(Ймовірнісно приблизно коректне навчання)
^[en]
^[en]
^[en]
^[en]
^[en]
^[en]
(Навчання асоціативних правил)
- (Алгоритм Apriori)
- ^[en]
^[en]
Метод зворотного поширення помилки — метод навчання багатошарового перцептрону

Некероване навчання

ЕМ-алгоритм
^[en]
^[en]

Напівкероване навчання

Навчання з підкріпленням

Метод часових різниць
Q-навчання
^[en]
(State-Action-Reward-State-Action)

Глибоке навчання

Глибока мережа переконань
(Машина Больцмана)
Згорткова нейронна мережа
Рекурентна нейронна мережа
(Ієрархічна часова пам'ять)

Інше

Самоорганізаційна Карта Кохонена - методом проектування багатовимірного простору в простір з нижчою розмірністю. Нейронна мережа з нескерованим навчанням, що виконує завдання кластеризації
(Метод корекції помилки) - метод навчання перцептрона
(Метод корекції зі зворотною передачею сигналу помилки) - метод навчання перцептрона

Інші

Аналіз потоків даних

(Фільтр Блума)
^[en])
(Alon-Matias-Szegedy Algorithm)
(Datar-Gionis-Indyk-Motwani Algorithm)

Множення матриць

Алгоритм перемножування матриць
Алгоритм Штрассена (1969)
(1978)
(1979)
(1981)
(Алгоритм Копперсміта — Вінограда) (1990)

Інші

Алгоритм Кулі — Тьюкі - алгоритм швидкого перетворення Фур'є
(Алгоритм Лукаса — Канаде) - диференційний локальний метод обчислення оптичного потоку
Алгоритм обчислення дня тижня
(Алгоритм Барнса — Хата) - моделювання гравітаційної задачі з N тіл відповідно до класичної гравітаційної теорії Ньютона
(Алгоритм Бута) - алгоритм добутку, який дозволяє здійснювати операцію добутку пари знакових двійкових чисел у додатковому коді
(Алгоритм Дойча — Йожи) - полягає у визначенні, чи є функція двійкової змінної $f(n)$ константою або збалансованою.
(Алгоритм зозулі) - розв'язування різноманітних задач оптимізації
(Алгоритм AC-3) - розв'язання зада́ч викона́ння обме́жень
(Алгоритм Шеннона — Фано) - один з перших алгоритмів стиснення
Алгоритм Шьонхаге — Штрассена - алгоритм множення великих цілих чисел
(Алгоритм Діксона) - є універсальним алгоритмом факторизації
(Метафон) - фонетичний алгоритм, для індексації слів в англійській вимові.
Саундекс - фонетичний алгоритм для індексації назв за звучанням, в англійській мові.
(CSA) - алгоритм шифрування, який використовується для захисту цифрового телевізійного потоку від несанкціонованого доступу.
(OPTICS) - алгоритм знаходження щільності на основі кластерів у просторових даних.
(Random forest) - алгоритм машинного навчання
(RBFS) - Рекурсивний пошук по першому найкращому збігу
(Алгоритм Кехена) - алгоритм обчислення суми послідовності чисел з рухомою комою
Алгоритм Евкліда - метод обчислення найбільшого спільного дільника
(Швидке піднесення до степеня) - алгоритм, призначений для піднесення числа x до натурального степеня n
Числа Фібоначчі - швидкий алгоритм обчислення чисел Фібоначчі
(Алгоритм Вітербі) - алгоритм пошуку найбільш відповідного списку станів (званого шляхом Вітербі)
(Метод Якобі)
(Стемінг) - скорочення слова до основи шляхом відкидання допоміжних частин
Алгоритм Луна - використовується для перевірки різних ідентифікаційних номерів
^[en]
(Офлайновий алгоритм Тар'яна для пошуку найближчого спільного предка)
(Алгоритм Тар'яна для обчислення сильно зв'язних компонентів)
(Криптографія на ґратках)
(Алгоритм Шора)
Karp-Papadimitriou-Shenker algorithm
Sticky sampling
Sample and Hold
Multi-stage
Count-sketch
Sketch-guided sampling
(Метод Куайна) - спосіб мінімізації функцій алгебри логіки
Метод Куайна — Мак-Класкі - табличний метод мінімізації булевих функцій
Карта Карно - метод спрощення виразів булевої алгебри

Див. також

Список структур даних

Посилання

. AlgoList. Архів оригіналу за 24 березня 2022. Процитовано 29 березня 2022. (рос.)