Проект "Ангор"
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: angor, Gexon  
Ангорум » Проект "Ангор" - общий раздел » Материалы для самообразования » Самые используемые алгоритмы (Перевод)
Самые используемые алгоритмы (Перевод)
GexonДата: Среда, 29.09.2010, 23:13 | Сообщение # 1
Оракул
Группа: Старший енот
Сообщений: 543
Статус: Offline
Самые используемые алгоритмы (Перевод)
Критерий выбора — распространенность алгоритма.

1. Алгоритм поиска А*
Поисковый алгоритм по графам, который находит путь от заданного начального узла к заданному целевому узлу. Он использует эвристические оценки, которые вычисляются для каждого узла. Оценка представляет собой вес наилучшего маршрута проходящего через этот узел. Он посещает узлы в порядке установленом оценками. Алгоритма А* также называют поиском «Наилучший из первых» (best-first search).

2. (Beam Search) Лучевой Поиск
Лучевой поиск это оптимизированный поиск «Наилучший из первых» (best-first search). Как и оригинал он использует эвристические функции оценки каждого узла. Однако, оцениваются только первые м наиболее перспективных узлов на каждом проходе, где м фиксированное число — ширина пучка.

3. (Binary search) Бинарный поиск
Техника для поиска конкретного значения в линейных массивах, исключая половину оставшихся данных на каждом шаге.

4. (Branch and bound) Ветвей и границ
Общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно в дискретной и комбинаторной оптимизации.

5. (Buchberger's algorithm) Алгоритм Бухбергера
В вычислительной алгебраической геометрии и вычислительной коммутативной алгебре, алгоритм Бухбергера это способ преобразования данного набора образующих полиномиального идеала в базис Грёбнера по отношению к некоторому мономиальному порядку.Можно рассматривать это как обобщение алгоритма Евклида для вычисления одномерных НОД (univariate gcd computation) и метода Гаусса для линейных систем.

6. (Data compression) Сжатие данных
Сжатие данных или кодирование источника это процесс представления информации, используя меньшее количество бит (или других несущих информацию единиц), чем используется для представления оригинала.

7. (Diffie-Hellman key exchange) Обмен ключами Диффи-Хеллмана
Криптографический протокол, который позволяет двум сторонам, которые ранее не имели информации друг о друге, совместно создать общий секретный ключ используя незащищенный канал связи. Этот ключ может быть использован для шифрования последующих сообщений с помощью симметричного ключа.

8. (Dijkstra's algorithm) Алгоритм Дейкстры
Алгоритм решения задачи поиска кратчайшего пути для графа с неотрицательными весами ребер.

9. (Discrete differentiation) Дискретные дифференциации
То есть, формула f'(x) = (f(x+h) — f(x-h)) / 2h.

10. (Dynamic programming) Динамическое программирование
Динамическое программирование представляет собой метод для сокращения времени выполнения алгоритмов, используя свойства перекрывающихся подзадач и оптимальной подструктуры.

11. (Euclidean algorithm) Алгоритм Евклида
Алгоритм определения наибольшего общего делителя (НОД) двух целых чисел. Это один из старейших известных алгоритмов, поскольку он появился в работе «Элементы» Евклида около 300 г. до н.е. Алгоритм не требует факторинга двух целых чисел.

12. (Expectation-maximization algorithm (EM-Training)) Алгоритм Максимизация-ожидания (МО-тренинг)
В статистических вычислениях, алгоритм максимизации ожидания (МО) используется для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в которых модели зависят от скрытых латентных переменных. МО попеременно выполняет шаг вычисления ожидания, который вычисляет ожидаемую величину скрытых переменных, и шаг максимизации, который вычисляет оценку максимального правдоподобия параметров с учетом данных и присвоения скрытым переменным их ожидания.

13. (Fast Fourier transform (FFT)) Алгоритм Быстрого преобразования Фурье (БПФ)
Эффективный алгоритм вычисления дискретного преобразования Фурье (ДПФ) и его обратного преобразования. БПФ имеют большое значение для широкого круга задач, начиная от цифровой обработки сигналов и решения частных случаев диф. уравнений до алгоритмов быстрого умножения больших чисел.

14. (Gradient descent) Градиентный спуск
Градиентный спуск является алгоритмом оптимизации, который приближается к локальному минимуму функции путем применения величины шага, пропорционально отрицательному значению градиента (или приближенного градиента) функции в текущей точке. Если вместо отрицательного значения градиента брать положительное значение, то будет выполнятся поиск локального максимума этой функции; процедура известная как градиент подъема.

15. (Hashing) Хеширование
Функции для подведения итогов или вероятностного идентифицирования данных. Обычно это означает, что к данным применяется математическая формула производящая строку, которая, с определенной степенью вероятности уникальна для этих данных. Строка намного короче, чем исходные данные, но может быть использована для однозначно идентифицирования их.

16. (Heaps (heap sort)) Кучи (сортировка кучи)
В информатике куча — специализированная структура данных основаная на структуре дерева. Кучи являются основными структурами данных многих приложений: алгоритмы Сортировки кучи — это алгоритмы нахождения мин, макс или обоих, средний или даже любого к-го элемента за нелинейное время используя граф-алгоритмы.

17. (Karatsuba multiplication) Умножения Карацуба
Для систем, в которых необходимо умножать числа в диапазоне от нескольких тысяч цифр, например, системы компьютерной алгебры и библиотеки больших чисел, долгое умножение происходит слишком медленно. В этих системах используются умножение методом Карацубы, который был открыт в 1962 году.

18. (LLL algorithm) LLL алгоритм
Алгоритм Ленстра-Ленстра-Ловасза сокращения сетки (Lenstra-Lenstra-Lovasz lattice reduction (LLL) algorithm), который предоставляет входную базисную сетку в виде базиса с сокращенными приближенно-ортогональными векторами. Алгоритм LLL нашлел широкое применение в криптоанализе схемы шифрования с открытым ключом: кнепсак криптосистем (knapsack cryptosystems), RSA с особыми настройками, и так далее.

19. (Maximum flow) Максимальный поток
Задача о максимальном потоке — задача о нахождении корректного максимального потока через транспортную сеть. Иногда она определяется как нахождение значения такого потока. Задачу о максимальном потоке можно рассматривать как частный случай более сложных проблем потоков в транспортной сети. Максимальный поток связан с разрезами сети по теореме минимального среза максимального потока. Алгоритм Форда-Фалкерсона вычисляет максимальный поток в сети.

20. (Merge sort) Сортировка слиянием
Алгоритм сортировки для перестройки списков (или любой другой структуры данных, с последовательным доступом, например, файловые потоки) в определенном порядке.

21. (Newton's method) Метод Ньютона
Эффективный алгоритм для нахождения приближений к нулю (или корней) вещественных функций. Метод Ньютона также известен как алгоритм нахождения корней уравнений в одном или более измерениях. Он также может быть использован для поиска локальных максимумов и минимумов функций.

22. (Q-learning) Алгоритм Q-обучения
Алгоритм Q-обучения является техникой обучения с закреплением, которая работает на основе запоминания действия-значения функции, что дает ожидаемую полезность принятия данного действия в данном состоянии и следованя фиксированной политике в дальнейшем. Достоинством Q-обучения является то, что этот метод в состоянии оценить ожидаемую полезность доступных действий, не требуя модели окружающей среды.

23. (Quadratic sieve) Квадратичные сито
Алгоритм квадратичного сита (КС) представляет собой современный алгоритм факторизации целых чисел, а на практике, второй по скорости метод (после метода сита числового поля, (number field sieve, NFS)). Этот метод является самым быстрым для целых десятичных чисел имеющих до 110 десятичных цифр, и значительно проще, чем алгоритм сита числового поля.

24. RANSAC
RANSAC — (аббр. RANdom SAmple Consensus) стабильный метод оценки параметров модели на основе случайных выборок. Это алгоритм для расчета параметров математической модели из набора наблюдаемых данных, которая содержит «выбросы"(«outliers»). Основное предположение состоит в том, что данные в основном соответствуют модели («inliers»), т.е. точки которые можно объяснить некоторым набором параметров модели, днако могут содержать «выбросы"(«outliers») — точки данных, которые не подходят модели.

25. RSA
Алгоритм шифрования с открытым ключом. Это первый известный алгоритм который может использоваться как для цифровой подписи так и для шифрования. RSA попрежнему широко используется в протоколах электронной коммерции, и считается безопасным при достаточно длинных ключах.

26. (Schоnhage-Strassen algorithm) Алгоритм умножения Шенхаге-Штрассена
В математике, алгоритм умножения Шенхаге-Штрассена асимптотически быстрый метод умножения больших целых чисел. Затраченое время расчитывается по формуле O(N log(N) log(log(N))). Алгоритм использует быстрое преобразование Фурье в кольцах.

27. (Simplex algorithm) Симплекс-метод
В математической теории оптимизации, симплексный алгоритм популярный метод для численного решения задачи линейного программирования. Задача линейного программирования ставится в виде набора линейных неравенств с учетом количества действительных переменных и фиксированных линейный функций, который необходимо максимизировать (или свести к минимуму).

28. (Singular value decomposition (SVD)) Алгоритм Сингулярного разложения (АСР)
В линейной алгебре, АСР является важным разложением прямоугольной вещественной или комплексной матрицы, часто применяется в обработке сигналов и статистике, например, расчет Псевдообращения матрицы (для решения проблемы наименьших квадратов), решение переопределенной СЛАР(система линейных алгебраических уравнений), матричное приближение, численное прогнозирование погоды.

29. (Solving a system of linear equations) Решение системы линейных уравнений
Системы линейных уравнений принадлежат к старейшим проблемам в области математики и у них есть много применений, таких как цифровая обработка сигналов, оценивание, прогнозирование и, как правило линейного программирования, а также в приближениях нелинейных задач численного анализа. Эффективный способ решения систем линейных уравнений является метод Жордана-Гаусса или разложения Холецкого.

30. Strukturtensor
В распознавании образов: Вычисляет значение для каждого пикселя которое указывает, принадлежит ли этот пиксель однородной области, краю или это вершина.

31. (Union-find) Поиск объединения
Заданное множество элементов, часто бывает необходимо разделить на несколько отдельных, непересекающихся групп. Набор непересекающихся данных (disjoint-set data structure) это структура данных, которая отслеживает такие разделения. Алгоритм «Поиск объединения» выполняет две полезные операции по такой структуре данных:
Поиск: Определяет, к каким группам относится (входит) данный элемент;
Объединение: Объединение или слияние двух групп в одну группу.

32. (Viterbi algorithm) Алгоритм Витерби
Алгоритм Динамического программирования для поиска вероятной последовательности скрытых состояний — известный как путь Витерби -, в результате которых выявляется последовательность наблюдаемых событий, особенно в контексте скрытых моделей Маркова.

 
GexonДата: Среда, 29.09.2010, 23:16 | Сообщение # 2
Оракул
Группа: Старший енот
Сообщений: 543
Статус: Offline
http://habrahabr.ru/blogs/algorithm/102889/ - оригинал тут
 
Ангорум » Проект "Ангор" - общий раздел » Материалы для самообразования » Самые используемые алгоритмы (Перевод)
  • Страница 1 из 1
  • 1
Поиск:


Copyright ООО "Дотакиллер" © 2018