Алгоритмы *

Перевод поста Майкла Тротта (Michael Trott) и Эрика Вайсштайна (Eric W. Weisstein) "Michael Trott & Eric W. Weisstein
The Top 100+ Sines of Wolfram|Alpha", существенно расширяющий вопросы, затронутые авторами.
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~12 МБ).

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

Чтобы прояснить то, что мы подразумеваем под “большим спектром задач” (о котором мы действительно так думаем), давайте возьмем в качестве примера такую непритязательную математическую функцию, как синус. Ниже мы привели список, который раскрывает 93 возможности того, что Wolfram|Alpha может делать с синусом, но в итоге мы добавили еще сверх того некоторое количество бонусных возможностей, перед включением которых в пост мы не могли устоять.

Давайте начнем с того, что просто введем в Wolfram|Alpha запрос sin(x), т. е. просто функцию синус от аргумента x, как она есть. Ниже представлено то, что сервис Wolfram|Alpha выдаст нам в качестве результата на этот запрос:

Структура публикации

• Получение кватерниона из вектора и величины угла разворота
• Обратный кватернион
• Умножение кватернионов
• Поворот вектора
• Рысканье, тангаж, крен
• Серия поворотов

Получение кватерниона из вектора и величины угла разворота

Ещё раз – что такое кватернион? Для разработчика – это прежде всего инструмент, описывающий действие – поворот вокруг оси на заданный угол:

(w, vx, vy, vz),

где v – ось, выраженная вектором;
w – компонента, описывающая поворот (косинус половины угла).

Приветствую всех читателей. Сегодня попробую продолжить серию достаточно редких статей, посвящённым естественным алгоритмам. В частности, эта статья будет посвящена модификации муравьиного алгоритма, известной как Max-Min Ant System (MMAS). Я расскажу об отличиях от классического муравьиного алгоритма и о причинах внесения таких модификаций. Подробности под катом.

Мы продолжаем публиковать лекции Натальи Васильевой, старшего научного сотрудника HP Labs и руководителя HP Labs Russia. Наталья Сергеевна читала курс, посвящённый анализу изображений, в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба.



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

Перевод статьи Стивена Вольфрама (Stephen Wolfram) "Dropping In on Gottfried Leibniz".

На протяжении многих лет меня интересовала личность Готфрида Лейбница, в частности из-за того, что он хотел создать что то на подобие Mathematica, Wolfram|Alpha и возможно даже A New Kind of Science но на три столетия раньше. Поэтому когда в недавнем прошлом я посетил Германию, то мне страстно захотелось побывать в его архивах в Ганновере.

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

Перевод поста Майкла Тротта (Michael Trott) "Making Formulas… for Everything—From Pi to the Pink Panther to Sir Isaac Newton".
Выражаю благодарность за помощь в переводе Сильвии Торосян.
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~7 МБ).

В компании Wolfram Research и Wolfram|Alpha мы любим математику и вычисления. Наши любимые темы — алгоритмы, следующие из формул и уравнений. Например, Mathematica может вычислить миллионы интегралов (точнее бесконечное их количество, встречающихся на практике), а также Wolfram|Alpha знает сотни тысяч математических формул (от формулы Эйлера и BBP-формул для Pi до сложных определённых интегралов, содержащих sin (x)) и множество формул физики (например, от закона Пуазейля до классических решений механики для точечной частицы в прямоугольнике или потенциала обратного расстояния в четырехмерном пространстве, в гиперсферических координатах), так же как менее известные формулы, такие как формулы для частоты дрожащей мокрой собаки, максимальной высоты песочного замка, или времени приготовления индейки.

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



Сегодня, на мой взгляд, одна из проблем навигационных устройств – это то, что они не ведут пользователя по полосам. Эта проблема увеличивает время в пути, пробки и аварийность. Недавно google maps начали отображать разметку дороги перед поворотом, что уже хороший результат, но и тут можно многое улучшить. Карты не знают на какой полосе сейчас находится машина, средствами gps узнать это проблематично, у gps слишком большая погрешность для этого. Если бы мы знали текущую полосу, то знали бы скорость движения по полосами и могли бы задолго подсказывать пользователю в явном виде, на какую полосу и когда ему лучше перестроиться. Например, навигатор говорил бы “Продолжайте держаться этой полосы до перекрестка” или “Перестройтесь на крайнюю левую полосу”.

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

Мне совершенно непонятна выгода от удобного интерфейса.

Да, он красивый, с ним проще работать. Но как посчитать материальную пользу?

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

И вот пару недель назад я заслушивался новыми объявлениями о вылетах. Было чувство, что их целиком записал профессиональный диктор, который всю жизнь учился на эту роль. Интерфейс стал лучше, он стал более натуральным.
Стал ли я от этого больше летать? Вряд ли.
Может, у меня появилось предпочтение между аэропортами? Не думаю, что это настолько важный момент.
Тем не менее, зачем-то люди потратили время и деньги на приведение объявлений к естественному виду. И это очень круто!

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

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

Все правила, описанные ниже, мы выработали сами. Большинство из них используем или скоро подключим на dadata.ru.

Эта статья создана нашим другом из коммьюнити, Дмитрием Петуховым, Microsoft Certified Professional, разработчиком компании Quantum Art.
Статья — часть цикла про Fraud Detection, остальные статьи можно найти в профиле у Дмитрия.

Azure Machine Learning – облачный сервис для выполнения задач прогнозной аналитики (predictive analytics). Сервис представлен двумя компонентами: Azure ML Studio – средой разработки, доступной через web-интерфейс, и web-сервисами Azure ML.
Типичная последовательность действий data scientist'a при поиске закономерностей в наборе данных с использованием алгоритмов обучения с учителем изображена и подробно описана под хабракатом.

Алгоритм Брезенхема является одним из старейших алгоритмов в машинной графике. Казалось бы, как можно применить алгоритм построения растровых прямых при создании домашней паяльной печи? Оказывается, можно, причем с очень достойным результатом. Забегая вперед, скажу, что данный алгоритм очень хорошо скармливается маломощному 8-битному микроконтроллеру. Но обо всем по порядку.

Как вы знаете, Badoo — сервис для поиска новых людей. Кроме всего прочего, мы позволяем искать людей вокруг и в «игре» тоже показываем людей, которые находятся недалеко от вас. Эта часть «вокруг» очень и очень важна. Ведь молодому человеку из Новосибирска гораздо интереснее познакомиться с девушкой, которая живет в пяти минутах ходьбы от него, а не во Владивостоке.
Мы до сих пор не рассказывали публично о том, как мы это делаем. Но новое открытие австрийских ученых настолько нас обрадовало, что мы решились это сделать. Перейдем же к делу.
Badoo работает по всему миру и наш поиск работает абсолютно одинаково, вне зависимости от того, в какой точке земного шара вы находитесь. Как же эффективно искать людей вокруг среди всех 200+ миллионов пользователей?
Решение нетривиально, честно говоря. Нам нужен какой-то индекс, какой-то способ сразу же сузить область поиска. В случае с земным шаром, самым простым разбиением является сетка географических широт и долгот. Однако проблема с этой сеткой в ее неравномерности. Ячейка у северного полюса и ячейка у экватора имеют совсем разные формы. Такое несимметричное разбиение вносит большие проблемы, если мы хотим равномерно распределить нагрузку по поисковому кластеру.

Для приложений Second Screen cуществует два основных способа синхронизации контента по аудиосигналу (Automatic Content Recognition, ACR): на базе аудио fingerprints и с использованием цифровых водяных знаков (ЦВЗ, digital watermark). Эти технологии имеют принципиально разные подходы.

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

Я уже писал о достигнутых нами результатах по распознаванию аудио на основе fingerprints. В этом посте хочу рассказать об аудио ЦВЗ и проблемах, с которыми мы столкнулись при построении ACR на их основе.

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

Как решать подобную задачу?

Давным-давно, в далёкой-далёкой галактике (т.е. больше года назад и за пределами дефолт-сити) один web программист решил написать свой Flash (был он не без мании величия, конечно). Задача тогда казалась непростой и очень интересной. В данной статье пойдёт речь об одной из проблем, которые встали у него на пути.
Те, кто рисовал во Flash знают, что в нём фигуры (закрашенные области) в пределах одного слоя никогда не перекрываются, а линии всегда рисуются поверх закрашенных фигур. У такого подхода есть, на мой взгляд, хороший плюс — ты имеешь на изображении то, что видишь. Однако, при написании векторного редактора это приводит к необходимости решения задачи корректного наложения рисуемых объектов (линий и закрашенных фигур) на уже существующие. Ниже я попытаюсь поэтапно показать, как это можно сделать.

Мы продолжаем публиковать лекции Натальи Васильевой, старшего научного сотрудника HP Labs и руководителя HP Labs Russia. Наталья Сергеевна читала курс, посвящённый анализу изображений, в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба.



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

Предлагаю читателям «Хабрахабра» перевод статьи «How To Decrypt Magnetic Card Data With DUKPT».

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

Оказалось, мои считыватели используют схему известную как DUKPT (Derived Unique Key Per Transaction — Определение Уникального Ключа На Транзакцию). Идея этой схемы состоит в том, что для каждой транзакции (или в нашем случае для каждого проката карты) данные шифруются с использованием ключа вычисленного для отдельного проката карты.

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

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

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

Задача 1. На прямой даны n отрезков, нужно выбрать максимальное по размеру подмножество непересекающихся.

Задача 2. На окружности даны n дуг (отрезков), нужно выбрать максимальное по размеру подмножество непересекающихся.

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

Свёрточная нейронная сеть (англ. convolutional neural network, CNN) — специальная архитектура искусственных нейронных сетей, предложенная Яном Лекуном и нацеленная на эффективное распознавание изображений, входит в состав технологий глубокого обучения (англ. deep leaning). Эта технология построена по аналогии с принципами работы зрительной коры головного мозга, в которой были открыты так называемые простые клетки, реагирующие на прямые линии под разными углами, и сложные клетки, реакция которых связана с активацией определённого набора простых клеток. Таким образом, идея сверточных нейронных сетей заключается в чередовании сверточных слоев (англ. convolution layers) и субдискретизирующих слоев (англ. subsampling layers, слоёв подвыборки).[6]


Рис 1. Архитектура сверточной нейронной сети

Ключевым моментом в понимании сверточных нейронных сетей является понятие так называемых «разделяемых» весов, т.е. часть нейронов некоторого рассматриваемого слоя нейронной сети может использовать одни и те же весовые коэффициенты. Нейроны, использующие одни и те же веса, объединяются в карты признаков (feature maps), а каждый нейрон карты признаков связан с частью нейронов предыдущего слоя. При вычислении сети получается, что каждый нейрон выполняет свертку (операцию конволюции) некоторой области предыдущего слоя (определяемой множеством нейронов, связанных с данным нейроном). Слои нейронной сети, построенные описанным образом, называются сверточными слоями. Помимо, сверточных слоев в сверточной нейронной сети могут быть слои субдискретизации (выполняющие функции уменьшения размерности пространства карт признаков) и полносвязные слои (выходной слой, как правило, всегда полносвязный). Все три вида слоев могут чередоваться в произвольном порядке, что позволяет составлять карты признаков из карт признаков, а это на практике означает способность распознавания сложных иерархий признаков [3].

Что же именно влияет на качество распознавания образов при обучении сверточных нейронных сетей? Озадачившись данным вопросом, наткнулись на статью Мэттью Зайлера (Matthew Zeiler).

Перевод поста Стивена Вольфрама (Stephen Wolfram) "The Wolfram Data Drop Is Live!". Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

Куда должны идти данные из интернета вещей? У нас есть отличная технология в Wolfram Language для интерпретации, визуализации, анализа запросов и прочих интересных вещей. Но вопрос в том, как должны все эти данные из подключённых к сети устройств и всех остальных источников попасть туда, где с ними можно делать всё вышеперечисленное? Сегодня мы запускаем то, что, на мой взгляд, является отличным решением данной проблемы: Wolfram Data Drop.



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

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

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

На прошлой неделе [статья опубликована в ноябре 2013] Twitter сошел с ума из-за того, что кто-то перевел почти 150 миллионов долларов за одну транзакцию в криптовалюте. Появление такого твита было в порядке вещей:



Транзакция 194 993 биткоинов стоимостью в 147 миллионов долларов порождает много тайн и спекуляций

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

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