Аперитив

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

while (n)
{
    ++count;
    n &= (n-1);
}

while (n)
{
    if (n&1)
        ++count;
    n >>= 1;
}

Упражнение: какое в среднем количество операций будет выполнено в первой и во второй реализации?

Блюдо

Пусть у нас есть n-битное число вида 2^i. Нам необходимо найти i за O(1).
Как это сделать? Пусть n = 2^k. Построим последовательность де Брёйна (de Bruijn) над алфавитом {0,1} для подстрок длины k.

Что такое последовательность де Брёйна?

В начале 2012 года по интернету гуляла видеозапись доклада Гарри Бернхардта на CodeMash под названием «WAT». На хабре были даже две хабрастатьи об этом докладе: раз, два. В этом выступлении рассказывалось про некоторые тонкости Ruby и JavaScript, которые кажутся нелогичными и вызывают реакцию: «WAT?».

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

Итак, сможете определить где подвох?

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



Ниже я расскажу о том, как делал этот девайс.

Введение

Common Lisp, а точнее, его объектная система, CLOS, предоставляет пользователю языка совершенно замечательный механизм, а именно, метаобъектный протокол.

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

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

Для чего он нужен? На самом деле, в зависимости от языка и объектной системы, список применений может быть практически безграничен. Это как добавление коду декларативности(аннотации в Java и аттрибуты в C#), так и разнообразная генерация кода и классов в рантайме(здесь можно вспомнить разнообразные persistance и ORM фреймворки), так и многое другое.

С моей лично точки зрения, лучше всего метаобъектные протоколы себя зарекомендовали со стороны закрепления паттернов проектирования на уровне объектной системы. Такие паттерны, как, скажем, синглтон, которые в языках без достаточно развитого ООП приходится снова и снова реализовывать методом copy-n-paste, в моем любимом Common Lisp создаются буквально из пары десятков строчек кода и переиспользуются в дальнейшем исключительно указанием метакласса^[1].

Тем не менее, в нижеследующем тексте я хочу сосредоточиться на кое-чем более интересном, а именно — на изменении правил работы самой объектной системы, самих ее основ. Именно добавление возможностей подобного изменения и было ключевой целью разработчиков метаобъектного протокола для Common Lisp.

Итак, дальнейший текст будет посвящен созданию прототипной объектной системы, подобной JavaScript, в Common Lisp, с использованием метаобъектного протокола и интеграцией ее в CLOS. Полный код проекта доступен на github^[2].

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

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

Балансировать структуру данных вероятностно проще, чем явно обеспечивать баланс. Для многих задач списки пропуска это более естественное представление данных по сравнению с деревьями. Алгоритмы получаются более простыми для реализации и, на практике, более быстрыми по сравнению со сбалансированными деревьями. Кроме того, списки с пропусками очень эффективно используют память. Они могут быть реализованы так, чтобы на один элемент приходился в среднем примерно 1.33 указатель (или даже меньше) и не требуют хранения для каждого элемента дополнительной информации о балансе или приоритете.

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

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

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

Надеюсь, что статья развлечет вас, хотя я буду писать четко и по делу.

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

В очередной раз надежды на обновление Стандартной модели разрушились после того, как в ЦЕРНе нашли бозон Хиггса. И несмотря на то, что, по мнению Стивена Хокинга, это открытие сделало физику скучнее, проблемы, которые Стандартная модель объяснить не может, всё еще остаются. Одна из них — какая частица может стать кандидатом на тёмную материю? Как вы знаете, она содержится во Вселенной, но увидеть её мы не можем.

И вот учёные в ЦЕРНе начинают новый эксперимент — SHiP (Search for Hidden Particles). Если такие частицы обнаружат, то Стандартную модель можно расширить. Это будет означать, что наше представление о структуре и эволюции Вселенной может поменяться. А учёные вполне могут претендовать на Нобелевскую премию. Проводить астрофизические исследования для SHiP будет космический телескоп Astro-H. Яндекс для этого эксперимента не только предоставит ЦЕРНу свои технологии машинного обучения: студенты и исследователи Школы анализа данных Яндекса будут работать совместно с его учёными.

Сотрудничество Яндекса и ЦЕРНа началось в 2011 году, когда мы предоставили ему свои сервера. В 2012 году мы разработали для организации поисковый сервис, который использовался в рамках одного из четырех основных экспериментов ЦЕРНа на Большом адронном коллайдере — Large Hadron Collider beauty experiment (LHCb). В 2013 году ученые-физики получили возможность использовать нашу собственную технологию машинного обучения — Матрикснет. Тогда же Яндекс стал ассоциированным членом европейского Центра ядерных исследований в рамках проекта CERN openlab.



Два года назад в Яндексе выступал Андрей Голутвин, научный консультант директора ЦЕРНа. Это было ровно за день до того, как было официально объявлено об обнаружении бозона Хиггса. А на прошлой неделе Андрей на специальном семинаре рассказал о новом эксперименте SHiP, в котором уже на этапе планирования предполагается использование технологий и знаний Яндекса. Лекция состоит из пяти частей:

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

Подробная расшифровка — под катом.

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

Я знал про них давно, но как-то скептически относился к бизнесу на базе Ардуино, когда рядом находится Китай, e-bay, таобао — где можно напрямую и достаточно недорого заказать Ардуино и другие комплектующие.

Но вот к нам в хакспейс попал новый набор «Матрешка Z», и я понял, что Амперка не просто продаёт Ардуино — они делают качественные образовательные наборы по электронике для начинающих.

Что же внутри?

В какой-то из весенних дней этого года я ехал в троллейбусе и листал комикс о Коше. В одном из выпусков была такая фраза «НО! Её можно понять, она же фракталами в горизонт перетекает, я бы тоже замешкался...». После этого я посмотрел в окно и понял, что если мы возьмём два подходящих дробно-линейных преобразования комплексной плоскости a(z) и b(z), и рассмотрим систему итерированных функций для a(z), b(z), a⁻¹(z), b⁻¹(z), взяв в качестве начального множества картинку с Кошем, то Кош будет перетекать фракталами в горизонт!

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

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

«В 1997 году Deep Blue обыграл в шахматы Каспарова.
В 2011 Watson обставил чемпионов Jeopardy.
Сможет ли ваш алгоритм в 2013 году отличить Бобика от Пушистика?»

Эта картинка и предисловие — из челленджа на Kaggle, который проходил осенью прошлого года. Забегая вперед, на последний вопрос вполне можно ответить «да» — десятка лидеров справилась с заданием на 98.8%, что на удивление впечатляет.

И все-таки — откуда вообще берется такая постановка вопроса? Почему задачи на классификацию, которые легко решает четырехлетний ребенок, долгое время были (и до сих пор остаются) не по зубам программам? Почему распознавать предметы окружающего мира сложнее, чем играть в шахматы? Что такое deep learning и почему в публикациях о нем с пугающим постоянством фигурируют котики? Давайте поговорим об этом.

Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life):

В одном мгновенье видеть Вечность,
Огромный мир — в зерне песка,
В единой горсти — бесконечность,
И небо — в чашечке цветка.

              сэр Уильям Блейк

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

              сэр Артур Конан Дойл "Этюд в багровых тонах"

Сегодня, я хочу поддержать почин уважаемого Unlimion и рассказать о попытке реставрации правил игры, считающейся, на сегодняшний день, древнейшей из известных игр, связанных с перемещением фишек по доске. Доски для этой игры были найдены в 1926-1927 г.г., знаменитым археологом сэром Леонардом Вулли, на раскопках развалин города-государства Ур в Месопотамии. Сама игра датируется 2600-2500 до н.э. Поскольку название игры до сих пор остаётся неизвестным, она именуется в честь города, в котором была найдена.

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

Данная статья составлена преподавателем Академического университета Валерием Исаевым по материалам практики по курсу функционального программирования.

Полагаю, ни для кого не секрет, что написание многопоточных приложений связано с целым рядом проблем, отсутствующих при разработке однопоточных программ.
Одна из проблем заключается в тестировании приложения.
Мы не можем контролировать порядок, в котором выполняются операции, следовательно, не поддается контролю и результат выполнения программы. Даже если мы получим ошибку, наступить на те же грабли второй раз будет не так-то просто.
Хочу предложить небольшой рецепт того, как можно протестировать многопоточное приложение.
Из ингредиентов нам понадобятся: haskell, QuickCheck, немного монад, соль/перец по вкусу.

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

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

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

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

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





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

Мэтт Паркер, отметившийся в проектах Numberphile и Standup Maths, в компании с командой Domino Computer Builders построили, наверное, самый медленный компьютер в мире из костей домино.


Немного деталей под катом.

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

Сразу раскрою мысль, вынесенную в заголовок. Использование потоков (также именуемых нити, треды, англ. threads) и средств прямой манипуляции ими (создание, уничтожение, синхронизация) для написания параллельных приложений оказывает столь же пагубное влияние на сложность алгоритмов, качество кода и скорость его отладки, какое вносило использование оператора Goto в последовательных программах.
Как когда-то программисты отказались от неструктурированных переходов, нам необходимо отказаться от прямого использования потоков сейчас и в будущем. И так же, как каждый из нас использует структурные блоки вместо Goto, вместо потоков должны использоваться структуры, построенные поверх них. Благо, все инструменты для этого появились во вполне традиционных языках.
^{Автор фото: Rainer Zenz}

В левой руке Морфеуса лежит 7 синих и 3 красных таблетки, а в правой 5 синих и 8 красных. Вы закрываете глаза и берете таблетку — она оказывается красной, однако вы не знаете из какой руки ее взяли. Какова вероятность, что вы взяли ее из правой руки?

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