Алгоритмы *

Топологическая сортировка (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;
}

Тернарный (или троичный) поиск — это алгоритм поиска минимума (или максимума) выпуклой функции на отрезке. Можно искать минимум (максимум) функции от вещественного аргумента, можно минимум (максимум) на массиве. Будем, для определённости, искать минимум функции f(x).

Он многим знаком, а для тех, кто не знает, расскажу вкратце.

Тернарный поиск заключается в следующем. Пусть есть рекурсивная функция search(L, R), которая по двум концам отрезка L, R определяет минимум на орезке [L, R]. Если R — L < eps, то мы уже вычислили точку, где достигается минимум, с точностью eps. Иначе, разделим отрезок [L,R] на три равных по длине отрезка [L, A], [A, B] и [B, R]. Сравним значение в точках А и В. Вспомнив, что функция f выпуклая, можно сделать вывод, что если f(A) > f(B), то минимум лежит на отрезке [A,R]. Иначе — на отрезке [L, B]. В соответсвии с этим, можно рекурсивно запуститься от одного из отрезков [L, B] или [A, R]. Каждый раз длина области поиска уменьшается в полтора раза, значит, минимум на отрезке длины X с точностью eps будет найден за время O(log(X/eps)).

А здесь я хочу рассказать о квадрарном (или четверичном) поиске.

В обсуждениях статьи Только 10% программистов способны написать двоичный поиск так никто и не написал, как же правильно подойти к решению этой задачи.
Если мы не хотим использовать циклический метод «гадание, затем тестирование, затем исправление ошибок», то без инварианта цикла здесь не обойтись.
Инвариант цикла – это соотношение, которое истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла. Все это описано у Дейкстры в книге «Дисциплина программирования», и детально разжевано у Гриса в книге «Наука программирования». Тем не менее, по моим наблюдениям, на практике этот метод практически НИКТО не использует, считая, что все это к реальности не имеет никакого отношения. Это большая ошибка.

Дональд Кнут (известный тем, что его книги никто не читает) пишет, что хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск без багов был опубликован только в 1962.

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

С массивами так: есть упорядоченный массив, берем число из середины массива, сравниваем с искомым. Если оно оказалось больше, значит искомое число в первой половине массива, если меньше — во второй. Продолжаем делить оставшуюся половину, когда находим нужное число возвращаем его индекс, если не находим возвращаем null.

Наверняка все, кто читает этот пост не раз использовали, или хотя бы слышали о решете Эратосфена — методе отыскания простых чисел. Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA. Есть довольно много подходов к данной задаче, но в этой статье я остановлюсь на некоторых модификациях самого простого из них — решета Эратосфена.

Краткая предыстория

Вообще, все началось давно. Настолько давно, что вряд ли остались свидетели holy wars тех дней, когда решалось — сколько же бит должно быть в байте.

Это сейчас нам кажется само собой разумеющимся, что 1 байт = 8 бит, что в байте можно закодировать 256 различных значений. Но когда-то было совсем не так. История помнит и семибитные кодировки, и шестибитные, и даже более экзотические системы (например — ЭВМ «Сетунь», которая использовала троичную логику, то есть один троичный бит — трит мог иметь три, а не два значения, для нее было справедливо соотношение 1 трайт = 6 тритам). Но если оставить в стороне всякую экзотику, то мэйнстримом все-таки были кодировки, в которых 6, 7 или 8 бит в байте.

Шестибитная кодировка (например — BCD) позволяла закодировать в одном байте 64 различных значения, что, как казалось, было вполне достаточно для кодирования алфавитно-цифровых символов, а «лишний» седьмой бит расширял кодировку уже до 128 символов.

Однако скоро восьмибитный байт стал общепринятым.