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

Полный список всех основных алгоритмов (300), по всем направлениям. С целью предоставить готовую программу для каждого, или описание алгоритма. Языки программирования включают Java, JavaScript и PHP, C или C++ либо в прямом виде, либо генерируются из источника в Script.

• Автомат
• Биоинформатика и хемоинформатика
• Сокращение
• Сжатие без потерь
• Сжатие с потерей информации
• Криптография
• Генератор случайных чисел
• Программная инженерия
• Выделение памяти
• Распределенные системы
• Операционная система (диск, расписание...)
• Геометрия
• Графы
• Графика
• Искусственный интеллект
• Компьютерное зрение
• Генетические алгоритмы
• Нейронная сеть
• Обучение
• Списки, таблицы и дерева
• Исследование
• Классификация
• Слияние
• Математика
• Алгебра
• Арифметика
• Скрытый логарифм
• Вся факторизация
• Тест первого числа
• Цифровая форма
• Статистика
• Основы
• Оптика
• Оптимизация и оперативный поиск
• Парсинг
• Прогнозирование (статистика)
• Логическое программирование
• Часть
• Науки
• Астрономия
• Медицинский
• (Обработка) Сигнал
• Текст
• Исследование
• Распознавание с приближением
• Обработка слов
• Утилиты
• Разное

Автомат

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

Биоинформатика и хемоинформатика

• Недлеман-Вунш. Выполняет глобальное выравнивание по двум последовательностям, для белков или нуклеотидов.
• Смит-Уотерман. Вариация Недлемана-Вунша.
• Алгоритм Ульманна для решения задачи изоморфизма подграфа (субграф изоморфизма) сольвинга. (1976). Определяет два графика, имеющие изоморфный подграф.
  Проблема крупнейших изоморфических подграфов решается с помощью модульного композиционного графа.

Сокращение

Сжатие без потерь

• Burrows-Wheeler transform. Предварительная обработка для улучшения сжатия.
• Дефлат. Сжатие данных, используется ZIP.
• Дельта кодирует. Помощь по сжатию данных, в которых часто появляются последовательности.
• Инкрементное кодирование. Кодировка Дельта применена к последовательностям строк.
• LZW. (Лемпель-Зив-Уэлч). Преемник LZ78. Создание таблицы перевода из данных для сжатия. Используется графическим форматом GIF.
• LZ77 и 78. Основа грядущих склонений в LZ (LZW, LZSS,...). Все они используют кодировку с помощью словаря.
• ЛЗМА. Инициалы цепи Лемпель-Зив-Марков-Алгоритм.
• ЛЗО. Алгоритм, ориентированный на скорость.
• ПРОМИЛЛЕ. (Предсказание частичным совпадением). Частичное заочное предсказание. Адаптивная и статистическая техника сжатия.
• Шеннон-Фано кодирует. Строит приставки на основе набора символов и их пробальности.
• Truncated binary encoding. Кодировка, обычно используемая для равномерного распределения с окончательным алфавитом. Улучшает двоичное кодирование.
• Рун-length кодирует. Первичный алгоритм, заменяющий единую последовательность на количество экземпляров.
• Секвитур. Использует добавочную грамматику для строки.
• EZW (Embedded Zerotree Wavelet). Постепенное кодирование для сжатия изображения в набор бит с прогрессивной точностью. Может использоваться при сжатии с потерей для более эффектного результата.
• Зопфли. Google, эффективное, но медленное сжатие. Название означает небольшой хлеб на швейцарском немецком языке.
• Бротли. Google, преемник Zopfli, на основе LZ 77, кодирует энтропию и контекстное моделирование.

Энтропийное кодирование

Принцип кодировки, который назначает коды символам таким образом, чтобы длина кодов соответствовала вероятности символов.

• Хаффман кодирует. Использует относительную частоту символов.
• Адаптивный Хафман кодирует. Адаптивная техника кодирования, основанная на алгоритме Хаффмана.
• Арифметическое кодирование. Кодировка разработана.
• Кодировка диапазона. Даже княжеское, как арифметическое кодирование, но с другим методом.
• Нет кодировки. Представляет число n с n другими, за которыми следует ноль.
• Элиас дельта, гамма, омега кодирование. Универсальное кодирование положительных целых чисел.
• Fibonacci coding. Кодировка положительных целых чисел в двоичные слова.
• Голомб кодирует. Оптимальное кодирование алфавитов по геометрическому распределению.
• Райс кодирует. Как Голомб.

Сжатие с потерей информации

• Линейный предсказательный кодинг. Использует спектральную огибающую в сжатой форме цифрового сигнала голоса.
• Законный алгоритм.
• Алгоритм Mu-law. Сжатие аналогового сигнала.
• Фрактальное сжатие. Сжатие изображений с использованием фракталов.
• Преобразование кодировки. Используется для данных типа звука или фотографий.
• Векторное квантование. Метод, используемый при сжатии с потерями.
• Сжатие Вавелета. Тип сжатия подходит для изображения и звука.

Криптография

Шифрование секретным ключом (симметричное )

Использует секретный ключ (или пару непосредственно связанных ключей), как для шифрования, так и для расшифровки.

• Продвинутый стандарт шифрования (AES), известный также как Rijndael.
• Блауфиш. Разработан Шнайром в качестве алгоритма общего использования, для замены стареющего DE.
• Стандарт шифрования данных (DES). Ранее DE Algorithm.
• IDEA (Международный алгоритм шифрования данных). Бывший IPES (Improved PES), также заменяет DES. Используется PGP (Pretty Good Privacy). Преобразует данные, разделенные на блоки, с помощью ключа.
• RC4 (или ARC4). Широко используется шифрование потоков, в том числе протокол SSL для интернет-трафика и WEP для беспроводных сетей.
• Алгоритм шифрования тини. Простой в реализации алгоритм блоков данных, использующий несколько формул.
• PES (предлагаемый стандарт шифрования). Предыдущее название IDEA.

Шифрование с открытым ключом (асимметричное)

Использует пару ключей, так называемый открытый и закрытый ключ. Открытый ключ шифрует сообщение, только закрытый ключ позволяет расшифровать его.

• DSA (алгоритм цифровой подписи). Генерирует ключи с простым и случайным числом. Использовался агентствами США, а теперь и в открытом доступе.
• ЭльГамаль. Основан на Difie-Hellman, используется в ПО GNU Privacy Guard, PGP и других криптографических системах.
• РСА (Ривест, Шамир, Адлеман). Широко используется в электронной коммерции. Использует простые числа.
• Diffie-Hellman (Merkle) key exchange (или экспоненциальный ключ обмена). Метод и алгоритм обмена секретным содержимым по незащищенному каналу связи. Используется RSA.
• NTRUEncrypt. Использует полиномиальные кольца со сверточными умножениями.

Генератор контрольного кода

Создает код из зашифрованного сообщения или файла любого размера.

• MD5. Используется для тестирования ISO-образов CD или DVD.
• RIPEMD (RACE Integrity Primitives Evaluation Message Digest). Основан на принципах MD4 и похож на ША-1.
• SHA-1 (алгоритм безопасного хэша 1). Наиболее используется во всех криптографических хешах функций SHA. Разработан американским агентством АНБ.
• HMAC. Аутентификация сообщений по хэш-ключам.
• Тигр (TTH). Используется в хэше «Тигровое дерево».

Безопасное шифрование с использованием случайных чисел

• Смотри. Генератор случайных чисел

Методы криптографии

Секретный обмен, Секретный сплиттинг, Ки Сплиттинг, М. Н.

• Секретная схема Шамира. Это формула, основанная на полиномиальной интерполяции.
• Секретная схема обмена Блэкли. Это геометрия, секрет - точка в m-мерном пространстве.

Другие методы и расшифровка

• Алгоритм Шора. Предполагаемый квантовый алгоритм, способный расшифровать код на основе асимметричных функций, таких как RSA.
• Субстрет sum. Набор целых, учитывая, есть ли подмножество, сумма которого равна нулю? Используется в криптографии.

Генераторы случайных чисел

• Блум Блум Шуб. Основан на формуле, использующей простые числа.
• Мерсенн твистер. Мацумото Нишимура, быстрый, имеет очень длинную периодичность.
• Lagged Fibonacci generator. Улучшает генератор линейной конгруентности, используя последовательность Фибославчи.
• Линейный конгрегатор. Один из старейших, не самый лучший, генерирует последовательность из трех чисел.
• Алгоритм yarrow. Брюс Шнайер, Джон Келси и Нильс Фергюсон. Криптографически безопасный генератор, может использоваться для генерирования действительно случайных чисел из входов аналоговых устройств.
• Фортуна. Представлен как улучшение алгоритма Ярроу.
• Линейная обратная связь shift register. Регистр смещения, ввод которого является линейной функцией предыдущего содержимого. Первоначальное содержание - «семя» (зерно).

Программная инженерия

• Алгоритмы восстановления и изоляции семантики.
• Вставка Юникода. Обеспечивает стандартный способ размещения имен, слов или строк в определенной последовательности.
• Преобразование CHS. Преобразование между системами дисковых адресов.
• Cyclic redundancy check. Вычисление управляющих слов.
• Контроль паритета. Метод обнаружения элементарных ошибок. Является ли число четным или нечётным?

Выделение памяти

• Сборщик гаражей. Диспетчер памяти.
• Пособие по памяти Бадди. Выделение памяти за счет уменьшения фрагментации.
• Генконсультор. Диспетчер быстрой памяти, основанный на стаже записей.
• Марк и свип.
• Эталонный учет. Простой диспетчер распределения, который подсчитывает количество связей в данных и извлекает пространство, когда оно равно нулю.

Распределенные системы

• Лампорт заказывает. Обработчик событий, основанный на отношениях happened-before (прибыл ранее).
• Снимок. Это резервное копирование общего состояния системы.
• Векторные замочки. Полное расписание событий.
• Марзулло. Распределенная синхронизация по выделенному времени.
• Пересечение. Другой алгоритм, основанный на отведенном времени.

Операционные системы

• Банкир. Алгоритм, позволяющий избежать посадок.
• Повторение страницы. Выбор страниц для жертвоприношения, когда отсутствует память.
• Булли. Выбор приоритетной должности.

Алгоритмы управления диском.

• Элеватор. Планирование работы диска как лифта.
• Короткометражный первый. Планирование диска для сокращения времени доступа.

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

• Петерсон. Позволяет двум процессам совместно использовать один и тот же ресурс без конфликтов, используя общую память для обмена данными.
• Пекарня Лампорта. Повышает надежность управления несколькими процессами в многозадачности с помощью взаимных исключений.
• Деккер. Другой конкурирующий алгоритм программирования, как у Питерсона.

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

• Earliest deadline первый планировщик. Когда происходит событие (конец задачи, новая задача и т. Д.), В списке можно найти процесс, который должен завершиться как можно раньше.
• Fair-share scheduling. Делит процессорное время между группами или пользователями. Для этого рекурсивно называется другой алгоритм управления общим доступом между процессами.
• Least slack time scheduling или Least Laxity First. Влияет на приоритеты в зависимости от различий во времени для процессов. срок, время готовности, время исполнения.
• Список планировщиков. Из списка процессов с приоритетами в первую очередь распределяет имеющиеся ресурсы по наиболее приоритетным направлениям. Возможные стратегии. критический путь, более длинный путь, первый уровень, больше времени обработки.
• Многоуровневая обратная связь.
• Rate-monotonic scheduling. Оптимальный, упреждающий алгоритм со статическим приоритетом. Приоритет отдается по принципу монотонной ставки (первый заканчивается первым договором).
• Round-Robin scheduling. Проще всего - назначает отрезки времени каждому процессу без приоритета.
• Короткая работа next (или первая). Затем выполняет ожидающий процесс, который имеет самое короткое время выполнения, без упреждения .
• Коротышка перекрасила время. Версия проработки самого короткого предстоящего процесса, которая завершает задачу в процессе перед выбором другого.

Геометрия

• Гифт wrapping. Определяет выпуклая оболочка набора точек.
• Гилберт-Джонсон-Кёрти расстояние. Найди самое короткое расстояние между двумя выпуклыми формами.
• Грэм просканировал. Определяет выпуклая оболочка набора точек на плоскости.
• Пересечение отрезка линии. Выясните, какие линии пересекаются с воображаемой линией.
• Точки в многоугольнике.
• Рей/плоское пересечение. Пересечение лучей с плоскостью.
• Пересечение линии/треугольника. Особый случай Рэя/Плоя.
• Многоугольник неявных поверхностей. Приближает поверхность, подразумеваемую многоугольным представлением.
• Триангуляция. Метод оценки расстояния или определения свойств топологического пространства.

Графы

• А * три поиска. Поиск оптимального пути между двумя узлами на графике. Улучшенный best-first, использующий эвристику для ускорения поиска.
• Беллман-Форд. Вычисляет самые короткие пути в графике значения (или дуги могут иметь отрицательный вес).
• Канонизация графов. Заключается в поиске канонической формы графа таким образом, чтобы он был изоморфным другому графу. Используется в хемоинформатике.
• Алгоритм Dijkstra. Вычисляет самые короткие пути в графике без дуги отрицательного значения.
• Нарушение методов. Вычисляет самые короткие пути в графике.
• Флойд-Уоршолл. Реши задачу наименьшего пути в ориентированном и валютированном графе.
• Цикл-поиск Флойда. Итеративный алгоритм, определяющий циклы.
• Алгоритм Хопкрофта-Карпа. Из двухпартового графика возвращает максимум размеров без общих точек. Альтернативами являются альгос breadth-first и depth-first.
• Джонсон. Короткий путь в ориентированном графике.
• Крускаль. Поиск минимального дерева пути для графика.
• Прим. Алгоритм Роберта Прима находит дерево минимального пути графа. Также называется DJP, Ярник или Прим-Ярник.
• Борувка. Как Крускаль.
• Форд-Фулькерсон. Вычисляет максимальный поток, проходящий в графике.
• Эдмондс-Карп. Реализация Ford-Fulkerson.
• Non blocking Minimal Spanning Switch. Телефонный обмен.
• Вудхаус-Шарп. Поиск минимального дерева пути для графика.
• На основе весны. Алгоритм рисования графика.
• Хунгарян. Найди идеальное совпадение.
• Раскраска. Раскраска графа.
• Неарест соседбур. Поиск ближайшего соседа.
• Выходит топологический. Классифицировать ациклический ориентированный граф так, чтобы каждый узел предшествовал узлам, с которыми он связан (в зависимости от значения дуг).
• Tarjan's off-line least common ancestors algorithm. Вычисляет ближайших общих предков к парам узлов в дереве.

Графика

• Бразильская линия. Использует переменные решения для отображения строки между двумя точками.
• Раскрашивание. Процесс раскрашивания черно-белого изображения или видео с несколькими символами для маркировки цветов. Экзамены.
• Деление. Под оригинальным названием «Depixelizing Pixel Art» этот алгоритм сглаживания преобразует изображение в грубые пикселы в реалистичное изображение. (Йоханнес Копф и Дани Лищинский). Демонстрация. Архив демонстраций. Реализация в C++.
• HDR. Есть множество алгоритмов контраста фотографий.
• Алгоритм линии DDA. Для рисования линии между двумя точками используется математика с плавающей запятой.
• Флуд филл. Раскрашивает область, ограниченную замкнутой линией.
• Алгоритм линии Сяолинь Ву. Алгоритм сглаживания линии.
• Алгоритм Painter's. Обнаружение видимых частей 3D-сцены.
• Рэй прослеживает. «Рендеринг», реалистичный рисунок.
• Фонг шадинг. В 3D создает освещение.
• Гурауд шадинг. Имитирует влияние лиумера и цвета на поверхность 3D-объекта.
• Сканлайн рендеринг. Построил образ, переместив воображаемую линию.
• Глобальное просветление. Восстанавливает прямое и отраженное освещение другими объектами.
• Интерполяция. Построил новую точку на увеличенном изображении.
• Ресинтезист. Удаляет объект на фото, восстанавливая фон. Используется Photoshop и The Gimp. Учебник по ресинтезированию.
• Алгоритм слоупа-перехвата. Это реализация формулы slop-intercept для рисования линии.
• Анимация сплайна. Сводит к минимуму ошибки с феноменом Рунге.
• 3D Surface Tracker Technology. Способ добавления изображений на стенах в видео с учетом скрытых поверхностей.

Искусственный интеллект

• Альфа-бета. Alpha max plus бета мин. Основной Algo используется для поиска лучшего удара в столовой игре, в частности (неудача, леди, реверси).
• Анализ синдикатов. Фактически сочетание алгоритмов Байеса, максимальной энтропии и SVM (машина с векторной поддержкой).
• Колонии муравьёв. Набор алгоритмов, основанных на поведении муравьев, которые достигают оптимизации для решения задачи.
• КЛА. Кортикальный алгоритм обучения. Для роботизированного обучения, основанного на трех свойствах, разрозненных распределенных представлениях, временном выводе, онлайн-обучении. Код проекта NuPic в Нументе.
• DE (Дифференцированная эволюция). Реши полиномиальную проблему Чебышева, которая относится к электронным фильтрам.
• Полуконтролируемое получение саркастических приговоров в онлайн-обзоре продукта.
  Алгоритм, признающий сакарство или иронию в твите или онлайн-документе. Такой алгоритм также будет иметь решающее значение для программирования гуманоидных роботов.

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

• Эпитома. Представляет изображение или видео меньшим размером.
• Количество объектов в изображении. Использует алгоритм подключенных компонентов для определения каждого объекта и подсчета объектов.
• Deep Dense Face Detector. Фарафад, Сабериан и Ли. Способен распознавать лица с разных ракурсов.
• Эволюция - конструктивные элементы. Университет Бригама Янга. За возможность идентифицировать известные объекты и добавлять новые объекты в базу знаний без участия человека.
• Алгоритм О'Кэрролла. На основе преобразования в математику зрения насекомых этот алгоритм оценивает, как двигаться, избегая объектов.
• Обнаружение отслеживания обучения. Обнаруживает движущиеся объекты и отслеживает их .
• Виола-Джонс, простой и быстрый фреймворк обнаружения объектов. Он способен распознавать лица и реализован в OpenCV.

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

Они используют три оператора: Выбор (выбор решения), воспроизведение (использование выбранного решения для построения других), замена (замена решения лучшим).

• Фитнес пропорциональный выбор. Также названный рулеткой, выбирай решения.
• Выбор узловой линии. Выбор решений, классифицированных по релевантности.
• Токарная селекция. Выбирай лучшее решение через какой-то турнир.
• Стохастический универсальный самплинг. Индивидуумы ассоциируются с прилегающими элементами линии, чтобы каждый имел соответствующий размер.

Обучение

• PAVA (Pool-Contricent-Violators Algithm). Леу, Хорник, Маир. Улучшает функцию для набора точек. Оптимизация изотонической регрессии. Код C++.
• Вес Множители. Присваивает вес различным стратегиям принятия решения. Это относится к признанию форм и встречается в естественной генетике.

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

• Сеть Хопфилда. Повторяющаяся нейронная сеть, работающая как двоичная адресная память. Он сходится в стабильное состояние.
• Бэкпропаж. Метод обучения помог тренировать искусственные нейронные сети.
• Самоорганизующаяся карта (Kohonen map). Обученные нейронные сети с использованием автономного обучения для получения низкопрофильного представления (2D, 3D) приведенных примеров.

Списки, таблицы и дерева

Исследование

• Дерево перевернуто (Splay tree). Бинарное дерево с функцией разворота для размещения узла в корне и соответствующей реорганизации остальных.
• Словарный поиск. См. предиктивный поиск.
• Выбор алгоритма. Поиск самого большого элемента уровня k в списке.
• Дихотомический поиск (бинарный поиск). Поиск объекта в упорядоченном списке.
• Бредт-первый поиск. Пересекает график уровня за уровнем.
• Depth-first search. Пересекает график с ветвью.
• Лучший поиск. Пересекает граф в порядке вероятной важности с использованием очереди приоритетов.
• Раздельный набор или поиск-союз (союз-поиск). С применением создания лабиринта.
• Единый-дешевый поиск. Поиск по дереву, который позволяет найти наименьшие затраты, если расходы меняются.
• Предсказательный поиск. Своего рода дихотомические исследования.
• Хэш-стол. Связывает ключи с элементами для поиска в списке без классификации с линейной длительностью.
• Интерполированный поиск. Смотрите предсказательные исследования.
• Скип-лист. Структура, состоящая из цепных списков для быстрого доступа, и алгоритм поиска/вставки.
• Медиана. Поиск медианы в списке неординарных чисел. Альго Торбена менее быстр, но не меняет картину.

Классификация

• Выходит бинарное дерево. Ранжирование двоичного дерева, инкрементное, аналогично сортировке по вставке.
• Богосорт. Неэффективный рейтинг стопки карт случайным отбором.
• Сортировка пузыря. Для каждой пары индексов взаимодействуют элементы, которые не в порядке.
• Бакет выходит. Разбивает список на пакеты и сортирует их по отдельности. Обобщает голубоньку.
• Выходит коктейль (или двухнаправленная пузырьковая сортировка). Сортировать сразу в двух направлениях.
• Комб выходит. Эффективная сортировка пузыря, которая устраняет небольшие значения в конце сортировки и использует пробелы между значениями.
• Отсчет выходит. Использует интервалы между числами в списке A для создания списка B. Индексы B используются для определения значений A меньше числа i.
• Гном выходит. Как сортировка по вставке, но перемещение в нужное место происходит с помощью серии инверсий, как в пузырьковой сортировке.
• Heapsort. Преобразует список в стек, удаляет самый большой элемент и добавляет его в конец списка.
• Тим выходит. Анализирует список, который необходимо классифицировать перед выбором оптимальной процедуры. Наверное, быстрее всех и не зависит от размера списка. Используется внутри Java, Python, C++.
• Сортировать по вставке. Определяет место текущего элемента в классифицированном списке и помещает его в него.
• Интрозорт или Интроспектива выходит. Запускается в quicksort и переключается на heapsort при достижении определенного уровня рекурсии.
• Мердж выходит. Классифицирует первую и вторую половины списка по отдельности и объединяет их (рекурсивно).
• Блинчик выходит. Взаимодействует с элементами какого-либо префикса в последовательности.
• Голубка выходит. Заполнение пустой таблицы элементами, которые необходимо классифицировать в другой таблице, по порядку.
• Постман выходит. Изменение сортировки пакетов, многоуровневое, используется почтовыми отделениями для почты.
• Квиксорт. Разделяет список на две части, при этом все элементы первого ниже, чем второй, и классы (рекурсивно).
• Сортировать по основаниям или сортировать радис. (Radix выходит). Классифицирует ключи, связанные с элементами списка или целыми числами из дигитов.
• Выбор выходит. Берет последний оставшийся элемент и добавляет его в конец классифицированного списка.
• Шелл выходит. Улучшенная сортировка по вставке с использованием интервала между значениями.
• Смутсорт. Смотрите хипсорт.
• Стохастик выходит. Смотри, богосорт.

Слияние

• Просто Мёрдж. Объединяет n сортируемых потоков в один. Сравниваются потоки, наименьшие входы каждого отправляются в исходящий поток.
• Tri k-way Merge (или p-way). Сортировка потока данных по повторяющимся слияниям.

Математика

Алгебра

• Алгоритм Бухбергера. Найди базу Грейбнера.
• Eigeneum algorithm.
• Расширенный евклидовый алгоритм. Решите уравнение ax + by =
c.
• Умножение фурье. Для очень больших чисел рассчитайте быстрое преобразование Фурье для двух чисел и умножьте оба результата на элемент.
• Грамм-Шмидт процесс. Ортогонализует набор векторов.
• Гаусс-Джордан выбыл. Реши систему линейных уравнений.
• Карацуба умножение. Эффективный рекурсивный алгоритм для больших чисел. Производное Тоом-Кука.
• Кнут-Бендикс дополняет. Чтобы переписать систему правил.
• Мультивариатный отдел. Полиномы по нескольким неопределенностям.
• Risch algorithm. Переводит неопределённый интеграл в алгебраическую проблему.
• Тоом-Кук (Тоом3). Разбивает каждое число на несколько частей.

Eigenalue algorithm

Алгоритмы поиска «Eigenvalue» (чистые значения) и/или Eigenvector (чистый вектор) матрицы.

• QR алгоритм. Популярный метод, основанный на QR-разложении.
• Обратная итерация. Итеративный алгоритм.
• Рейли коэффициент итерации. Распространяет принцип обратной итерации, используя коэффициент Рейли, чтобы постепенно получить достаточные оценки эйгенейта.
• Арнольди итерация. Вычисляет эйгенетические оценки ортогональной проекции А в подпространстве Крылова.
• Итерация Lanczos. Метод поиска нулевого верцера в процессе квадратичного фильтрации.
• Якоби метод. Цифровая процедура расчета эйгенераторов и эйгенвекторов реальной симметричной матрицы.
• Бисекция.
• Дивид-и-кончай. Используется для реальных симметричных матриц.

Алгоритмы eigenvector

• Алгоритм eigenvector Ричардсона.
• Алгоритм Max-Plus eigenvector. Для нелинейного управления H1.
• Алгоритм Abrams и Lloyd eigenvector.

Арифметика

• Двоичный PGCD. Расчет самого большого общего делителя быстро.
• Умножение Бута. Умножает два целых числа, используя дополнение на 2.
• Евклидовый алгоритм. Вычисляет PGCD.
• Двоичное (или египетское) умножение. Наибольшее кратное разбивается на сумму мощности, равную двум, и создается таблица сил двух из вторых.

Скрытый логарифм в теории групп

• Baby-step giant-step. Это ряд известных шагов для расчета логарифма.
• Ро-алгоритм Полларда для логарифмов. Аналог одноименного алгоритма для целочисленной факторизации, который может применяться и к вычислению отдельного логарифма.
• Алгоритм Похлига-Хеллмана. Решение проблемы для мультипликативной группы, порядок которой является целым числом. Основан на китайской теореме об остатке, и выполняется в полиномиальной длительности .
• Вычисленный индекс алгоритма. Хорошо известный алгоритм для некоторых групп, таких как мультипликативная группа modulo m.

Вся факторизация

Разбить целое число на первичные факторы.

• Метод факторизации Ферма. Представление четного целого числа как разница двух квадратов.
• Пробная дивизия. Самый простой алгоритм. попытка разделить целое число на последовательные простые числа.
• Lenstra elliptic curve factorization или elliptic curve factorization method (ECM). Быстрый, требующий субэкспоненциальной длительности использования эллиптических кривых.
• Поллард ро. Изменение Полларда п-1 эффективно для разбивания чисел на небольшое количество факторов.
• Поллард п-1. Разделенный алгоритм, который подходит только для целых чисел с определенными типами факторов.
• Конгруентность скверов. Найти конгруентность квадратов modulo n - это способ факторизации целого n.
• Квадратик сиве. Используй идею метода Диксона. Это алгоритм, который проще, чем «номерное поле», и самый быстрый для целых чисел меньше 100 цифр.
• Диксон. Метод факторизации общего использования.
• Специальный номер поля. Идеальный специализированный алгоритм для факторизации чисел Ферма.
• Общий номер поля sieve (GNS). Производное от «специального номера поля». Эффективен для больших чисел. Шаг за шагом.

Тест первого числа

Определить, является ли заданное число простым .

• AKS primality test (Агравал-Кайяль-Саксена). Первый опубликованный алгоритм, который является одновременно полиномиальным, детерминистическим и безусловным. Обобщение теоремы Ферма, распространённое на полиномы.
• Fermat primality test. Имеет значение «Истинное равенство» или «Набор равных» для первичных значений, чтобы затем проверить, содержат ли они или называют проверяемое число.
• Miller-Rabin primality test. Похоже на тест Ферма. Неподобающий и вероятностный алгоритм.
О
• Эратосхене. Древний алгоритм для поиска простых чисел до определенного целого числа.
• Сиве из Аткина. Оптимизированная версия критерия Эратостена.
• Соловей-Страссен первичный тест. Тот же принцип, что и тест Ферма.

Цифровая форма

• Fibonacci. Вычисление последовательности Фибославчи.
• Метод дуги-градиента. Разрешение линарных уравнений.
• Танцы Линкс. Найди все решения проблемы точного покрытия.
• От алгоритма Бура. Расчеты кривых.
• От Casteljau's algorithm. Вычисляет кривые Безье.
• Ложное положение метода. Приближение корней функции.
• Гаусс-Лежандр. Вычисление десятичных знаков пи.
• Кахан самомнение. Эффективное добавление чисел с плавающей запятой.
• СТАВКА. Цифровая интеграция, имитация Монте-Карло.
• Ньютон-метод. Поиск нулевых значений функций.
• Скругления. Классическое округление целых чисел.
• Сухой метод. Приближение корней функции.
• Shifting nth-root. Вывод корня по цифрам.
• Корневой сквер. Аппроксимация квадратного корня числа.
• Алгоритм Борвейна. Вычисляет значение 1/e.

Статистика

• Метрополис-Гастингс. Создает последовательность образцов для вероятного распределения переменной или более.

Основы

Матричный расчет или оптимизация.

• Экспонентация по скварингу. Вычисляет мощность матриц.
• Рутисхаузер. Тридиагонизация матриц.
• Страссен алгоритм. Быстрое умножение матриц.
• Символическое разложение Холеского. Эффективное хранение матриц.
• Алгоритм Жа. Улучшает Rutishauser для тридиагонализации ориентированных матриц.
• Строка массива умножения. Оптимизация умножения последовательности матриц наиболее эффективным способом с помощью динамического программирования.

Оптика

• Герхберг Сакстон. Определение фазы по изображению и плоскости дифракции.

Оптимизация и оперативный поиск

См. также Графы.

• Оптимальная организация. Разместить наибольшее количество объектов на ограниченной поверхности.
• Ант колонизация оптимизация. Вероятностная техника решения задач, сводящихся к поиску правильного пути на графике.
• BFGS (метод Бройдена-Флетчера-Гольдфарба-Шанно). Решение проблемы нелинейной оптимизации без ограничений.
• Беллман-Форд. (1955). Вычисляет самый короткий путь между вершиной и всеми остальными вершинами на ориентированном графе. Поддерживает отрицательные значения, в отличие от альго Дейкстры .
• Бранч и баунд. (Разделение и оценка.) Метод поиска оптимального решения задач сдержанной и комбинаторной оптимизации.
• Комбинированный метод градиента. Итеративный алгоритм для цифрового решения систем линейных уравнений, матрица которых симметрична и положительна.
• Стратегическая эволюция. Техника оптимизации, основанная на идее адаптации и эволюции. Операторы такие: подбор, рекомбинация, мутация, отбор окружающей среды.
• Максимальный поток Почти линейный. Алгоритм Келнера, Тата Ли, Ореккии, Сидфорда, чтобы получить максимальный поток, рассматривая все пути одновременно.
• Гаусс-Ньютон. Реши задачу наименьшего нелинейного квадрата.
• Понижение курса. Подход к локальному минимуму функции по шагам, пропорциональным отрицательному градусу (или приближенному) функции в текущей точке.
• Градиент вверх. Подход к локальному максимуму функции, как «градиент», с шагами, прямо пропорциональными градиенту.
• Венгерский (Кун-Мункре). Оптимизирует распределение ресурсов или рабочих станций при меньших затратах.
• Левенберг-Маркардт. Как Гаусс-Ньютон.
• Линейный поиск. Итерационный подход для поиска локального минимума элемента при оптимизации без ограничений.
• Местный поиск. Мета-эвристика для решения сложных задач оптимизации, таких как максимизация критерия среди нескольких решений-кандидатов.
• Проблема стабильных браков. Его используют в экономике, математике, биологии и других науках. Мы хотим связать набор x несовместимых элементов и набор y несовместимых элементов, чтобы каждый x нашел наиболее подходящую для него y и наоборот. Источник JavaScript.
• Метод Нельдера-Мид (downhill simplex). Нелинейная оптимизация.
• Метод Ньютона в оптимизации. Один и тот же алгоритм, который находит корни уравнений в одном или нескольких измерениях, также может использоваться для поиска локальных минимумов и максимумов функций.
• Паксос. Набор распределенных алгоритмов для достижения консенсуса среди нескольких предложений и множества факторов.
• PSO, Particle Swarm Optimization (рой частиц). Интеллект роя, моделируемого частицами в многомерном пространстве, с расположением и скоростью.
• Random-restart hill climbing. Мета-алгоритм, построенный по алгоритму «hill climbing optimization».
• Симплекс. Решение задачи линейного программирования.
• Симулируемый год. Обобщенный и вероятностный мета-алгоритм для задачи глобальной оптимизации, основывается на принципе отжига в металлургии.
• Стипест отстает. См. понижение.
• Стохастический тоннель. Подход к минимизации функции на основе метода выборки Монте-Карло.
• Tabu search. Оптимизация поиска с помощью структур хранения.
• Трастовый поиск. Другой итерационный подход к поиску локального минимума элемента при оптимизации без ограничений.

Парсинг

• Алгоритм CEK. Эффективный алгоритм ^{O (n3}) для любой неконтактной грамматики.
• Алгоритм Эрли. Другой алгоритм O ⁽ⁿ³) для неконтактных грамм.
• Инсайд-аутсайд. Алгоритм O (ⁿ³) переоценивает вероятность постановки в неконтактных вероятностных грамматиках.

Парсеры LL

Парсирует неконтактную грамматику сверху вниз, слева направо. Как и ANTLR, который является LL (*).

Парсеры LR

Парсе неконтактную грамматику снизу вверх, поэтому начиная с последних потомков каждой ветви.

• Dijkstra's shunting yard algorithm. Обычно используется для реализации парсеров, предшествующих оператору, которые преобразуют неверную нотацию в обратную польскую нотацию.
• LALR (Look-Ahead LR). Идут слева направо с чтением одного токена. Якк и Бисон - парсеры LALR (1). Превосходят эсеры.
• SLR (простой LR) парсер. Анализатор LR (0), измененный для предотвращения конфликтов со смещением и уменьшением. Остается ниже LR (1).
• Канонический LR парсер или LR (1). Заранее увидишь токен.
• ГЛР. (Generalized LR parser) Масару Томиты. Расширение LR для управления недетерминированными или двусмысленными грамматиками. Он эффективен для натурального языка.

Рекурсивные парсеры вниз

Парсеры LL построены из набора взаимоисключающих процедур, представляющих правила производства грамматики.

• Пакрат. Линейный алгоритм длительности для неконтактных грамм LL (k). Копирует и запоминает варианты, чтобы избежать их отсутствия.

Прогнозирование (статистика)

• Баум-Уэлч. Находит неизвестные параметры скрытой модели Маркова (HMM) с помощью алгоритма «вперед-назад».
• Витерби. Вычисляет путь Витерби (Viterbi path), последовательность состояний, которая имеет наибольшую вероятность появления в последовательности событий.

Логическое программирование

• Алгоритм Дэвиса-Путнэма. Проверь достоверность утверждения первого порядка.

Часть

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

• Алгоритм Гровера. Обеспечивает квадратичное ускорение при нескольких проблемах поиска.
• Алгоритм Шора. Обеспечивает экспоненциальное ускорение при расчете числа.
• Дойч-Йозса. Критерий баланса для логической функции.

Науки

Астрономия

• Эфемериды.
• Позиции Луны и другие небесные объекты.
• Юлианский день. Число дней, прошедших с понедельника, 1 января, 4713 года до нашей эры в пролептическом юлианском календаре. Алгоритм - это формула. У нас есть варианты. гелиоцентрический, хронологический, модифицированный, сокращенный, усеченный юлианский день, Дублинский, Лилианский.
• Джулианская дата. День юлианский ненароундный, с десятичной дробью.

Медицинский

• Расчеты для лекарств.
• Помощь в диагностике.

(Обработка) Сигнал

• КОРДИК. Быстрая тригонометрическая функция.
• Радужный поток. Сводит историю сложных страй к счету инверсий элементарных страй.
• Осем. Обработка медицинских изображений.
• Герцель алгоритм. Может использоваться для расшифровки DTMF.
• Осторожный Фурье. Определяет частоты в сегменте сигнала.
  • Fast Fourier transform
  • Cooley-Tukey FFT
  • Rader's FFT
  • Bluestein's FFT
  • Bruun's FFT
  • Прайм-фактор FFT
• Ричардсон-Люси деконволюция. Алгоритм выделения изображения.
• Elser Difference-Map. Микроскопическая рентгеновская дифракция.
• Шазам. Распознавание музыкального произведения путем сравнения сигнала и определения его специфики.

Текст

Исследование

• Aho-Corasik.Поиск в тексте путем построения таблицы из слов.
• Битап (или shift-or, shift-and, Baeza-Yates-Gonnet). Нечеткий алгоритм поиска разработан Udi Manber и Sun Wu.
• Бойер-Мур стринг-поиск. Поиск по тексту путем пропущения подстрок, не содержащих букв искомого слова.
• Берроуз Уилер трансформирует. Строковое преобразование, которое можно использовать для более быстрого поиска слов в тексте.
• Кнут-Моррис-Пратт. Создает таблицу во время поиска, чтобы пропустить подстроки.
• Проблема самой длинной общей подсистемы. (Алгоритм Хаскелла). Имеет две последовательности.
• Более длинная подпоследовательность увеличивается. Общий для двух последовательностей. Это сводится к поиску самого длинного пути в графе, ориентированном без циклов.
• Самая короткая общая супер-последовательность. Имеет две последовательности.
• Рабин-Карп стринг поиск. Хеш используется для нескольких поисков.
• Хорспул. Упрощение алгоритма Бойера-Мура. O (мин).

Сравнение с приближением

• Расстояние от Левенштейна (или расстояние редактирования). Минимальное количество операций (вставка, удаление, замена) для преобразования слова в другое слово.
• Саундекс. Фонетический алгоритм индексации слов по их звучанию (на английском языке).
• Метафона.Индексация слов по звуку (на английском языке).
• NYSIS. (Система идентификации и разведки штата Нью-Йорк). Фонетический алгоритм, улучшающий саундекс.

Обработка слов

• Латентное выделение ресурсов (LDA). Анализ документов для связи содержимого с контекстом. Используется поисковиками.
• Латентная семантическая индексация (LSI). Или скрытое семантическое индексирование. Автоматизация методов присоединения текста к контексту из слов, которые обычно появляются в этом контексте.
• Стемминг. Метод уменьшения слов до их стем или корней.

Утилиты

• Судный день. День недели.
• Обмен Xor. Изменяет значения двух переменных без промежуточной переменной.
• Хамминг в весе. Находит количество бит 1 в двоичном слове.
• Луна. Метод проверки идентификационных номеров.
• Создать битную маску. Алгоритм манипуляции битами.

Разное

• BrowseRank. Альтернатива PageRank, основанная на поведении пользователей.
• Форма листьев. Из 28 параметров этот алгоритм восстанавливает форму всех листьев, производимых природой.
• Hypertext Induced Topic Selection (HITS, патент 1997 года). Алгоритм расчета баллов веб-страниц Йоном Клейнбергом. Один балл зависит от входящих, а другой - от исходящих.
• PageRank. (1998) Алгоритм оценки страниц Ларри Пейджа и Сергея Брина (Google) по входящим и исходящим ссылкам. Балл зависит и от многих других критериев, см. Патент Google на оценку страниц.
• Шрайер-Симс. Перестановка групп. Метод расчета BSGS (Base and Strong Generating Set). Используется алгебраическими алгоритмами.
• Робинсон-Шенстед. Комбинаторный алгоритм.

Связи

• Алгоритмы преобразования изображений,

Последнее обновление: 16 марта 2021 года.

Законно: Вы можете свободно печатать эту страницу. Не используйте его на другом сайте, а разместите ссылку на эту страницу .

Algorithms

Определение алгоритма слова - Классификация - История алгоритмов - Список алгоритмов - Сиве эратосенов - Номер Fibonacci