Алгоритмы *

Странно, но статей о извлечение знаний (data mining) и кластеризации (как одном из основных инструментом, которие используются для извлечения знаний) на Хабре совсем немного. А если говорить говорить о конкретных алгоритмах, то рассматривались только hard/soft k-means.

В статье ниже описывается теория и реализация (Python + matplotlib) не очень известного, но крайне интересного иерархического метода который можно назвать алгоритмом а-квазиэквивалентности.

На примере хранения дерева комментариев.

Многие наверняка сталкивались с проблемой хранения комментариев, по крайней мере задумывались об этом. Очевидным решением «в лоб» является ссылка на родительский комментарий и, как следствие, рекурсивные вызовы при необходимости отобразить дерево. Современные СУБД поддерживают иерархические запросы, но мне кажется, что это просто перенос проблемы за пределы области видимости, может быть я не прав. В любом случае я писал для Google Application Engine, там разговора об иерархических запросах не идёт вообще.

Мне очень не нравилась перспектива рекурсии и множество мелких запросов к базе, поэтому я стал изобретать какой-то способ получить все комментарии одним простым запросом. И такой способ я довольно быстро «изобрёл». Опросил нескольких знакомых, оказалось, что мало кто на эту тему задумывался, поэтому возьму на себя смелость описать что именно я реализовал.

Стандартная статья о нечеткой логике обычно грешит двумя вещами:

1. В 99% случаев статья касается исключительно применения нечеткой логики в контексте нечетких множеств, а точнее нечеткого вывода, а еще точнее алгоритма Мамдани. Складывается впечатление, что только этим способом нечеткая логика может быть применена, однако это не так.
2. Почти всегда статья написана на математическом языке. Замечательно, но программисты пользуются другим языком с другими обозначениями. Поэтому оказывается, что статья просто непонятна тем, кому, казалось бы, должна быть полезна.

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

В процессе реализации одной программы я столкнулся с задачей поиска простых чисел до числа N порядка . На хабре уже неоднократно писали про различные способы и методы, но не упоминали про основной метод решения, что я сегодня и постараюсь исправить.

Всем доброго времени суток!

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

Дерево ван Эмде Боаса (van Emde Boas tree) — ассоциативный массив, который позволяет хранить целые числа в диапазоне [0; U), где U = 2^k, проще говоря, числа, состоящие не более чем из k бит. Казалось бы, зачем нужно еще какое-то дерево, да еще позволяющее хранить только целые числа, когда существует множество различных сбалансриованных двоичных деревьев поиска, позволяющих выполнять операции вставки, удаления и прочие за O(log n), где n — количество элементов в дереве?

Главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов.

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

Введение

Если вы когда-нибудь интересовались не слишком популярными языками, то должно быть слышали о «Хиндли-Милнере». Этот алгоритм вывода типов используются в F# и Haskell и OCaml, как и в их предшественнике ML. Некоторые исследователи даже пытаются использовать ХМ для оптимизации динамических языков вроде Ruby, JavaScript и Clojure.

И не смотря на его распространенность, до сих пор не было простого и понятного объяснения, что же это такое. Как же эта магия работает? Всегда ли выводимые типы будут верными? Или чем Хиндли-Милнер лучше, скажем, Java? И пока те, кто действительно знает что такое ХМ будут восстанавливаться от очередного умственного перенапряжения, мы попробуем разобраться в этом сами.

В процессе обучения программированию я столкнулся с задачей поиска 1M первых простых чисел.

На Хабре уже не раз писали об этом. Но, чаще всего, речь шла о поиске всех простых чисел до числа N. Я же расскажу о том, как решал задачу нахождения N первых простых чисел.

На первый взгляд может показаться, что разницы в этих задачах практически нет. И это действительно так, пока мы не поймем, что перебор делителей справляется с задачей крайне плохо.

В результате проведенной работы на поиск 1 миллиона простых чисел у меня уходит всего 0,262 секунды, что, конечно же, не предел, но уже впечатляет. Алгоритм реализован на C++.

На днях нужно было разобраться с этим алгоритмом, но беглый поиск в google ничего путнего не дал. На Хабре тоже нашлась только одна статья, которая мне не особо помогла. Разобравшись, попробую поделиться с общественностью в доступной форме:

Введение

Точное физическое моделирование требует высокополигональных карт. Чем выше точность карты, тем больший объем памяти она занимает и тем больше приходится обрабатывать данных, чтобы получить высоту. Сплайновая интерполяция позволяет получить сетку любого разрешения, с любым, удобным в данный момент, шагом по широте и долготе.

Данная заметка является развитием предыдущего текста, "Проблемы обобщения PageRank". Суть в том, чтобы более-менее полноценно рейтинговать людей с помощью алгоритма PageRank. Почему именно PageRank? Ну, конечно можно составить что-то типа суммы-анкеты из разных слагаемых и вычислять ее для каждого пользователя. Например, образование среднее столько-то баллов, высшее столько-то, должность офисный планктон столько-то, топ-менеджер столько-то, ученая степень есть/нету, опыт работы столько-то лет (вычисляем функцию от количества лет), рейтинг на Хабре такой-то, количество френдов в Фейсбуке столько-то и т. д. и т. п. Мало что список получится длинным и непонятно, учтете ли вы все наиболее значимые факторы. Но понадобится еще каким-то образом (скорее «на глазок») определить коэффициенты значимости при каждом слагаемом, и это тоже задача. Метод PageRank дает на мой взгляд любопытный способ решить эту последнюю задачу.

Введение

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

Введение

Возникла однажды интересная задача: организовать возможность работы программы с трехмерными изображениями земной поверхности больших размеров. После изучения множества литературы и различных источников, стало ясно, что эффективных подходов в общем доступе не найти.

С одной из наиболее активных угроз мы сталкиваемся сегодня в интернете — это кибер-преступность.Все чаще преступники разрабатывают более совершенные средства получения прибыли от онлайновой преступной деятельности. Эта статья демонстрирует рост популярности, сложного метода, называемый Fast-Flux сети, который, как мы наблюдаем, находит все более широкое применение в «дикой природе». Fast-Flux сети — сети взломанных компьютерных систем с публичными записями DNS, которые постоянно меняются, в некоторых случаях каждые 3 минуты. Постоянно меняющаяся архитектура, делает гораздо более трудным слежение за преступной деятельностью и закрытые оной.

Если ваш веб проект так или иначе будет связан с поиском и предоставлением пользователям некоторых данных, то перед вами наверняка встанет задача реализации строки поиска. При этом, если в проекте по какой-либо причине не удастся использовать технологии умных сервисов как Google или Яндекс, то поиск частично или полностью придется реализовать самостоятельно. Одной из подзадач наверняка будет реализация нечеткого поиска, ведь пользователи часто ошибаются и иногда не знают точных терминов, названий или имен.

В данной статье описывается возможная реализация нечеткого поиска, которая была применена для поиска на сайте edatuda.ru.

Эта статья с месяц висела у меня в черновиках, пока кто-то мне наконец не привел карму к тонусу. Не знаю кто, но спасибо тебе

Сегодня, зайдя в очередной раз на хабр, наткнулся на вот эту интересную статью. Там описывается алгоритм хэширования изображений. Когда я читал эту статью, мне пришла в голову мысль, как можно изменить этот алгоритм, чтобы он кушал изображения, у которых сильно различается, например, яркость (но сами изображения при этом идентичны).

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Однажды я был поражён одним из удивительных свойств голограммы, которое заключается в том, что разбив голографический снимок объекта на осколки, по каждому из осколков можно восстановить изображение всего объекта, правда с несколько ухудшенным качеством. Прочитав топик «Эксперимент с голографическим кодированием и декодированием информации» товарища eresik я непременно сам захотел реализовать подобную цифровую голограмму. Взяв за основу его алгоритм, я запустил Delphi и принялся за дело. Наконец, немного повозившись с коэффициентами, я стал получать адекватные чёрно-белые картины похожие на те, которые получал eresik. При затирании части голограммы, как ни удивительно, исходное изображение восстанавливалось! Так каким же образом это может происходить? Я попытаюсь рассказать, как можно наглядно объяснить это свойство голограммы, не вдаваясь в физику и математику.

Доброго времени суток, уважаемые Хабровчане!

Хочу поделится с вами реализацией алгоритма «Метод рекурсивного спуска» на примере написания парсера формул с поддержкой переменных и функций на языке Java

Эта статья в (скорее всего, во всяком случае я надеюсь :) ) будет интересна для новичков, или кому-то применить как фундамент для своего решения данной задачи.
Кому интересно — прошу под кат

* от англ. «unscented filtering and nonlinear estimation» (by Переводчик Google)
По просьбе dmitriyn решил опубликовать свое видение на так называемый «Unscented Kalman filter», который является распространением линейной фильтрации Калмана на случай, когда уравнения динамики и наблюдения системы нелинейны и не могут быть адекватно линеаризованы.
Как название данного метода фильтрации «кошерно» удобочитаемо переводится на русский я пока не знаю, что отражено в названии статьи, поэтому решил просто скопипастить довольно забавный, на мой взгляд, машинный перевод. Еще одна забавная версия перевода — нечуткий фильтр.