Двоичная куча (binary heap) – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению).

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

Введение

Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков. В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-heap, поскольку корень поддерева является максимумом из значений элементов поддерева. В этой статье для простоты используется именно такое представление. Напомню также, что дерево называется полным бинарным, если у каждой вершины есть не более двух потомков, а заполнение уровней вершин идет сверху вниз (в пределах одного уровня – слева направо).

Предыстория

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

В статье собраны всем известные методы и предельно извращенные. Эту статью я решил написать после недавнего прочтения поста в блоге Badass JavaScript и решил её дополнить своими находками.

Первый способ

Он всем известен — обфускация минимизаторами такими как JS Packer, JSmin, YUI Compressor, Closure compiler или можно просто пугуглить «JavaScript Obfuscator» и найдется ещё сто штук разных обфускаторов.
Они превращают существующий код

function MyClass(){
    this.foo = function(argument1, argument2){
        var addedArgs = parseInt(argument1)+parseInt(argument2);
        return addedArgs;
    }
    var anonymousInnerFunction = function(){
        // do stuff here!
    }
}

В какой-то такой вид:

function MyClass(){this.foo=function(c,b){var d=parseInt(c)+parseInt(b);return d};var a=function(){}};

Или такой:

var _0xd799=["\x66\x6F\x6F"];function MyClass(){this[_0xd799[0]]=function (_0xefcax2,_0xefcax3){var _0xefcax4=parseInt(_0xefcax2)+parseInt(_0xefcax3);return _0xefcax4;} ;var _0xefcax5=function (){} ;} ;

Или вот такой:

eval(function(p,a,c,k,e,d){e=function(c){return c};if(!''.replace(/^/,String)){while(c--){d[c]=k[c]||c}k=[function(e){return d[e]}];e=function(){return'\\w+'};c=1};while(c--){if(k[c]){p=p.replace(new RegExp('\\b'+e(c)+'\\b','g'),k[c])}}return p}('4 0="3 5!";9 2(1){6(1+"\\7"+0)}2("8");',10,10,'a|msg|MsgBox|Hello|var|World|alert|n|OK|function'.split('|'),0,{}))

Но ничего не стоит его восстановить с помощью jsbeautifier.org либо просто убрать eval и получить исходный код, многое потеряем, но смысл кода восстановим. Ну и с первого взгляда мы видим, что перед нами JavaScript.

Все это были цветочки под катом жесткие методы обфускации.

В наше время все большую популярность набирают генетические алгоритмы. Их используют для решения самых разнообразных задач. Где-то они работают эффективнее других, где-то программист просто решил выпендриться…

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

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

Как это все выглядит вы можете увидеть на следующем рисунке:

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

В создании программы мне также помогли сайт о Brainfuck'е и таблица ASCII символов

Статья по настройке Медиаджика. Что это такое — можно прочесть тут


Подробности под катом.

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

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

К счастью, решить большинство этих проблем в Linux может технология LVM. Она создаёт дополнительную абстракцию — логические тома, которые видны в системе, как обычные разделы, однако реально ими не являются. Эта технология очень полезна для серверов, однако и на домашних компьютерах она приходится очень к месту. Я больше не думаю, какого размера диск выделить под систему, чтобы какой-нибудь texlive не забил бы всё место, но и чтобы лишние 5 — 10 гигабайт не пропадали просто так. LVM имеет ряд существенных преимуществ, значительно упрощающих жизнь:

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

Вступление

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

Содержание:

1. Что нам понадобится?
2. Коротко о синтаксисе
3. Переменные
4. Функции
5. Списки
6. Регистрация скрипта в GIMP
7. Написание кода
8. Заключение

На фоне нынешних рассуждений о том, «справится ли мой телефон/калькулятор/часы с проигрыванием HD-видео» отошел на задний план интересный исторический факт: немногим более 10 лет назад проблемой была даже не скорость декодирования видео (теплый ламповый MPEG декодировался тогда отдельными аппаратными декодерами; остальные перебивались возможностями имеющегося ЦП), а скорость его вывода на экран. Многоэкранная среда убивает на корню идею переноса блока памяти с декодированным изображением в видеопамять, ведь окна могут перекрывать друг друга самым причудливым образом.

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

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

LESS — новый препроцессор для CSS. Проще говоря, LESS позволяет использовать в вашем CSS-файле переменные, операторы, классы и вложенные конструкции. В этой статье вы узнаете об основных возможностях LESS и о том, как быстро подключить его к популярному фреймворку Ruby on Rails 3.

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

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

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

Эта статья о некоторых технических аспектах реализации бесплатного сервиса для загрузки, хранения и просмотра видео. Будут рассмотрены вопросы настройки серверного программного обеспечения, даны примеры команд для конвертации видео и примеры кода на языке PHP.

ptrace (от process trace) — системный вызов в некоторых unix-подобных системах (в том числе в Linux, FreeBSD, Max OS X), который позволяет трассировать или отлаживать выбранный процесс. Можно сказать, что ptrace дает полный контроль над процессом: можно изменять ход выполнения программы, смотреть и изменять значения в памяти или состояния регистров. Стоит оговориться, что никаких дополнительных прав при этом мы не получаем — возможные действия ограничены правами запущенного процесса. К тому же, при трассировке программы с setuid битом, этот самый бит не работает — привилегии не повышаются.

В статье будет показано, как перехватывать системные вызовы на примере ОС Linux.

Несколько недель назад мне для некого опыта потребовался источник постоянного напряжения 7V и силой тока в 5A. Тут-же отправился на поиски нужного БП в подсобку, но такого там не нашлось. Спустя пару минут я вспомнил о том, что под руки в подсобке попадался блок питания компьютера, а ведь это идеальный вариант! Пораскинув мозгами собрал в кучу идеи и уже через 10 минут процесс начался.

Статья гуляет в интернете уже довольно давно, но, как автор думаю имею право на ее перепост здесь. Многое (если не все) написаное здесь устарело, и может показаться бесполезным с первого взгляда, однако пройдя этот путь, спустя 6 лет могу сказать, это не оказалось лишним. Итак.
В этой статье я хочу рассказать о CGI интерфейсе вообще, его реализации для windows и использовании при написании CGI-программ языка ассемблер в частности. В рамки этой статьи не входит полное описание CGI, так-как в Интернете материала по этому вопросу просто море и пересказывать все это здесь я просто не вижу смысла.

Все мы хоть раз в жизни использовали команду cat /proc/cpuinfo. Многие — лишь для того, чтобы узнать количество процессоров и ядер в системе, некоторые — узнать о поддержке конкретной технологии, например, аппаратной виртуализации.
Однако очень мало линуксоидов воспринимают всерьез самую длинную строку вывода — так называемые flags, а еще меньше знают, как расшифровывается тот или иной параметр, поскольку зачастую флаги имеют дикие и непонятные имена. Я постараюсь описать большинство распознаваемых флагов, специфичных для архитектуры x86.

В этом топике расскажу о том, как я из старенького цифровика и линзы из CD-ROM'а сделал инструмент для микрофотографии.

А почему бы и нет?

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

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

Все мы тут собрались умные, образованные, красивые и опытные. И на сегодняшний день, мне кажется, почти все используют тот, или иной вид RPC между JavaScript и PHP, который работает на API из того, или иного фреймворка. Кое кто даже разрабатывает какие-то свои костыли и подпорки. Я не исключение, конечно же. Правда пошел я по пути наименьшего сопротивления и, собственно, речь в этой статье пойдет как раз об этом — об очередной реализации XML\JSON RPC для JavaScript и PHP.

Предыстория такова, что мне необходимо было разработать некую систему управления данными. Естественно, что данные хранятся в СУБД, а управлять ими надо через веб. Привязываться к фреймворкам готовым очень не хотелось, потому выбор был не велик — PHP-быдлокодинг, или MVC с рендерингом на основе готовых разработок вроде smarty. Однако, примерно в то же время, я обратил внимание на такие проекты как extJS (он же Sencha теперь) и qooxdoo, которые позволяют создавать полноценные веб-приложения минуя утомительную HTML-верстку, генерацию HTML/XML, XSLT преобразования и многие другие «страшные» вещи, характерные для MVC и PHP-быдлокода. Потому созрел следующий план действий.: