Обновить
228.61

Алгоритмы *

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

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

Методы распознавания текстов

Время на прочтение6 мин
Количество просмотров60K
Несмотря на то, что в настоящее время большинство документов составляется на компьютерах, задача создания полностью электронного документооборота ещё далека до полной реализации. Как правило, существующие системы охватывают деятельность отдельных организаций, а обмен данными между организациями осуществляется с помощью традиционных бумажных документов.
Читать дальше →

Моноиды и их приложения: моноидальные вычисления в деревьях

Время на прочтение20 мин
Количество просмотров24K
Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.

Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция


Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = ab — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John""Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(ab) ⊗ c = a ⊗ (bc)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
ae = ea = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если ae, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:
public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
Читать дальше →

Динамика по подотрезкам: базовые вещи и «одна хорошо, а две лучше»

Время на прочтение8 мин
Количество просмотров22K
Добрый вечер.
В этом посте я разберу задачу B «Дубы» с практического тура городской олимпиады школьников Санкт-Петербурга по информатике.
Задача эта на динамическое программирование по подотрезкам и идея решения интересна тем, что удобнее посчитать две динамики вместо одной. Если вас заинтересовало (незнание динамики не освобождает, но будет труднее) — добро пожаловать.
Читать дальше →

Макромедиа: анализ и интерпретация мультимедиа информации. M-Lang

Время на прочтение6 мин
Количество просмотров2.9K
Данная статья посвящена общей проблематике использования и разработки макромедиа технологий. Опираясь на известные принципы и методы анализа и обработки информации, автор поставил перед собой цель определить основные понятия и правила, необходимые для разработки некой порождающей грамматики и языка описания процесса анализа мультимедийной информации.
Рассматриваются два подхода к анализу мультимедийной информации: контентный, и контентно-интерпретационный. Так же в статье изложены основные правила и приведены примеры конструкций и спецификаций языка описания алгоритмов анализа графической информации — M-Lang.
Читать дальше →

Обсуждение работы алгоритма Романова на примере

Время на прочтение1 мин
Количество просмотров2.9K
В продолжение вчерашнего обсуждения.

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

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

Unit-тест и подробный лог работы приложения я выложил здесь:

gist.github.com/791064

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

Как видно из лога работы, тест заканчивается ситуацией, когда на очередном шаге построения гиперструктуры базисный граф оказался пустым множеством, что согласно алгоритму означает, что формула не выполнима (пункт 2b внизу страницы 11 в тексте статьи).

Чтобы не переписывать здесь еще раз статью, предлагаю в обсуждении задавать вопросы, которые требуют дополнительных разъяснений.

Почему я не верю в простые алгоритмы для NP-полных задач

Время на прочтение3 мин
Количество просмотров12K
На днях в этом блоге было опубликовано открытое письмо учёным по поводу предполагаемого полиномиального алгоритма для задачи 3-SAT. Обсуждение в том топике ещё далеко не закрыто и говорить о том, что в алгориме найдены ошибки пока преждевременно, но мне хочется написать почему «граждане учёные» не выстраиваются в очередь чтобы поскорее проверить это доказательство.

Примерно полгода назад, в августе 2010-го была опубликована попытка доказать что P≠NP. Тогда один математик-блогер, Скотт Оронсон, чтобы не казаться голословным в своём недоверии к этому доказательству поставил свой дом на то, что доказательство окажется ошибочным. Пожалуй, я ничего не потеряю если последую (с меньшим размахом) его примеру и поставлю на то, что нынешний алгоритм неправилен свой автомобиль (Auris 2008-го года выпуска).

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

Открытое письмо ученым и эталонная реализация алгоритма Романова для NP-полной задачи 3-ВЫП

Время на прочтение3 мин
Количество просмотров9.6K
С момента предыдущей публикации о полиномиальном алгоритме Романова для 3-ВЫП прошло 4,5 месяца.

За это время мы с Владимиром Федоровичем подготовили вариант статьи, чтобы отправить его коллегам-ученым и попутно реализовали эталонную реализацию этого алгоритма на Java.
Читать дальше →

Фильтр Блума

Время на прочтение3 мин
Количество просмотров63K
И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

Как фильтр это делает?

MATLAB и быстрое преобразование Фурье

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

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

Trie, или нагруженное дерево

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

Что это ?


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

Несколько советов по эмпирическому анализу алгоритмов

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

Вступление


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

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

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

Алгоритм синтеза многосвязной сети

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

Построение суффиксного дерева: алгоритм Укконена

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

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


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

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

На самом деле можно.
Реализация и доказательство алгоритма под катом

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

Алгоритм «diamond-square» для построения фрактальных ландшафтов

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

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

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

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

Алгоритмы поиска в строке

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

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


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

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

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

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

Как работают и зачем нужны датагриды

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

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

Генетические алгоритмы в MATLAB

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

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


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

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

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

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе

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

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

image

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

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

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

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

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

Прямой нечеткий логический вывод

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

Введение


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

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

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