Алгоритмы *

Приветствую, %username%. Сегодня разработаем скрипт составления рейтинга схожести интересов между людьми.

Заинтересовались? Прошу под кат

27 мая в офисе Mail.Ru Group прошёл очередной Moscow Data Science Meetup. На встрече собирались представители крупных российских компаний и научных организаций, а также энтузиасты в области машинного обучения, рекомендательных систем анализа социальных графов и смежных дисциплин. Гости делились друг с другом своим опытом решения практических задач анализа данных. Предлагаем вашему вниманию видеозаписи и презентации трёх докладов, представленных на встрече.

Понадобилось мне недавно написать аналог функции strstr(поиск подстроки в строке). Я решил его ускорить. В результате получился алгоритм. Я не нашел его по первым ссылкам в поисковике, зато там куча других алгоритмов, поэтому и написал это.

График сравнения скорости работы моего алгоритма, с функцией strstr на 600 кб тексте русскоязычной книги, при поиске строк размером от 1 до 255 байт:

Изображение с сайта abv24.com

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

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

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

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

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

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

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

Итак, призовые места заняли:

1. Antelle — 83.67% правильных ответов. Приз 3000 USD.
2. SHB — 83.11% правильных ответов. Приз 2000 USD.
3. chianti — 83.00% правильных ответов. Приз 1000 USD.

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

Полную таблицу результатов смотрите в английской версии на GitHub.

Перевод поста Стивена Вольфрама "Untangling the Tale of Ada Lovelace".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации.

---

Содержание

Ранние годы Ады
Чарльз Бэббидж
Уровень развития этой области
Возвращаемся к Аде
Возвращаясь к Бэббиджу
Статья Ады
После статьи
После смерти Ады
Что стало с Бэббиджем?
Повторное открытие
О чем на самом деле писала Ада
Вычисление чисел Бернулли
Бэббидж vs. Ада?
Секретный ингредиент Бэббиджа
В большем масштабе
А что, если...
Какими они были?
Заключение

---

Ада Лавлейс родилась 200 лет назад. Для некоторых она является знаменательной фигурой в истории вычислительной техники; для других — изрядно переоцененной личностью. В течение долгого времени я пытался разобраться, как всё было на самом деле. И вот, к её двухсотлетию, я решил разобраться в том, что называл для себя "тайной Ады".

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

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

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

Автор: Людмила Дежкина, Senior Full Stack developer

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

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

• интерпретация изображений;
• калибровка камеры по эталону;
• устранение оптических искажений;
• определение сходства;
• анализ перемещения объекта;
• определение формы объекта и слежение за объектом;
• 3D-реконструкция;
• сегментация объекта;
• распознавание жестов.

Сейчас OpenCV используется во многих сферах. Вот несколько интересных примеров:

1. Google:
   
   1. Google self-driving car — в беспилотных автомобилях Google OpenCV используется для разработки прототипа распознавания окружающей обстановки;
      (сегодня построенная система основывается преимущественно на LIDAR — в связи с трудностями распознавания при плохом освещении)
   2. Google Glass — в этих очках 3D-реконструкция изображения построена на OpenCV;
   3. Google Mobile;
   
   
2. Робототехника и Arduino;
3. Промышленное производство — иногда какой-нибудь завод делает на OpenCV систему подсчета деталей или что-то вроде того.

В процессе подготовки задачи для вступительного испытания на летнюю школу GoTo, мы обнаружили, что на русском языке практически отсутствует качественное описание основных метрик ранжирования (задача касалась частного случая задачи ранжирования — построения рекомендательного алгоритма). Мы в E-Contenta активно используем различные метрики ранжирования, поэтому решили исправить это недоразуменее, написав эту статью.

Как чуден и глубок русский курлык
— Генератор постов

Обработка естественного языка (natural language processing, NLP) — тема, на мой взгляд, очень интересная. Во-первых, задачи тут чисто алгоритмические: на вход принимаем совершенно примитивный объект, строчку, а извлечь пытаемся вложенный в него смысл (ну или хотя бы частичку смысла). Во-вторых, необязательно быть профессиональным лингвистом, чтобы решать эти задачи: достаточно знать родной язык на более-менее приличном уровне и любить его.

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

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

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

Недавно мне понадобилось написать 2-3-дерево и я начал искать информацию в русскоязычном интернете. К сожалению, ни на хабре, ни на других ресурсах я не смог найти достаточно полную информацию на русском языке. На всех ресурсах было одно и то же: свойства дерева, как вставляются ключи в дерево, поиск в дереве и иногда простой пример, как удаляется ключ из дерева; не было реализации.

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

Вызов MATLAB из Mathematica с помощью MATLink

Как можно вызывать функции MATLAB напрямую из Mathematica и организовать обмен данными и переменными между двумя системами?

Для этого существует кроссплатформенный пакет под названием MATLink. С помощью него легко организовать вызов функций MATLAB прямо из Mathematica и передавать различные данные от одной системы другой.

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

А теперь по порядку.

Недавно я увидел на Хабрахабре пост про Road Rash и мне стало интересно: «А как устроена система паролей в двух других частях?». Своими наблюдениями и результатом я хотел бы поделиться с вами в этой статье.

Первый Road Rash

Теория

Пароль состоит из 20 позиций, каждая позиция состоит из 5 битов, итого 20*5= 100 битов. Эти биты сохраняют данные игровые параметры:

• номер занятого места (0-15) на пяти разных трассах (0 означает, что на этой трассе ты ещё не ездил).
• количество очков (0-10485750)
• количество денег ((-83886070)-83886070)
• текущий уровень (1-5)
• мотоцикл (1-8)

Теперь посмотрим из чего состоит сырой пароль:

13 июня стартовал ML Boot Camp — состязание по машинному обучению от Mail.Ru Group. В связи с этим мы хотим поделиться с вами впечатлениями о его предыдущем запуске, историями успеха победителей и рассказываем, что нового ждет участников в этом году.

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

Итак, 20 июня мы запускаем наш следующий курс для аналитиков. Для тех, кто летом в Москве и хочет посвятить это время учебе. Следующий курс для менеджеров стартует 5-го июля.

Отзывы по нашим предыдущим курсам можно почитать здесь.

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

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

Спасибо за ожидание! Публикуем предварительные результаты конкурса по программированию.

Протестировано 312 решений, из них 50 упало или зависло, ещё 3 оказались слишком медленными, чтобы пройти все тесты. Из оставшихся 259 решений 12 по разным причинам были объявлены «вне конкурса»: решения не работали без поправки типа файла данных (авторы забыли галочку «gzip») или были присланы сотрудниками Hola.

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

Решение победителя конкурса показало результат в 83.67% правильных ответов. Полные списки решений с результатами тестирования находятся в английской версии поста на GitHub.

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

С системой RDS (Radio Data System) сталкивался хоть раз каждый, кто видел в автомагнитоле название станции вроде «Дорожное радио». Помимо названия, могут отображаться дополнительные данные — название воспроизводимой песни, температура, частота вещания и т.д.


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

Продолжение под катом (осторожно много картинок).

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

Всем кому интересно, добро пожаловать под кат.