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

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

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

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

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

Рассмотрим следующую ситуацию. Допустим вы хотите поехать за границу, но валюту вам не меняют — вы можете перевезти с собой лишь товары для реализации на свободном рынке «там». С собой в самолет разрешено взять не более 20 кг. Возникает вопрос – какие товары взять, чтобы перевезти максимальную ценность, учитывая ограничение по весу? Водку (17$ / 1,5 кг), большую матрешку (30$ / 2,5 кг), балалайки (75$ / 6 кг) или еще что-то и в каких количествах?

Нет, я не буду рассказывать с какими параметрами нужно генерировать радужные таблицы, или как придумывать «стойкие» пароли. Сама по себе тематика немного устарела и едва ли поможет в отвлеченных вопросах. Но, как оказалось, в основу «радужных таблиц» положен замечательный способ (я бы не стал называть его методом или алгоритмом) размена времени на память, то бишь «time-memory trade off». Это не первый (и, наверное, не последний) топик про предвычисления, но, надеюсь, он Вам понравится.

Читая в очередной раз Хабр, я заинтересовался статьей «Морской бой с искусственным интеллектом — по-честному» и программой «Интеллектуальный морской бой».
Попробовав сыграть с ней, я обнаружил, что стратегия программы пока оставляет желать лучшего, т.к. счет был 9:1 в мою пользу.
Я решил поделиться своими мыслями со всеми, и в частности с автором(michurin) программы, т.к. проект очень интересный.

Внимание!
После прочтения данной статьи исход игры «Морской бой» перестанет быть для вас случайностью.

Статья писалась простым языком без использования формул.
«Любая формула, включенная в книгу, уменьшает число ее покупателей вдвое» Стивен Хокинг.

Сегментация изображений и выделение границ объектов (edge detection) играют важную роль в системах Computer Vision и применяются для задач распознавания сцен и выделения (определения) объектов. По большому счету, это такой же инструмент, как, например, сортировка, предназначенный для решения более высокоуровневых задач. И поэтому понимание устройства данного класса алгоритмов не будет лишним при построении подобных систем с учетом предъявляемых требований (в плане качество/производительность) и специфики поставленных задач.

В данной статье кратко описан алгоритм «Efficient Graph-Based Image Segmentation» авторов Pedro F. Felzenszwalb (MIT) и Daniel P. Huttenlocher (Cornell University), опубликованный в 2004 году. Да, алгоритм относительно старенький, но, несмотря на это, он до сих пор остается весьма популярным, демонстрируя неплохие результаты в плане производительности.

Под катом – большая смесь картинок и текста, не требовательная к текущему уровню знаний тематики. Любопытство приветствуется.

Здравствуйте, на Хабре уже была статья Indalo, посвященная AdaBoost, точнее, некоторому его применению. Я же хочу более детально остановиться на самом алгоритме, заглянуть в его реализацию и продемонстрировать его работу на примере моей программы.

Итак, в чем же заключается суть методики Adaboost?

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

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

Продолжая статью “Использование Hadoop для решения реальных задач”, хочу напомнить, что в прошлой статье мы остановились на том, что посчитали такую характеристику как tf(t,d), и сказали, что в следующем посте мы будем считать idf(t) и завершим процесс вычисления значения TF-IDF для данного документа и термина. Поэтому предлагаю долго не откладывать и переходить к этой задаче.

Важно заметить, что idf(t) не зависит от документа, потому как считается на всем корпусе. Это нетрудно увидеть, посмотрев на формулу:



Вероятно, она нуждается в некоторых пояснениях. Итак, |D| это мощность корпуса документов — иными словами, просто количество документов. Мы знаем его, поэтому считать ничего не надо. Знаменатель же логарифма — это количество таких документов d которые содержат интересующий нас токен t_i.

Вчера я задал вопрос в своем ХабраБлоге — интересно ли людям узнать, что такое Hadoop с точки зрения его реального применения? Оказалось, интересно. Дело недолгое — статью я написал довольно быстро (по крайней мере, ее первую часть) — как минимум, потому, что уже давно знал, о чем собираюсь написать (потому как еще неплохо помню как я сам тыкался в поиске информации, когда начинал пользоваться Hadoop). В первой статье речь пойдет об основах — но совсем не о тех, про которые обычно рассказывают :-)

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

Что такое Hadoop?

Ну скажите, какой смысл об этом писать? Уже не раз это проговаривалось, неоднократно начинали писаться посты на тему Hadoop, HDFS и прочая. К сожалению, обычно все заканчивалось на довольно пространном введении и фразе “Продолжение следует”. Так вот: это — продолжение. Кому-то тема, затрагиваемая в этой статье может показаться совершенно тривиальной и неинтересной, однако же лиха беда начало — любые сложные задачи надо решать по частям. Это утверждение, в частности, мы и реализуем в ходе статьи. Сразу замечу, что я постараюсь избежать написания кода в рамках этой конкретной статьи — это может подождать, а понять принципы построения программ, работающих с Map/Reduce можно и “на кошках” (к тому же с текущей частотой кардинального изменения API Hadoop любой код становится obsolete примерно через месяц).

Когда я начинал разбираться с Хадупом, очень большой сложностью лично для меня стало первоначальное понимание идеологии Map/Reduce (я предпочитаю писать это словосочетание именно так, чтобы подчеркнуть, что речь идет не о продукте, а о принципе). Суть и ценность метода станет понятна в самом конце — после того, как мы решим несложную задачу.

Эта заметка написана по мотивам одного любопытного поста, краткий коммент её же автора к которому сподвиг меня разобраться в происходящем поподробнее. Предлагается сравнить две вариации алгоритма сортировки пузырьком. Первая из них – обычный пузырёк, с небольшой оптимизацией — внутренний цикл можно закончить немного раньше, зная, что оставшаяся часть массива уже отсортирована:
for (i=0; i<N; i++)
  for (j=0; j<N - (i+1); j++)
    if (a[j] > a[j+1])
      swap(a[j], a[j+1]);

Во втором варианте внутренний цикл проходит по другой части массива, однако алгоритмически этот вариант эквивалентен первому (подробности ниже):
for (i=0; i<N-1; i++)
    for (j=i; j>=0; j--)
        if (a[j] > a[j+1])
            swap(a[j], a[j+1]);

Запускаем (код), например, для N=100 000 на массиве int'ов, и получаем около 30 секунд в первом случае, и меньше 10 секунд — во втором, то есть отличие в 3 раза! Откуда же тогда берётся такая разница?

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

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

Вообще, чем мне не нравится Adjacency List, так это рекурсией, особенно, когда нужно выбрать дерево, без каких либо ограничений, например:

• Все дерево комментариев;
• Карта сайта;
• Навигационное меню;
• и т.д.;

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

В одном из американских издательств вышел любопытный сборник научных работ по моделированию инфекционных болезней. Одна из статей в сборнике (18-страничный PDF) посвящена весьма «актуальной» сегодня теме — моделированию атаки зомби [When Zombies Attack!: Mathematical Modelling Of An Outbreak Of Zombie Infection – P. Munz, I. Hudea, J. Imad and R.J. Smith?].

Учёные составили базовую математическую модель скорости распространения атаки зомби, в зависимости от количества жителей.

Первая статья цикла

Интро

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

Пролог

В продолжение опубликованной на выходных статьи.

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

Интро

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

В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.

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

Недавно на Хабре была статья, посвященная алгоритмам на графах. С позволения автора, мой первый хабратопик продолжит цикл.

Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.

Ранее я показал элементарную реализацию алгоритма шинглов, позволяющую определять, являются ли два документа почти дубликатами или нет. В этот раз я поясню реализацию алгоритма, описанную Зеленковым  Ю. Г. и Сегаловичем И.В. в публикации «Сравнительный анализ методов определения нечетких дубликатов для Web-документов».
Этим я начинаю серию из трех теоретических статей, в которых постараюсь доступным языком описать принцип алгоритмов шинглов, супершинглов и мегашинглов для сравнение веб-документов.