Архив рубрики: Алгоритмы

Калибровка компаса — Хардкор

Этот пост немного выбивается из общей тематики блога и будет интересен скорее интересующимся DIY и роботостроением, чем программистам, однако нам пригодится все: и навык программирования в области анализа данных, и математическая смекалка, и 3D-воображение 🙂   Небольшое интро Очень часто … Читать далее

Рубрика: DIY, Алгоритмы, Программирование | Метки: , , , , , , , | 23 комментария

Рандом с учетом весов за O(1) — Walker’s alias method

Есть массив A[n] с весами. Нужно выбрать случайный элемент, но не равномерным рандомом, а в соответствии с этими весами. (В общем, это дискретное распределение вероятности) Чем примечателен метод алиаса, так это константным временем выполнения O(1)

Рубрика: Алгоритмы, Программирование, Разное | Метки: , , , | 2 комментария

Поворот в пространстве и кватернионы

Ориентация в пространстве Термин «ориентация» подразумевает наличие какой либо начальной системы координат, относительно которой ориентация будет являться простым поворотом. Например, она могла бы быть привязана к Земле, если мы определяем положение относительно нее, или, другой пример, к туловищу модели, ориентацией … Читать далее

Рубрика: Алгоритмы, Программирование | Метки: , | 16 комментариев

Метод наименьших квадратов и распределение Гаусса

Применение МНК для подбора параметров гауссиан выборки Функция нормального распределения (Гаусса) называется гауссианой и представляет из себя ни что иное как «кривую колокола», верхушка которого будет располагаться в точке математического ожидания (медианы), а отклонение (разброс) определяет его ширину. Ее же мы увидим, … Читать далее

Рубрика: Алгоритмы | Метки: , , , , | 2 комментария

Фильтрация шумовых выбросов

Проблема Предположим, мы производим «измерение» некой двумерной величины много раз. Но наш «прибор» с некоторой вероятностью дает сбой, поэтому мы получаем примерно такой результат: Невооруженным глазом заметен кластер «правильных» измерений. Но как его выделить программно? Актуально, когда вариант «ручного» просмотра … Читать далее

Рубрика: Алгоритмы | Метки: , , , , , , , | Добавить комментарий

Наивное деление слова по слогам

Мое внимание привлекла задача по разделению слова на слоги: дело в том, что это интуитивно просто, но сформулировать правило словами, думаю, никто не сможет. Да и из того, что кто-нибудь сформулирует, всегда легко найти дюжину исключений. Создание базы данных «валидных … Читать далее

Рубрика: Алгоритмы | Метки: , , | 5 комментариев

Python: Быстрое удаление из deque по индексу

Объект deque в python — это коллекция, представляющая собой нечто общее между стеком и очередью. deque (double-ended queue — двусторонняя очередь) позволяют потокобезопасно добавлять и «отщипывать» элементы только с начала и конца коллекции, зато за константное время O(1). Начиная с python … Читать далее

Рубрика: Алгоритмы, На заметку | Метки: , , | 1 комментарий

Расстояние Левенштейна — определяем «похожесть» строк

Интересный и очень полезный алгоритм «дистанция Левенштейна» (Levenshtein distance), так же известная как редакционное расстояние или дистанция редактирования. Эта «дистанция» — это минимальное количество правок одной строки (под правками подразумеваются три возможные операции: стирание символа, замена символа и вставка символа), чтобы … Читать далее

Рубрика: Алгоритмы | Метки: , , | 18 комментариев