wiki-linki.ru - поиск статей википедии и связей между ними

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


Если Вы планируете добавить какой-либо алгоритм в этот список, убедитесь, пожалуйста, что его здесь ещё нет (возможно, алгоритм упоминается под каким-либо альтернативным названием). Внимательно посмотрите, к какой именно категории относится данный алгоритм. В случае, когда из названия не ясно, что именно делает алгоритм, напишите, пожалуйста, краткое описание.
Если Вы планируете написать статью про один из алгоритмов, упомянутых в этом списке, пожалуйста, прочитайте сначала руководство «» или посмотрите несколько уже написанных статей, посвящённых алгоритмам.

Комбинаторные алгоритмы

Общие комбинаторные алгоритмы

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

  • Алгоритм Кристофидеса — эвристический приближенный алгоритм для решения метрической задачи коммивояжера на графе.
  • Метод ближайшего соседа
  • Неблокирующий минимальный охватывающий переключатель например, для телефонной связи
  • Построение транзитивного замыкания графа (установление факта достижимости вершин)

Алгоритмы нахождения максимального потока

  • Алгоритм Форда — Фалкерсона
  • Алгоритм Эдмондса — Карпа, локально-максимального увеличения
  • Алгоритм Диница
  • Алгоритм Карзанова
  • Алгоритм Малхотри — Кумара — Махешвари
  • Алгоритм Галила — Наамада
  • Алгоритм Слейтора — Тарьяна
  • Алгоритм Голдберга — Тарьяна
  • Алгоритм CHM
  • Алгоритм Кинга
  • Алгоритм Голдберга — Рао

Алгоритмы нахождения максимального паросочетания

Алгоритмы поиска

  • Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма

Алгоритмы на строках

Алгоритмы поиска строки

Примерное соответствие

Деревья для строковых последовательностей

Алгоритмы сортировки

  • Наивная сортировка — генерация всех (....) возможных перестановок и проверка на отсортированность
  • Блочная сортировка (также известен как корзинная сортировка), ср. с поразрядной
  • Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
  • Глупая сортировка, найти отличия от Bogosort
  • Сортировка Бентли — Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
  • Сортировка бинарным деревом
  • Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
  • Цифровая сортировка (Сортировка по отделениям)

Алгоритмы слияния

  • Простой алгоритм слияния (англ. Simple Merge algorithm )
  • (....)-мерный алгоритм слияния (англ. k-way Merge algorithm )

Алгоритмы сжатия данных

  • Преобразование Барроуза — Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь
  • Преобразование Шиндлера (англ. ST) — модификация преобразования Барроуза — Уилера
  • Кодирование длин серий (Групповое кодирование, также известен как англ. RLE) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
  •  — сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
  • (EZW-кодирование)
  • Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
    • Алгоритм Шеннона — Фано — самый простой алгоритм кодирования
    • Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
      •  — техника адаптивного кодирования, основывающаяся на коде Хаффмана
    •  — используется для однородного вероятностного распределения с конечным алфавитом
    • Арифметическое кодирование — развитие энтропийного кодирования
  •  — метод сжатия данных, который близок по эффективности к арифметическому кодированию
  • дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа
  • Кодирование Фибоначчи — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
  • Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
  •  — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

  •  — сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
  • А-закон — стандартный алгоритм компандирования. Применяется в РФ.
  • Мю-закон — стандартный алгоритм компандирования
  • Фрактальное сжатие — метод, использующий фракталы для сжатия изображений
  •  — тип сжатия данных для «естественных» данных, таких как аудио-сигналы или фотографические изображения
  •  — техника, часто используемая в сжатии данных с потерями
  • Вейвлетное сжатие — тип компрессии данных хорошо подходящий для сжатия изображений (иногда также используется для сжатия видео и аудио)

Вычислительная геометрия

  •  — определение наименьшего расстояния между двумя выпуклыми фигурами
  •  — трудоёмкость (....).
  • Поиск диаметра множества точек
  • Алгоритм Цируса — Бека — отсечение линий.
  • Алгоритм Сазерленда — Ходжмана — отсечение многоугольника.
  • Построения контура прямоугольников (стороны параллельны осям координат).
  • Нахождение ядра многоугольника
  • Регуляризация многоугольника — декомпозиция многоугольника на монотонные части.

Построение выпуклой оболочки набора точек

  • Построение ВП через треугольники — трудоёмкость (....).
  • Построение ВП перебором рёбер на принадлежность — трудоёмкость (....).
  • Алгоритм сканирования Грэхема — трудоёмкость (....).
  • Алгоритм Экла — Туссена — трудоёмкость (....). Улучшение алгоритма Грэхема.
  • Алгоритм Эндрю — трудоёмкость (....). Улучшение алгоритма Грэхема.
  • Алгоритм быстрой оболочки — трудоёмкость (....), в среднем — (....).
  • Построение методом «разделяй и властвуй» через построение касательных — трудоёмкость (....).
  • Алгоритм заворачивания подарков (Джарвиса) — трудоёмкость (....), (....) — количество точек в выпуклой оболочке.
  •  — трудоёмкость (....), (....) — количество точек в выпуклой оболочке.
  • Алгоритм Чана — трудоёмкость (....), (....) — количество точек в выпуклой оболочке.
  • Инкрементальный алгоритм (fast online hull) — через построение касательных (....), с помощью сбалансированного дерева — (....).
  • Приближённая выпуклая оболочка снизу (lower approximate hull) — методом полос. Трудоёмкость (....), где (....) — количество полос.
  • Приближённая выпуклая оболочка сверху (upper approximate hull) — методом полос. Трудоёмкость (....), где (....) — количество полос.
  • Алгоритм Ли (выпуклые оболочки) — построение выпуклой оболочки простого многоугольника через отрезание карманов. Трудоёмкость (....).

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

  • Триангуляция через поиск диагоналей — ищется диагональ, многоугольник делится на два и далее рекурсивно. Трудоёмкость (....).
  • Триангуляция через отрезание ушей — ищется образующая треугольник диагональ, соседние с треугольником вершины — следующие претенденты на отрезание. Трудоёмкость (....).
  • Триангуляция монотонного простого многоугольника — трудоёмкость (....).
  • Жадная триангуляция — трудоёмкость (....).
  • Оптимальная триангуляция — NP-полная задача. Суммарная длина всех рёбер минимальна среди всех триангуляций данного множества.

Триангуляция Делоне

  • Итеративные алгоритмы построения триангуляции Делоне — трудоёмкость (....).
  • Алгоритмы построения триангуляциии Делоне слиянием — трудоёмкость (....) и (....).
  • Алгоритмы прямого построения триангуляциии Делоне — трудоёмкость (....).
  • Двухпроходные алгоритмы построения триангуляциии Делоне — трудоёмкость (....) и (....).
  • Триангуляциии Делоне с ограничениями — трудоёмкость (....).

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

  • Простой алгоритм построения диаграммы Вороного — трудоёмкость (....).
  • Алгоритм построения диаграммы Вороного через заметающую прямую — трудоёмкость (....).
  • Рекурсивный алгоритм построения диаграммы Вороного — трудоёмкость (....).

  • Локализация точки для выпуклого многоугольника — время запроса (....).
  • Локализация точки в звездном многоугольнике — время запроса (....).
  • Метод луча — принадлежность точки простому многоугольнику (....).
  • Метод углов — принадлежность точки выпуклому многоугольнику. Трудоёмкость (....).
  • Метод полос — простой многоугольник. Время запроса (....), память (....).
  • Метод детализации триангуляции Киркпатрика — простой многоугольник. Время запроса (....), память (....).
  • Трапецоидальная карта — простой многоугольник. Рандомизированный алгоритм, время запроса (....), память (....).
  • Метод цепей — простой многоугольник. Время запроса (....), память (....).

Пересечения

  • Пересечение отрезков (алгоритм Бентли — Оттманна) — поиск всех точек пересечения отрезков на плоскости (....), (....) — количество точек пересечения.
  • Алгоритм Чазелла — Эдельсбруннера — пересечение отрезков за (....).
  •  (алгоритм Шеймоса — Гоя) — трудоёмкость (....).
  • Алгоритм Сазерленда — Коэна — для выпуклых многоугольников. Трудоёмкость (....).
  • Пересечения выпуклых многоугольников — трудоёмкость (....).
  • Алгоритм Шеймоса — Хоуи — для выпуклых многоугольников методом полос. Трудоёмкость (....).
  • Пересечения выпуклых многоугольников с заметающей прямой — трудоёмкость (....).
  • Пересечение звёздных многоугольников — трудоёмкость (....).
  • Пересечение полуплоскостей — трудоёмкость (....).

  • Поиск диаметра множества точек через вращающиеся калиперы
  • Определение ширины многоугольника
  • Построение суммы Минковского двух выпуклых многоугольников
  • Поиск максимального расстояния между двумя множествами точек
  • Поиск минимального расстояния между двумя выпуклыми многоугольниками
  • Построение мостов для двух выпуклых многоугольников
  • Построение критических опорных прямых для выпуклых многоугольников

Компьютерная графика

  • Алгоритм Брезенхэма — растеризует отрезок линии с заданными координатами начала и конца
  •  — алгоритм для аппроксимации отрезка на дискретной графической поверхности
  • Алгоритм DDA-линии — чертит точки двухмерного массива в форме прямой линии между двумя заданными точками (использует вычисления с плавающей точкой)
  •  — заполняет соединённый регион многомерного массива указанным значением
  • Алгоритм Ву — алгоритм для сглаживания прямой
  •  — определяет видимые части трёхмерной сцены
  •  — рендеринг реалистичных изображений
  • Затенение по Фонгу — модель освещения и метод интерполяции в трёхмерной компьютерной графике
  • Затенение по Гуро — алгоритм моделирования различных эффектов света и цвета на поверхности объекта в трёхмерной компьютерной графике
  • (англ. Scanline rendering) — конструирует образ с помощью перемещения воображаемой линии над образом
  •  — рассматривает прямое освещение и отражение от других объектов
  • Алгоритмы интерполяции — конструирование новых точек данных, таких как в цифровом увеличителе
    •  — уменьшение ошибки с помощью

Компьютерное зрение

  •  — представление образа или видео при помощи меньшего образа или видео

Криптографические алгоритмы

См. также Разделы в криптографии для аналитического глоссария
  • AES (англ. Advanced Encryption Standard) — победитель соревнования NIST, также известен как Rijndael
  • Blowfish
  • DES (англ. Data Encryption Standard) — иногда, алгоритм DEA (англ. Data Encryption Algorithm), победитель соревнования NBS, заменён на AES для большинства применений
  • RC2
  • IDEA (англ. International Data Encryption Algorithm)
  • RC4
  • Алгоритмы разделения секрета
    • Рюкзак — на данный момент доказана нестойкость схемы
    • Схема Шамира
    • Схема Blakey
  • Алгоритмы подбрасывания монеты по телефону
  • MD5 Резюме сообщения 5 (Message Digest 5) Разработан Рональдом Ривестом (RFC 1321) — существует метод генерации коллизий
  • RIPEMD-160
  • SHA-1
  • HMAC — аутентификация сообщение с помощью хеш-ключа
  • Тигр — обычно используется в Тигровых деревьях хэшей

Цифровая обработка сигналов

  •  — Уменьшает комплексную историю давлений в расчёте элементарных противодействий для использования в анализе усталости
  • Osem — алгоритм для обработки медицинских изображений
  •  — Может быть использован для декодирования цифр тональных сигналов
  •  — алгоритм увеличения резкости образа

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

  •  — Преобразование между системами адресации диска
  • Чётность — Проверка четности количества единиц в двоичной записи числа. Позволяет обнаруживать ошибку в одном разряде.
  • Алгоритм соединения (СУБД) — реализация операции соединения реляционной алгебры.

Алгоритмы распределённых систем

  •  — Частичное упорядочение событий в зависимости от того, что случилось раньше
  •  — снимок процесса записывающий глобальное состояние системы
  •  — Полное упорядочение событий
  •  — распределённая синхронизация часов
  •  — другой алгоритм синхронизации часов

Алгоритмы выделения и освобождения памяти

  •  — «скромный» сборщик мусора
  •  — алгоритм выделения памяти таким образом, чтобы фрагментация была наименьшей.
  •  — Быстрые сборщики мусора, которые разделяют память по возрасту
  • Подсчёт ссылок

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

  •  — Алгоритм, использующийся для избежания взаимных блокировок
  •  — выбор страницы-жертвы при условиях небольшого объёма памяти
  • : скорость выполнения лучше, чем у LRU
  • (CAR): алгоритм замены страниц со скоростью выполнения, сравнимой с адаптивным алгоритмом замещения кэша
  •  — выбор нового лидера среди множества компьютеров
  • rsync — алгоритм, использующийся для эффективной передачи файлов между двумя компьютерами

Дисковые алгоритмы-планировщики

  •  — дисковый алгоритм планирования, который работает как лифт
  •  — дисковый алгоритм планирования для уменьшения времени поиска

Сетевые алгоритмы

  • : получение точных оценок времени распространения пакетов сообщений при использовании TCP/IP
  • : техника эффективного сохранения и поиска в таблицах роутинга
    • : улучшение эффективности TCP/IP за счёт объединения пакетов
  • Шейпинг

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

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

Генетические алгоритмы

  •  — также известен как выбор рулеточного колеса

Медицинские алгоритмы

Нейронные сети

Вычислительная алгебра

  • Преобразования Хаусхолдера (QR-разложение) — вычисление обратной матрицы, собственный векторов и собственных значений матрицы; используется также для решения систем линейных уравнений.
  • Решение систем линейных уравнений
    • Метод Гаусса (Гауссово исключение) — стандартный метод решения систем линейных уравнений
  • Структурированное гауссово исключение — применяется, когда матрица системы является разреженной
  • Метод Жордана — Гаусса — модификация метода Гаусса для матричного представления
  • Преобразования Холеского — метод, эффективный для ленточных и разреженных матриц
  • Метод Пранис — Праневича — решение систем линейных уравнений с параллельными вычислениями по компонентам

Теоретико-числовые алгоритмы

  • Целочисленная арифметика (алгоритмы для работы с большими числами)
    • Умножение столбиком больших чисел
    • «Быстрый столбик»
    • Умножение Карацубы — алгоритм быстрого умножения чисел
    • Деление на одноразрядное число (DO)
    • Деление больших чисел
  • Быстрое возведение в степень — вычисляет степени чисел при помощи возведения в квадрат
  • Алгоритмы модулярной арифметики
    • Алгоритм Монтгомери — модулярное умножение и возведение в степень
    • Алгоритм нахождения порядка элемента
    • Алгоритм Тонелли — Шенкса — решение квадратичных сравнений
    • Решение систем линейных сравнений
  • Решение систем линейных уравнений над полем
    • Алгоритм Ланцоша — эффективен над полем характеристики 2
    • Алгоритм Видемана
  • Дискретное логарифмирование:
  • Алгоритм COS (алгоритм Копперсмита — Одлыжко — Шреппеля) — достаточно эффективный субэкспоненциальный алгоритм
  • Решето числового поля — наиболее эффективный на данный момент алгоритм дискретного логарифмирования
  • В произвольном конечном поле
  • (алгоритм index-calculus) — сведение дискретного логарифмирования в произвольном конечном поле к аналогичной задаче в простом поле
  • Алгоритм Копперсмита — эффективный алгоритм дискретного логарифмирования в конечном поле характеристики 2
  • Алгоритмы нахождения наибольшего общего делителя (НОД) двух чисел
  • Расширенный бинарный алгоритм — модификация бинарного алгоритма нахождения НОД, аналогичная расширенному алгоритму Евклида
  • Тест Миллера — модификация теста на основе малой теоремы Ферма; опирается на расширенную гипотезу Римана
  • (N-1)–метод проверки простоты — тест на простоту при известном разложении на множители числа (....); также используется для построения больших простых чисел
  • (N+1)–метод проверки простоты — тест на простоту при известном разложении на множители числа (....)
  • Алгоритм Конягина — Померанса — модификация (....)-метода
  • Вероятностные тесты простоты
  • Факторизация — разложение числа на множители
  • Алгоритм Шуфа — вычисление порядка группы точек эллиптической кривой
  • (LLL-алгоритм, L³-алгоритм)

Численные алгоритмы

Смотри также Список разделов численного анализа
  •  — нахождение всех решений задачи точного покрытия
  •  — вычисление сплайнов
  •  — вычисление цифр числа пи
  •  — более аккуратный метод суммирования чисел с плавающей точкой
  • школьный (ручной) алгоритм — аппроксимирует квадратный корень числа

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

Грамматический разбор

  •  — алгоритм для разбора любой контекстно-свободной грамматики, он предназначен для определённых грамматик, на которых он действует практически за линейное время и (....) в худшем случае.

Квантовые алгоритмы

Приложения квантовых вычислений к различным категориям проблем и алгоритмы

Теория вычислений и автоматов

  •  — алгоритм для преобразования недетерминированного автомата в детерминированный
  • Алгоритм Тодда — Коксетера — процедура для создания сомножеств

Другие

Примечания

Литература

Ссылки

  • [http://www.compression.ru/ Сайт по методам сжатия данных]
  • [http://rain.ifmo.ru/cat/view.php/ Дискретная математика: Алгоритмы] — библиотека алгоритмов и визуализаторов
  • [http://algolist.manual.ru/ Алгоритмы, методы, исходники]


Вопрос по теме Сформулируйте свой вопрос в одном предложении. Для вопросов и ответов используется сервис Отвечай.ru

Проект wiki-linki.ru основан на данных Wikipedia, доступной в соответствии с GNU Free Documentation License.