Алгоритмы *

Как сообщает Брюс Шнаер в своём блоге Национальный институт стандартов и технологий США (National Institute of Standards and Technology, NIST) собирается в скором времени представить новый хеш-алгоритм, который будет называться SHA-3.

За право бороться в финале на звание нового SHA-3 NIST выбрало 5 финалистов: BLAKE, Grøstl, JH, Keccak, и Skein. Последний является детищем самого Брюса Шнаера.

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

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

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

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

Хочу рассказать как я создавал, и потом переводил собственную систему частиц на GPU. Как я наивно думал просто будет сделать (мол чо там, двигать частицы, тююю). На самом деле о нюансах, возникающих при реализации, можно говорить очень много и долго, поэтому далее я расскажу только об решении проблем «узких» мест.

История вопроса

Заказчик разрабатывает динамические музыкальные фонтанные комплексы, которые управляются через dmx контроллеры по сценарию. Редактор сценариев он сделал самостоятельно. Но на практике создавать сценарии оказалось неудобным, потому что для того, чтобы видеть как получается нужно иметь целиком построенный и запущенный фонтан. Кроме того, если вдруг дизайнеру хореографу захотелось добавить дополнительные сопла для фонтана — то этого сделать уже практически невозможно. Поэтому заказчик захотел обзавестись модулем для моделирования фонтанов, чтобы хореограф мог без настоящего фонтана разрабатывать сценарии. В целом у меня вышло что-то в таком духе: вот видео того что было смоделировано Hawaii50.wmv, а вот то, что вышло в реале после конструирования фонтана: H5OClip.wmv

Месяц назад несколько раз на Хабре проскакивали статьи о замечательном ресурсе Coursera, где можно пройти курсы обучения по различным направлениям. Среди прочего меня очень заинтересовал курс «Алгоритмы» (часть 1), на который я подписался и начал его изучать. Сейчас курс приближается к завершению, а я решил написать небольшой отчет по первой части курса (надеюсь меня хватит и на описание второй части курса по его завершению), чтобы уважаемый %username% мог определить стоит ли записываться на следующую итерацию курса или нет.

Когда на хабре был опубликован пост о том, что компания Stripe проводит конкурс Capture the Flag, я незамедлительно зарегистрировался как участник.

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

Уровни с 0-го по 6-й не представляли особого труда — стандартные SQL- и JavaScript-инъекции, загрузка на сервер PHP-скрипта вместо картинки и т.п.

А вот 7-й уровень заставить меня поломать голову…

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

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

Предлагаю ознакомиться с принципом работы алгоритма Диффи – Хеллмана в замечательном видео от Art of the Problem в моем переводе.

Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.

Фильтр размытия по гауссу (широко известный “gaussian blur” в фотошопе) достаточно часто применяется сам по себе или как часть других алгоритмов обработки изображений. Далее будет описан метод, позволяющий получать размытие со скоростью, не зависящей от радиуса размытия, используя фильтры с бесконечной импульсной характеристикой.

На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.

Признавайтесь, кто в детстве часами напролёт просиживал за игрой в «Денди» или «Сегу»? А кто по мере прохождения игры записывал пароли на бумажку или в специально заведённую тетрадку? Если это вы, и раз уж вы читаете этот сайт, то у вас наверняка хоть раз возникал вопрос: «а как же это работает?»

Я постараюсь объяснить принципы работы классических механизмов генерации паролей на примерах из игр моего детства. Заранее прошу меня извинить за то, что все примеры будут с платформы NES (да, та, которая «Денди»), хотя тематика только ею не ограничивается. Так уж получилось, что не нашёл в себе достаточно мотивации, чтобы провести немного больше исследований и написать немного больше текста.

«Что позволило остаться GIF, это — циклическое проигрывание анимации, которое добавил Netscape. Если бы Netscape не добавил поддержку GIF в свой браузер, GIF умер бы в 1998»

— Александр Тревор (Alexander Trevor),
руководитель команды по созданию GIF в CompuServe

Формат GIF в июне этого года отпраздновал свое 25-летие, и является сегодня самым старым графическим форматом, который распространен в интернете. Посвящая выходные просмотру смешных анимированных гифок понимаешь, что некоторые из них были бы в разы лучше со звуком. Все текущие решения для циклической анимации со звуком (например: coub.com, gifsound.com) предлагают отказаться от GIF, но это — не выход. И я решил пожертвовать просмотром гифок на выходных для решения этой крайне важной проблемы.

Первая в интернете гифка со звуком по ссылке. Надо нажать на синюю кнопку, а потом на гифке. Плеер должен работать во всех современных браузерах (тестировался в последнем Firefox и Chrome).

Гифок под катом не будет, а будет процесс создания расширения для стандарта, написания конвертера и плеера.

Сформулируем задачу.
Дано N узлов, расположенных на плоскости. Задан входной узел (Вх) и выходной узел (Вых). Необходимо обнаружить кратчайший путь, охватывающий все узлы, начинающийся во входном узле, заканчивающийся в выходном узле и проходящий через каждый узел только один раз.

Есть мнения, что задача коммивояжёра может формулироваться ещё двумя способами:
1. Необходимо обнаружить кратчайший гамильтонов цикл.
2. Необходимо обнаружить кратчайший путь, начинающийся в заданном узле.

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

Фильтр Kuwahara выполняет нелинейную фильтрацию изображений с сохранением резких краев. После фильтрации изображение похоже на грубо нарисованную красками, картину.

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

• Что есть информация?
• Как мозг представляет знания?
• Что такое язык?
• Какова роль языка в мышлении?
• Как совершаются поступки?
• Как осуществляется планирование?
• Какова природа фантазий и воспоминаний?
• Что такое мотивация?
• Какова природа эмоций?
• Откуда берется многообразие эмоциональных оценок?
• Что есть смысл?
• Как рождается мысль и какова ее природа?
• Что такое внимание?
• Что есть любовь?
• Что есть гармония и красота?

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

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

Прошлая статья привлекла большой интерес. И даже, на некоторое время, стала лучшей за 24 часа. У меня появилось несколько идей и на часть вопросов в комментариях нужно ответить более развернуто.

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

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