Программируемые алгоритмы


Программируемые алгоритмы

Нижеследующее — это список алгоритмов. Также смотрите список структур данных, список основных разделов теории алгоритмов и список терминов, относящихся к алгоритмам и структурам данных.

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы сжатия без потерь

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

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

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

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

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

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

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

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

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

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

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

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

    Локализация точки (англ.)

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

    Пересечения

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

    Вращающиеся калиперы (англ.)

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

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

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

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

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

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

    См. также Разделы в криптографии для аналитического глоссария

    Wikimedia Foundation. 2010.

    Смотреть что такое "Программируемые алгоритмы" в других словарях:

    • вершинный шейдер — Вершинные шейдеры это программы, выполняемые видеочипами, которые производят математические операции с вершинами (vertex, из них состоят 3D объекты в играх), иначе говоря, они предоставляют возможность выполнять программируемые алгоритмы по… …   Справочник технического переводчика

    • программируемый логический контроллер — ПЛК [Интент] контроллер Управляющее устройство, осуществляющее автоматическое управление посредством программной реализации алгоритмов управления. [Сборник рекомендуемых терминов. Выпуск 107. Теория управления. Академия наук СССР. Комитет научно… …   Справочник технического переводчика

    • Программируемая пользователем вентильная матрица — ППВМ типа Stratix IV GX фирмы Altera Программируемая пользователем вентильная матрица (ППВМ, FPGA) полупроводниковое устройство, которое может быть сконфигурировано производителем или разработчиком после изготовления; отсю …   Википедия

    • OptiX — Графический движок Официальный логотип OptiX Разработчик nVidia Дата анонса 6 августа 2009 года Дата выпуска 5 ноября 2009 года …   Википедия

    • История криптографии — Основная статья: Криптография История криптографии насчитывает около 4 тысяч лет. В качестве основного критерия периодизации криптографии возможно использовать технологические характеристики используемых методов шифрования. Первый период… …   Википедия

    • Цифровой сигнальный процессор — (англ. Digital signal processor, DSP; сигнальный микропроцессор, СМП; процессор цифровых сигналов, ПЦС)  специализированный микропроцессор, предназначенный для цифровой обработки сигналов (обычно в реальном масштабе времени) …   Википедия

    • ГОСТ 19619-74: Оборудование радиотелеметрическое. Термины и определения — Терминология ГОСТ 19619 74: Оборудование радиотелеметрическое. Термины и определения оригинал документа: 34. Адаптация телеметрической системы к объекту Адаптация к объекту Е. Telemetry system adaptation to object Процесс автоматического… …   Словарь-справочник терминов нормативно-технической документации

    • CORDIC — (Метод CORDIC от англ. COordinate Rotation DIgital Computer  цифровой вычислитель поворота системы координат; метод «цифра за цифрой», алгоритм Волдера)  итерационный метод сведения прямых вычислений сложных функций к выполнению… …   Википедия

    • ПЦС — Цифровой сигнальный процессор (англ. Digital signal processor, DSP; сигнальный микропроцессор, СМП; процессор цифровых сигналов, ПЦС) специализированный микропроцессор, предназначенный для цифровой обработки сигналов (обычно в реальном масштабе… …   Википедия

    • КОГЕН — (Cohen) Герман (1842 1918) немецкий философ, основатель и виднейший представитель марбургской школы неокантианства. Основные работы: ‘Теория опыта Канта’ (1885), ‘Обоснование Кантом этики’ (1877), ‘Обоснование Кантом эстетики’ (1889), ‘Логика… …   История Философии: Энциклопедия

    Книги



    Поделиться ссылкой на выделенное

    Прямая ссылка:
    Нажмите правой клавишей мыши и выберите «Копировать ссылку»

    We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.