Алгоритмы *

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Тема сегодняшней лекции

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

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

Ищем индекс

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

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

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

Введение

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

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

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

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

Дело было на третьем курсе, появился у нас предмет ИИС (интеллектуальные информационные системы). Так как я давно интересовался распознаванием образов, удалось выпросить тему «распознавание рукописных цифр». Я решил не возиться с нейронными сетями и придумать что-то свое, простое, но достаточно эффективное.

Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P ≠ NP.

Само доказательство на ~100 страницах.

Можно почитать более или менее адекватный комментарий на ycombinator.

Добавить нечего, читаем и/или ждем мнений специалистов в этой области.

P.S. На всякий случай, ссылка о том, что такое NP и P. (спасибо, SMiX)

В наше время все большую популярность набирают генетические алгоритмы. Их используют для решения самых разнообразных задач. Где-то они работают эффективнее других, где-то программист просто решил выпендриться…

Так что же такое генетический алгоритм? Если верить википедии, то генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

Как это все выглядит вы можете увидеть на следующем рисунке:

Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач.
Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.
Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети.

↑ Пример ориентированного неотсортированного графа, к которому применима топологическая сортировка

Два плюс два, умножить на два?

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

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

Те кто играли в бета-версию Starcraft 2 наверняка заметили, как изменился алгоритм поиска путей движения юнитов. Многое из сказанного в статье основано на личных оценках. Я не программировал ни BroodWar, ни StarCraft 2 и некоторые выводы будут основаны на моих догадках. Также не верьте на 100% моим словам, постарайтесь сделать собственные заключения. В статье будут как факты, так и домыслы.

Перевод статьи The Mechanics of Starcraft 2 Pathfinding

Итак, мы постепенно выходим на финишную прямую сборки Кубика Рубика 5х5х5! Осталось дособирать рёбра куба и центральные квадраты. Кроме того, есть программа-эмулятор кубика, так что даже если куба нет, можно попробовать собрать его на ПК.
Ссылка на первую часть

В далеком 2008 году в мои руки попал кубик рубика нестандартных размеров. Как собирать такое чудо, я тогда и понятия не имел. Поначалу мы с друзьями собирали его частично, не имея понятий об алгоритме сборки, но потом захотелось всё-таки научиться собирать его полностью. Через гугл я нашёл некоторое подобие алгоритма сборки, но он к сожалению был неполный и грешил неточностями. Некоторое время анализировав нагугленное и алгоритм классической сборки кубика 3х3х3 я осознал полный алгоритм сборки куба не только 5х5х5, но и 4х4х4 (хотя у меня под рукой не было такого куба, я написал программу для моделирования такого кубика в 3D и проверил алгоритм). Всем, кто хотел бы научиться собирать такой кубик — добро пожаловать под кат.

Роберто Иерусалимши рассказывает, как эффективно соединять немодифицируемые строки.
Несмотря на то, что код написан на Lua, алгоритм подойдёт и для других языков, в которых строки нельзя изменять.

Постановка вопроса: как найти декартово произведение произвольного количества последовательностей с помощью LINQ?

Для начала, давайте убедимся, что мы знаем, о чем идет речь. Я буду обозначать последовательности как упорядоченные множества: {a, b, c, d...} Декартово произведение двух последовательностей S1 и S2 есть последовательность всех возможных упорядоченных пар таких, что их первый элемент из S1, а второй — из S2. Так, к примеру, если у вас есть две последовательности {a, b} и {x, y, z}, то их декартово произведение выглядит как {{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}}.

Для упрощения, предположим, что S1 и S2 состоят из элементов одного типа. Разумеется, мы можем определить декартово произведение последовательности строк с последовательностью чисел как последовательность кортежей (string, int), но впоследствии это окажется тяжело обобщать, потому что система типов C#, в частности, не лучшим образом работает с кортежами произвольной длины.

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

Проблема

Основная задача, которую будем решать в рамках данного топика — подготовка сканов и фотографий письменных источников (книг, лекций и т.п.) для их печати, компактного хранения, упаковки в djvu и т.п.
Photoshop и FineReader рассматривать не будем. Хотя они и предоставляют ряд полезных инструментов, но стоят денег, вообще говоря.
При наличии сканера обычно всё просто: получаются изображения достаточно хорошего качества, чтобы можно было обойтись минимальной обработкой.
С фотографиями интереснее: добавляются проблемы с освещением и геометрические искажения. Увы, исправление геометрических искажений автоматизировать, как минимум, сложно. А вот с освещением и фоном вполне можно побороться. Чем и займёмся.

Продолжение статьи про проект Stanford University (ныне Cornell University) "Make3D", который поставил перед собой пока еще не ставшую типичной задачу восстановления трехмерной модели сцены всего из одного фотоснимка.

Публикация состоит из: Часть 1, Часть 2
Публикуется для утоления любопытства, с целью разоблачения магии дать понять как это устроено.

Проект из Stanford University (ныне Cornell University) "Make3D", примечателен тем, что поставил перед собой пока еще не ставшую типичной задачу восстановления трехмерной модели сцены всего из одного фотоснимка. До сих пор, чтобы добиться подобного результата, разработчики восстанавливали трехмерную информацию, комбинируя несколько (два и более) снимков одного и того же объекта. В данном же случае было продемонстрировано, что значительный объем информации содержится в монокулярных признаках (monocular cues) самого изображения, которые до этого зачастую игнорировались. В практической реализации уже удалось добиться удовлетворительных результатов более чем на 60% произвольных фотоснимков, предоставленных и оцененных сторонними пользователями системы при проведении ее испытаний.

Публикация состоит из: Часть 1, Часть 2
Публикуется для утоления любопытства, с целью разоблачения магии дать понять как это устроено.

Достопочтенный SergeyACTIVITI в своём посте поведал нам про такую полезную вещь, как задача о рюкзаке, решение которой с успехом реализовано в решателях COIN-OR или GLPK. А что же внутри?

Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой из которых есть объём v[i] и стоимость c[i], и каждую из которых можно брать сколько угодно раз. При этом все объёмы и все стоимости будут положительными и целыми. Как же работает алгоритм?

В прошлый раз мы говорили о том, что число бинарных деревьев с n вершинами равно C(n), где C(n) – это n-ое число Каталана. Я заинтересовался чего больше: произвольных деревьев из n вершин или бинарных деревьев из n вершин. Ответ может вас удивить, он не лежит на поверхности.


Распространённый ответ на этот вопрос я получу сразу: «Разумеется, произвольных деревьев больше, т.к. бинарное дерево – это частный случай произвольного дерева». Можете ли вы сказать, почему это неверно? Бинарных деревьев больше, чем произвольных деревьев! Существует два бинарных дерева из двух вершин: одно с левым потомком ребёнком корня, а другое – с правым потомком корня. Но есть только одно произвольное дерево с двумя вершинами, в нём нет разницы между «левым» и «правым» потомком.

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

Здесь я хочу рассказать и обсудить несколько алгоритмов для нахождения старшего единичного бита числа.

На всякий случай, поясню: старшим битом называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа. Чтобы избежать многих случаев, будем здесь считать, что мы имеем дело с натуральным числом в пределах от 1 до 2^31 — 1 включительно. Кроме того, чтобы не слишком углубляться в теорию вероятности, будем считать, что число, в котором требуется определить старший бит, с одинаковой вероятностью будет любым из возможных чисел.

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

int bit1(int x) {
   int t = 1 << 30;
   while (x < t) t >>= 1;
   return t;
}