Обновить
226.01

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Нечеткая логика на практике

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

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

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

Алгоритм нахождения N первых простых чисел — Решето Аткина

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

Читать дальше

Дерево ван Эмде Боаса

Время на прочтение6 мин
Количество просмотров19K
Всем доброго времени суток!

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

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

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

Что же там еще есть такого вкусного?

Алгоритм определения попадания точки в контур на основе комплексного анализа

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

image
Читать дальше →

Просто о Хиндли-Милнере

Время на прочтение5 мин
Количество просмотров22K

Введение


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

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

Алгоритм нахождения N первых простых чисел

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

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

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

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

Читать дальше →

Умножение длинных чисел методом Карацубы

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

Генерация аналитических поверхностей на примере карт. Часть 3

Время на прочтение4 мин
Количество просмотров3.2K

Введение


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

PageRank-сеть разнородных объектов

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

Генерация аналитических поверхностей на примере карт. Часть 2

Время на прочтение3 мин
Количество просмотров3.4K

Введение


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

Генерация аналитических поверхностей на примере карт

Время на прочтение4 мин
Количество просмотров5.9K

Введение


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

Fast flux DNS или новые технологии киберпреступности

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

Реализация нечеткого поиска

Время на прочтение6 мин
Количество просмотров43K


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

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

Ближайшие события

Еще одна версия алгоритма сравнения изображений

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

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

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

Время на прочтение3 мин
Количество просмотров501K

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


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

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

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

Эксперимент с голографическим кодированием/декодированием цветных изображений

Время на прочтение4 мин
Количество просмотров12K
image

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

Парсер формул с помощью метода рекурсивного спуска

Время на прочтение6 мин
Количество просмотров79K


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

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

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

Без запаха фильтрации и нелинейного оценивания*

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

Двоичные таблицы Юнга

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

Алгоритм Карацубы для умножения двух чисел

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

Читать дальше →

Вклад авторов