«Как автоматизировать сочинение музыки?» — этот вопрос тревожит умы музыкантов еще со времен средневековья. Кеплер превращал траектории движения планет в музыку; Моцарт и его современники изобрели игру в «музыкальные кости» — они броском кубиков выбирали из большой таблицы такты и составляли из них менуэты. Но только с появлением компьютеров алгоритмическая генерация музыки получила настоящее развитие. Теория вероятности, марковские цепи, искусственные нейронные сети — все это стало инструментами создания музыки.

И снова здравствуйте! После перерыва в месяц продолжаем экскурсию по форматам изображений и алгоритмам сжатия. Где мы остановились? Ах, да, восьмидесятые годы.

Увидев в очередной раз презренный посыл в Google в ответ на вопрос о том, как развернуть собственную LAMP'у, решил написать данный пост. Чтобы хоть как-то разбавить тонны радостных отчётов об успешной установке из блогов, суть которых сводится к одной команде aptitude install blah-blah.

Нет, ну конечно понятно, PHP самый надёжный язык, а все движки сайтов, на нём написанные, являются живым воплощением непробиваемой защиты от взлома. Тогда да — aptitude install apache2 — и будет вам счастье. Не забудьте оставить phpmyadmin по дефолтному адресу, да поставьте какое-нибудь дырявое FTP решето.

Вообще, как оказалось, многие даже не в курсе, что взломав сайт и получив возможность исполнять свой PHP код, злоумышленник на системе с дефотными настройками сможет как минимум прочитать в вашей системе почти что угодно. Оно и понятно — работая с Linux привыкаешь как-то, что по дефолту безопасность находится на вполне достаточном уровне. А тут такая дыра…

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

Те, кому тема веб-серверов надоела, возможно смогут найти в статье интересные приёмы многопользовательского ограниченного доступа к серверу по SFTP.

И нет, это не ещё одна статья с описанием установки Linux и выполнением aptitude install apache2. Скорее наоборот: в этой статье я хотел показать фатальную недостаточность данных манипуляций и мягко говоря некомпетентность тех, кто их тиражирует в интернете.

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

Идея распознавать людей по радужной оболочке появилась в далёком 1987 у доктора Джона Доугмана и была запатентована в 1989. Примерно тогда же появился прототип. На тот момент это была вершина технологии. Пару лет до первой коммерческой цифровой камеры + алгоритм обработки изображения на компьютерах уровня i386/i486. До сих пор я не представляю, как можно получать на таком оборудовании стабильный результат.
Задачка о которой я хочу рассказать появилась на свет где-то в 2006-2009 годах. Процессоры к этому времени несколько ускорились, появились хорошие камеры, патент 1989 года истёк и системы распознавания по глазам теперь получил право делать каждый. Люди, которые решили сделать клон системы захотели использовать современные технологии и улучшить алгоритм. Самое первое, что бросалось в глаза — старый алгоритм сравнения глаз использовал изображение глаза в близком ИК диапазоне. То, что глаза бывают цветными не учитывалось.

Проглядывая книжку «Эффективное использование C++», Скотта Мейерса, которая ( и я никого не удивлю ) достойна всяческих похвал, меня очень тронуло, то с какой возбуждённостью, вдохновлённостью, трепетом ( может мне показалось? ) автор говорит о шаблонах и их возможностях. Приведу маленький кусочек:

Метапрограммирование шаблонов ( template metaprogramming — TMP ) — это процесс написания основанных на шаблонах программ на C++, исполняемых во время компиляции. На минуту задумайтесь об этом: шаблонная метапрограмма — это программа, написанная на C++, которая исполняется внутри компилятора C++…
Было доказано, что технология TMP предоставляет собой полную машину Тьюринга, то есть обладает достаточной мощь для любых вычислений...

Да уж… сердце забилось, в очередной раз удивился — только подумать — полная машина Тьюринга со всеми вытекающими последствиями… Как по мне, это просто невероятно и удивительно… хотя, кто его знает…

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

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

Начнём с того, что рассмотрим ряд клеток, в которых, кроме одной, находятся нули:

... 0  1  0  0  0  0  0  0 ...

Рассмотри следующее правило, заменяем число в клетке на сумму этого числа и соседа слева. Получим следующую серию состояний:

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  2  1  0  0  0  0 ...
... 0  1  3  3  1  0  0  0 ...
... 0  1  4  6  4  1  0  0 ...
... 0  1  5 10 10  5  1  0 ...
... 0  1  6 15 20 15  6  1 ...

Не сложно увидеть, что это — треугольник Паскаля. А теперь вместо обычного сложения будем использовать сложение по модулю два. Известно (и даже недавно рассказывалось в хабрастатье Треугольник Серпинского и треугольник Паскаля), что получится дискретный аналог треугольника Серпинского:

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  0  1  0  0  0  0 ...
... 0  1  1  1  1  0  0  0 ...
... 0  1  0  0  0  1  0  0 ...
... 0  1  1  0  0  1  1  0 ...
... 0  1  0  1  0  1  0  1 ...

Интересно? Читаем дальше!

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

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

О чем эта статья

В статье рассказывается про библиотеку Property Tree Library, а именно:

• Что такое Property Tree;
• Примеры использования Property Tree;
• Как конвертировать Property Tree в XML-код и обратно.

Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

Разница в том, что контейнеры в STL реализованы на красно-чёрных деревьях, а аналогичные контейнеры cpp-btree — на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера).

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

Доброго Нового Года!

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

Пусть имеется набор N из n целых положительных чисел от 1 до n.
Самоочевидно, что для хранения n чисел необходимо иметь n ячеек. Вне зависимости от порядка, в котором числа будут записаны.

Исходный массив

3

5

2

1

8

4

7

6

9

10

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

Упорядоченный массив

1

2

3

4

5

6

7

8

9

10

С течением времени изменяются наши представления о способах взаимодействия с компьютером. На смену «классических» клавиатуры и мыши, в нашу жизнь прочно вошли тачпады и сенсорные экраны. Но это не последняя ступень эволюции для средств ввода информации. С появлением устройств дополненной реальности, например таких, как Google Glass, возникает необходимость в интерфейсах способных гармонично вписываться в данную концепцию. Предпосылки к возникновению таких интерфейсов имеются, так, например, появились такие устройства как Intel Creative Camera, Microsoft Kinect или Leap Motion. Основными управляющими элементами в данных устройствах являются руки пользователя. Поэтому, одной из фундаментальных алгоритмических задач, для взаимодействия с подобными устройствами, является детектирование рук и пальцев пользователя и реконструкция их пространственного расположения.
В данной статье речь пойдет о одном из способов решения задачи детектирования ладоней и пальцев.

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

В этом посте речь пойдет о применении линейного конгруэнтного метода для получения псевдослучайных чисел разрядности 64 и 128 бит с пояснением принципа работы и подбора параметров.

Если вам в тягость пользоваться ГСЧ из стандартной библиотеки, у вас к нему нестандартные требования или просто охота держать под контролем весь процесс генерации случайных чисел в своем приложении, добро пожаловать под кат.

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

В этой статье я попробую показать, как обучить каскад с нуля за несколько часов, натренировав на поиск простого предмета в видеопотоке (примером будет очаровательная сова с фотографии). Все обучающие выборки и программы будут приложены.
Зачем всё это нужно? Каскад Хаара это один из простейших способов распознавания классов объектов с большой скоростью работы. К ним относятся лица и руки людей, номера автомобилей, пешеходы. Детектором Хаара просто находить животных в кадре (кстати, удивительно, что я не видел ещё ни одной автоматической кормушки для синиц на raspberry pi). К тому же, готовые реализации OpenCV есть под большинство существующих систем (даже для blackfin'a встречал). Всё это делает Хаара одним из самых удобных методов, позволяющих решать задачи видеообработки даже людям, которые никогда не работали с обработкой видео.

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

Этим летом я принял участие в Научно-образовательной школе МГУ, которая проводится Московским Государственным Университетом и Лабораторией Научного Творчества СУНЦ МГУ. В этой статье я хотел бы рассказать вам о проекте, который я разработал во время школы на спецкурсе по программированию под руководством MAD_GooZe.

Для нетерпеливых

Идея проекта

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

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

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

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

Основные понятия
Изображение — отображение объекта на воспринимающие органы. То есть, описание объекта, как множество признаков. Часто объект представляется в виде вектора. Если множество признаков постоянное, то объект отождествляется с его изображением.
Образ (класс) — подмножество множества объектов или изображений.
Решающая функция — функция, на вход которой подается изображение, определяющая принадлежность объекта некоторому классу.

Краткое описание
Суть данного метода, а впрочем, любого алгоритма, применяемого для распознавания образов состоит в том, чтобы составить такую решающую функцию, которая будет для каждого объекта определять принадлежность его к нужному классу.
В данном случае, решающая функция составляется итеративно, по маркированной обучающей выборке (для каждого объекта из ОВ известен его класс).

Много раз уже просили написать статью о том, как в приложении реализовать платное отключение рекламы. По In-app уже были статьи на хабре. Правда, они старую версию API рассматривали. В принципе, новая версия не особо то и отличается от старой. Была похожая статья, но там больше именно про отображение рекламы рассказывалось, а второй части статьи мы так и не увидели. Как оказалось, многим до сих пор интересен этот вопрос, решил написать как это реализовать в своём приложении.

Введение

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

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

В этот раз речь пойдет о создании кроссплатформенных приложений с плагинами на C++ с использованием библиотеки wxWidgets. Рассматриваться будут операционные системы Windows, Linux и OS X, как наиболее популярные.

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

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

Для разработки приложений под ОС Android, Google предоставляет два пакета разработки: SDK и NDK. Про SDK существует много статей, книжек, а так же хорошие guidelines от Google. Но про NDK даже сам Google мало что пишет. А из стоящих книг я бы выделил только одну, Cinar O. — Pro Android C++ with the NDK – 2012.

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

Abstract: Рассказ про некоторые возможности IPv6 на примере конфигурации сложной домашней IPv6-сети. Включает в себя описания мультикаста, подробности настройки и отладки router advertisement, stateless DHCP и т.д. Описано для linux-системы. Помимо самой конфигурации мы внимательно обсудим некоторые понятия IPv6 в теоретическом плане, а так же некоторые приёмы при работе с IPv6.

Зачем IPv6?

Вполне понятный вопрос: почему я ношусь с IPv6 сейчас, когда от него сейчас нет практически никакой пользы?

Сейчас с IPv6 можно возиться совершенно безопасно, без каких-либо негативных последствий. Можно мирно разбираться в граблях и особенностях, иметь его неработающим месяцами и nobody cares. Я не планирую в свои старшие годы становиться зашоренным коболистом-консерватором, который всю жизнь писал кобол и больше ничего, и все новинки для него «чушь и ерунда». А вот мой досточтимый воображаемый конкурент, когда IPv6 станет продакт-реальностью, будет либо мне не конкурентом, либо мучительно и в состоянии дистресса разбираться с DAD, RA, temporary dynamic addresses и прочими странными вещами, которым посвящено 30+ RFC. А что IPv6 станет основным протоколом ещё при моей жизни — это очевидно, так как альтернатив нет (даже если бы они были, их внедрение — это количество усилий бОльшее, чем завершение внедрения IPv6, то есть любая альтернатива всегда будет отставать). И что адреса таки заканчиваются видно, по тому, как процесс управления ими перешёл во вторую стадию — стадию вторичного рынка. Когда свободные резервы спекуляций и хомячаяния адресов закончится, начнётся этап суровой консолидации — то есть выкидывание всего неважного с адресов, перенос всех «на один адрес» и т.д. Примерно в это время IPv6 начнёт использоваться для реальной работы.

Впрочем, рассказ не про будущее IPv6, а про практику работы с ним. В Санкт-Петербурге есть такой провайдер — Tierа. И я их домашний пользователь. Это один из немногих провайдеров, или, может быть, единственный в городе, кто предоставляет IPv6 домашним пользователям. Пользователю выделяется один IPv6 адрес (для маршрутизатора или компьютера), плюс /64 сетка для всего остального (то есть в четыре миллиарда раз больше адресов, чем всего IPv4 адресов быть может — и всё это в одни руки). Я попробую не просто описать «как настроить IPv6», но разобрать базовые понятия протокола на практических примерах с теоретическими вставками.

Структура сети:

(Оригиналы картинок: github.com/amarao/dia_schemes)

• 1, 2, 3 — устройства в локальной сети, работают по WiFi
• 4 — WiFi-роутер, принужденный к работе в роле access point (bridge), то есть коммутатора между WiFi и LAN
• 5 — eth3 сетевой интерфейс, который раздаёт интернет в локальной сети
• 6 — мой домашний компьютер (основной) — desunote.ru, который раздачей интернета и занимается, то есть работает маршрутизатором
• 7 — eth2, интерфейс подключения к сети Tiera