Алгоритмы *

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

Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

Разница в том, что контейнеры в STL реализованы на красно-чёрных деревьях, а аналогичные контейнеры cpp-btree — на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера).

B-деревья известны как инструмент для работы с дисковой памятью: базами данных и файловой системой. Но те же свойства, которые дают выигрыш там, позволяют эффективнее использовать и оперативную память. Каждый узел красно-чёрного дерева содержит один элемент, требует три указателя плюс по биту информации на элемент для сбалансированности. Для сравнения, контейнеры на B-деревьях хранят несколько элементов на узел, поэтому уменьшают оверхед указателей и экономят значительное количество памяти.

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

На хабре уже много-много-много раз писали про игру «Жизнь». Совсем недавно была удивительная статья Жизнь на плоскости Лобачевского. Но игра «Жизнь» является частным случаем т. н. клеточных автоматов. Существует много других клеточных автоматов совсем не похожих на игру «Жизнь», но тем не менее очень интересных. Про некоторые из них и хочется рассказать здесь.

Начнём с того, что рассмотрим ряд клеток, в которых, кроме одной, находятся нули:

... 0  1  0  0  0  0  0  0 ...

Рассмотри следующее правило, заменяем число в клетке на сумму этого числа и соседа слева. Получим следующую серию состояний:

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  2  1  0  0  0  0 ...
... 0  1  3  3  1  0  0  0 ...
... 0  1  4  6  4  1  0  0 ...
... 0  1  5 10 10  5  1  0 ...
... 0  1  6 15 20 15  6  1 ...

Не сложно увидеть, что это — треугольник Паскаля. А теперь вместо обычного сложения будем использовать сложение по модулю два. Известно (и даже недавно рассказывалось в хабрастатье Треугольник Серпинского и треугольник Паскаля), что получится дискретный аналог треугольника Серпинского:

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  0  1  0  0  0  0 ...
... 0  1  1  1  1  0  0  0 ...
... 0  1  0  0  0  1  0  0 ...
... 0  1  1  0  0  1  1  0 ...
... 0  1  0  1  0  1  0  1 ...

Интересно? Читаем дальше!

Коллеги, нужен ваш совет. Мы сейчас занимаемся переводом отличного учебника Dasgupta, Papadimitriou, Vazirani. Algorithms. McGraw-Hill. 2006 на русский язык. Так вот, хочется услышать ваше мнение на тему того, как в русских учебниках по алгоритмам должен быть оформлен псевдокод: выделять ключевые слова? переводить ключевые слова на русский? помечать конец блока ключевым словом? (Опрос — снизу). Несколько потенциальных способов оформления приведены ниже. Буду благодарен за любые советы/замечания.

Меня зовут Василий, уже более трех месяцев, как я работаю математиком в компании Surfingbird.

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

Постановка задачи рекомендательной системы уже описана Сергеем Николенко в статье Рекомендательные системы: постановка задачи.
В основе большинства рекомендательных систем лежат так называемые методы коллаборативной фильтрации. Наша рекомендательная система не исключение. Все алгоритмы коллаборативной фильтрации опираются только на информацию о рейтингах, проставляемых пользователями, и не анализируют контент ресурсов (в нашем случае веб-страниц). Поэтому, эти алгоритмы работают при достаточно большом количестве рейтингов, как правило это 10-20 рейтингов. Задача выдачи релевантных рекомендаций для новых пользователей и для новых сайтов называется проблемой холодного старта.

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

Это первый пост из блога Surfingbird, который я выношу в общие хабы алгоритмов и искусственного интеллекта; честно говоря, раньше просто не догадался. Если интересно, заходите к нам, чтобы прочесть предыдущие тексты, – я не знаю, что произойдёт, если просто добавить новые хабы к постам несколькомесячной давности.

Краткое содержание предыдущих серий о рекомендательных системах:

• рекомендательные системы: постановка задачи;
• user-based и item-based коллаборативная фильтрация;
• SVD, часть I;
• SVD и базовые предикторы;
• SVD на Perl;
• оверфиттинг и регуляризация;
• теорема Байеса и наивный Байес;
• LDA (Latent Dirichlet allocation, тематическое моделирование).

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

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

Идея распознавать людей по радужной оболочке появилась в далёком 1987 у доктора Джона Доугмана и была запатентована в 1989. Примерно тогда же появился прототип. На тот момент это была вершина технологии. Пару лет до первой коммерческой цифровой камеры + алгоритм обработки изображения на компьютерах уровня i386/i486. До сих пор я не представляю, как можно получать на таком оборудовании стабильный результат.
Задачка о которой я хочу рассказать появилась на свет где-то в 2006-2009 годах. Процессоры к этому времени несколько ускорились, появились хорошие камеры, патент 1989 года истёк и системы распознавания по глазам теперь получил право делать каждый. Люди, которые решили сделать клон системы захотели использовать современные технологии и улучшить алгоритм. Самое первое, что бросалось в глаза — старый алгоритм сравнения глаз использовал изображение глаза в близком ИК диапазоне. То, что глаза бывают цветными не учитывалось.

Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.

Давайте рассмотрим среду: в ней могут существовать частицы «еды» и агенты. С помощью сенсоров агенты могут получать информацию о среде. Если агент находится достаточно близко к частице пищи, то она считается «съеденной» и исчезает, а в тот же самый момент в случайном месте среды появляется новая частица еды. Задача группы агентов — собирать пищу. Эффективность рассматривается исходя из суммарного количества собранной пищи.

Давайте смоделируем конкурентную среду для автоматического поиска оптимального поведения группы агентов. Алгоритм поведения агентов будем конструировать в виде нейронной сети.

Не так давно я считал. что нет оправдания использованию java.util.LinkedList в качестве реализации java.util.List. Но что-то заставило меня его поискать. Давайте разберемся. Любой грамотный Java-специалист знает, что java.util.ArrayList нужно использовать тогда, когда нам нужен быстрый доступ по индексу, а java.util.LinkedList, если нам нужно вставлять или удалять элементы в середине списка. Не многие из них догадываются, что если мы будем вставлять или удалять элементы в середине списка методами remove(int index) и add(int index, E element), то на поиск нужного элемента будет затрачено время в среднем пропорциональное размеру списка O(N). Так когда же возникает выгода от использования java.util.LinkedList?

На днях прочитал пост об автоматизированном формирование футбольных чемпионатов и решил поделится своим решением данной задачи, которое использовал для небольшой игры. Реализация жеребьевки сделана не стандартным подходом, при помощи хранимых процедур MS SQL Server.

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

Таблица игр чемпионата

Основная хранимая процедура — это процедура формирования игр чемпионата между командами. При формировании я придерживался основных правил турнира:

• Количество команд участвующих в турнире должно быть четным;
• Каждая команда должна сыграть с другой 2 раза — на своем стадионе и на стадионе соперников;
• В одном туре одна и та же команда может играть лишь один раз;
• За победу в матче команда получает — 2 очка, за ничью — 1 очко, а за проигрыш соответственно — 0.

Давайте поэтапно рассмотрим алгоритм формирования таблицы игр. Логику буду стараться описывать детально, не скучно и с демонстрацией схем. Как пример давайте возьмем чемпионат в котором участвуют 4 команды, хотя алгоритм может работать с любым четным количеством команд. Условно давайте обозначим наши команды под номерами 1, 2, 3 и 4, которые в моей реализации являются их прямыми ID.

Вчера на американских биржах произошла маленькая, но очень интересная аномалия, о которой оперативно сообщила аналитическая компания Nanex Research.

31 января 2013 года примерно за 400 миллисекунд до официальной публикации недельногого отчёта по запасам природного газа резко увеличилась торговая активность по фьючерсам на природный газ и паям индексных фондов, таких как UGZ, UNG и BOIL.

Отчёт опубликован в 10:30:00. На графике вверху показана активность на торгах индексным фондом UGZ в промежутке с 10:29:59 до 10:30:02, с официальными метками времени транзакций от разных бирж.

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.

Известно, что набором правильных шестиугольников можно описать практически любой контур и создать тем самым фигуру произвольной формы. Такой принцип можно применить при построении топографических карт на подобие тому, как это реализовано в Sid Meier’s Civilization V, или же использовать в системах, основой которых являются те самые шестиугольники (сотовые операторы). Для придания информативности, каждой ячейке карты можно присваивать контрольное значение, будь то уровень сигнала сети, высота, глубина, наличие определенного вида ресурсов и т.п., характеризующее участок карты — соты. Это может выглядеть примерно так. Однако для глаз данное представление является не вполне презентабельным, и его можно визуализировать, добавив каждой ячейке соответствующий цвет.

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

1. Имеется N команд – участников.
2. Каждая команда за первый круг сыграет N-1 матчей.
3. Команда N ни в каком из туров не может сыграть сама с собой.
4. В каждом туре соперники образуют уникальные, не повторяющиеся ранее пары.
5. Если в каком-то из туров команда N играет с командой M, то соответственно в этом же туре команда M играет с командой N.

Сопоставив процесс формирования случайных пар соперников процедуре заполнения двумерного массива DrawTable[i, j] случайными величинами, получил следующее (язык C#, .Net 4.0):

Вдохновленный статьей «Решение MintEye CAPTCHA в 23 строки кода», а также горя желанием глубже разобраться в методах выделения краев изображения, таких как оператор Собеля и оператор Кэнни, я решил попытаться самостоятельно повторить описанный в статье алгоритм.

Быстренько набросав скрипт, загружающий с сайта MintEye набор «подопытных» изображений, я было приготовился открыть любимую IDE, чтобы приступить к экспериментам с «высокими технологиями», но заглянув в каталог со скачанными картинками, обнаружил одну очень любопытную закономерность.

Международная космическая станция

НАСА объявило конкурс на оптимизацию алгоритмов движения солнечных панелей для Международной космической станции. Конкурс ISS Longeron Challenge проводится совместно с порталом TopCoder.

После публикации на Хабре своей первой статьи, об одном из способов организации иерархии в реляционной БД, у меня осталось чувство не доведенного до конца дела.
Судя по комментариям, кто-то принимал предложенный метод за другой, спрашивали чем не устраивает “django-mttp”, рассказывали о поддержке деревьев в PostgreSQL…
Спасибо всем отписавшимся, но из-за сумбурного изложения в самой статье, думаю, что я не сумел донести до читателя то, что хотел. А “если я чего решил, то выпью обязательно”(с)

Поэтому, я решился на еще одну попытку изложения интересующего меня подхода. А именно — хранение иерархии в числовом коде, вычисляемом на основании данных о размерности дерева. То есть, заранее определены максимальные количество Уровней и количество Детей у каждого Родителя (возможные диапазоны достаточно велики, поэтому, заранее пугаться этого не стоит). При таких вводных, код, каждого иерархического элемента, будет являться и путем до него, и включать диапазон всех Детей. А это сулит скорость, и много еще чего…
Далее — с картинками и таблицами, без привязки к какой-либо БД (ибо это не важно).