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

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

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

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

Обхід графа

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

Сортування

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

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

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

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

• Алгоритм Борувки ($\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
• Алгоритм Данцига — знаходження найкоротших шляхів до всіх вершин планарний планарного спрямованого графа
• Алгоритм Лі(Хвильовий алгоритм) — дозволяє знайти мінімальний шлях в графі з ребрами одиничної довжини.

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

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

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

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

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

• Алгоритм Форда — Фалкерсона (1956) — обчислює максимальний потік у графі
• Алгоритм Едмондса — Карпа (1969) — модифікація алгоритму Форда — Фалкерсона
• Алгоритм Дініца (1970)
• Алгоритм Едмондс - Карпа^{[прояснити]} (1972) — локально-максимального збільшення
• Алгоритм Дініца 2 (1973)
• Алгоритм Карзанова (1974)
• Алгоритм Черкаського (1977)
• Алгоритм Малхотри — Кумара — Махешварі (1977)
• Алгоритм Галіла (1980)
• Алгоритм Галіла — Наамада (1980)
• Алгоритм Слейтора — Тар'яна (1983)
• Алгоритм Габо (1985)
• Алгоритм Голдберга - Тар'яна (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.]

Інше

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

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

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

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

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

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

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

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

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

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

• Алгоритм Ахо — Корасік: алгоритм оснований на дереві префіксів, що знаходить всі збіги в словнику
• Алгоритм бітап - нечіткий алгоритм, що з'ясовує приблизну рівність рядків
• Алгоритм Бояра — Мура
• Алгоритм Бояра — Мура — Горспула
• Алгоритм Кадана - знаходить максимальний підмасив довільного розміру
• Алгоритм Кнута — Моріса — Прата: не проводить повторної перевірки рівних літер
• Алгоритм Коменц — Вальтер: подібно до алгоритму Ахо — Корасік шукає всі збіги в словнику
• Алгоритм Рабіна — Карпа: ефективний пошук за багатьма шаблонами
• Пошук найдовшої спільної підпослідовності: динамічний алгоритм Хаскеля
• Найдовша зростаюча підпослідовність
• Пошук найкоротшої спільної надпослідовності
• Пошук найдовшого спільного рядка

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

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

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

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

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

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

• Сортування вибором
• Пірамідальне сортування
• Плавне сортування
• Декартове дерево
• Tournament sort

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

• Сортування включенням
• Сортування Шелла
• Двійкове дерево пошуку
• Сортування вставкою з проміжками
• Patience sorting
• Splaysort
• Сортування двійковим деревом
• Library sort
• Patience sorting
• Cycle sort

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

• Сортування злиттям
• Ниткоподібне сортування
• Cascade merge sort
• Oscillating merge sort
• Polyphase merge sort

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

• Сортування за розрядами
• Сортування комірками
• Сортування підрахунком
• Цифрове сортування
• Burstsort
• Bead sort

Гібридні

• Timsort
• Block sort
• Introsort
• Spreadsort

Інші

• Топологічне сортування
• Sorting network
• Bitonic sorter
• Flashsort
• Pancake sorting

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

• Atlantic City algorithm
• Лас-Вегас (алгоритм)
• Алгоритм Монте-Карло

Інформатика

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

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

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

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

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

• Асиметричні алгоритми (алгоритми з відкритим ключем):
  • DSA
  • Схема Ель-Гамаля
  • NTRUEncrypt
  • RSA
• Криптографічні хешувальні функції:
  • BLAKE
  • HMAC
  • JH
  • 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)$.

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

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

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

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

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

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

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

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

• Метод Ейлера

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

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

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

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

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

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

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

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

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

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

• Прихована марковська модель
• Баєсова мережа
  • Наївний баєсів класифікатор
• Метод найближчих k-сусідів
• Дисперсійний аналіз
• Випадковий ліс
• Метод опорних векторів
• Мінімальна довжина повідомлення
  • Analogical modeling
• Ледаче навчання
• Навчання на прикладах
• Метод групового урахування аргументів
• Кригінг
• Умовне випадкове поле
• Information Fuzzy Networks
• Ensembles of classifiers
  • Bootstrap aggregating
  • Підсилювання (машинне навчання)
• Ripple-down rules
• Ймовірнісно приблизно коректне навчання
• Logistic model tree
• Learning vector quantization
• Learning automata
• Inductive logic programming
• Gene expression programming
• Case-based reasoning
• Навчання асоціативних правил
  • Алгоритм Apriori
  • Eclat algorithm
• Averaged one-dependence estimators
• Метод зворотного поширення помилки — метод навчання багатошарового перцептрону

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

• ЕМ-алгоритм
• Векторне квантування
• Generative topographic map
• Information bottleneck method

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

• Метод часових різниць
• Q-навчання
• Learning automata
• State-Action-Reward-State-Action

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

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

Інше

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

Інші

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

• Фільтр Блума
• Алгоритм Флажолет — Мартіна)
• Алгоритм Алона — Матіаса — Сцегді (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
• Числа Фібоначчі - швидкий алгоритм обчислення чисел Фібоначчі
• Алгоритм Лю Хуея
• Алгоритм Брента — Саламіна
• Алгоритм Вітербі - алгоритм пошуку найбільш відповідного списку станів (званого шляхом Вітербі)
• Алгоритм Ріша
• Метод Якобі
• Стемінг - скорочення слова до основи шляхом відкидання допоміжних частин
• Алгоритм Луна - використовується для перевірки різних ідентифікаційних номерів
• Алгоритм Шраєра–Сімса
• Алгоритм Гопкрофта — Тар'яна
• Офлайновий алгоритм Тар'яна для пошуку найближчого спільного предка
• Алгоритм Тар'яна для обчислення сильно зв'язних компонентів
• Криптографія на ґратках
• Алгоритм Шора
• Karp-Papadimitriou-Shenker algorithm
• Count-Min sketch
• Sticky sampling
• Lossy counting
• Sample and Hold
• Multi-stage Bloom filters
• Count-sketch
• Sketch-guided sampling
• Метод Куайна - спосіб мінімізації функцій алгебри логіки
• Метод Куайна — Мак-Класкі - табличний метод мінімізації булевих функцій
• Карта Карно - метод спрощення виразів булевої алгебри

Див. також

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

Посилання

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