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

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

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

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

Обхід графа

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

Сортування

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

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

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

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

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

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

• Алгоритм Дейкстри (${\displaystyle O(|E|+|V|\log |V|)}$) — обчислює найкоротший шлях у графі з невід'ємними вагами ребер
• Алгоритм Флойда — Воршелла (${\displaystyle O(|V|^{3})}$) — розв'язує проблему знаходження всіх пар найкоротших шляхів в підвішеному направленому графі
• Алгоритм Джонсона (${\displaystyle O(V^{2}\log V+VE)}$) — обчислює найкоротші шляхи між усіма парами вершин зваженого орієнтованого графа
• Алгоритм Беллмана — Форда (${\displaystyle O(|V||E|)}$) — знаходить найкоротші шляхи у зваженому графі (де деякі ваги ребер можуть бути негативними)
• Алгоритм Левіта — знаходження найкоротших шляхів до всіх вершин
• Алгоритм пошуку A* (${\displaystyle 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)

Кліки

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

Цикли

• Простий цикл
• Гамільтонів цикл
• Ейлерів цикл

Парування

• Алгоритм Гопкрофта — Карпа (${\displaystyle O(E{\sqrt {V}})}$) — знаходить найбільше парування в двочастковому графі
• Угорський алгоритм (алгоритм Куна) (${\displaystyle 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]
• ^[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

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

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

• Код Хаффмана
• Алгоритм Лемпеля — Зіва — Велча
• Кодування довжин серій

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

• Дискретне перетворення Фур'є
• Дискретне косинусне перетворення

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

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

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

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

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

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

• Лінійний пошук

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

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

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

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

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

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

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

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

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

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

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

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

• Алгоритм Форчуна — алгоритм побудови діаграми Вороного через замітаючу пряму. Трудомісткість ${\displaystyle 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 тіл відповідно до класичної гравітаційної теорії Ньютона
• Алгоритм Бута - алгоритм добутку, який дозволяє здійснювати операцію добутку пари знакових двійкових чисел у додатковому коді
• Алгоритм Дойча — Йожи - полягає у визначенні, чи є функція двійкової змінної ${\displaystyle 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. (рос.)