Алгоритмы *

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

Защита документов обеспечивается путем нанесения на бланки сложных композиций различных гильоширных элементов. Гильоширный элемент представляет собой замысловатый рисунок из множества многократно пересекающихся тончайших кружевных линий (рисунок 1). Обычно такие элементы представлены разного рода защитными сетками, розеттами, бордюрами, виньетками и уголками. Гильош может быть как симметричным, так и асимметричным по своему дизайну.

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

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

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

image: пузырьки

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

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g₀, g₁, g₂, ..., g_n> — дискретному объекту, степенной ряд g₀ + g₁z + g₂z² +… + g_nzⁿ +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.


КДПВ: задача о ранце на живом примере

Предыстория

Всё началось 10 лет назад, когда я учился в девятом классе. Я случайно подслушал разговор учителя по информатике, рассказывающего задачку кому-то из старших: дан набор чисел, и ещё одно число — контрольное. Надо найти максимальную сумму чисел из набора, которая не превышала бы контрольное число.

Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2ⁿ (количество сочетаний, умноженное на длину суммы).

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

Многие знают, что одно из первых, что говорят в техническом ВУЗе — забыть все, что проходили в школе. Данная рекомендация актуальна и здесь. Полезно иногда с чистого листа начать.

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

Задача каждого торгового алгоритма всегда одна и та же — принести денег владельцу. Алгоритм тем лучше, чем больше денег он в состоянии принести.

15 ноября исполнилось 25 лет со дня триумфа Советской космонавтики — полностью автоматический полет многоразового транспортного космического корабля Буран. Хроника данного события.

В 1976 году в СССР в обстановке строжайшей секретности началась разработка многоразового транспортного космического корабля Буран в рамках проекта «Буран-Энергия».
Это был грандиозный проект. В его создании принимали участие 86 министерств и ведомств и 1286 предприятий СССР (всего около 2,5 миллиона человек).

Свой первый и единственный космический полёт «Буран» совершил 15 ноября 1988 года. Орбитальный корабль был запущен c космодрома Байконур при помощи ракеты-носителя «Энергия». После облёта Земли Буран произвёл посадку на специально оборудованном аэродроме «Юбилейный» на Байконуре. Полёт прошёл без экипажа, полностью в автоматическом режиме. В отличие от американского Шаттла, который совершал посадку только на ручном управлении.

Более подробно про сам Буран можно узнать на Wikipedia. Но самая полная информация собирается на сайте http://www.buran.ru

В далеком (а может и не очень далеком) 1975 году Альфред Ахо и Маргарет Корасик опубликовали статью, в которой был подробно описан алгоритм эффективного поиска всех вхождений всех строк-образцов в заданную строку. В дальнейшем этот алгоритм и получил название «алгоритм Ахо-Корасик». Неудивительно, что через некоторое время появились технические и «художественные» переводы данной статьи на русский язык. Порой мне даже встречались вольные изложения сути алгоритма в том виде, в котором его понимает автор. Причем последний, судя по тексту, узнал об алгоритме далеко не из первоисточника. Я не знаю существовал ли перевод, который послужил первоисточником проблемы, но мне всё больше и больше попадаются статьи с описанием алгоритма Ахо-Корасик, в котором допущена одна и та же кардинальная ошибка. Последней каплей была статья пользователя rmq на хабре, которую данная ошибка не миновала. Собственно об этой ошибке мне и хотелось бы рассказать общественности в своей статье.
Замечание: статья пользователя rmq, как выяснилось позже, не содержит этой ошибки. Как она решена там расскажу ниже. А ему огромное спасибо, если бы не его топик я бы не написал свой и не получил бы инвайт!
Перед началом, еще пара слов о целевой аудитории: Скорее всего, тем, кто давно знаком с алгоритмом Ахо-Корасик, моя статья будет не интересна, так как о его особенностях они давно уже знают. По крайней мере, все мои знакомые программисты не один раз применявшие данный алгоритм знают о существовании его неверных интерпретаций не понаслышке. А вот новичкам и тем, кому не довелось часто применять его на практике, эта статья может оказаться довольно полезной.
Итак, начнем.

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

Оптический поток (Optical flow) – технология, использующаяся в различных областях computer vision для определения сдвигов, сегментации, выделения объектов, компрессии видео. Однако если мы захотим его по-быстрому реализовать в своем проекте, прочитав про него на википедии или где-нибудь еще, то, скорее всего, очень быстро наткнемся на то, что он работает очень плохо и сбоит при определении сдвигов уже порядка 1-2 пикселей (по крайней мере так было у меня). Тогда обратимся к готовым реализациям, например, в OpenCV. Там он реализован различными методами и совершенно непонятно, чем аббревиатура PyrLK лучше или хуже обозначения Farneback или чего-нибудь в этом роде, да и придется поразбираться со смыслом параметров, которых в некоторых реализациях очень много. Причем, что интересно, эти алгоритмы как-то работают, в отличие от того, что мы написали сами. В чем же секрет?

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

В статье будет много картинок. Объяснение как решать задачу рекурсивно и как она решается бинарным поиском.
В общем статья посвящается тем смелым, кто пока еще боится Ханойской башни, но хочет перестать её бояться.

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

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

Сегодня предложу Вашему вниманию симпатичный алгоритм, который хоть и придумали совсем недавно (11 лет назад), но «прототипом» послужило счётное устройство с трёхтысячелетней историей.

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

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

На Yet another Conference 2013 мы представили разработчикам нашу новую библиотеку Yandex SpeechKit. Это публичный API для распознавания речи, который могут использовать разработчики под Android и iOS. Скачать SpeechKit, а также ознакомиться с документацией, можно здесь.

Yandex SpeechKit позволяет напрямую обращаться к тому бэкэнду, который успешно применяется в мобильных приложениях Яндекса. Мы достаточно долго развивали эту систему и сейчас правильно распознаем 94% слов в Навигаторе и Мобильных Картах, а также 84% слов в Мобильном Браузере. При этом на распознавание уходит чуть больше секунды. Это уже весьма достойное качество, и мы активно работаем над его улучшением.



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

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

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

Удовлетворить эти требования одновременно непросто. Если рассмотреть широкоизвестные структуры данных, такие как массивы, списки, деревья, стеки, очереди, кольцевые буфера — то такой структуры, которая бы позволила эффективно выполнить оба требования, не встречается. В случае массива имеем незначительные накладные расходы по памяти, но операция вставки имеет сложность O(n), где n — размер редактируемого текста. В случае списка сложность вставки и удаления составляет O(1), однако накладные расходы по памяти в несколько раз превышают размер собственно текста. Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе.

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

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

Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.

А что это мы всё об умных да об эффективных алгоритмах? А давайте эту тоскливую осеннюю пятницу развеем чем-нибудь контрпродуктивным!?

Представляю Вашему вниманию ТОП-5 самых нетрадиционных сортировок всех времён и народов.

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

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

Если у вас такого устройства нет, то прошу под кат.

Sentiment analysis (по-русски, анализ тональности) — это область компьютерной лингвистики, которая занимается изучением эмоциональной окраски текстов, подробнее см. в статье Irokez’а. Это очень важное направление машинного обучения: анализ тональности нужен для лучшего «понимания» текстов, перевода с одного языка на другой.

Сложность задачи заключается в непростых лингвистических конструкциях, которые часто используют люди. Даже человек не сразу распознает негатив во фразе вроде «В этой книге хороша только обложка». Как обучить этому компьютер?

Точность определения эмоций у лучших компьютерных программ до сегодняшнего дня составляла не более 80%. Группе учёных из Стэнфорда при участии небезызвестного Эндрю Нг удалось довести её до 85%, а при дальнейшем обучении рекурсивной нейросети точность вполне может повыситься до 95%, говорит один из авторов исследования. Заметим, что 95% — это будет абсолютно феноменальный результат, не все люди способы распознавать сарказм и определять тональность слов с такой точностью.