Алгоритмы *

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

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

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

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

На прошлой неделе Phys.org разразился новостью: стартап LightOn предложил альтернативу центральным процессорам (CPU) и графическим процессорам (GPU) для решения задач анализа больших данных. Авторский коллектив базируется в университете Пьера и Марии Кюри, Сорбонне и всех прочих правильных местах во Франции. Решение основано на оптической аналоговой обработке данных «со скоростью света». Звучит интересно. Поскольку в пресс-релизе не было никаких научно-технических подробностей, пришлось поискать информацию в патентных базах данных и на сайтах университетов. Результаты расследования под катом.

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

Итак, первое моё знакомство с языками программирования состоялось в школе, и был это Бэйсик. С тех пор с языками программирования я не пересекался. Прошло больше 20 лет и мне понадобилось изучить один из современных языков программирования. Всем критериям предъявляемым мной языку программирования, которые я смог сформулировать на тот момент, полностью удовлетворял C#. Засучив рукава, я принялся его изучать и у меня появилась возможность оценить насколько изменились языки программирования за это время.

Многое было привычно, если не по внешнему виду, то по концепции: переменные, циклы, операторы ветвления… А что-то было совсем новым: ООП с его классами (полями, методами, свойствами), наследованием и т. д.
Конечно, многое порадовало. Классы теперь позволяют заниматься распределением обязанностей: Так, ты мне принеси «то»; Ты сделай «это»; Ты посчитай мне «это», результат сообщишь. Это очень напоминает наше взаимодействие с окружающей средой. Например, зашли в прачечную, отдали грязное постельное бельё, забрали чистое. Зашли в ателье, отдали ушить брюки, забрали готовый вариант. Зашли в закусочную, сделали заказ, получили завтрак. Очень удобно и наглядно.
Но вернёмся с теме статьи. Я никак не ожидал спустя 20 лет увидеть в языках программирования некоторые вещи:

Если вы знаете, почему после выполнения `hset mySey foo bar` мы потратим не менее 296 байт оперативной памяти, почему инженеры instagram не используют строковые ключи, зачем всегда стоит менять hash-max-ziplist-entries/hash-max-ziplist-val и почему тип данных, лежащий в основе hash это и часть list, sorted set, set — не читайте. Для остальных я попробую об этом рассказать. Понимание устройства и работы хеш таблиц в Redis критически важно при написания систем, где важна экономия памяти.

О чём эта статья — какие расходы несёт Redis на хранения самого ключа, что такое ziplist и dict, когда и для чего они используются, сколько занимают в памяти. Когда hash хранится в ziplist, когда в dicth и что нам это даёт. Какие советы из модных статей об оптимизации Redis не стоит воспринимать всерьёз и почему.

Продолжаем серию аналитических исследований востребованности навыков на рынке труда. В этот раз благодаря Павлу Сурменку sharky мы рассмотрим новую профессию – Data Scientist.

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

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

Примерами могут служить последняя цифра номера кредитной карты, девятая цифра VIN автомобилей, продаваемых в в США, или последняя цифра ISBN.

Алгоритм контрольной цифры ван Дамма — относительно новый и потому малоизвестный. Он опубликован 2004 году.

Алгоритм обнаруживает все ошибки в одной цифре и все одиночные перестановки соседних цифр. Он заметно проще, чем сравнимый по возможностям алгоритм Верхуффа, и не требует использования специальных символов (таких как X в 10-значном ISBN).

Важное уточнение — калькулятор обычный, без кнопки sin. Как в бухгалтерии или на рынке.



Под катом три разных варианта решения из разных эпох, от древнего Самарканда до США времён холодной войны.

Приятная новость для всех, у кого нет возможности обучаться в Технопарке, Техносфере или Технотреке: теперь курсы этих проектов доступны в виде онлайн-курсов на платформе Stepic! На сегодняшний день доступна запись по пяти дисциплинам:

• Алгоритмы и структуры данных — запуск 8 декабря.
• Подготовительная программа по программированию на С/C++ — запуск 9 декабря.
• Многопоточное программирование на С/С++ — запуск 10 декабря.
• Hadoop. Система для обработки больших объемов данных — запуск 10 декабря.
• Разработка веб-сервиса на Java (часть 1) — запуск 11 декабря.

Со временем количество курсов будет увеличено.

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

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

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

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

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


*Подробно опишу правила еще раз в разделе про ИИ.

Читателей статьи условно разделяю на три группы.

1. Начали программировать несколько часов назад.
   Вам будет сложно, лучше предварительно пройдите какой-нибудь небольшой курс по введению в Android-разработку, разберитесь с двумерными массивами и интерфейсами. А потом загрузите проект с гитхаба. Комментарии и эта статья помогут вам разобраться, что и как работает.
2. Уже умеете программировать, но еще не можете назвать себя опытными.
   Вам будет интересно, потому что вы очень быстро сможете сделать свою игру. Я взял на себя грязную работенку по построению логики игры и ui-составляющей, вам же оставляю творческую часть. Вы можете сделать другой режим игры (2 на 2, онлайн и т.п.), изменить алгоритмы бота, создать уровни и т.д.
3. Опытные.
   Вам может быть интересно подумать над ИИ — написать его не так легко, как кажется на первый взгляд. Так же я был бы очень рад получить от вас замечания по коду — уверен, далеко не все я сделал оптимально.

В июне 2013 года АНБ опубликовало описание двух лёгких блочных шифров — Simon и Speck [1].

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

Прошло два года, практических атак ни на Simon, ни на Speck не появилось [2], а преимущества (простота и гибкость) — остались.

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

Я хочу рассказать о разработанном мной сервисе реферирования новостных текстов на английском, русском и немецком языках.

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

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

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

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

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

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

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

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

В этой статье мы рассмотрим способы применения машинного обучения в сфере высокочастотного трейдинга (HFT) и анализа микроструктурных данных. Машинное обучение – это замечательный раздел информатики, использующий модели и методы из статистики, теории алгоритмов, теории вычислительной сложности, искусственного интеллекта, теории управления и огромного числа других дисциплин. Основным объектом исследования машинного обучения являются эффективные алгоритмы, позволяющие создать хорошие предсказательные модели на основании больших наборов данных – именно поэтому оно так хорошо подходит для решения задач высокочастотного трейдинга: заключения сделок и расчета показателя «альфа».

Когнитивная система IBM Watson теперь может обсуждать различные проблемы людей не хуже любого эксперта. Команда специалистов из Технологического университета Джорджии (США) совместно с представителями IBM в течение шести месяцев обучали когнитивную систему понимать окружающий мир и находить пути решения некоторых важных проблем.

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

О чём статья

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

Дайте код!

X = np.array([ [0,0,1],[0,1,1],[1,0,1],[1,1,1] ])
y = np.array([[0,1,1,0]]).T
syn0 = 2*np.random.random((3,4)) - 1
syn1 = 2*np.random.random((4,1)) - 1
for j in xrange(60000):
    l1 = 1/(1+np.exp(-(np.dot(X,syn0))))
    l2 = 1/(1+np.exp(-(np.dot(l1,syn1))))
    l2_delta = (y - l2)*(l2*(1-l2))
    l1_delta = l2_delta.dot(syn1.T) * (l1 * (1-l1))
    syn1 += l1.T.dot(l2_delta)
    syn0 += X.T.dot(l1_delta)

Слишком сжато? Давайте разобьём его на более простые части.

Другие статьи цикла:
Здравствуйте, я Meklon и я кофеин-зависимый
Компот из кофейных сухофруктов. Знакомимся с каскарой — лучшим другом велосипедиста

Продолжаю кофейную тематику, которую я начал еще на geektimes: Здравствуйте, я Meklon и я кофеин-зависимый. Сегодня мы будем творить непотребства с софтом для биоинженерных задач — CellProfiler. Нормальные люди им считают клетки, плазмиды, экспрессию белка и прочие нужные вещи. Мы долбанутые, поэтому будем проводить гранулометрический анализ помола по микрофотографии, бить кофе статическим электричеством и думать, как прицепить к этому безобразию фен. Ну и конечно нам потребуется скотч для получения графена картины распределения частиц.

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

Заранее предупрежу: довольно много картинок.

В данной статье речь пойдёт о реализации игры «Жизнь» на логических элементах в симуляторе «Atanua».