Пару месяцев назад нами (2Товарища и Антон Исайкин) была обнаружена уязвимость, присущая в основном большим интернет-проектам (вроде Рамблера, Мейла, Яндекса, Оперы и пр.). Удалось получить доступ к файловым структурам известнейших сайтов (в общей сложности 3320 сайтов) и в ряде случаев их полные исходные коды.

Важный UPD под катом!

1. Изначально компания Intel планировала провести в Политехническом музее всего три лекции, поэтому появлению постера к четвертой части я сам был удивлен. Лекция называется «Я, РОБОТ. Робототехника на грани постбиологической эволюции» и проведет её Сергей Кернбах, доктор естественных наук (Германия), руководитель группы коллективной робототехники, институт параллельных и распределенных систем (Штутгартский университет).

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Очень сильное колдунство

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

Вспомним-ка еще раз структуру дерамиды. В ней есть ключ x, по которому дерамида есть дерево поиска, случайный ключ y, по которому дерамида есть куча, а также, возможно, какая-то пользовательская информация с (cost). Давайте совершим невозможное и рассмотрим дерамиду… без ключей x. То есть у нас будет дерево, в котором ключа x нет вообще, а ключи y — случайные. Соответственно, зачем оно нужно — вообще непонятно :)

На самом деле расценивать такую структуру стоит как декартово дерево, в котором ключи x все так же где-то имеются, но нам их не сообщили. Однако клянутся, что для них, как полагается, выполняется условие двоичного дерева поиска. Тогда можно представить, что эти неизвестные иксы суть числа от 0 до N-1 и неявно расставить их по структуре дерева:

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

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

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

[FF D8]

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

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

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

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

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

Замечательный сайт www.sorting-algorithms.com позволяет увидеть, как сортируются данные разными алгоритмами. Вы сможете посмотреть анимацию в зависимости от алгоритма, исходных данных.



Все это бегает и сортируется прямо на ваших глазах!

Работает на Google App Engine, видимо, поэтому и лежит от посетителей с «Хабра».

Введение

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

Введение

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

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

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



Такой предельно упрощённой и наглядной моделью могут оказаться «Живые графы» — конечные автоматы на графе, каждый узел которого содержит некое исполняющее устройство (автомат) с конечным числом состояний и с набором примитивных правил, управляющих созданием или изменением новых связей между узлами.

Маркетинг магазина в реале начинается с выбора места. Есть два пути решения задачи: так называемый «жоп-филинг», то есть интуитивное принятие решения и продуманный просчёт.

Общая задача такая:

• Есть интернет-магазин, нужна точка в реале;
• Место должно способствовать наибольшей прибыли точки как отдельного розничного магазина;
• И хорошо работать как пункт самовывоза интернет-магазина.

Нечем заняться? тогда может быть просто написать 3D Console Software Rendering?
Добро пожаловать под кат!

 

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

То, что мы сегодня создадим, корректнее будет назвать LKM (Linux Kernel Module или загрузочный модуль ядра). Стоит сказать, что драйвер – это одна из разновидностей LKM.

Писать модуль мы будем под ядра линейки 2.6. LKM для 2.6 отличается от 2.4. Я не буду останавливаться на различиях, ибо это не входит в рамки поста.

Мы создадим символьное устройство /dev/test, которое будет обрабатываться нашим модулем. Хочу сразу оговориться, что размещать символьное устройство не обязательно в каталоге /dev, просто это является частью «древнего магического ритуала».

Где-то когда-то я читал, что создатели первой спецификации USB намеревались сделать этот стандарт простым для реализации в железе за счет усложнения программного обеспечения. Таким образом цель была максимально удешевить производство и сделать USB устройства очень доступными. Сейчас можно сказать, что чипмейкерам это удалось, но так ли уж прост для реализации в железе этот стандарт? Боюсь, что ответ не очевиден.



Предположим мне нужно сделать свое простое USB устройство. Какие у меня есть варианты?

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

Несколько лет назад ко мне пришел мой босс и сказал: «У нас есть новый проект для тебя. Это перенос сайта, который уже имеет 1 миллион посетителей в месяц. Тебенеобходимо его перенести и убедиться, что посещаемость может вырасти в будущем без всяких проблем.» Я уже был опытным программистом, но не имел никакого опыта в области масштабируемости. И мне пришлось познавать масштабируемость трудным путем.

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение

В качестве введения рекомендую прочесть пост про двоичные деревья поиска того же winger, поскольку без понимания того, что такое дерево, дерево поиска, а так же без знания оценок сложности алгоритма многое из материала данной статьи останется для вас китайской грамотой. Обидно, правда?

Следующий пункт нашей обязательной программы — куча (heap). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:

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

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

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

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

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



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

Но обо всем по порядку.

Понимание роли мозга

Нет невежества страшнее, чем невежество по отношению к самому себе.

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

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

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

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