Алгоритмы *

Однажды я был поражён одним из удивительных свойств голограммы, которое заключается в том, что разбив голографический снимок объекта на осколки, по каждому из осколков можно восстановить изображение всего объекта, правда с несколько ухудшенным качеством. Прочитав топик «Эксперимент с голографическим кодированием и декодированием информации» товарища eresik я непременно сам захотел реализовать подобную цифровую голограмму. Взяв за основу его алгоритм, я запустил Delphi и принялся за дело. Наконец, немного повозившись с коэффициентами, я стал получать адекватные чёрно-белые картины похожие на те, которые получал eresik. При затирании части голограммы, как ни удивительно, исходное изображение восстанавливалось! Так каким же образом это может происходить? Я попытаюсь рассказать, как можно наглядно объяснить это свойство голограммы, не вдаваясь в физику и математику.

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

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

Дистрибутив:
MLDemos 0.3.2 for Windows (минимальные требования: XP SP3)
MLDemos 0.3.2 for Mac (минимальные требования: Snow Leopard)
MLDemos 0.1.3 for Linux 32bit (deb) (билд для: Ubuntu 10.04)

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

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

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

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

Здравствуй, Хабр!

В этой статье я хочу поделиться опытом распознавания рукописных математических выражений. Хотя уже и существуют такие средства распознавания рукописных формул как «Панель математического ввода» mip.exe в Windows7, разнообразие подходов к решению данной проблемы не может не впечатлять. Об одном из таких подходов я и собираюсь рассказать.

Недавно прочитал пост из «Дополненной реальности», в котором упоминается Фильтр Калмана в сравнении с более простым «альфа-бета» фильтром. Давно собирался сочинить нечто вроде сниппета по составлению ФК, и вот думаю самое время. В статье я вам расскажу как на практике можно составить расширенный ФК не особо утруждая себя высоконаучными размышлениями и глубокими теоретическими изысканиями.

Захотелось мне как-то сделать кодирование информации основываясь на голографическом принципе. Захотелось не просто так, а для проверки кое-каких своих идей и теорий. Теории не подтвердились, идеи не реализовались. Но поскольку подобного алгоритма я «с наскока» не нашёл и пришлось придумывать его самому, основываясь на учебниках по физике, то решил поделиться им на хабре. Алгоритм, кстати, довольно простой.

Здравствуй, Хабр! Мы с тобой уже побаловались фильтрами Блума и MinHash. Сегодня разговор пойдёт о ещё одном вероятностном-рандомизированном алгоритме, который позволяет с минимальными затратами памяти определить примерное число уникальных элементов в больших объёмах данных.

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

Способ всем хорош, но требует относительно большой объём памяти для своей работы, ну а мы с вами, как известно, неугомонные гении эффективности. Зачем много, если можно мало — примерный размер словарного запаса упомянутого выше Шекспира, можно вычислить используя всего 128 байт памяти.

Привет, Хабр!

4 мая 2011 года крупнейшая здравоохранительная организация штата Калифорния «Heritage Provider Network» сообщила о проведении конкурса на лучший алгоритм прогнозирования, благодаря которому станет возможным сократить расходы на здравоохранение.

Конкурс стартовал ещё 4 апреля 2011 года в 19:00 по Гринвичу и будет длиться почти 2 года — до 3 апреля 2013 года.

Главный приз конкурса, а именно 3 000 000 $, получит тот, кто разработает алгоритм, позволяющий предсказать с наибольшей достоверностью на основе данных за предыдущие годы, сколько дней в этом году пациенты проведут в больнице.

В качестве исходных данных предоставляются анонимные выборки аналогичных данных за минувшие 3 года.

Если вы пишете программы для кофемолок (холодильников, ZX Spectrum, телевизоров, встроенных систем, старых компьютеров — нужное подчеркнуть), и хотите использовать при этом красивые шрифты, не спешите сохранять буквы в растровый формат. Потому что сейчас я расскажу, как сделать растеризатор векторных шрифтов размером в пару килобайт, не уступающий по качеству FreeType 2 с выключенным хинтингом.

Статья будет интересна и тем, кто просто хочет узнать, как работают библиотеки-растеризаторы.

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2^k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n²)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.

Университет Сан-Франциско создал с использованием HTML5 коллекцию визуализаций различных алгоритмов и структур данных. Посмотреть и потыкать кнопки можно вот тут.
Список визуализированных алгоритмов и структур данных со ссылками под катом.

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



Под катом есть еще видео

Редакционное расстояние, или расстояние Левенштейна — метрика, позволяющая определить «схожесть» двух строк — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. В статье излагается метод вычисления редакционного расстояния при использовании небольшого объема памяти, без существенной потери скорости. Данный подход может быть применен для больших строк (порядка 10⁵ символов, т.е. фактически для текстов) при получении не только оценки «схожести», но и последовательности изменений для перевода одной строки в другую.

Хотя сам Зденек Катал был против, но исходные коды его алгоритма отслеживания объектов в видеопотоке Tracking-Learning-Detection (aka Predator) всё-таки попали в открытый доступ. Судя по всему, они были какое-то время выложены на сайте автора и кто-то успел сделать копию. А поскольку код публиковался под лицензией GPL 2.0, то не осталось никаких препятствий для его дальнейшего распространения.

Проект TLD на github: 1, 2, 3, 4, 5

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

Сам трекинг осуществляется методом Лукаса-Канаде и с помощью OpenCV.

Чешский студент из британского университета Суррея Зденек Катал (Zdenek Kalal) в рамках практической части кандидатской диссертации разработал алгоритм Tracking-Learning-Detection (aka Predator) для отслеживания объектов в видеопотоке с самообучением (точность распознавания улучшается с каждым фреймом).

Демо проекта

Исходные коды на github: 1, 2, 3, 4, 5

Иногда полезно представить граф в графической форме, так чтобы была видна структура. Можно привести десятки примеров, где это может пригодиться: визуализация иерархии классов и пакетов исходного кода какой-нибудь программы, визуализация социального графа (тот же Twitter или Facebook) или графа цитирования (какие публикации на кого ссылаются) и т.д. Но вот незадача: количество ребер в графе зачастую настолько велико, что нарисованный граф просто невозможно разобрать. Взгляните на эту картинку:



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

Введение

Добрый день.
Не нашел простого и внятного описания данного алгоритма на русском языке. Решил восполнить сей пробел. Прежде всего что это такое? LR(0)-анализатор в первую очередь это синтаксический анализатор. Цель синтаксического анализатора обработать входной поток лексем(базовые элементы языка, которые производит лексический анализатор на основе входного потока символов, примеры лексем — число, запятая, символ) и сопоставить его с описанием языка заданного в определенном формате. Сопоставление заключается в построении определенной структуры данных, чаще всего — дерева. Дальше эта структура пойдет на следующий этап — семантический анализ, где уже компилятор пытается понять смысл, заключенный в дереве.

Существует 2 класса синтаксических анализаторов — восходящие анализаторы и нисходящие. Первые строят дерево начиная с листьев, которые являются входными лексемами, вторые соответственно наоборот начинают с корня дерева. Собственно LR и значит то, что анализатор будет читать поток слева направо (L — 'Left') и строить дерево снизу вверх (пусть не смущает буква R, которая значит Right, объяснения даны чуть ниже). Индекс 0 обозначает то что мы не предпросматриваем следующие лексемы, а работаем только с текущей. Какие же плюсы даёт нам выбор этого типа анализаторов?

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

Есть и недостатки:

• Относительная сложность построения.
• Можно вогнать анализатор в ступор неоднозначностью описания языка.