Алгоритмы *

Число Бейкона

Немного истории, Кевин Бейкон американский актёр сыгравший во множествах фильмам, в 1994 отметил что актёры, с которыми он снимался, работали со всеми голливудскими (и не только) актёрами. Общественность тут же отреагировала и создала игру “назвать имя актёра и связать его с Кевином Бейконом”. Корпорация добра даже встроила игру в свой поисковик, например Число Бейкона для актёра Джона Траволты равно 2 (Джон снимался с Оливией Ньютон-Джон в фильме Бриолин, она же, в свою очередь, сыграла с Кевином Бейконом в фильме “У нее будет ребенок”).

А теперь давайте поговорим о том, как эту игру можно представить, и как можно вычислить число Бейкона при помощи графа.

Гипотетически предположим, что вы сумели доказать равенство P=NP. Что же теперь нужно сделать для обретения господства над целым миром?

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

        Принцип работы этих алгоритмов похож: мы анализируем реакцию пользователей (feedback) на предыдущие записи и пытаемся прогнозировать его реакцию на текущие события. Если реакция «положительная», событие попадает в ленту, если «отрицательная» — не попадает.

Один хороший человек захотел сделать электронную книгу под iOS, коллекцию афоризмов. Фразы вылетают случайно, данные предоставлены в формате комма сепарейтед валью. С флешкой и устным ТЗ он пришел к другу-программисту. Программист оценил примерный объем работы

• Конвертируем данные в sqlite;
• Заводим три UIView (левый, правый и центральный);
• В каждый UIView добавляем UITextView и UILabel;
• Обрабатываем нажатие touchesBegin для листания афоризмов вправо-влево;
• Добавляем кнопку — показать случайный афоризм.
• Добавляем закладки.
• Получаем 1000 долларов США

Работы на 2 дня, программист согласился.
Однако в ТЗ было еще одно условие — при случайном выборе афоризма по экрану должен кататься игральный кубик. Самый обыкновенный, из шести граней.

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

Введение

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

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

Отметим, что приводимые подходы применимы не только к текстам, а вообще к любым объектам, которые можно представить в виде символьных последовательностей, например, какие-нибудь макромолекулы (ДНК, РНК, протеины) из генетики. Всего мы рассмотрим 4 метода:

1. Признаковое описание.
2. Попарное наложение (выравнивание) текстов.
3. Формирование профиля и скрытой марковской модели.
4. Представление фрагментами.

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

И снова здравствуйте! Сегодня я продолжаю серию статей в блоге Surfingbird, посвящённую разным методам рекомендаций, а также иногда и просто разного рода вероятностным моделям. Давным-давно, кажется, в прошлую пятницу летом прошлого года, я написал небольшой цикл о графических вероятностных моделях: первая часть вводила основы графических вероятностных моделей, во второй части было несколько примеров, часть 3 рассказывала об алгоритме передачи сообщений, а в четвёртой части мы кратко поговорили о вариационных приближениях. Цикл заканчивался обещанием поговорить о сэмплировании — ну что ж, не прошло и года. Вообще говоря, в этом мини-цикле я поведу речь более предметно о модели LDA и о том, как она помогает нам делать рекомендации текстового контента. Но сегодня начну с того, что выполню давнее обещание и расскажу о сэмплировании в вероятностных моделях — одном из основных методов приближённого вывода.

Введение

Друзья, рассмотрим нынче же задачу линейной регрессии в присутствии выбросового (некоррелированного с сигналом) шума. Эта задача часто возникает при обработке изображений (напр., при цветовой сегментации [1]), в том числе — акустических [2]. В случаях, когда координаты случайных величин можно грубо дискретизовать, а размерность задачи низка (2-3), кроме стандартных методов робастной регрессии можно воспользоваться быстрым преобразованием Хафа (БПХ) [3]. Попробуем сравнить этот последний метод по точности и устойчивости с «классическими».

Использование БПХ для линейной регрессии

Задача линейной регрессии на плоскости состоит в восстановлении линейной зависимости между двумя переменными, заданными в виде множества пар (x, y). Задавшись некоторым уровнем дискретизации координат, можно отобразить это множество на однобитном или целочисленном изображении (в первом случае мы отмечаем только факт наличия в исходных данных точки с примерно такими координатами, во втором — еще и их число). Фактически, речь идет о двумерной гистограмме исходных данных. Таким образом, неформально задача может быть сведена к поиску на изображении прямой, которая наилучшим образом описывает изображенное распределение точек.В обработке изображений в подобных случаях используется преобразование Хафа.

Преобразование Хафа является дискретным аналогом преобразования Радона и ставит в соответствие каждой прямой на изображении сумму яркостей пикселей вдоль нее (то есть одновременно вычисляет всевозможные суммы вдоль дискретных прямых). Можно ввести разумную дискретизацию прямых по сдвигам и наклонам так, чтобы параллельные дискретные прямые плотно упаковывали плоскость, а выходящие из одной точки на одном крае изображения прямые расходились по наклону на противоположном крае на целое число пикселей. Тогда таких дискретных прямых на квадрате n² будет примерно 4 * n². Для этой дискретизации существует алгоритм быстрого вычисления преобразования Хафа с ассимптотикой O(n² * log n). Этот алгоритм является близким аналогом алгоритма быстрого преобразования Фурье, хорошо параллелизуется и не требует никаких операций, кроме сложения. В работе [3] можно прочитать об этом чуть больше, кроме того, там объясняется, почему преобразование Хафа от сглаженного гауссовским фильтром изображения вообще можно применять в задаче линейной регресии. Здесь же мы продемонстрируем устойчивость этого метода.

Привет, Хабр! Мой предыдущий пост, посвященный программированию графики, был благодушно воспринят сообществом, и я отважился ещё на один. Сегодня я расскажу об алгоритме рендеринга теней Parallel-Split Shadow Mapping (PSSM), с которым я впервые столкнулся, когда возникла рабочая необходимость отображать тени на большом расстоянии от игрока. Тогда я был ограничен набором возможностей Direct3D 10, сейчас я реализовал алгоритм на Direct3D 11 и OpenGL 4.3. Подробнее алгоритм PSSM описывается в GPU Gems 3 как с математической точки зрения, так и с точки зрения реализации на Direct3D 9 и 10. За подробностями прошу под кат.

Введение

Всем доброго времени суток!

Уверен, что многие из вас уже интересовались методами разделения секретной визуальной информации. Если это так, то вы наверняка знакомы с работой Мони Наора и Ади Шамира, посвященной визуальной криптографии, а также с постом от 19 апреля 2013 года Схема разделения секретной визуальной информации . Я изучил предложенный в этой статье алгоритм и код функции, написанный на MATLAB, и пришел к выводу, что он написан не рационально: его можно записать значительно короче, а также повысить эффективность его работы. Как это сделать, я опишу ниже. Также рассмотрю как организовать.

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

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

Шифрование данных с помощью кватернионов выполнялось на FPGA DE5-NET, XeonPhi 7120P, GPU Tesla k20.
У всех троих приблизительно одинаковая пиковая производительность, но имеется разница в энергопотреблении.

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

Для выяснения криптостойкости алгоритма QES прошу использовать поисковики для подробного описания алгоритма, одним из авторов которого является Nagase T., а одна из статей, например, Secure signals transmission based on quaternion encryption scheme.

Каким же образом можно зашифровать и расшифровать данные с помощью кватернионов? Довольно просто!
Для начала возьмем кватернион: q = w + x*i + y*j + z*k и составим на его основе матрицу поворота, которую назовем, например P(q).
Прим. картинка ниже из википедии и матрица там названа Q.

Столкнулся с проблемой реализации древовидных комментариев на одном проекте, в этой заметке выкладываю своё решение.

Описание задачи

• Хранение иерархических данных (древовидных комментариев) в реляционной БД MySQL
• Простое добавление узлов/ветвей
• Выборка всего дерева одним запросом, с отсортированными в нужном порядке ветвями

В принципе, задача классическая, и сначала я её решил с помощью объединения Adjacency List и Materialized Path. Другими словами, в таблице добавлены колонки

id INT(11)
parentid INT(11)
mpath VARCHAR(255)

В mpath хранился полный путь ветки в дереве, например /1/3/4/5/8/9, где через знак "/" перечислялись ID комментария.

При таком подходе очень легко добавлять новые комментарии практически любого уровня вложенности. Выборка при этом производилась запросом:

SELECT *
FROM messages
WHERE postid=$postid
ORDER BY mpath ASC

Проблема возникла при росте числа комментариев.

Комбинаторика в старших классах школы, как правило, ограничивается текстовыми задачами, в которых нужно применить одну из трёх известных формул — для числа сочетаний, перестановок или размещений. В институтских курсах по дискретной математике рассказывают и о более сложных комбинаторных объектах — скобочных последовательностях, деревьях, графах… При этом, как правило, ставят задачу вычислить количество объектов данного типа для некоторого параметра n, например количество деревьев на n вершинах. Узнав количество объектов для фиксированного n, можно задаться и более сложным вопросом: как все эти объекты за разумное время предъявить? Алгоритмы, решающие подобного рода задачи, называются алгоритмами комбинаторной генерации. Таким алгоритмам, например, посвящена первая глава четвёртого тома «Искусства программирования» Дональда Кнута. Кнут очень подробно рассматривает алгоритмы генерации всех кортежей, разбиений числа, деревьев и других структур. Придумать какой-нибудь алгоритм, работающий умеренно быстро, для каждой из этих задач несложно, но с дальнейшей оптимизацией могут возникнуть серьёзные проблемы.

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



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

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

Друзья, всем привет!

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

Столкнулся тут с задачкой, стали интересны пути решения, отличные от моего, и, желательно, на другом языке.

Условие достаточно простое. Есть случайное число и заданное количество игровых кубиков. Значение каждого кубика может быть от 1 до 6. Нужно разбить число таким образом, чтобы на выходе получился массив значений для каждого кубика. Причём при каждом вызове значения этих кубиков должны быть случайными.
Например:
Число 18 и 4 кубика. Ответ: [6,3,5,4];

Моё решение под катом и спойлером…

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

Несколько дней назад на хабре был топик, в котором сообщалось о том, российская компьютерная программа впервые в истории смогла пройти тест Тьюринга:

Программе, разработанной Владимиром Веселовым из России и украинцем Евгением Демченко удалось вчера убедить 33% судей в том, что она на самом деле — 13-летний одессит Евгений Густман, любитель конфет и гамбургеров и сын врача-гинеколога.

Понять то, что это блеф, не имеющий под собой никаких оснований, было достаточно просто.

Настало время подробно рассказать, как работает наша реализация алгоритма распознавания номеров: что оказалось удачным решением, что работало весьма скверно. И просто отчитаться перед Хабра-пользователями — ведь вы с помощью Android приложения Recognitor помогли нам набрать приличного размера базу снимков номеров, снятых совершенно непредвзято, без объяснения как снимать, а как нет. А база снимков при разработке алгоритмов распознавания самое важное!