Список алгоритмів
Нижче наведений не вичерпний список алгоритмів.
Комбінаторні алгоритми
Обхід графа
- Пошук в ширину: обходить граф рівень за рівнем
- Пошук в глибину: обходить граф гілка за гілкою
- Пошук в глибину з ітеративним заглибленням: обходить граф гілка за гілкою щоразу збільшуючи глибину обходу
- Пошук за першим найкращим збігом: обходить граф в порядку важливості елементів, використовується черга з пріоритетами
Сортування
- Топологічне сортування — будується коректна послідовність виконання дій, будь-яка з яких може залежати від іншої
Компонента зв'язності графа
- Алгоритм Косараджу (матриця суміжності , список суміжності ) — алгоритм для знаходження компонент сильної зв'язності орієнтованого графа
- Міст — ребро, видалення якого збільшує кількість компонент зв'язності
- Двозв'язна компонента (Шарнір) — вершина, видалення якого збільшує кількість компонент зв'язності
- Алгоритм Габова — компонент сильної зв'язності по шляхах
- Алгоритм Тар'яна
Побудова кістякового дерева
- Алгоритм Борувки () — знаходить мінімальне кістякове дерево в графі
- Алгоритм Крускала () — знаходить мінімальне кістякове дерево в графі
- Алгоритм Прима (списки суміжності (матриця суміжності)) — знаходить кістякове дерево мінімальної ваги у зв'язному графі
- нім. Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes
Пошук найкоротшого шляху
- Алгоритм Дейкстри () — обчислює найкоротший шлях у графі з невід'ємними вагами ребер
- Алгоритм Флойда — Воршелла () — розв'язує проблему знаходження всіх пар найкоротших шляхів в підвішеному направленому графі
- Алгоритм Джонсона () — обчислює найкоротші шляхи між усіма парами вершин зваженого орієнтованого графа
- Алгоритм Беллмана — Форда () — знаходить найкоротші шляхи у зваженому графі (де деякі ваги ребер можуть бути негативними)
- Алгоритм Левіта — знаходження найкоротших шляхів до всіх вершин
- Алгоритм пошуку A* () — пошук найкоротшого шляху між двома вершинами з додатніми вагами ребер.
- англ. 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)
Кліки
- Алгоритм Брона-Кербоша — пошуку всіх клік (знаходження найбільших максимальних незалежних по включенню множин вершин графа).
Паросполучення
- Алгоритм Гопкрофта — Карпа () — знаходить найбільше парування в дводольному графі
- Угорський алгоритм (Алгоритм Куна) () — знаходження парування мінімальної (або максимальної) ваги між елементами двох скінчених множин за поліноміальний час
- Алгоритм Габо
Інше
- Алгоритм на основі пружин — алгоритм для малювання графа
- Неблокуючий мінімальний охоплюючий перемикач наприклад, для телефонного зв'язку
- Алгоритм Ґірвана - Ньюмана — алгоритм пошуку спільнот в складних системах (соціальних мережах).
Алгоритми пошуку в масиві (списку,...) даних
Елементи впорядковані (відсортовані)
- Двійковий пошук: шукає елемент у впорядкованому списку
- Інтерполяційний алгоритм пошуку: подібний до алгоритму двійкового пошуку
Елементи не впорядковані (не відсортовані)
- Лінійний пошук: шукає елемент у не відсортованому списку
- Алгоритм вибору: знаходить k-ий найбільший елемент
- Хеш-таблиця: шукає елемент у невпорядкованій множині за час O(1)
Із створення нової структури
- Бінарне дерево пошуку: використовує бінарне дерево для збереження елементів
- Алгоритм пошуку SMA*: модифікація алгоритму А* з обмеженим використанням пам'яті
- Алгоритм пошуку D*: вдосконалений варіант А*, враховує нову інформацію про середовище
- Пошук за критерієм вартості: алгоритм пошуку на деревах, що знаходить найдешевший шлях
Пошук на рядках
- Алгоритм Ахо — Корасік: алгоритм оснований на дереві префіксів, що знаходить всі збіги в словнику
- Алгоритм бітап - нечіткий алгоритм, що з'ясовує приблизну рівність рядків
- Алгоритм Бояра — Мура
- Алгоритм Бояра — Мура — Горспула
- Алгоритм Кадана - знаходить максимальний підмасив довільного розміру
- Алгоритм Кнута — Моріса — Прата: не проводить повторної перевірки рівних літер
- Алгоритм Коменц — Вальтер: подібно до алгоритму Ахо — Корасік шукає всі збіги в словнику
- Алгоритм Рабіна — Карпа: ефективний пошук за багатьма шаблонами
- Пошук найдовшої спільної підпослідовності: динамічний алгоритм Хаскеля
- Найдовша зростаюча підпослідовність
- Пошук найкоротшої спільної надпослідовності
- Пошук найдовшого спільного рядка
Приблизний збіг
- Алгоритм Гіршберга - алгоритм знаходження відстані редагувань
- Відстань Левенштейна
- Метафон: алгоритм індексування слів за їх вимовою в англійській мові
- Алгоритм Нідлмана — Вунша
- NYSIIS: фонетичний алгоритм
- Алгоритм Сміта - Вотермана
- Саундекс
Сортування обміном
Сортування вибором
- Сортування вибором
- Пірамідальне сортування
- Плавне сортування
- Декартове дерево
- 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
- Лас-Вегас (алгоритм)
- Метод Монте-Карло
- Monte Carlo 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
- Криптографічні хешувальні функції:
- Криптографічні генератори псевдовипадкових чисел
- Алгоритм Блум Блум Шуба — базується на складності факторизації цілих чисел
- 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
Обчислювальна математика
Абстрактна алгебра
Обчислювальна геометрія
Задачі геометричного пошуку (запиту)
- Належність точки многокутнику — визначити чи точка знаходиться ззовні чи всередині даного многокутника. Трудомісткість — .
- Найближча пара точок
Побудова опуклої оболонки множини точок
- Алгоритм Грехема — трудомісткість .
- Алгоритм загортання подарунка (Джарвіса) — трудомісткість , — кількість точок опуклої оболонки.
- Алгоритм Ендрю — трудомісткість . Вдосконалений алгоритм Грехема.
- Алгоритм Кіркпатрика — Зейделя — трудомісткість , — кількість точок опуклої оболонки.
- Алгоритм Чена — трудомісткість , — кількість точок опуклої оболонки.
- Алгоритм швидкої оболонки — трудомісткість , в середньому — .
- Задача динамічної підтримки опуклої оболонки
Тріангуляція
- Тріангуляція многокутника — розкладання простого многокутника на множину трикутників
- Тріангуляція Делоне множини P, коли жодна точка множини P не знаходиться всередині кола описаного довкола трикутника з тріангуляції
- Псевдотріангуляція — розбиття на псевдотрикутники
- Алгоритм Форчуна — алгоритм побудови діаграми Вороного через замітаючу пряму. Трудомісткість .
Символьні обчислення
Теорія чисел (алгоритми)
- Двійковий алгоритм обчислення найбільшого спільного дільника — ефективний спосіб обчислення НСД.
Чисельні методи
Диференціальні рівняння
Елементарні та спеціальні функції
Інтерполяція та екстраполяція
Монте-Карло
Пошук коренів
Чисельне інтегрування
Розробка програмного забезпечення
Розподілені обчислення
- Алгоритм вибору лідера — позначення одного процесу як організатора завдання, розподіленого між декількома вузлами.
Операційні системи
- Алгоритм банкіра: Алгоритм уникнення взаємних блокувань.
- Алгоритм хулігана: Вибір нового лідера із багатьох комп'ютерів.
- Алгоритми заміни сторінок: Вибір сторінки для заміни в умовах браку пам'яті.
- Адаптивний кеш замін: швидкодія краща за попередній алгоритм.
Машинне навчання та статистична класифікація
Навчання з учителем
- Прихована марковська модель
- Баєсова мережа
- Метод найближчих k-сусідів
- Дисперсійний аналіз
- Випадковий ліс
- Метод опорних векторів
- Мінімальна довжина повідомлення
- Analogical modeling
- Ледаче навчання
- Навчання на прикладах
- Метод групового урахування аргументів
- Кригінг
- Умовне випадкове поле
- Information Fuzzy Networks
- Ensembles of classifiers
- Ripple-down rules
- Probably approximately correct learning
- 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
Навчання з підкріпленням
- Temporal difference learning
- Q-learning
- Learning automata
- State-Action-Reward-State-Action
Інше
- Самоорганізаційна Карта Кохонена - методом проектування багатовимірного простору в простір з нижчою розмірністю. Нейронна мережа з нескерованим навчанням, що виконує завдання кластеризації
- Метод корекції помилки - метод навчання перцептрона
- Метод корекції зі зворотною передачею сигналу помилки - метод навчання перцептрона
Інші
Аналіз потоків даних
- Фільтр Блума
- Алгоритм Флажолет — Мартіна)
- Алгоритм Алона — Матіаса — Сцегді (Alon-Matias-Szegedy Algorithm)
- Алгоритм ДГІМ (Datar-Gionis-Indyk-Motwani Algorithm)
Множення матриць
- Алгоритм перемножування матриць
- Алгоритм Штрассена (1969)
- Алгоритм Пана (1978)
- Алгоритм Біні (1979)
- Алгоритми Шенхаге (1981)
- Алгоритм Копперсміта — Вінограда (1990)
Інші
- Алгоритм Кулі — Тьюкі - алгоритм швидкого перетворення Фур'є
- Алгоритм Лукаса — Канаде - диференційний локальний метод обчислення оптичного потоку
- Алгоритм обчислення дня тижня
- Алгоритм Барнса — Хата - моделювання гравітаційної задачі з 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. (рос.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.