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

Введение

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

Деревья принятия решений

Дерево принятия решений — это дерево, в листьях которого стоят значения целевой функции, а в остальных узлах — условия перехода (к примеру “ПОЛ есть МУЖСКОЙ”), определяющие по какому из ребер идти. Если для данного наблюдения условие истина то осуществляется переход по левому ребру, если же ложь — по правому.

Пользователь yruslan опубликовал хорошую статью про арифметику с плавающей запятой: «Что нужно знать про арифметику с плавающей запятой».

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

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

Жизнь — дерьмовая штука. По крайней мере, так считают многие «взрослые» люди, с которыми мне довелось общаться. Они постоянно жалуются на свою работу, неудовлетворительные отношения и раздолбаев-детей, которые никак не хотят становиться такими, какими хотят их видеть родители. Жизнь для этих людей — это бесконечная карусель разочарований, неприятностей и несбывшихся надежд. Они встают рано утром с больной головой, заливают в рот пару литров кофе и едут на работу в состоянии, которому позавидовали бы самые отъявленные зомби. Они ненавидят свою работу и считают, что их занятия бессмысленны и никому не нужны. Но, не смотря на это, они с упорством леммингов продолжают делать эту работу, день за днём, год за годом. Они продираются сквозь собственную жизнь, надеясь, что всласть поживут потом, когда отработают 10-20-30 лет. Так вот, это всё херня. Когда вам будет пятьдесят, вы настолько устанете от такой жизни, что единственным вашим желанием будет лечь и сдохнуть. Да и здоровье будет уже не то, потому что вы слили его, занимаясь всякой ерундой, до которой вам даже не было дела. Так что, когда вы выйдете на пенсию, вы не поедете в Африку охотиться на львов, потому что солнце плохо сказывается на вашем давлении. Вы также не поедете на Северный полюс, потому что у вас артрит и холод — не лучшее для него лекарство. Южный полюс отпадает ещё и потому, что вы недолюбливаете пингвинов, что неудивительно, учитывая ваш 30-летний стаж работы сисадмином. Так что же вам остаётся? Поездки на дачу и вечера в уютной компании телевизора, вот что. Прожив 30 лет в постоянной борьбе с самим собой, у вас просто не останется сил на то, чтобы оторвать задницу от дивана.

Постановка задачи

Пусть дан массив A длины N, и дано число K ≤ N. Требуется найти максимум (минимум, сумма ...) в подотрезках длины K данного массива. Это частный случай задачи RMQ (Range Minimum Query — минимум на отрезке), но с дополнительными ограничениями — постоянная длина отрезка поиска. В данном решении задача не предполагает возможность изменения элементов массива.

Сначала немного жёлтого:

Удостоверяющий центр Comodo Internet Security (их корневой сертификат объявлен заслуживающим доверия большинством производителей браузеров) подписало следующие сертификаты для неизвестных мошенников:

* mail.google.com, www.google.com
* login.yahoo.com (3шт)
* login.skype.com
* addons.mozilla.org
* login.live.com

Если мошенник предъявит этот сертификат, то он будет принят как правильный браузерами. Другими словами, не будет ни малейшего метода определить, что сайт поддельный.

Теперь подробнее. Эти сертификаты были выпущены, после чего началась подковёрная буча, производители браузеров (как минимум хром и файрфокс) внесли их в black list (вкомпиленный в код). Для firefox'а это произошло 17ого марта 2011 года, все версии, вышедшие до этого момента будут доверять этим сертификатам (я хотел было написать «подвержены уязвимости», но проблема в том, что это не уязвимость, это распиз… ство Comodo, которому почему-то все вынужены доверять). В теории, должна осуществляться проверка на то, не входит ли сертификат в список отзыва (его туда внесли), однако, на практике, если доступ к этому списку ограничен, то браузеры не выдают внятных предупреждений и доверяют сертификату.

Ссылки:

1) Пресс-релиз comodo: www.comodo.com/Comodo-Fraud-Incident-2011-03-23.html
2) Secity Advisory от MS: www.microsoft.com/technet/security/advisory/2524375.mspx
3) Детективная история о том, как обнаружили «странное» в патчах в firefox'е до офицального обнародования результатов беспечности Comodo: blog.torproject.org/blog/detecting-certificate-authority-compromises-and-web-browser-collusion
4) О политической составляющей произошедшего: avva.livejournal.com/2321707.html

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.

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

"Снэпшот" (дословно — «фотография», «моментальный снимок», здесь и далее под этим словом мы будем понимать конкретно, не уточняя, «снэпшот данных») это моментальная копия состояния данных в системе хранения, или программе, зафиксированная на определенный момент времени. Это может быть моментальное состояние содержимого файла, базы данных, или файловой системы (как частного случая «базы данных»).
В применении к системам хранения данных этот термин появился вместе с первыми системами хранения NetApp и был, на тот момент первой и главной их «фичей».

В первой части нашей темы мы рассмотрели решение задачи static RMQ за (O(nlogn), O(1)). Теперь мы разберёмся со структурой данных, называемой дерево отрезков, или интервалов (в англоязычной литературе – segment tree или interval tree). С помощью неё можно решать dynamic RMQ за (O(n), O(logn)).

Определение

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

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

Введение

Задача RMQ весьма часто встречается в спортивном и прикладном программировании. Удивительно, что на Хабре ещё никто не упомянул эту интересную тему. Попробую восполнить пробел.

Аббревиатура RMQ расшифровывается как Range Minimum (Maximum) Query – запрос минимума (максимума) на отрезке в массиве. Для определённости мы будем рассматривать операцию взятия минимума.

Пусть дан массив A[1..n]. Нам необходимо уметь отвечать на запрос вида «найти минимум на отрезке с i-ого элемента по j-ый».



Рассмотрим в качестве примера массив A = {3, 8, 6, 4, 2, 5, 9, 0, 7, 1}.
Например, минимум на отрезке со второго элемента по седьмой равен двум, то есть RMQ(2, 7) = 2.

В голову приходит очевидное решение: ответ на каждый запрос будем находить, просто пробегаясь по всем элементам массива, лежащим на нужном нам отрезке. Такое решение, однако, не является самым эффективным. Ведь в худшем случае нам придётся пробежаться по O(n) элементам, т.е. временная сложность этого алгоритма – O(n) на один запрос. Однако, задачу можно решить эффективнее.

Итак, что же это значит, когда кто-либо говорит, что foo выглядит как pythonic? Что значит, когда кто-либо смотрит в наш код и говорит, что он unpythonic? Давайте попробуем разобраться.

В Python-сообществе существует неологизм pythonic, который можно трактовать по разному, но в общем случае он характеризует стиль кода. Поэтому утверждение, что какой-либо код является pythonic, равносильно утверждению, что он написан в соответствии с идиома Python’a. Аналогично, такое утверждение в отношении интерфейса, или какой-либо функциональности, означает, что он (она) согласуется с идиомами Python’a и хорошо вписывается в экосистему.

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

Понятие Pythonicity плотно связано с минималистической концепцией Python’a и уходом от принципа «существует много способов сделать это». Нечитабельный код, или непонятные идиомы – все это unpythonic.

При переходе от одного языка к другому, некоторые вещи должны быть «разучены». Что мы знаем из других языков программирования, что не будет к месту в Python’e?

О Bitcoin я узнал относительно недавно, но он меня сразу подкупил своей идеей p2p. Чем глубже я зарывался в их Wiki, тем больше проникался этой идеей. Ее реализация красива и элегантна с технической точки зрения.

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

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

Что это означает для нас, для обычных людей? У вас есть компьютер, где стоит Ubuntu или ещё какой-то Дебиан-подобный Linux? Назовём его Компьютер №1. На нём вы сможете сделать что-то обычное, типа

apt-get install kerrighed-kernel...

ну, вероятно, придётся уж потратить и пару минут на конфигурацию. Далее, перезагрузив Ubuntu, вы увидите новоиспечённое ядро в grub-меню. Выбираете и попадаете в обычную Ubuntu с одним необычным свойством, назовём его "SSI with DRBL"…

Что за зверь «SSI with DRBL»?

Техника, известная как «Чтение по спирали/по часовой стрелке» (“Clockwise/Spiral Rule”) позволяет любому программисту разобрать любое объявление языка Си.

Следуйте этим простым шагам:

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

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

Предыстория

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

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

В качестве инструмента для реализации был выбран Auto It, но потом оказалось что задача не такая тривиальная, как выглядит на первый взгляд, и пришлось подключать дополнительные инструменты. Сразу скажу, что никакие «грязные» методы вроде чтения памяти процесса или перехвата траффика я не использовал, только autoit для имитации кликов мышки и клавиатуры и чтения цветов пикселей с экрана.

Google выпустил открытую библиотеку Contracts for Java, которая упрощает реализацию методов контрактного программирования в Java. С помощью библиотеки Contracts for Java предусловия, постусловия и инварианты можно добавлять в Java как булевые выражения внутри аннотаций.

Как сказано в официальном анонсе, библиотека разработана двумя программистами Google в свободное от основной работы время (20% на личные проекты) и основана на Modern Jass и сделана под впечатлением от языка Эйфель, в котором впервые был реализован метод контрактного программирования.

Последние блоки /8 распечатаны, интернет бурлит, эксперты спорят, лидеры индустрии точат зубы друг на друга, предвидя вираж борьбы за рынки в условиях новой реальности.

История эта напоминает как минимум три разных истории сразу:

• проблему 2000 года (кто-нибудь помнит такую?),
• традиционно внезапное для ЖКХ наступление зимы в конце ноября,
• мировой финансовый кризис: все ждали, что пузыри однажды лопнут, но никто не понимал, куда и зачем в связи с этим бечь — авось как-нибудь само, too big to fail, и все такое.

Каждый дует в свою дуду (ну а в какую ж еще?)

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

Попробую привести аргументацию каждой из групп.

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

Долгое время я считал, что криптографические алгоритмы шифрования и хеширования, вроде AES и MD5, устроены очень сложно и написать их совсем не просто, даже имея под рукой полную документацию. Запутанные реализации этих алгоритмов на разных языках программирования только укрепляли это мнение. Но недавно у меня появилось много свободного времени и я решил разобраться в этих алгоритмах и написать их. Оказалось, что они очень просто устроены и для их реализации нужно совсем немного времени.

В этой статье я напишу как устроен алгоритм шифрования AES (которого иногда называют Rijndael) и напишу его на JavaScript. Почему на JavaScript? Чтобы запустить программу на этом языке, нужен только браузер в котором вы читаете эту статью. Чтобы запустить программу, скажем, на C, нужен компилятор и найдётся совсем мало желающих, готовых потратить время на компиляцию кода из какой то статьи. В конце есть ссылка по которой можно скачать архив с html страницей и несколькими js файлами — это пример реализации AES на JavaScript.

Дорогие друзья, доброго времени суток!

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

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