Алгоритмы *

Что такое HFT, или рассказ о том, в какие дебри могут завести программиста интерес к финансовым рынкам, и хобби в виде написания роботов для алгоритмического трейдинга. Доклад на Таллинском Devclub.

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

Для начала хочу поблагодарить автора статей «Декодирование JPEG для чайников» и «Изобретаем JPEG», которые очень помогли мне в работе по написанию данной публикации. Когда я занялся вопросами изучения алгоритмов сжатия изображений с потерями, то в части алгоритма JPEG меня всё время мучил вопрос: «Почему роль базисного преобразования в алгоритме JPEG отведена именно частному случаю преобразования Фурье?». Здесь автор даёт ответ на этот вопрос, но я решил подойти к нему не с точки зрения теории, математических моделей или программной реализации, а с точки зрения схемотехники.

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

Осенью Академический университет и Computer Science Center запускают годовую образовательную программу по основам программирования (code.stepic.org). Программа запускается на платформе онлайн-обучения Stepic. При успешном завершении программы студентам будет выдан диплом о профессиональной переподготовке от Академического университета.

В последнее время на Хабрахабр появилось много статей посвященных разработке для FPGA/ПЛИС. Это произошло как при непосредственном участии моих коллег, так и других пользователей. Видно, что такие статьи способствует популяризации этой сферы разработки и показывают, что уже есть существенный интерес к направлению разработки hardware в целом (образно называемого «железом»).

В этой статье я вступлю на практически «непаханое поле» разработки для ASIC и расскажу об одном интересном аспекте создания цифровых частей (IP-блоков) в микросхемах ASIC. Эта сфера разработки еще более узкая по сравнению с FPGA.

ASIC (application-specific integrated circuit, «интегральная схема специального назначения») — интегральная схема, специализированная для решения конкретной задачи.

Введение

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

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

Моделирование работы генетического алгоритма, в котором естественный отбор определяется условиями среды

Моделирование – метод научного познания объективного мира через построение и изучение моделей.

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

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

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

В этом докладе рассматриваются алгоритмические задачи, связанные с мин-плюс многочленами. Конкретнее — разрешимость систем линейных мин-плюс многочленов. Эта задача оказывается полиномиально эквивалентной задаче об определении победителя в так называемых циклических играх (mean payoff games), известной задаче, лежащей в пересечении сложностных классов NP и coNP. Второй результат, который обсуждается в ходе доклада, это аналог теоремы Гильберта о нулях для мин-плюс алгебры.



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

Доклад был прочитан на факультете компьютерных наук, открытом в НИУ ВШЭ при поддержке Яндекса. Лектор Владимир Подольский — старший научный сотрудник Математического института им. В.А. Стеклова. На ФКН читает лекции и ведет семинары в рамках курса «Дискретная математика». Доклад основан на совместных работах с Дмитрием Григорьевым.

Под катом — полная расшифровка лекции.

За последние тридцать лет технологии распознавания речи серьёзно продвинулись вперед, начав свой путь в исследовательских лабораториях и дойдя до широкого круга потребителей. Эти технологии начинают играть важную роль в нашей жизни. Их можно встретить на рабочем месте, дома, в машине. Их используют в медицинских целях и в других сферах деятельности. Распознавание речи входит в топ-10 перспективных технологий мирового уровня.


^{Оригинал картинки Vladstudio}

Выражаем большое спасибо за подготовку статьи Евгению Григоренко, Microsoft Student Partner, за помощь в написании данной статьи. Остальные наши статьи по теме Azure можно найти по тегу azureweek

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

Но все мы знаем печальную истину. Многое возможно только с пользованием сложных алгоритмов машинного обучения, которых у нас совершенно нет времени изучать. И именно это останавливает от разработки, так как без таких инноваций мы совершенно затеряемся среди аналогов. Но решение этой проблемы есть, и имя ему Microsoft Project Oxford. Если вы хотите узнать, как Microsoft Project Oxford может упростить Вашу жизнь и сделать Ваши приложения по-настоящему интеллектуальными, то добро пожаловать под кат.

Ритейл, все-таки, штука интересная. Особенно, если разрабатываешь сервис для его аналитики. Каждый поход в магазин превращается в мини-исследование. Идешь себе вдоль полок и думаешь:
“С чем лучше сосиски коррелируются с кетчупом или мариноваными огурцами? А черт, ладно, беру и то, и то!”
“Hoegaarden почти раскупили, а ведь до вечера пятницы еще целых полдня. Эх, че ж так плохо спрос то спрогнозировали? ”

Интересно, а что применяют управляющие для прогнозирования продаж?

А иногда приходишь с этим вопросом к ритейлерам, а тебе в ответ люди говорят «Нууууу, обычно как-то так ...» и начинают делать широкие жесты руками. Да вот, приблизительно, такие, как на картинке.



Так вот, мы в Datawiz.io, решительно не согласны с таким подходом.

Здравствуйте все!

На волне непрекращающихся дискуссий о Hadoop и прочих больших данных мы не могли пройти мимо замечательной публикации Джерри Овертона, рассказывающей о профессиональном подходе к анализу больших данных в компаниях любого размера. Понятные картинки, предоставленные автором, а также краткий парад технологий, без которых современному Data scientist'у не обойтись. Поэтому пусть статья и начинается с (ошибочной!) посылки: «Не читайте книги по Data Science», она заслуживает публикации в блоге нашего издательства.

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

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

В Datawiz.io, собрав несколько мат-гиков, мы решили попытаться изменить сложившуюся ситуацию. Интересно же использовать свои знания на чем-то реальном, измеримом, и даже, возможно, приносящем пользу обществу. Остановились мы на ритейл индустрии. Ритейл предлагает множество данных для обработки, просто водопад цифр: продажи, чеки, ценообразование, покупатели, программы лояльности,… Есть с чем порезвится.

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

Затрагиваемые вопросы:

• Влияние программной архитектуры на потребление памяти и производительность;
• Различия при работе в 32 и 64 битных режимах;
• Различия между указателями и индексами массива;
• Влияние выравнивания данных внутри классов/структур;
• Влияние кеша процессора на производительность;
• Оценка стоимости поддержки ООП в языках высокого уровня;
• Признание факта необходимости учитывать низкоуровневые особенности платформы даже при разработке на языках высокого уровня.

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

О платформе, предназначенной для испытания новейших препаратов против эпилепсии, и о том, какое отношение к ней имеет EPAM, читайте далее в статье.

Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984)

Популярность стохастических алгоритмов все растет. Многие из них базируются на генерации большого количества различных случайных величин. Далеко не всегда равномерно распределенных. Здесь я попытался собрать информацию о быстрых и точных генераторах случайных величин с известными распределениями. Задачи могут быть разными, разными могут быть и критерии. Кому-то важно время генерации, кому-то — точность, кому-то — криптоустойчивость, кому-то — скорость сходимости. Лично я исходил из предположения, что мы имеем некий базовый генератор, возвращающий псевдослучайное целое число, равномерно распределенное от 0 до некого RAND_MAX

unsigned long long BasicRandGenerator() {
    unsigned long long randomVariable;
    // some magic here
    ...
    return randomVariable;
}

и что этот генератор достаточно быстрый. Я имею ввиду, что дешевле сгенерировать с десяток случайных чисел, нежели чем посчитать логарифм или возвести в степень одно из них. Это могут быть стандартные генераторы: std::rand(), rand в MATLAB, Java.util.Random и т.д. Но имейте ввиду, что подобные генераторы редко подходят для серьезной работы. Зачастую они проваливают разные статистические тесты. А также, помните, что вы полностью зависите от них и лучше использовать свой собственный генератор, чтобы иметь представление о его работе.

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


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

Равномерное распределение

В день запуска ботов в Telegram я за 3 часа собрал бота, который присылает температуру воздуха в ответ на геолокацию пользователя. С того же дня я бредил вызовом такси через бота в Telegram, так как API службы такси у меня был под рукой.

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

В этом примере будет создан простой детектор движения, на базе фоторезистора и Arduino. Управляется при помощи Arduino Support Package для MATLAB.

Перевод поста Джона Маклуна (Jon McLoone) "Doing Spy Stuff with Mathematica".
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе.

---

Я читал о IT проблемах недавно арестованных, как заявлялось, русских шпионов. Говорилось, что они пользовались не самыми надёжными инструментами цифровой стеганографии (вики). И мне стало интересно — насколько быстро я смогу реализовать стеганографию через цифровые изображения в Mathematica, используя метод, известный как "вставка младшего бита" (least significant bit insertion).

Идея стеганографии основывается на том, чтобы спрятать сообщения в какой-то другой информации таким образом, чтобы никто факта коммуникации не заметил. Само слово происходит от латино-греческий комбинации, означающей «скрытное письмо»; данным термином назывался процесс нанесения секретного сообщения на лысую голову человека, на которой затем отрастали волосы и, тем самым, прятали сообщение. В случае цифровой стеганографии всё делается посредством математики.

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

Небольшая предыстория. Этот пост я написал для двух целей. Во-первых, обкатать конвертор разметки Markdown + в хабрачитаемый вид. Во-вторых, рассказать об интересной задаче из data streaming. К концу написания, я обнаружил пост про LogLog четырехлетней давности. На мою удачу автор предыдущего поста делал упор на реализацию. Я же, полагаясь на , расскажу больше о математике.

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

• Пакетов так много, что запомнить их все нельзя. Сказать ушедшему пакету «Вернись! Я все прощу,» — тоже.
• Всех возможных адресов . Столько памяти на роутере нет.

Задача. Есть последовательность целых чисел , все числа принимают значения от до . Требуется в один проход посчитать количество различных чисел, используя памяти.

Знаменитая игра Джона Конвея «Жизнь», благодаря своей простоте, занимательности и поучительность, реализовывалась программистами так много раз, что уступает вероятно только пресловутой сортировке «пузырьком».

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