Алгоритмы *

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

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

Дерево ван Эмде Боаса (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», который является распространением линейной фильтрации Калмана на случай, когда уравнения динамики и наблюдения системы нелинейны и не могут быть адекватно линеаризованы.
Как название данного метода фильтрации «кошерно» удобочитаемо переводится на русский я пока не знаю, что отражено в названии статьи, поэтому решил просто скопипастить довольно забавный, на мой взгляд, машинный перевод. Еще одна забавная версия перевода — нечуткий фильтр.

Итак, как и обещал, продолжение темы о таблицах Юнга. Напомню, что под таблицей Юнга понимается числовая матрица, обладающая некоторыми специальными свойствами. Матрица – это двумерный массив. И вот тут должен возникнуть естественный вопрос – а почему, собственно, массив должен быть двумерным? А что, если мы попробуем реализовать на тех же принципах таблицу размерности три, или четыре, а лучше всего, конечно, пять звездочек! О том, куда приведет нас такое обобщение, можно прочитать под катом…

Как-то раз пришлось реализовывать умножение длинных чисел, через половинки их представления на C++. 128-битные числа были представлены как пара 64-битных. Оказалось что перемножить два 128-битных числа и получить все 256 бит результата по сложности сравнимо с 4-мя произведениями 64-битных половинок. Как же это работает…

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

Зачем определять площадь сложной фигуры?

Да мало ли зачем. Например, возникла необходимость определить площадь территории на карте. Конечно, можно посмотреть в справочнике или поискать в интернете, но иногда и территории бывают нестандартными — допустим, вы озаботились проблемами лесов в пойме Амазонки и хотите ежемесячно измерять площадь зелёных пятен на фотографиях со спутника. Если вы ботаник (в хорошем смысле слова), то вам может понадобиться измерить площадь листовой поверхности разных сортов одного растения. Или, к примеру, более прозаичная задача — нужно зашпатлевать кусок стены, а банки шпатлёвки хватает только на 1 кв. м. — нужно выяснить, покупать одну банку или раскошелиться на две.