Алгоритмы *

Событие в объектно-ориентированное программировании (ООП) — это сообщение, которое возникает в различных точках исполняемого кода при выполнении определённых условий. Данные сообщения направляются обработчикам (слушателям), что позволяет своевременно реагировать на изменившееся состояние системы.

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

В настоящей статье я хотел бы сделать обзор популярных алгоритмов для решения задачи нахождения максимальной общей подпоследовательности или LCS (longest common sequense). Так как акцент сделан на обучении, а не на реальном использовании, в качестве языка для реализации выбран Python, что позволит сократить количество кода и сконцентрироваться на основных идеях.

Данная статья рассказывает не только о наиболее распространённых фильтрах обработки изображений, но в понятной форме описывает алгоритмы их работы. Статья ориентирована, прежде всего, на программистов, занимающихся обработкой изображений.

Введение

Структуры данных можно разделить на две группы: эфемерные (ephemeral) и персистентные (persistent).

Эфемерными называются структуры данных, хранящие только последнюю свою версию.
Персистентные структуры, то есть те, которые сохраняют все свои предыдущие версии, в свою очередь можно разделить еще на две подгруппы: если структура данных, позволяет изменять только последнюю версию, она называется частично персистентной (partially persistent), если же позволяется изменять любую версию, такая структура считается полностью персистентной (fully persistent).

Далее будет рассмотрено дерево отрезков и его полностью персистентная версия.
Весь код доступен на GitHub.

Люди, использующие системы контроля версий исходного кода (SVN, Mercurial, Git и т.п.), наверняка часто пользуются возможностью сравнения версий файлов для просмотра внесенных пользователями изменений. Существует множество независимых программ сравнения версий (WinMerge, BeyondCompare и др.). При сравнении версий, как правило, две версии файла показываются рядом друг с другом таким образом, чтобы одинаковые (неизменившиеся) части документов были расположены напротив друг друга, а изменившиеся (добавленные и удаленные) выделяются соответствующим цветом.
Уверен, многим было бы интересно узнать, какие алгоритмы могут использоваться для реализации такого сравнения.

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

Введение

Начнем с определения. Пусть у нас есть строка s_0..n-1. Полиномиальным хешем этой строки называется число h = hash(s_0..n-1) = s₀ + ps₁ + p²s₂ +… + p^n-1s_n-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а s_i — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

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

Первая часть.

Во второй части будут рассмотрены арифметическое кодирование и преобразование Барроуза-Уилера (последнее часто незаслуженно забывают во многих статьях). Я не буду рассматривать семейство алгоритмов LZ, так как про них на хабре уже были неплохие статьи.

Итак, начнем с арифметического кодирования — на мой взгляд, одного из самых изящных (с точки зрения идеи) методов сжатия.

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

Многим людям приходилось использовать генератор случайных чисел в программах для создания непредсказуемости, чтобы сделать движение и поведение объектов более натуральным или генерировать текстуры. Генераторы случайных чисел, конечно, имеют свои области применения, но иногда их выход может быть слишком «жесткий», чтобы казаться естественным. В этой статье мы представляем функцию, которая имеет очень широкий спектр применения, больше, чем я мог бы думать, но в основном везде, где вам нужно чтобы что-то выглядело естественного происхождения. К тому же вывод может быть легко настроен под ваши нужды.

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

Для создания функции шума Перлина, вам нужны две вещи, функции шума и функция интерполяции.

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

В этой статье я коснусь фундаментальных моментов сжатия и основных типов алгоритмов.

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


Изображение отрендерено с помощью Maxwell Render.

Давным-давно, когда я был ещё наивным школьником, мне вдруг стало жутко любопытно: а каким же волшебным образом данные в архивах занимают меньше места? Оседлав свой верный диалап, я начал бороздить просторы Интернетов в поисках ответа, и нашёл множество статей с довольно подробным изложением интересующей меня информации. Но ни одна из них тогда не показалась мне простой для понимания — листинги кода казались китайской грамотой, а попытки понять необычную терминологию и разнообразные формулы не увенчивались успехом.

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

Статья представляет собой нечто вроде “практического руководства” для построения весьма интересных трехмерных графиков функций вида z=f(x,y), с примером реализации на C#.

Доброго времени суток.

В той или иной степени интересуюсь алгоритмами. Наткнулся на свежую статью
«Поиск повторений в двумерном массиве, или вычислительная сложность на примере» http://habrahabr.ru/post/141258/. Автор стати,Singerofthefall, довольно интересно рассказывает про решение задачи и оптимизации алгоритма. Очень интересно. Однако, по моему мнению, прежде всего необходимо было определить не алгоритм, а инструмент которым будет решаться задача. И вот инструмент был выбран неправильный, отсюда вся сложность и оптимизации.
Для решения задачи автора более всего подходили инструменты БД, соответственно и надо было их использовать.

Преобразование Хафа служит для поиска на изображении фигур, заданных аналитически: прямых, окружностей и любых других, для которых вы сможете придумать уравнение с небольшим количеством параметров. О преобразовании Хафа написано немало, и данная статья не ставит цели подробно осветить все аспекты. Я лишь объясню общий принцип, останавливаясь на особенностях, мешающих его реализации на GPU «в лоб» и, конечно же, предложу решение. Те, кто знают проблемы и хотят сразу видеть решение, могут пропустить пару-тройку разделов.

В Санкт-Петербурге есть замечательное место, где из программистов делают ученых — теоретиков Computer Science. Это Академический Университет Российской Академии Наук (АУ РАН).

На тот момент, когда я поступила на Теоретическое Отделение кафедры Математических и Информационных Технологий АУ, отделение имело только один выпуск, состоящий из двух человек. Сейчас Академический Университет уже заработал себя прекрасное имя. Его выпускники работают в ведущих компаниях города, он принимает студентов из других городов, обеспечивая их жильем, а платное отделение стоит всего-навсего 10 тыс. рублей в семестр.

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

Доброго времени суток, уважаемое хабрасообщество.

Когда я учился в институте на втором или третьем курсе (то есть, в общем, не так и давно), был у меня, помимо прочих, предмет под названием «алгоритмы и структуры данных». Рассказывали там, однако, не только про сами алгоритмы и структуры, но и о таком понятии, как «вычислительная сложность». Признаюсь, тогда это меня не очень заинтересовало.

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

Однако недавно мне пришлось сильно изменить свое мнение из-за простой, казалось бы, задачи.

Этот топик повествует об использовании Radix Tree на практическом примере. Radix Tree или дерево остатков — это структура данных, формируемая по принципу хранение значений в листовом узле. Промежуточные узлы представляют собой элемент конечного значения. Это может быть бит для чисел, символ для строк или цифра для номера, как в примере ниже. Приведенный алгоритм сжатия с использованием Radix Tree используется в реальной embeded системе, для хранения параметров телефонного файрвола.

Вступление

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

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

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

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

Анатомия (объектная декомпозиция)

Модель конечного автомата включает следующие базовые сущности:

1. Состояние — это режим функционирования управляемой системы, отличный от других по предоставляемым возможностям. Таким образом, снапшоты кешей и буферов, варианты циклов «от забора и до обеда» и другие акциденции управляемой системы в понятие «состояния» не входят. В норме состояний должны быть считанные единицы; если счет пошел на второй десяток — скорее всего, управляемую систему следует раздробить или иерархизировать.
2. Условие — это логическое значение (true или false) на одном из «входов» системы. Суперпозиция состояний всех входов автомата однозначно определяет целевое состояние автомата. Таким образом, любой входной сигнал, значимый для состояния автомата, в конечном счете сводится к установке значения одного или нескольких условий.
3. Реакция — это отклик автомата на отличие текущего состояния от целевого. Принципиально различных видов реакции мы насчитали два с половиной: прямой переход между состояниями, маршрут и стоп-маршрут («кирпич»). Прямой переход может быть и пустой операцией (NOP) — например, в случае, если изменение входов вызвано уведомлением о завершении асинхронной операции.

Итак, в прошлых частях мы разобрались как сравнительно просто сворачивать спирали РНК. Теперь нам предстоит понять, как вообще сворачивается РНК. То РНК, которое мы взяли в виде примера имеет три спирали. Две из них L1 и L2 можно свернуть независимо. А вот с третьей проблемы. Эта третья состоит из концов РНК, и при ее сворачивании начинают двигаться наши свернутые спирали L1 и L2. Во-первых, при этом они мешают друг другу, и следовательно и сворачиванию третьей спирали. Во-вторых, возможно образование около десятка разнообразных псевдосимметричных структур — спирали L1, L2 могут по разному располагаться по отношению к сворачиваемым концам РНК.

Здесь мы попробуем разобраться как эти проблемы решить.

Недавно я наткнулся на интересную статью, опубликованную rgen3, в которой описан DTW-алгоритм распознавания речи. В общих чертах, это сравнение речевых последовательностей с применением динамического программирования.

Заинтересовавшись темой, я попробовал применить этот алгоритм на практике, но на этом пути меня поджидало некоторое количество граблей. Прежде всего, что именно нужно сравнивать? Непосредственно звуковые сигналы во временной области — долго и не очень эффективно. Спектрограммы — уже быстрее, но не намного эффективнее. Поиски наиболее рационального представления привели меня к MFCC или Мел-частотным кепстральным коэффициентам, которые часто используются в качестве характеристики речевых сигналов. Здесь я попытаюсь объяснить, что они из себя представляют.