Алгоритмы *

По работе неоднократно сталкивался с необходимостью быстро определить наличие в сигнале гармонических составляющих. Часто для примерной оценки достаточно воспользоваться алгоритмом быстрого преобразования Фурье. Тем более, что его реализации есть практически во всех математических пакетах и библиотеках, да и собственноручно реализовать не составит особого труда. Между тем, опыт показывает, что, при всей своей простоте, метод начинает вызывать некоторые вопросы, когда возникает необходимость не просто посмотреть наличие дискреток в сигнале, но и выяснить их абсолютные значения, т.е. нормализовать полученный результат.

В этой статье я постараюсь объяснить, что же все-таки выдает в качестве результата fft (Fast Fourier transform) на примере MATLAB (и в качестве бонуса проведу небольшой ликбез по этому весьма полезному, на мой взгляд, языку).

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

Что это ?

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

Вступление

В ноябре прошлого года появилась книга Magnus Lie Hetland под названием «Python Algorithms: Mastering Basic Algorithms in the Python Language». Автор много лет занимается программированием и сейчас читает курс теории алгоритмов в одном из норвежских университетов. В своей книге он довольно простыми словами объясняет методы построения и анализа алгоритмов, а также приводит множество примеров, ориентированных на программистов на Python. Автор сосредотачивает свое внимание на практическом подходе к построению и оптимизации решений различных алгоритмических задач. В одном из обзоров говорится, что эту книгу можно сравнить с классическим трудом Кормена.

Мы с tanenn понемногу переводим эту книгу, и я предлагаю вашему вниманию перевод части первой главы — «Empirical Evaluation of Algorithms».

Вступление
С «официальным» алгоритмом синтеза многосвязных сетей я лично не сталкивался ни в Интернете, ни в процессе обучения в техническом ВУЗе. Cуществуют скорее методики построения многосвязных сетей нежели зарегистрированные и запатентованные алгоритмы. Для тех кто ни разу не сталкивался с такой задачей хочется заметить, что она в основном возникает в процессе моделирования и проектирования телекоммуникационных сетей различных масштабов. Реализовывать полученный в процессе такого моделирования проект на практике или нет, зависит прежде всего от его целей. Если это курсовая работа студентов специальностей связанных с телекоммуникациями, то описанные ниже рекомендации для них вполне применимы. Организации занимающиеся проектированием сетей национальных или хотя бы городских масштабов используют свои практические методы построения многосвязных сетей, однако не исключено, что информация представленная в статье будет полезна и для них.

По просьбам трудящихся выкладываю описание и доказательство алгоритма Укконена.

Описание задачи

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

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.

Думаю, многие знакомы с весьма необычной игрой Minecraft (справа — пример сгенерированной в ней карты), в которой игрок находится на (практически) бесконечной поверхности Земли и может исследовать окружающий мир с минимальными ограничениями.

Как же автору игры, Notch'у, удалось добиться подобного сходства его случайных «миров» с земными просторами? В этом топике я как раз и рассмотрю один из способов построить искусственный ландшафт такого рода (и вскользь упомяну пару других способов), а также расскажу о моем небольшом усовершенствовании этого алгоритма, позволяющем значительно увеличивать размеры ландшафта без заметных потерь в производительности.

Внутри вас ждет несколько схем и красивых картинок, довольно много букв и ссылка на пример реализации алгоритма.

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

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

Суть генетических алгоритмов

Данный топик посвящен решению оптимизационных задач при помощи генетических алгоритмов в среде MATLAB. Заранее приношу извинения за большой объем данных: он обусловлен тем, что при написании топика основной поставленной задачей было подробно раскрыть каждый из настраиваемых в MATLAB параметров работы генетических алгоритмов.

Генетические алгоритмы – это метод решения оптимизационных задач, основанный на биологических принципах естественного отбора и эволюции. Генетический алгоритм повторяет определенное количество раз процедуру модификации популяции (набора отдельных решений), добиваясь тем самым получения новых наборов решений (новых популяций). При этом на каждом шаге из популяции выбираются «родительские особи», то есть решения, совместная модификация которых (скрещивание) и приводит к формированию новой особи в следующем поколении. Генетический алгоритм использует три вида правил, на основе которых формируется новое поколение: правила отбора, скрещивания и мутации. Мутация позволяет путем внесения изменений в новое поколение избежать попадания в локальные минимумы оптимизируемой функции.

(Под катом основная часть + несколько скриншотов).

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

На написание статьи, подтолкнула публикация Прогнозирование временных рядов.

Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).

Введение

В 1965 г. в журнале «Information and Control» была опубликована работа Л.Заде под названием «Fuzzy sets». Это название переведено на русский язык как нечеткие множества. Побудительным мотивом стала необходимость описания таких явлений и понятий, которые имеют многозначным и неточный характер. Известные до этого математические методы, использовавшие классическую теорию множеств и двузначную логику, не позволяли решать проблемы этого типа.

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

Для начала вкратце о задаче и о самом алгоритме:

Предисловие

— Кибердворник дядя Федя силой ровно в три медведя, — сообщил Поль, извлекая из недр кибердворника блок регулировки. — Я тут уже знаю одного Федю. Приятный такой, веснушчатый. Очень, очень асептический молодой человек. Это не твой родственник?

Аркадий и Борис Стругацкие (Полдень. ХХII век).

Статья посвящена вопросу применимости генетических алгоритмов к проблеме идентификации динамической системы.
Обновлено: опубликовано продолжение ТАУ-Дарвинизм: реализация на Ruby

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



Конечно, для современных видеокарт такая задача является примитивной, однако в те времена на 3.5 мегагерцовом «Cпектруме» о подобных мощностях можно было лишь помечтать. Так что забудьте о графических процессорах, матрицах вращения и нереально ресурсоёмких вычислениях и попробуйте хотя бы примерно прикинуть, каким образом можно реализовать вот такую красивость.

Любопытно? Тогда добро пожаловать под кат!

Вместо предисловия

Урок русского языка в грузинской нерусской школе.
Учительница:
— Дэти, это нэльзя понять, это надо запомнить: ОТ ВАС пишется раздельно, а
КВАС — вместе.

Анекдот взят тут.

Введение

На написание статьи вдохновила игра «Wesnoth» — пошаговая стратегия с элементами RPG. В этой игре персонажи перемещаются по карте, состоящей из шестиугольных полигонов. Таким образом, окруженный со всех сторон персонаж может быть атакован шестью вражескими. По этой причине тактическая составляющая в игре очень важна. Возник вопрос: как повлияет на игровой процесс переход от карты с фиксированной геометрией полигонов на карту с произвольной геометрией?

Предисловие

На написание статьи вдохновили две публикации:

• Живые графы
• Обзор методов эволюции...

Захотел изложить свои мысли и свой взгляд на этот вопрос именно как практик от программирования «с математическим бэкграундом». Это будет повествование «на пальцах». Специалистом в генной инженерии не являюсь и сужу по поверхностным описаниям механизмов функционирования живых клеток и ДНК.

Как находить тексты похожие по смыслу? Какие есть алгоритмы для поиска текстов одной тематики? – Вопросы регулярно возникающие на различных программистских форумах. Сегодня я расскажу об одном из подходов, которым активно пользуются поисковые гиганты и который звучит чем-то вроде мантры для SEO aka поисковых оптимизаторов. Этот подход называет латентно-семантический анализ (LSA), он же латентно-семантическое индексирование (LSI)

Введение
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок

, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» с сложностью временной сложностью O(N) в худшем случае.

На данный момент происходит лавинообразное увеличение числа мультимедиа-ресурсов, в частности ­ изображений. Как следствие, возрастают требования к средствам систематизации и поиска подобных ресурсов. Большинство существующих на данный момент систем,
осуществляющих поиск информации по описанию (англ. Description-Based Image Retrieval, DBIR), уже не могут в полной мере удовлетворить потребности человека. Поэтому все больше растет интерес к поиску объектов по содержанию (англ. Content-Based Image Retrieval, CBIR).

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