12 мая ЦЕРН объявил «Higgs Boson Machine Learning Challenge», конкурс на лучший алгоритм по поиску событий с участием бозона Хиггса в наборе экспериментальных данных. Конкурс продлится до 15 сентября, победителей ждут денежные призы от $2000 до $7000. Удачное решение может быть интегрировано в реальный процесс обработки данных с детектора ATLAS. Для участия в конкурсе не нужны специальные знания в физике элементарных частиц.

Что такое «Инверсная кинематика»?

Задачей инверсной кинематики является поиск такого набора конфигураций сочленений, который обеспечил бы максимально мягкое, быстрое и точное движение к заданным точкам. Однако, множество существующих ныне методов страдают от таких недостатков как высокая вычислительная сложность и неестественность результирующих поз. В этой статье описан новый (вероятно, на момент написания статьи — 2010 г.) эвристический метод под названием «Метод прямого и обратного следования» ( Forward and Backward Reaching Inverse Kinematics, далее просто FABRIK),
FABRIK избегает использования вращений и матриц в пользу непосредственного получения точки на прямой. Благораря этому, дело обходится всего несколькими итерациями, имеет низкую стоимость вычислений и визуально естественную позу в результате. FABRIK так-же без проблем справляется с наложением ограничений а так-же использованием нескольких цепей и/или конечных точек. Именно об этом методе этот пост.

Не всё так просто

На первый взгляд, JavaScript может показаться достаточно простым языком. Возможно, это из-за достаточно гибкого синтаксиса. Или из-за схожести с другими известными языками, например, с Java. Ну или из-за достаточно малого количества типов данных, по сравнению с Java, Ruby, или .NET.

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

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

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

Есть некоторое множество объектов, и некоторое множество тегов. Каждый объект может содержать несколько тегов. Какие-то теги очень редкие, а какие-то встречаются часто. Одному объекту один тег может быть сопоставлен несколько раз.
Новые объекты, теги и связи между ними непрерывно добавляются.
Задача — очень быстро отвечать на вопросы вида: «сколько есть объектов, у которых есть тег А или B, но нету тега С» и похожие. На такие запросы хотелось бы отвечать за десятые доли секунды, при этом не останавливая загрузку данных.

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

SELECT 
    COUNT(*) 
FROM (
    SELECT 
        object_id, 
        (MAX(tag == A) OR MAX(tag == B)) AND MIN(tag != C) AS good
    FROM tags
    WHERE tag IN (A, B, C)
    GROUP BY object_id
) WHERE good == 1;

Чтобы такой запрос выполнялся быстро, мы разбили данные между серверами кластера по object_id, а внутри каждого сервера отсортировали их по тегам. Таким образом сервер, выполняющий запрос, может отправить запрос без изменений на все сервера с данными, а затем просто сложить их результаты. На каждом сервере с данными для выполнения запроса достаточно найти строки для тегов A, B и C (а так как данные по тегу отсортированы, это быстрая операция), после чего выполнить запрос за один проход по этим строкам. Худший тег имеет несколько десятков миллионов объектов, несколько десятков миллионов строк обработать за десятые доли секунды видится возможным.
Стоит отметить, что подзапрос содержит GROUP BY object_id. GROUP BY в данной ситуации можно выполнить несколькими способами, например, если данные после тега отсортированы по object_id, то можно выполнить что-то похожее на merge sort. В данной ситуации, однако, мы данные по object_id не отсортировали, и оптимизатор разумно решил, что для выполнения GROUP BY надо построить хеш-таблицу.

Мы загрузили все данные в кластер, и запустили запрос. Запрос занял 25 секунд.

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

Возьмём, к примеру, такой код:

System.out.println("Hello World!");

Он транслируется в три инструкции байткода: getstatic (для загрузки статического поля System.out), ldc (для загрузки константной строки «Hello World!») и invokevirtual (для выполнения виртуальной функции println). Попробуйте прикинуть, сколько констант нужно для того, чтобы этот код работал.

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





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

В этой моей статье, как и в предыдущей рассматривается цифровая схемотехника с точки зрения программиста. Но в этот раз будет разобрана «более алгоритмическая» задача сортировки чисел, с разбором verilog-кода. Рассматриваемое аппаратное решение позволяет отсортировать n чисел за время 2*n. На картинке ДПВ показан вывод на монитор от тестового проекта для ПЛИС, там каждой линии соответствует один тик сортировщика, сначала n тиков случайные числа записываются в сортировщик, затем n тиков выводятся числа отсортированные.

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

На конференции SIGGRAPH ASIA 2013 Thomas Geijtenbeek, Michiel van de Panne и Frank van der Stappen представили метод симуляции физики двуногих существ на основе мускульного контроля с оптимизацией перемещения мышц и других контролируемых параметров. В результате был получен метод управления передвижением для множества двуногих существ. Все приводящие в действие силы являются результатом работы симулированных 3D-мускул и модели нейронных задержек, включенных в цепи ответных реакций. Перечисленные контроллеры генерируют вращающие движения, которые учитывают биомеханические ограничения. Контроллеры находят различные походки на основе требуемой скорости, могут учитывать неровные поверхности и внешние возмущения, способны следовать в задаваемом направлении.

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



Ученые генетически модифицировали бактерию сальмонеллы, которая тянется к опухолям, используя вещества, выделяемые раковыми клетками. В бактерии находятся микроскопические роботы, где-то 3 микрометра размером, каторые автоматически выпускают капсулы, наполненные лекарствами, как только бактерия достигает опухоли.

Всем программистам рано или поздно приходится передавать данные. Ни для кого не секрет, что библиотек сериализации в Java существует примерно >9000, а в C++ они вроде и есть, а вроде их и нет. К счастью для большинства, несколько лет назад появился Google Protobuf, который принёс достаточно удобный способ определять структуры данных и быстро завоевал всенародную любовь. Это была фактически первая, доступная широким массам библиотека, позволяющая гонять по сети готовые структуры данных, не связываясь при этом с чем-то вроде XML. На дворе был 2008 год.

Вернёмся немного назад. В 2006 году простой индийский программист (как бы подозрительно это ни звучало!) Анил Мадхавапедди, один из самых известных сейчас в мире OCaml-разработчиков и автор свежевышедшей книги Real World OCaml, защищал в Кембридже кандидатскую диссертацию. Именно о ней я сегодня вам и расскажу.

Анил сразу пошёл дальше, чем Google. Он сразу подумал, для чего люди обычно пересылают по сети какие-то формализованные структуры данных? Чтобы реализовать какой-то протокол. А что такое протокол? Это какой-то конечный автомат. А где мы можем взять хороший пример сложного, хорошо спроектированного и проверенного временем протокола? Да прямо в обычном сетевом стеке! Итак, были взяты набор сетевых структур данных и протоколов: Ethernet frame, IPv4, ICMP, TCP, UDP, SSH, DNS и DHCP и постановка задачи: большая часть этих протоколов (особенно SSH и DNS) реализуются, что называется «руками», а хочется, чтобы не было типичных для C переполнений буфера, все переходы совершались автоматически, это всё можно было верифицировать, и чтобы работало быстро, а не как обычно.

Поскольку никто не будет читать диссертацию, сразу скажу: это более чем удалось. По результатам работы были написаны референсные реализации DNS и SSH-сервера и произведено сравнение с BIND и OpenSSH. OCaml-реализации давали по сравнению с традиционными прирост производительности от незначительного, до почти двухкратного. Кроме того была найдена ошибка в RFC на SSH (рабочая группа была уведомлена и RFC исправлен). О том, что было сделано, и как с этим жить, читайте под катом.

Компания Mozilla порадовала новостью об очередном улучшении производительности Asm.js. Этот промежуточный язык обеспечивает исключительно высокую скорость выполнения кода, написанного на языках вроде C и C++, является свободной альтернативой Google Native Client и работает в любом браузере (хотя в Firefox — быстрее всего).

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

Некоторые из проведённых оптимизаций небольшие и незначительные, а другие более серьёзные. Например, Firefox недавно научился оптимизировать некоторые операции с плавающей запятой таким образом, что вместо чисел float64 вычисления осуществляются с менее точными числами float32, что даёт очень большую прибавку в производительности. Соответствующее изменение было внесено в Asm.js, компилятор Emscripten и движок SpiderMonkey.

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

Итак, вернемся к теме поста. Я давно хотел немного больше узнать о комплексных числах, а не только то, что корень из минус единицы равен i. Особенно вызывали интерес фигуры имеющие фрактальную структуру, хотелось понять, что это значит, и как сделать такую визуализацию. Где то на полке стояла книжка по ТФКП, а так же закончился курс по комплексному анализу на курсере, и появилось немного свободного от работы времени. Приступим.

^{(источник)}

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

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

Привет, %username%!
Я расскажу и покажу как работает основа генерации денег в криптовалютах — майнинг. Как создается первый блок, новые блоки и как появляются деньги из ниоткуда.
Чтобы было проще понять, мы напишем свой импровизированный майнер для импровизированной криптовалюты HabraCoin.

Системы IBM Blue Gene помогали определить структуру генома человека, копировали силу мозга, запускали самолеты, определяли опухоли, предсказывали климатические изменения, определяли месторождения горючих полезных ископаемых и др.

Сейчас мы можем добавить в этот список моделирование 15 000 пузырьков. Звучит несерьезно? Но на самом деле это исследование получило премию Гордона Белла, вручаемую за достижения в области высокопроизводительных вычислений.

Конденсат Бозе-Эйнштейна — это агрегатное состояние вещества, предсказанное и описанное индийским физиком Шатьендранатом Бозе и Альбертом Эйнштейном ещё в середине 20-х годов прошлого века. Тем не менее, впервые бозе-конденсат был получен экспериментально только в 1995-м. Физики Эрик Корнелл, Карл Виман и Вольфганг Кеттерле получили за это Нобелевскую премию. Им удалось получить конденсат из атомов рубидия и натрия, охлаждённых до нескольких десятков нанокельвинов. В 2010 году был получен конденсат из фотонов, причём при комнатной температуре.

8 декабря этого года группа учёных из лаборатории IBM Research в Цюрихе опубликовала работу, в которой описан способ получения такого конденсата с использованием плёнки из люминесцентного полимера, подобного тому, что используется в OLED-дисплеях. Это значительно удешевляет процесс и приближает перспективу промышленного использования оптоэлектронных устройств на основе конденсата Бозе-Эйнштейна в высокопроизводительных вычислениях. Раньше для получения конденсата нужны были сверхчистые кристаллы.

Японский кроссворд — это известная головоломка, ответом которой является рисунок. Что это такое и как это решать, можно почитать на Википедии. Я хочу показать, как можно написать программу, которая будет решать японский кроссворд в системе Wolfram Mathematica путем перебора.

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

Это достаточно вольный перевод статьи. Дело в том, что несмотря на конструкции в одну строчку, материал сложен для понимания.
Беря во внимание то, что в комментариях Прелюдия или как полюбить Haskell просили, чтобы код был понятный, я внёс достаточно ремарок, и, надеюсь, код будет понятен и тем, кто далёк от Хаскеля.

Давайте начнём с самого трудного — с самого заголовка: многим непонятны все его слова.
Хаскель — это чистый и ленивый функциональный язык.
Лёб — это немецкий математик, о котором мы поговорим чуть позже.
Ну, и наконец, самое интересное — странные петли.

Странные петли — это запутанные категории, когда двигаясь вверх или вниз в иерархической системе, находишь то же самое, откуда начал движение.
Зачастую такие петли содержат само-референтные ссылки.
Например, подобной странной петлёй обладает рекурсивные акронимы: «PHP — PHP: Hypertext Preprocessor».
Ну, и на сегодняшний день наиболее загадочным словом, содержащим странные петли, является понятие «я».

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

Немецкий математик Лёб мигрировал в 39-м году ХХ-го столетия в Великобританию. Лёб, в частности, развивал математическую логику и миру прежде всего известен Теоремой Лёба. Это теорема развивала труды Гёделя о неполноте математики. Теорема Лёба о взаимосвязи между доказуемостью утверждения и самим утверждением, она гласит, что

во всякой теории, включающей аксиоматику Пеано (аксиоматика о натуральных числах), для любого высказывания P доказуемость высказывания «если доказуемо P, тогда P истинно» возможна только в случае доказуемости самого высказывания P.

Всю эту сложность высказывания можно записать символически:


Можно ли такую функцию написать на Хаскеле?! Можно! И всего в одну строчку!