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

Алгоритм

  13  x  19 ->     0
   6     38       19
   3     76 ->
   1    152 ->    95
   0    304      247
                 ^^^

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

Если число в левом столбце нечётное, мы добавляем число из правого столбца в нарастающую сумму. Изначально она будет равна нулю.

Затем в левом столбце ниже мы записываем число из заголовка, делённое пополам (с отбрасыванием остатка). 13 / 2 = 6. А во втором столбце мы пишем число, равное удвоению заголовка столбца, 19*2 = 38.

Поскольку число в левом столбце чётное, мы не увеличиваем нарастающую сумму.

(Скриншот из презентации: slideplayer.com/slide/3238789)

Приглашаем всех на открытую лекцию Computer Science центра, посвященную задаче выполнимости булевых формул — одной из самых известных и важных алгоритмических задач. Лекция пройдёт в рамках встречи со слушателями онлайн-курса «Алгоритмы: теория и практика. Методы». Время и место проведения: 25 декабря, 19:00, БЦ Таймс (г. Санкт-Петербург, ул. Кантемировская 2А, 4 этаж). Участие бесплатное, но требуется регистрация: goo.gl/IiNvV8

Задача выполнимости — каноническая трудная задача, по которой проводится огромное количество исследований: как практических, так и теоретических. В частности, этой задаче посвящена ежегодная международная конференция. Каждый год проходят соревнования программ для данной задачи (так называемых сат-солверов). Такие программы активно используются во многих прикладных областях. Буквально несколько месяцев назад Дональд Кнут дописал том 4B монографии «Искусство программирования», треть которого посвящена задаче выполнимости.

Привет, Хабр! В этой статье речь пойдет о таком не очень приятном аспекте машинного обучения, как оптимизация гиперпараметров. Две недели назад в очень известный и полезный проект Vowpal Wabbit был влит модуль vw-hyperopt.py, умеющий находить хорошие конфигурации гиперпараметров моделей Vowpal Wabbit в пространствах большой размерности. Модуль был разработан внутри DCA (Data-Centric Alliance).

Для поиска хороших конфигураций vw-hyperopt использует алгоритмы из питоновской библиотеки Hyperopt и может оптимизировать гиперпараметры адаптивно с помощью метода Tree-Structured Parzen Estimators (TPE). Это позволяет находить лучшие оптимумы, чем простой grid search, при равном количестве итераций.

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

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

«The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». Или, по-русски: «Десятичное число 585 в двоичной системе счисления выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-й подобный палиндром».

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

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

Как конкретно ведут себя инсайдеры на бирже? Зависят ли их сделки от занимаемой должности в компании (генеральный или финансовый директор), меняется ли поведение инсайдеров с течением времени (повлиял ли на него, к примеру, кризис 2008 года)?

Группа исследователей из технологического института Джорджии провели исследование на основе данных о 12 млн транзакций, совершенных 370 тысячами инсайдеров в период с 1986 по 2012 год. Целью этой работы было выявление паттернов поведения игроков на фондовом рынке, с помощью которых регулирующие органы могли бы обнаруживать и пресекать незаконную инсайдерскую торговлю. Мы представляем вашему вниманию основные моменты этого документа.

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

А еще сегодня 16 декабря, день рождения Иоганна Радона, австрийского математика, ректора Венского университета, который в 1917 году ввел интегральное преобразование функции многих переменных, родственное преобразованию Фурье, используемое сегодня во всех томографах.

Иоганн Радон был профессором 6 университетов (а в одном из них даже без кафедры), был президентом Австрийского математического общества. В Австрии в честь него назвали «Институт вычислительной и прикладной математики» и медаль.

О том, как проходила разработка софта для томографа и какие задачи решались в процессе — под катом.

Привет Хабр,

Если вам давно было интересно, как Big Data применяется в разных областях бизнеса, науки и государственного управления и это хотелось услышать от самих людей, которые этим занимаются, то добро пожаловать на Фестиваль Данных, который будет проходить 19 декабря на Выставке Высоких Технологий SMIT в Музее Москвы.

В течение нескольких часов работы Фестиваля ведущие эксперты отрасли из Yandex, Школы Данных «Билайн», Data-Centric Alliance, Авито, ГУП «НИ и ПИ Генплана Москвы, НИУ ВШЭ расскажут гостям выставки о перспективах использования анализа данных в ближайшие несколько лет.

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

Под катом много картинок, аккуратнее с траффиком.

Я пишу мультипротокольный (но не мультиплатформенный, увы, сейчас только windows) мессенджер, который пока что поддерживает только протокол TOX. Но речь не о мессенджере, а о его интерфейсе, а если точнее, об основной его функции — AlphaBlend. Да, я решил написать свой велосипед GUI. Ну а какой современный GUI без полупрозрачных элементов и плавных закруглений? Поэтому остро встала необходимость смешивать изображения с учетом полупрозрачности, т.е. альфа-смешивание или alpha blending. К счастью, в windows GDI такая функция имеется — AlphaBlend. Работает как надо, делает то что нужно. Но я тот еще строитель велосипедов, и мне стало интересно, смогу ли я написать такую же функцию, но более быструю. Результат моих трудов под катом.

В различного рода сложности реализуемых алгоритмов при программировании МК, всегда возникают рутинные циклические и не очень задачи. Одни требуют повышенной точности, другие таким критерием не обязаны обладать. Аппаратных таймеров на борту МК может быть приличное количество, например STM32F4 — аж 14 штук, и это не считая SysTick (системного), а в других и пара тройка за счастье: тот же PIC16, например.

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

Однажды в студеную зимнюю пору… ровно год назад, у нас появилась нетривиальная задача. Есть экран на электронных чернилах, есть процессор 16МГц (да-да, во встраиваемой электронике, особенно сверхнизкого энергопотребления, встречаются и такие) и совсем нет памяти. Ну, т.е. килобайтов 8 RAM и 256 Flash. Килобайтов, Карл. И в эти унылые килобайты необходимо запихнуть несколько изображений 800х600 в четырех оттенках серого. Быстро перемножив в уме 800 на 600 и на 2 бита на пиксель получаем 120 тысяч байтов. Несколько не влезает. Надо сжимать.

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

Данная статья — иллюстрация, каким образом битовые трюки могут быть использованы не только в задачах на собеседованиях, но и при решении реальных задач. В статье дано описание одного метода быстрой генерации ходов в русских шашках на основе магических битбордов (magic bitboard). Битборды — представление позиции в виде нескольких беззнаковых целых чисел, каждый бит которого отвечает за состояние некоторого элемента игры, например клетки. Обычно использование битбордов даёт выигрыш по производительности и по объёму используемой памяти, но связано с более изощрённым программированием. При этом часто возникает задача получения значения определённых бит в битборде, например, для последующего обращения к таблице. Есть два основных подхода к решению этой задачи. Первый — использование и поддержка избыточного представления в виде дополнительных битбордов с перенумерацией битов. Такие битборды асто называют вращаемые. Второй способ — умножение на магическую константу, сдвиг и обращение к таблице. О таких магических битбордах и пойдёт речь в этой статье.

Дата: 10 декабря 2015 года, начальнику отдела №8 от следователя id1033.
Тип запроса: инициация расследования.
Причина: в связи с подозрительной активность юзера id1596704383 в период с 30 июля 2005 по 9 декабря 2015, прошу предоставить необходимые ресурсы по Форме 2 и наделить полномочиями в соответствии с протоколом «Observer-z».
Обоснование: на основе данных, полученных из открытых источников системой аналитики ПОПСИИ-2014 («Можжевельник») были выявлены уникальные сигнатуры (присвоены идентификаторы с sig8876 по sig8951), свидетельствующие об активном сборе и аналитике материалов из сети из разряда «Первоисточник-18». Согласно распоряжению от 20 ноября 2015, докладывать незамедлительно о любой активности в реальности связанной с «Первоисточник-18», уведомляю, что 10 декабря в 16-00 по московскому времени, юзер id1596704383 перешел к активным действиям в реальности.

К запросу прилагаю материалы, перехваченные из черновиков юзера id1596704383 10 декабря 2015 года на публичном ресурсе «Habrahabr».


«Я — дьявол или ангел» (Ада Лавлейс, из письма Чарльзу Бэббиджу 1843)

200 лет со дня рождения Ады Лавлейс, первого программиста человечества

10 декабря 1815 года у поэта Байрона родилась дочка, которая в 1842 году в свои 27 лет написала первую программу для вычислительной машины (паровой) Бэббиджа.

«Суть и предназначение машины изменятся от того, какую информацию мы в нее вложим. Машина сможет писать музыку, рисовать картины и покажет науке такие пути, которые мы никогда и нигде не видели.» Ада Лавлейс

Ada — язык программирования, созданный в 1979—1980 годах в ходе проекта Министерством обороны США с целью разработать единый язык программирования для встроенных систем (то есть систем управления автоматизированными комплексами, функционирующими в реальном времени). Имелись в виду, прежде всего, бортовые системы управления военными объектами (кораблями, самолётами, танками, ракетами, снарядами и т. п.). 10 декабря 1980 года был утверждён стандарт языка.

Возможно, многие из читателей пытались собрать кубик Рубика 3×3 самостоятельно, но после множества неудачных попыток либо бросали это занятие, либо искали готовое решение. Целью этой статьи является показать на примере кубика Рубика что найти решение любой (из класса решаемых) задачи самостоятельно, есть вполне выполнимая задача для каждого, если при этом руководствоваться определенным набором правил. Данное решение получено мною за 10 часов, плюс этого алгоритма что он не требует запоминать сложные комбинации и длительное время тренироваться — достаточно собрать данным способом всего несколько раз.

Привет, хабр!

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

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

Введение

Допустим у нас есть некоторое множество, которое состоит из N элементов. Будем считать, что элементы пронумерованы от нуля до N-1. Набор k-элементных подмножеств данного множества (сочетаний) можно представить либо в виде массива индексов длины k. Либо в виде последовательности из N бит, в которой установлено ровно k из них. У Дональда Кнута в его TAoCP приводится алгоритм генерации сочетаний в лексикографическом порядке, когда сочетания заданы в виде массива индексов. Мы попробуем перенести этот алгоритм на случай битовых масок.

Часть 1

Давай сразу код!

import numpy as np
X = np.array([ [0,0,1],[0,1,1],[1,0,1],[1,1,1] ])
y = np.array([[0,1,1,0]]).T
alpha,hidden_dim = (0.5,4)
synapse_0 = 2*np.random.random((3,hidden_dim)) - 1
synapse_1 = 2*np.random.random((hidden_dim,1)) - 1
for j in xrange(60000):
    layer_1 = 1/(1+np.exp(-(np.dot(X,synapse_0))))
    layer_2 = 1/(1+np.exp(-(np.dot(layer_1,synapse_1))))
    layer_2_delta = (layer_2 - y)*(layer_2*(1-layer_2))
    layer_1_delta = layer_2_delta.dot(synapse_1.T) * (layer_1 * (1-layer_1))
    synapse_1 -= (alpha * layer_1.T.dot(layer_2_delta))
    synapse_0 -= (alpha * X.T.dot(layer_1_delta))

Часть 1: Оптимизация

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

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

Когда мы общаемся с нашими заказчиками, то, будучи специалистами в этой области, активно используем соответствующую терминологию, в частности слово «распознавание». При этом слушающая аудитория, воспитанная на Cuneiform и FineReader, часто вкладывает в этот термин именно задачу сопоставления вырезанного участка изображения некоторому числу (коду символа), которая в наши дни решается нейросетевым подходом и является далеко не первым этапом в задаче распознавания информации. В начале необходимо локализовать карточку на изображении, найти информационные поля, выполнить сегментацию на символы. Каждая перечисленная подзадача с формальной точки зрения является самостоятельной задачей распознавания. И если для обучения нейронных сетей существуют зарекомендовавшие себя подходы и инструменты, то в задачах ориентации и сегментации каждый раз требуется индивидуальный подход. Если вам интересно узнать про подходы, которые мы использовали при решении задачи распознавания банковской карточки, тогда добро пожаловать под кат!

В первой части я сказал, что хеш таблица это немного LIST, SET и SORTED SET. Судите сами — LIST состоит из ziplist/linkedlist, SET состоит из dict/intset, а SORTED SET это ziplist/skiplist. Мы уже рассмотрели словарь (dict), а во второй части статьи будем рассматривать структуру ziplist — вторую наиболее часто применимую структуру под капотом Redis. Посмотрим на LIST — вторая часть его «кухни» это простая реализация связного списка. Это пригодится нам, чтобы внимательно рассмотреть часто упоминаемый совет об оптимизацию хеш таблиц через их замену на списки. Посчитаем сколько памяти требуется на накладные расходы при использовании этих структур, какую цену вы платите за экономию памяти. Подведём итоги при работе с хеш таблицами, при использовании кодировки в ziplist.

В прошлый раз мы закончили на том, что сохранённые с использованием ziplist 1,000,000 ключей заняли 16 мб оперативной памяти, тогда как в dict эти же данные потребовали 104 мб (ziplist в 6 раз меньше!). Давайте разбираться какой ценой:

— Не могли бы вы построить нам статистическую модель?
— С удовольствием. Можно посмотреть на ваши исторические данные?
— Данных у нас ещё нет. Но модель всё равно нужна.

Знакомый диалог, не правда ли? Далее возможны два варианта развития событий:

A. «Тогда приходите, когда появятся данные.» Вариант рассматриваться не будет как тривиальный.
Б. «Расскажите, какие факторы по вашему мнению наиболее важны.» Остаток статьи про это.

Под катом рассказ о том, что такое improper model, почему их красота устойчива и чего это стоит. Всё на примере многострадального набора данных о выживании пассажиров Титаника.