Алгоритмы *

Пару лет назад я собирался написать интерпретатор Пролога на Delphi. Я решил начать с создания парсера. Написание анализатора специально под Пролог показалось мне жутко сложным, казалось, легче будет написать универсальный анализатор и синтаксис Пролога к нему. Ну, так как это все безумно сложно и долго, я забросил эту задумку. А вот парсер остался. Здесь я расскажу про его написание.

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

Кандидат наук из Федеральной политехнической школы Лозанны Басилио Норис создал замечательную программу, которая великолепно подходит для демонстрации некоторых задач, которые решают алгоритмы машинного обучения (классификация, кластеризация, регрессия — различными методами). В одной программе собраны библиотеки, алгоритмы и фрагменты кода, которые удалось найти. В отличие от 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)

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

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

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

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

Введение.

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

Рассмотрим лучший известный приближенный алгоритм решения задачи о вершинном покрытии.

В статье расскажу как можно очень быстро перечислить связные объекты на бинарном растре, значительно быстрее, чем я рассказывал в предыдущей статье. Казалось бы, куда такие скорости; теперь мы будем «расправляться» с картинками 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 с выключенным хинтингом.

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

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

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

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

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

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

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

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

Первого мая в Computer Science клубе при ПОМИ РАН состоятся три интересные лекции. Лекции можно послушать вживую в ПОМИ РАН (Санкт-Петербург, наб. р. Фонтанки, д. 27; вход свободный, никакой предварительной регистрации не требуется) или же по трансляции, организуемой проектом Лекториум.

В 11:15 Михаил Рыбалкин (ПОМИ РАН и GGA Software Services) расскажет о подструктурном поиске химических соединений в базах даных. В 13:00 Игорь Куралёнок (СПбГУ и Яндекс) сделает доклад о практическом применении методов машинного обучения. Наконец, в 14:35 Максим Алексеев (University of South Carolina) расскажет о комбинаторных задачах и алгоритмах сравнительного анализа геномов.

Если на вас ссылается кто-то авторитетный, это поднимает ваш статус больше, чем ссылки («голоса») от многих малоавторитетных источников — такова была первоначальная идея ранжирования сайтов Гуглом. Она нашла свое очевидное продолжение в social network analysis, где формула для PageRank является разновидностью центральностей, т.е. определением того, какой из узлов социального графа является более «центральным» и по какому признаку. Я не специалист в данной тематике; из беглого осмотра по диагонали мне показалось, что social network analysis в интернете применяется в основном для нужд social media marketing, где ранжирование людей не является основной целью. Скорее, цель smm — эффективней продвигать бренды, увеличивать продажи и т. п. Однако ранжирование людей может быть самостоятельной интересной целью. Вот здесь я краткотезисно перечислил эти интересы.

Ранее мы рассматривали эти вопросы использования расширенной реальности для создания оригами:

• Интерфейсы → Оригами и расширенная реальность
• Алгоритмы → Оригами и расширенная реальность (продолжение)

Эта статья посвящена техническим деталям применения баркодов для генерации подсказок в расширенной реальности.