Сообщения

Алгоритмы: Расстояние Левенштайна

-
Изображение
Расстояние Левенштейна — метрика, позволяющая определить «схожесть» двух строк — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. Применение Расстояние Левенштейна и его обобщения активно применяется: для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированного текста или речи). для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы. в биоинформатике для сравнения генов, хромосом и белков. С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками: При перестановке местами слов или частей слов получаются сравнительно большие расстояния; Расстояния между совершенно разными короткими словами оказываются небольшими, в то время как ...
Далее...

Алгоритмы: Метод Монте-Карло

-
Изображение
Методы Монте-Карло (ММК) — группа численных методов для изучения случайных процессов. Суть метода заключается в следующем: процесс моделируется при помощи генератора случайных величин. Это повторяется много раз, а потом на основе полученных случайных данных вычисляются вероятностные характеристики решаемой задачи. Например, чтобы узнать, какое в среднем будет расстояние между двумя случайными точками в круге, методом Монте-Карло, нужно взять много случайных пар точек, для каждой пары найти расстояние, а потом усреднить. Используется для решения задач в различных областях физики, химии, математики, экономики, оптимизации, теории управления и др. Метод имеет две основных особенности. Первая — простая структура вычислительного алгоритма. Вторая — ошибка вычислений, как правило, пропорциональна  ,  где   — некоторая постоянная, а   — число испытаний.  Ясно, что добиться высокой точности на таком пути невозможно. Поэтому обычно г...
Далее...