Я хотел бы подарить сообществу Хабра статью, в которой стараюсь дать достаточно полное описание подходов к алгоритмам подсчёта единичных битов в переменных размером от 8 до 64 битов. Эти алгоритмы относятся к разделу так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью многих программистов. Я хочу показать, что в основах этой алхимии нет ничего сложного, и вы даже сможете разработать собственные методы подсчёта единичных битов, познакомившись с фундаментальными приёмами, составляющими подобные алгоритмы.

Многие студенты, впервые сталкиваясь с описанием какой-нибудь хитроумной штуки, вроде алгоритма Кнута – Морриса – Пратта или красно-чёрных деревьев, тут же задаются вопросами: «К чему такие сложности? И это, кроме авторов учебников, кому-нибудь нужно?». Лучший способ доказать пользу алгоритмов – это примеры из жизни. Причём, в идеале – конкретные примеры применения широко известных алгоритмов в современных, повсеместно используемых, программных продуктах.



Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.

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

Интервьюер: Мы ищем шеф-повара во французский ресторан. Расскажите о своем опыте работы.

Соискатель: Можно сказать, что у меня уже 20 лет профессионального опыта. Я занимаюсь готовкой с 7 лет. Когда мама уходила на работу — я сам разогревал себе пиццу в микроволновке.

— Что такое векторное управление?
— Держать ток под 90 градусов.

Термин «векторное управление» электродвигателями знаком всем, кто хоть как-то интересовался вопросом, как с помощью микроконтроллера управлять двигателем переменного тока. Однако обычно в любой книге по электроприводу глава про векторное управление находится где-нибудь ближе к концу, состоит из кучи волосатых формул с отсылками ко всем остальным главам книги. Отчего разбираться в этом вопросе совсем не хочется. И даже самые простые объяснения всё равно держат путь через дифференциальные уравнения равновесия, векторные диаграммы и кучу другой математики. Из-за чего появляются примерно вот такие вот попытки как-то закрутить двигатель без использования мат.части. Но на самом деле векторное управление – это очень просто, если понимать принцип его работы «на пальцах». А там уже и с формулами разбираться в случае надобности будет веселее.

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

Го или Ур? Можно долго спорить, какая из игр древнее, но победит, в этом противостоянии, скорее всего, Манкала. Археологи предпочитают иметь дело с материальными свидетельствами, но как только речь заходит о настольных играх, всё быстро уходит в область предположений. Было найдено немало досок, но гораздо меньше сведений о том, как на них играть. Древние не утруждали себя детальным описанием правил.

С Манкалой ситуация прямо противоположная. Это не одна игра, а весьма многочисленное семейство. В одной только Западной Африке, счёт идёт на десятки (если не на сотни) разновидностей. Доска (как материальный артефакт) для таких игр не обязательна. Достаточно взять пригоршню камушков и выкопать несколько ямок в песке. Не удивительно, что археологи испытывают затруднения с определением возраста этих игр. Им попросту нечего искать! Но для внимательного исследователя «настольных игр», манкалы не менее интересны, чем птицы семейства пересмешниковых для Чарлза Дарвина.

Израильские ученые Шимон Ивэн (Shimon Even) и Ишай Мансур (Yishay Mansour) еще в 1997 году задались вопросом: насколько минимальной конструкцией может обладать стойкий блочный шифр? Под минимальностью они подразумевали число конструктивных элементов в схеме шифра, а под стойкостью — любую (формально верную) оценку снизу сложностей атак на этот шифр. Как говорится, под катом — описание минимального (и по сей день) блочного шифра с доказуемой стойкостью.

Здравствуйте, любители нашего хаброблога и прочие читатели!

Мы планируем вновь отметиться на поле неувядающего Node.js и рассматриваем возможность издания этой книги:



Поскольку вполне понятен читательский интерес «а как он впихнул все это в двести страниц, и зачем мне это нужно»? под катом предлагаем перевод доскональной статьи Томислава Капана о том, зачем на самом деле нужен Node.js.

Небольшой отчет о том, как мы решали ICFP Contest 2015. Мы участвовали в данном соревновании впервые, однако результат получился довольно неплохой. Можно поискать нас в таблице промежуточных результатов под именем «WILD BASHKORT MAGES». Финальные результаты ожидаются в течение нескольких ближайших недель, когда организаторы протестируют все решения на полном наборе тестов.



В этом году в качестве задачи предлагалось написать решалку (или ИИ, кому как удобнее) для гексагонального тетриса. Все как в обычном тетрисе — укладываем фигурки, убираем заполненные строки, получая за это очки. Решение должно работать для разных размеров игрового поля и укладываемых фигурок произвольной конфигурации. Команды действий с фигурками (перемещения и повороты) кодируются обычными символами, в итоге решением является строка команд. За специальные секретные последовательности символов в строке-решении, называемые power words, даются дополнительные бонусные очки. По сюжету — данные строки именовались даваром, и организаторы собирали его для того, чтобы отсрочить пробуждение Ктулху.

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



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

Данная статья посвящается светлой памяти моего учителя, доктора технических наук, профессора Кабелькова Александра Николаевича, основателя и первого декана Физико-математического факультета ЮРГТУ (НПИ)

Введение

Данное видео иллюстрирует повторный эксперимент — вместо «барашка» используется какая-то самодельная ерунда



Это случилось в 1985 году, на орбитальной станции «Салют-7», во время посещения её экипажем корабля «Союз Т-13» в составе космонавтов Джанибекова В. А. и Савиных В. П. Не буду описывать своими словами, процитировав один из многочисленных сетевых источников

Когда космонавты распаковывали доставленный на орбиту груз, то им приходилось откручивать так называемые «барашки» – гайки с ушками. Стоит ударить по ушку «барашка», и он сам раскручивается. Затем, раскрутившись до конца и соскочив с резьбового стержня, гайка продолжает, вращаясь, лететь по инерции в невесомости (примерно как летящий вращающийся пропеллер). Так вот, Владимир Александрович заметил, что пролетев примерно 40 сантиметров ушками вперед, гайка вдруг совершает внезапный переворот на 180 градусов и продолжает лететь в том же направлении, но уже ушками назад и вращаясь в другую сторону. Затем, опять пролетев сантиметров 40, гайка снова делает кувырок на 180 градусов и продолжает лететь снова ушками вперед, как в первый раз и так далее. Джанибеков неоднократно повторял эксперимент, и результат неизменно повторялся. В общем, вращающаяся гайка, летящая в невесомости, совершает резкие 180-градусные периодические перевороты каждые 43 сантиметра. Также он пробовал вместо гайки использовать другие предметы, например, пластилиновый шарик с прилепленной к нему обычной гайкой, который точно так же, пролетев некоторое расстояние, совершал такие же внезапные перевороты.

Думаю, что для затравки этого вполне достаточно. На самом деле, в «эффекте Джанибекова» нет ничего экстраординарного (хотя ему причисляют и возможную смену полюсов Земли каждые 12000 лет, и прочие глобальные катаклизмы). Используя аппарат тензорной алгебры и теорию устойчивости механического движения, попробуем разобраться, что происходит с загадочной гайкой.

Привет! На Хабре периодически появляются статьи, где авторы хотят вставить математические формулы: , или даже


У некоторых это получается, у некоторых — с трудом. parpalak сделал web-сервис для вставки svg формул, и это очень круто. Я хочу дополнить его небольшим скриптом, с которым вставка многих формул сведется к одной команде.

This constructor is so secret, not even STL maintainers know about it...

Stephan T. Lavavej

Этот конструктор настолько секретный, что даже сопровождающие STL не знают о нём...

пер.: Door

У std::shared_ptr есть небольшой секрет: очень полезный конструктор, о котором большинство программистов даже не слышали. Он был добавлен только в стандарте С++11, и его не было даже в TR1 версии shared_ptr. Однако он поддерживается gcc с версии 4.3, и компилятором MSVC еще с времен Visual Studio 2010. В Boost он появился примерно с 1.35.0.

В большинстве обучающих материалов, в которых описывается std::shared_ptr ничего нет об этом конструкторе. Скотт Майерс ни словом не обмолвился о нем в «Effective Modern C++», другой автор — Nicolai Josuttis уделил этому конструктору около половины страницы в своей книге «The C++ Standard Library».

Итак, что представляет собой этот секретный конструктор?

Перевод поста Джона Маклуна "Droste Effect with Mathematica". Код, приведенный в статье, можно скачать в конце поста.
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

Эффект Дросте (wiki) представляет собой рекурсивное включение изображением самого в себя. Название происходит от какао-порошка Droste, который в 1904 году продавался в упаковке, на которой была изображена медсестра, которая держала коробку, на которой была медсестра, ну и так далее. Самая простая реализация — отмасштабировать и трансформировать изображение, а затем поместить его на свою немодифицированную точную копию, затем начать процесс снова. Взгляните на демонстрацию, в которой используется оригинальные иллюстрации упаковки Droste. Однако значительно более интересных результатов можно достичь, если использовать теорию функций ко́мплексного переменного (ТФКП). Эшер М. К. был первым, кто популяризировал идею конформных отображений применительно к изображениям, однако с помощью компьютеров мы легко можем реализовать эту идею на фотографиях для получения чего-то подобного:

Здравствуйте, уважаемые читатели!

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

Галилей был неправ. Земля не вращается вокруг Солнца. Она вращается вокруг вас, уже десятки лет. По крайней мере, по вашему собственному представлению.

Шрикумар Рао

Читатель спрашивает:

Где Солнце и планеты приобрели угловой момент, который привёл к их вращению? Я не говорю про орбиты, а про вращение вокруг осей. Я понимаю аналогию с фигуристом, в которой распростёртые руки увеличивают вращение из-за сохранения углового момента. Но фигурист сам закручивает себя. Если фигурист стоит на месте, он может вытягивать и поджимать руки, но вращаться от этого он не начнёт.

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



Легко заставить что-либо вращаться быстрее, если оно уже вращается – нужно лишь поменять момент инерции. А что такое момент инерции?

Суффиксное дерево – мощная структура, позволяющая неожиданно эффективно решать мириады сложных поисковых задач на неструктурированных массивах данных. К сожалению, известные алгоритмы построения суффиксного дерева (главным образом алгоритм, предложенный Эско Укконеном (Esko Ukkonen)) достаточно сложны для понимания и трудоёмки в реализации. Лишь относительно недавно, в 2011 году, стараниями Дэни Бреслауэра (Dany Breslauer) и Джузеппе Италиано (Giuseppe Italiano) был придуман сравнительно несложный метод построения, который фактически является упрощённым вариантом алгоритма Питера Вейнера (Peter Weiner) – человека, придумавшего суффиксные деревья в 1973 году. Если вы не знаете, что такое суффиксное дерево или всегда его боялись, то это ваш шанс изучить его и заодно овладеть относительно простым способом построения.

Скачать статью в виде документа Mathematica (NB), CDF-файла или PDF.
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

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

Введение

Будучи мотивирован вычислительными преимуществами, которыми обладает Mathematica, некоторое время назад я решил приступить к исследованию свойств арбелоса — весьма интересной геометрической фигуры. С тех пор я был впечатлен большим количеством удивительных открытий и вычислительных проблем, которые возникали из-за всё расширяющегося объёма литературы, касающейся этого примечательного объекта. Я вспоминаю его сходство с нижней частью культового велосипеда пенни-фартинг из The Prisoner (телесериал 1960-х), шутовской шапкой Панча (знаменитых Punch and Judy) и символом инь-ян с одной перевёрнутой дугой; см. рис. 1. В настоящее время существует специализированный каталог архимедовых кругов (круги, содержащиеся в арбелосе) [1] и важные применения свойств арбелоса, которые лежат вне поля математики и вычислительных наук [2].

Многие известные исследователи занимались этой темой, в том числе Архимед (убитый римским солдатом в 212 г. до н.э.), Папп (320 г. н.э.), Кристиан О. Мор (1835-1918), Виктор Тебо (1882-1960), Леон Банкофф (1908-1997), Мартин Гарднер (1914-2010). С недавних пор свойствами арбелоса занимаются Клейтон Додж, Питер Ай. Ву, Томас Шох, Хироши Окумура, Масаюки Ватанабе и прочие.

Леон Банкофф — человек, который привлекал всеобщее внимание к арбелосу в последние 30 лет. Шох привлёк внимание Бэнкоффа к арбелосу в 1979 году, открыв несколько новых архимедовых кругов. Он послал 20-страничную рукописную работу Мартину Гарднеру, который направил её Бэнкоффу, который затем отправил 10-страничный фрагмент копии рукописи Доджу в 1996 году. Из-за смерти Бэнкоффа запланированная совместная работа была прервана, пока Додж не сообщил о некоторых новых открытиях [3]. В 1999 году Додж сказал, что ему потребуется от пяти до десяти лет, чтобы отсортировать весь материал, которым он располагает, разложив всё это дело по стопкам. В настоящее время эта работа все ещё продолжается. Не удивительно, что в четвертом томе The Art of Computer Programming, сказано о том, что важная работа требует большого количества времени.


Рис. 1. Велосипед пенни-фартинг, куклы Панч и Джуди, физический арбелос.

Арбелос (“нож сапожника” в греческом языке) назван так из-за своего сходства с лезвием ножа, использующегося сапожниками (Рис. 1). Арбелос — плоская область, ограниченная тремя полуокружностями и общей базовой линией (рис. 2). Архимед, вероятно, был первым, кто начал изучать математические свойства арбелоса. Эти свойства описаны в теоремах с 4-ой по 8-ую его книги Liber assumptorum (или Книги лемм). Возможно, эту работу написал не Архимед. Сомнения появились после перевода с арабского Книги лемм, в которой Архимед упоминается неоднократно, но ничего не сказано о его авторстве (однако, существует мнение, что эта книга — подделка [4]). Книга Лемм так же содержит знаменитую архимедову Problema Bovinum [5].

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

Бен Кэменс обнаружил, что в выпадающем списке Shop by Department на сайте «Амазон» ховер-эффект происходит очень быстро, абсолютно без какой-либо задержки. Тем самым происходит нарушение старого, выработанного ещё в 90-х годах прошлого века правила: перед отображением пункта подменю необходим так называемый гистерезис, запаздывание.



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

Пожалуй, начну с того, что если перегружаться 15 раз в год, то любой «тюнинг» процесса загрузки отнимает больше времени, чем будет выиграно на перезагрузках за все время жизни системы. Однако, спортивный интерес берет свое, тем более, что люди интересуется процессом оптимизации быстродействия. А загрузка оказалась самым очевидным кандидатом в примеры того, как на мой взгляд должен выглядеть этот самый процесс. Сразу скажу, что грузиться будем с 5400 rpm винта, грузиться будем в «рабочую» систему: помимо недобитой вендорской крапвари там стоит еще куча всякого типа вижуал студии, антивируса, скайпа, стима, гуглапдейтера и пр…

Про то, почему отключение pagefile-а скорее вредно, чем полезно — как нибудь в другой раз, а пока…

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


Уязвимость рекурсивных алгоритмов навигации муравья: спираль смерти

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

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