Алгоритмы *

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

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

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

Осторожно, 4 мегабайта!

Оптический поток (Optical flow) – технология, использующаяся в различных областях computer vision для определения сдвигов, сегментации, выделения объектов, компрессии видео. Однако если мы захотим его по-быстрому реализовать в своем проекте, прочитав про него на википедии или где-нибудь еще, то, скорее всего, очень быстро наткнемся на то, что он работает очень плохо и сбоит при определении сдвигов уже порядка 1-2 пикселей (по крайней мере так было у меня). Тогда обратимся к готовым реализациям, например, в OpenCV. Там он реализован различными методами и совершенно непонятно, чем аббревиатура PyrLK лучше или хуже обозначения Farneback или чего-нибудь в этом роде, да и придется поразбираться со смыслом параметров, которых в некоторых реализациях очень много. Причем, что интересно, эти алгоритмы как-то работают, в отличие от того, что мы написали сами. В чем же секрет?

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

Данная разновидность поразрядной MSD-сортировки «заточена» для строк. Впрочем, алгоритм так назван отнюдь не за лексическую специализацию. Автор Аллен Бичик (Allen Beechick) выбрал название в честь себя любимого, ABCsort расшифровывается как Allen Beechick Character sort.

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

Что касается алгоритма, то это единственно известная мне сортировка, за использование которой её изобретатель требует деньги.

Яндексу ежедневно приходится отвечать на десятки миллионов запросов. Поисковая система должна уметь быстро и точно их обрабатывать. Без применения лингвистики поисковая система сможет найти только точные совпадения в проиндексированных документах. Чтобы найти релевантные документы, системе необходимо правильно определить язык запроса, исправить опечатки, произвести морфологический разбор каждого слова, расширить запрос синонимами или вообще его переформулировать. В этой лекции Алексей Зобнин постарался дать студентам Малого ШАДа ответы на следующие вопросы:

• Зачем нужно учитывать морфологию?
• Как и зачем мы определяем язык запроса и документа?
• Что такое корпус языка?
• Что такое языковые модели, и как они применяются в поиске?
• Как производится морфологический анализ несловарных слов?
• Как определить правильное значение и морфологическую парадигму омонимов?
• Какие бывают опечатки, и как мы их исправляем?
• Что такое расширения запроса и чем они могут быть полезны?

Страница лекции

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

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

В данной статье будет показан математический подход к составлению алгоритмов на примере следующих вопросов и задач:

• Двоичные коды Грея. Их существование. Перебор подмножеств данного множества в порядке минимального изменения.
• Существование и реализация перебора подмножеств из k элементов в порядке минимального изменения.

Итак, приступим.

Вступление

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

В ходе данной публикации я хочу поделиться идеей реализации хорошо известного примитива синхронизации readers-writer lock на основе, так называемых атомарных операций. Как известно, readers-writer lock призван решать проблему синхронизации доступа к разделяемому ресурсу таким образом, чтобы избегать одновременных чтения и записи, но, при этом позволять параллельное чтение сколь угодно большому количеству потоков.

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

В статье будет много картинок. Объяснение как решать задачу рекурсивно и как она решается бинарным поиском.
В общем статья посвящается тем смелым, кто пока еще боится Ханойской башни, но хочет перестать её бояться.

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

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

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

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

«Усложнённость (Simplexity) — процесс, которым природа достигает простых результатов сложными путями.» — Bruce Schiff

1. Введение

Представьте себе следующую задачу: у нас есть таблица из n целочисленных ключей A₁, A₂, …, A_n, и целочисленное значение X. Нам нужно найти индекс числа X в этой таблице, но при этом мы особо никуда не торопимся. На самом деле, мы бы хотели делать это как можно дольше.

Для этой задачи мы могли бы остановиться на самом тривиальном алгоритме, а именно, перебирать все A_n по порядку и сравнивать их с X. Но, может так случиться, что X = A₁, и алгоритм остановится на самом первом шаге. Таким образом, мы видим, что наивный алгоритм в наилучшем случае имеет временную сложность O(1). Возникает вопрос — можем ли мы улучшить (то есть, ухудшить) этот результат?

Разумеется, мы можем сильно замедлить этот алгоритм, добавив в него пустых циклов перед первой проверкой равенства X и A₁. Но, к сожалению, этот способ нам не годится, потому что любой дурак заметит, что алгоритм просто-напросто впустую тратит время. Таким образом, нам нужно найти такой алгоритм, который бы всё-таки продвигался к цели, не смотря на отсутствие энтузиазма, или вовсе желания до неё в конечном итоге дойти.

Технологический стартап Vicarious объявил о разработке решения, позволяющего успешно проходить современные CAPTCHA-тесты, в том числе наиболее популярную в современном интернете reCAPTCHA, в 2009 году приобретенную компанией Google.

С помощью машинного обучения и использования принципов строения мозга человека, исследователям удалось достичь 90% точности распознавания CAPTCHA от Google, Yahoo, PayPal, Captcha.com и других проектов. Этот прогресс показывает, что современные CAPTCHA уже не эффективны в качестве теста Тьюринга.

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

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

Любительница поэзии и программист Джулия Эванс написала красивую программку gzip.jl, которая показывает, как gzip осуществляет декомпрессию текста, сжатого с помощью алгоритма LZ77.

_{(лучше смотреть без звука)}


LZ77 использует словарный подход и кодирует совпадения текста. При повторном упоминании одинакового фрагмента алгоритм использует код предыдущего упоминания (красным цветом).

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

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