Алгоритмы *

Просматривая различный код по выводу на экран какой-нибудь даже примитивной графики, я заметил чрезмерную любовь некоторых программистов к тригонометрии. Часто код пестрит синусами, косинусами и арктангенсами там, где без них можно обойтись. Этим грешат даже хорошие программисты, которые способны спроектировать сложную систему, но почему-то не освоили вектора в объёме школьной программы. Буквально азов векторной алгебры хватает для решения многих насущных проблем. В этом топике я хочу провести краткий ликбез, напомнить основные действия с векторами на плоскости и в качестве примера решить две задачи без тригонометрии: поиск отражённого луча по падающему лучу и произвольно расположенному зеркалу, а также рисование наконечника стрелки. Если вы можете представить в голове рисование произвольно направленной стрелки без синусов и косинусов, смело пропускайте этот топик. Для остальных постараюсь объяснять попроще.

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Введение

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

Есть хорошая статья Питера Норвига, в которой он рассказывает как написать спеллчекер в 20 строк кода. В этой статье он показывает как поисковые системы могут исправлять ошибки в запросах. И делает это довольно элегантно. Однако, у его подхода есть два серьезных недостатка. Во-первых, исправление более трех ошибок требует больших ресурсов. А гугл, кстати, неплохо справляется и с четырьмя ошибками. Во-вторых, нет возможности проверки связного текста.



Итак, хочется исправить эти проблемы. А именно, написать корректор коротких фраз или запросов, который:

• умел бы выявлять три (и более) ошибки в запросе;
• умел бы проверять «разорванные» или «слипшиеся» фразы, например expertsexchange — experts_exchange, ma na ger — manager
• не требовал много кода для реализации
• мог бы достраиваться до исправления ошибок на других языках и других типов" ошибок

Остальное — под катом.

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

В статье я покажу как использовать метод динамического программирования по профилю для решения задачи о подсчёте количества гамильтоновых циклов на прямоугольной решётке размером 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