Алгоритмы *

Эта статья адресована тем читателям, кто занимается программированием алгоритмов, и особенно интересуется труднорешаемыми задачами. Тем хабралюдям, которые против размещения алгоритмов на Хабре следует немедленно прекратить читать данную работу.

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

Предупреждаю, что статья содержит около 2000 слов (8 страниц А4), но дорогу осилит идущий.

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



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

Зачем использовать компрессию, почему бы не хранить все данные?

Хочется представить хабрасообществу интересный проект, который, пока что не освещался на хабре.

UnLogo

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

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

Видео под катом.

Предисловие

Совсем недавно в этом блоге была опубликована статья, посвященная алгоритму поведения роя пчел. Данная статья рассказывает о другом алгоритме роевого интеллекта, называемом муравьиным алгоритмом. Она состоит из введения, вкратце рассказывающего о заимствованном природном механизме, описания оригинального алгоритма Марко Дориго, обзора других муравьиных алгоритмов и заключения, в котором указываются области применения муравьиных алгоритмов и перспективные направления в их исследованиях.

Введение

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

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

Решая упражнения к книге «Программируем коллективный разум», я решил поделиться реализацией одного из алгоритмов упомянутого в этой книге (Глава 2 — Упражнение 1).

Исходные условия следующие: пусть мы имеем словарь с оценками критиков:

critics={'Lisa Rose': {'Superman Returns': 3.5, 'You, Me and Dupree': 2.5, 'The Night Listener': 3.0}, 
           'Gene Seymour': {'Superman Returns': 5.0, 'The Night Listener': 3.5, 'You, Me and Dupree': 3.5}}

Чем выше оценка, тем больше нравится фильм.
Надо вычислить: насколько схожи интересы критиков для того, например, чтобы можно было на основе оценок одного рекомендовать фильмы другому?

Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.

Условие

Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.

Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя.
Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).
Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

На рисунке я продемонстрирую работу такой гипотетической структуры.

Есть один замечательный сайт, посвящённый алгоритмам — наверняка многие из Вас о нём слышали и выкачивали его содержимое Teleport’ом или чем-нибудь подобным. Но совсем недавно Максим (автор сайта) создал очень удобную pdf-книжку из всех статей, что присутствовали на сайте. Я знаю, что ему будет приятно узнать, что его труды пригодились IT-сообществу, поэтому я и решил написать тут о электронной книге с алгоритмами.

Прошлый топик, про оценку сложности алгоритмов был весьма положительно оценён хабрасообществом. Из этого я могу сделать вывод, что тема базовых алгоритмов весьма интересна. Сегодня я хочу представить вам часть, посвящённую алгоритмам сортировки. Про базовые алгоритмы писать для Хабра совсем несерьёзно, а вот про сортировки Шелла, пирамидальную и быструю рассказать всё-таки стоит. (Если кому-то интересно почитать про базовые методы, милости прошу сюда)

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

Замечательный сайт www.sorting-algorithms.com позволяет увидеть, как сортируются данные разными алгоритмами. Вы сможете посмотреть анимацию в зависимости от алгоритма, исходных данных.



Все это бегает и сортируется прямо на ваших глазах!

Работает на Google App Engine, видимо, поэтому и лежит от посетителей с «Хабра».

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

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

В качестве испытательной функции была выбрана следующая функция:

На Хабрахабре неоднократно обсуждался генетический алгоритм, его преимущества и недостатки. Но генетический алгоритм (а точнее целая плеяда различных его подвидов) не является единственным в своём роде. Его относят к так называемым естественным алгоритмам. К ним также принадлежат алгоритм «имитации отжига», алгоритм «поведения роя пчёл» и алгоритм «поведения колонии муравьёв» и ещё несколько почти неизвестных алгоритмов.

Я хотел бы остановиться на втором, менее популярном но не менее интересном алгоритме синтеза и оптимизации — алгоритме поведения роя пчёл — и объяснить его принцип.

Возможно, многие из читателей задавались вопросом, как людям удаётся собирать кубик Рубика 3×3 за 7 секунд. Если даже предположить, что рекордсмену сильно повезло, то таблица мирового рейтинга по среднему из пяти результатов уже не оставляет сомнений: если больше 80 человек в среднем укладываются в 12 секунд, очевидно они что-то знают. В этом кратком обзоре я постараюсь приоткрыть секреты скоростной сборки. Сразу оговорюсь, что после прочтения этой статьи вы не станете чемпионами: здесь приведены только основные моменты и ссылки на более подробную информацию. Кроме того, даже после изучения метода полностью вам потребуются долгие тренировки для достижения хороших результатов. Зато вы получите неплохое представление о том, как это делается, и при желании будете знать, куда двигаться дальше. Я думаю, при достаточной усидчивости после нескольких месяцев тренировок многие смогут достичь среднего результата в районе 30 секунд.

Здравствуйте, уважаемое хабрасообщество.
В последнее время на хабре стали появляться статьи, так или иначе связанные с анализом и обработкой сигналов и изображений (например Обнаружение устойчивых признаков изображения: метод SURF, Интегральное представление изображений от BigObfuscator), в связи с чем я хотел бы вкратце осветить такой инструмент для анализа сигналов, как wavelet-преобразование.

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

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

Однажды мне понадобилось решить простенькую (как мне тогда казалось) задачу – в PHP-скрипте узнать длительность mp3-файла. Я слышал о ID3 тегах и сразу подумал, что информация о длительности хранится либо в тегах, либо в заголовках mp3-файла. Поверхностные поиски в интернете показали что за пару-тройку минут решить эту задачу не получится. Поскольку от природы я довольно любопытен а время не поджимало — решил не использовать сторонние инструменты а разобраться в одном из самых популярных форматов самостоятельно.

Если Вам интересно, что там внутри – добро пожаловать под кат (трафик).

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


Посмотреть можно здесь:
часть1
video.yandex.ru/users/ya-events/view/129
часть2
video.yandex.ru/users/ya-events/view/128

Чтобы не откладывать в долгий ящик сразу порассказываю несколько других примеров для MapReduce, обещанные в топике "MapReduce без зауми". (Если не понимаете полностью что такое MapReduce — прочитайте тот топик сначала! Без него не разберетесь)

Поговорим тут о подсчетах национальностей в городах, средних оценках и приводах учеников, ТИЦ, PageRank, входящих ссылках, нишевых ключевых словах, словах-синонимах, социальных сетях и общих друзьях. Постараемся обойтись без математических знаков и зауми.

Однако тема сама по себе сложная и все же напрячь мозги придется. Когда поймете — будет очень просто.

Входящие ссылки

Допустим у нас есть Интернет. В Интернете есть исходящие ссылки.

Допустим на входе у нас есть такие данные об ИСХОДЯЩИХ ссылках, собранные нашим паучком:

habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com, yandex.ru
thematicmedia.ru -> habrahabr.ru, autokadabra.ru
autokadabra.ru -> habrahabr.ru, yandex.ru

Т.е. мы знаем, что Хабр ссылается на Apple, MS, Ubuntu и Яндекс но кто ссылается на Хабр? Да, вопрос примитивный, но все же разложим на MapReduce. Дальше будет интереснее и этот пример понадобится.

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

Сразу скажу — топик — для тех, кто не разобрался что такое MapReduce. Для тех, кто разобрался — полезного тут ничего не будет.

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

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

Как посчитать все слова в Википедии (неправильный подход)

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

В самом простом случае мы можем завести хеш (dict, map, hash, ассоциативный массив, array() в PHP) и считать в нем слова.

$dict['word1'] += 1

Но что делать когда память под хеш кончится, а мы посчитали только одну сотую всех слов?

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

[FF D8]

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

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

Даже не зная, как происходит кодирование, мы уже можем кое-что извлечь из файла.

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.