Алгоритмы *

Википедия о ДРАКОНе.

ДРАКОН иногда называют правильными блок-схемами. Но в первую очередь он отлично подходит для записи алгоритмов.
Внутри НПЦ АП (Научно-производственный центр автоматики и приборостроения) ДРАКОН используется с помощью закрытой технологии ГРАФИТ-ФЛОКС.

За рамками НПЦ АП есть открытые общедоступные среды, на которых можно писать реальные программы на так называемых гибридных языках, например: ДРАКОН-Си, ДРАКОН-JavaScript, ДРАКОН-Java, ДРАКОН-C#, ДРАКОН-Python, ДРАКОН-Tcl, ДРАКОН-ASM и т.д.



Доклад представлен на Международной научно-технической конференции «Системы и комплексы автоматического управления летательных аппаратов», посвящённой 105-летию со дня рождения академика АН СССР Н.А. Пилюгина. Конференция проводилась 21 мая 2013 в Институте проблем управления РАН.

Текстовая версия доклада (более подробная)

Я иногда путешествую по разным странам, и языковой барьер, довольно часто, становится серьезным препятствием для меня. И если в странах, где используются языки германской группы, я еще как то могу сориентироваться, то в таких странах как Китай, Израиль и арабские страны без сопровождающего, путешествие превращается в загадочный квест. Невозможно понять местное расписание автобусов/поездов/электричек, названия улиц в небольших городах очень редко есть на английском языке. А уж проблема с выбором, что бы поесть, из меню на непонятном языке вообще сродни ходьбы по минному полю.
Так как я разработчик под iOS, я подумал, а почему бы не написать такое приложение: наводишь камеру на вывеску/расписание/меню и тут же получаешь перевод на русский.

На Coursera сейчас идёт курс Introduction to Data Science от University of Washington, в ходе которого студентов будут учить работе с большими массивами данных, статистическому анализу, data mining, алгоритмам машинного обучения и прочим таким вещам. Авторы курса приглашают организации (коммерческие, некоммерческие и даже просто отдельных людей), которым будет полезна помощь в работе с данными, принять участие, подкинув студентам для решения задачи из реальной жизни.

Схема примерно такая: организация формулирует задачу и предоставляет данные (собственные или из открытых источников), студенты её решают и пишут отчёт. Отчёт потом оценивается другими студентами, плюс организация даёт свой отзыв о работе.
В плюсе все: организация бесплатно получает рабочие руки мозги, а студент — опыт.

На что при загрузке сайта расходуется больше трафика? Чаще всего это картинки, и их суммарный «вес» частенько в несколько раз больше, чем у разметки, скриптов и стилей. В файлах изображений распространенных форматов растровые данные хранятся в сжатом виде, и это значительно лучше, чем несжатый BMP. А если хочется ещё лучше? Ведь в достаточно крупных проектах каждый байт на счету (например, в TradingView, чего уж там скромничать).

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

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

Описание небольшого трюка по анимации вращения планет или других шарообразных штуковин. На написание этой статьи меня натолкнула статья Сфера из двух треугольников (стоит почитать). А сам трюк основан на весьма простом способе создания в Photoshop псевдо-объемной картинки из плоской, который описан под катом.

микродемо

В математике сети дорог (автомобильных и не только) представляются взвешенным графом. Населенные пункты (или перекрестки) — это вершины графа, ребра — дороги, веса ребер — расстояния по этим дорогам.

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

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

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

Думаю, что многим из присутствующих здесь известна игра Космические Рейнджеры. Также, я не думаю, что сильно ошибусь, если скажу, что, в значительной мере, своим очарованием эта игра обязана, фактически возрожденным ей, текстовым квестам. Некоторые из этих квестов, такие как «Цитадели» или «Лыжный курорт», вполне могут рассматриваться как самостоятельные игры.

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

По мотивам одного вчерашнего поста про оптимизацию условных переходов при расчете x=sign(a,b)*min(abs(a), abs(b)) якобы в 10 раз. Краткая сводка:

• оптимизация налицо, но размер мнимый: не в 10 раз, а 2.5 раза;
• бенчмарки надо делать правильно: не надо мерить CPU stalls, RAM bandwidth итп вместо исследуемой функции;
• бенчмарки надо делать правильно: иначе могут дико дрожать;
• выставлять только приоритет прикольно, но на коротких бенчмарках зря: +0.5% скорости, -15% дрожания;
• нужно мерить исследуемую функцию и только ее, только так получаешь корректные данные;
• нужно греть проц, нужно считать минимум из N прогонов/секунд, только так побеждаешь дрожание;
• нужно пользовать SSE, с ним получилось 8.6 раз, причем код… читается.

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

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



Интересный метод, описан в статье «A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition» L.R. Rabiner, которая вводит модель скрытой цепи Маркова и описывает три ценных алгоритма: The Forward-Backward Procedure, Viterbi Algorithm и Baum-Welch reestimation. Несмотря на то, что эти алгоритмы представляют интерес только в совокупности, для большего понимания описывать их лучше по отдельности.

При оптимизации времени выполнения алгоритма, использующего LDPC декодер, профайлер привел к функции, вычисляющей следующее значение:

где a и b — целые числа. Количество вызовов шло на миллионы, а реализация ее была достаточно

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

С недавних пор существует элегантная формула для вычисления числа Пи, которую в 1995 году впервые опубликовали Дэвид Бэйли, Питер Борвайн и Саймон Плафф:


Казалось бы: что в ней особенного — формул для вычисления Пи великое множество: от школьного метода Монте-Карло до труднопостижимого интеграла Пуассона и формулы Франсуа Виета из позднего Средневековья. Но именно на эту формулу стоит обратить особое внимание — она позволяет вычислить n-й знак числа пи без нахождения предыдущих. За информацией о том, как это работает, а также за готовым кодом на языке C, вычисляющим 1 000 000-й знак, прошу под хабракат.

Представим воображаемого хитрого дядю, который хочет обмануть и заработать деньги на «лопухах». Назовем его Геннадий Обмануев.
В самый обычный вторник, Геннадию Обмануеву вдруг пришла гениальная идея: создать лотерею, в которой каждый игрок может сам указывать свой шанс на победу и, следовательно, множитель выигрыша и играть на выставленных им правилах! Для того, чтобы всегда оставаться в плюсе, Геннадий в конце каждой удачной игры берет символическую плату в 5% от выигрыша.


*если кратко об игре

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

Вместо вступления

В стандартной колоде для покера 54 карты. Без двух джокеров, которые не участвуют в игре, выходит 52 карты. Если вы хорошенько перемешаете колоду, то, возможно, создадите уникальную комбинацию из карт, которую никогда никто не создавал до вас. Потому что различных вариантов расположений 52 карт равно:


Что-то мне подсказывает, что комбинация на изображении не так уникальна.

Теперь к теме

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

Я слышал, что у [блондинов/низких людей/тех, кто носит кепки/любой подходящий вариант] интуиция просто отстой! Вот спорим, что ты не сможешь угадать (в этот момент разводчик достает колоду карт) цвет каждой следующей карты? Можешь перетасовать колоду, как захочешь! За каждую угаданную карту плачу по тысяче рублей! А если не угадаешь, то ты даешь мне два рубля, потом докидываешь до четырех, до восьми рублей и дальше, ну ты понял? И чтобы было честно — остановить игру может лишь тот, кто проигрывает в общем счете, у кого выигрыш меньше. Идет?

Большинство читателей уже поняли схему и с улыбкой прикидывают сумму, которую может выиграть разводчик.
Мне стало интересно, до каких пор игрок выигрывает и как нужно действовать, чтобы увеличить шансы на выигрыш (лучший способ — отказаться от игры!). Естественно, правило про остановку игры я не учитываю, с ним выиграть невозможно.

При разработке современного сайта часто возникает необходимость реализовать функционал вывода близлежащих географических точек. Самым оптимальным способом решения этой задачи является перекладывание работы по реализации определения точек на плечи MySQL. Если конкретней, то нам будут нужны возможности пространственных расширений MySQL (до версии 5.0.16 эти расширения были доступны только для MyISAM, более поздние версии MySQL поддерживают работу пространственных расширений с InnoDB, NDB, BDB и ARCHIVE).

Расстояние между точками будет вычисляться по формуле гаверсинусов. Формула позволяет получать расстояние между точками с очень низкой погрешностью (величина погрешности прямо пропорциональна расстоянию между точками, и не превышает 10-20 километров при вычислении очень больших расстояний, например между штаб-квартирой Google в Калифорнии (37.422045, -122.084347) и оперным театром в Сиднее, Австралия (-33.856553, 151.214696)).

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

Некриптографические хеш-функции

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

Критерии, которые важны для некриптографических хеш-функций:

Эпоха путешествий во времени еще не наступила, а человечество уже давно пытается разрешить сопутствующие им парадоксы. Мы поговорим о самом очевидном из них: что же все-таки произойдет при вмешательстве в ход истории? Существует несколько вариантов того, как поток времени реагирует на действия путешественника из будущего. Эти модели можно увидеть в фантастических фильмах, о них все больше начинают говорить ученые, но какая модель ближе к истине — единого мнения пока нет. Мы только начинаем проникать в тайны времени, и еще не обладаем возможностью экспериментировать с перемещениями в прошлое. Что же можно прояснить в данном вопросе уже сейчас? Под катом нас ждет экскурсия по основам механики времени, мы порассуждаем о парадоксах, и проведем небольшой эксперимент. Да, это будет испытание виртуальной машины времени, построенной на основе алгоритма «Жизнь»!

В рамках своей научной активности реализовал так называемый Федеративный Фильтр Калмана (Federated Kalman Filter). В этой статье рассказывается о том, что такое «Федеративный ФК», чем он отличается от обобщенного, а также описывается консольное приложение, реализующее данный фильтр и генетические алгоритмы для подбора параметров его математической модели. Приложение было реализовано с использованием TPL (Task Parallel Library), поэтому пост будет интересен не только специалистам по цифровой обработке сигналов.

UPD1: после прочтения двух недавних статей решил тоже присоединиться к эксперименту/исследованию/авантюре (называйте как хотите). В конце статьи добавил еще один опрос — "Стали бы Вы поощрать рублем такие узко специализированные статьи на Хабрахабре?".

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

Небольшое предисловие

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

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