Часть первая – историческая.

Введение

Существующие алгоритмы сжатия данных можно разделить на два больших класса – с потерями, и без. Алгоритмы с потерями обычно применяются для сжатия изображений и аудио. Эти алгоритмы позволяют достичь больших степеней сжатия благодаря избирательной потере качества. Однако, по определению, восстановить первоначальные данные из сжатого результата невозможно.
Алгоритмы сжатия без потерь применяются для уменьшения размера данных, и работают таким образом, что возможно восстановить данные в точности такими, какие они были до сжатия. Они применяются в коммуникациях, архиваторах и некоторых алгоритмах сжатии аудио и графической информации. Далее мы рассмотрим только алгоритмы сжатия без потерь.
Основной принцип алгоритмов сжатия базируется на том, что в любом файле, содержащем неслучайные данные, информация частично повторяется. Используя статистические математические модели можно определить вероятность повторения определённой комбинации символов. После этого можно создать коды, обозначающие выбранные фразы, и назначить самым часто повторяющимся фразам самые короткие коды. Для этого используются разные техники, например: энтропийное кодирование, кодирование повторов, и сжатие при помощи словаря. С их помощью 8-битный символ, или целая строка, могут быть заменены всего лишь несколькими битами, устраняя таким образом излишнюю информацию.

Вступление

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

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

Буквально на днях для Visual Studio 2010 выпущено два набора официальных обновлений. Первый – Power Tools – нацелен на добавление множества мелких функциональных вещей увеличивающих продуктивность труда. Второй — Modeling Feature Pack добавляет к архитектурным инструментам Visual Studio массу полезных возможностей.

Кроме этих инструментов, в этой статье я расскажу еще о двух полезнейших расширений Visual Studio. Кстати, число расширений в онлайн-хранилище доступном из Extension Manager постоянно растет и уже приближается к 2000 штук.

На днях, после долгого перерыва, надо было поработать на WPF, и возникло желание заменить поднадоевший стандартный вид окон Windows 7 на что-нибудь более вдохновляющее, скажем в стиле Visual Studio 2012:

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

Сегодня мы поговорим о:

• Что такое Mesh Wi-Fi
• Полноценная Mesh Wi-Fi сеть
• Зачем такие сети нужны
• Какие проблемы решает эта технология
• Плюсы и минусы Mesh сетей
• Какие технологии и протоколы используются
• Сравнительная таблица Mesh протоколов
• Mesh сети и органы власти

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

Cloudtunes

Cloudtunes один из тех проектов, глядя на которые я не понимаю мотивации разработчиков выкладывать такие наработки в открытый доступ. Не сочтите меня за сугубо меркантильную личность, но данный проект — это грубо говоря клон iTunes в облаке и это просто великолепный сервис. Cloudtunes обеспечивает единый интерфейс для вашей медиатеки, синхронизируя данные между Dropbox, Youtube, Lastfm и тд. Серверная часть написана на Python (Tornado, Celery, Mongo DB, MongoEngine, Redis), а клиентская на CoffeeScript (Backbone.js, SocketIO, Handlebars, Compass, SoundManager).

OpenVZ — это OpenSource-реализация технологии контейнерной виртуализации для ядра Linux, которая позволяет запускать на одной системе с ядром OpenVZ множество виртуальных окружений с различными дистрибутивами Linux внутри. За счет своих особенностей (контейнерная виртуализация идет на уровне ядра, а не железа) по ряду показателей производительности – плотности, эластичности, требованиям к размеру оперативной памяти, скорости отклика и т.д. – она работает лучше, чем другие технологии виртуализации. Например, тут можно посмотреть сравнения производительности OpenVZ с традиционными системами гипервизорной виртуализации. Но, помимо этого, в Linux и OpenVZ есть и масса вариантов тонкой настройки.
В данной статье мы рассмотрим нетривиальные варианты настроек контейнеров ядра OpenVZ, которые позволяют улучшить производительность всей системы OpenVZ.

Не прошло и года, как я добрался до продолжения статьи про асинхронность. Эта статья развивает идеи той, самой первой статьи про асинхронность [1]. В ней обсуждается достаточно сложная задача, на примере которой будет раскрыта мощь и гибкость использования сопрограмм в различных нетривиальных сценариях. В заключение будут рассмотрены две задачи на состояние гонки (race-condition), а также небольшой, но очень приятный бонус.

Организация Linux Foundation взяла под своё крыло проект Dronecode, цель которого — создание свободной и открытой платформы для беспилотных летательных аппаратов (БПЛА).

Ключевым участником является компания 3D Robotics, которая предоставила в общественное пользование платформу APM Autopilot Suite для управления БПЛА (платформа раньше была известна как ArduPilot).

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

Приветствую Хабравчан!

Думаю, данной темой не многих удивишь — достаточно набрать в поисковике фразу arduino bruteforce и сразу станет понятно, насколько распространен перебор паролей при помощи платформы Arduino. Я же хочу рассказать о том, как это быстро организовать с наименьшим наборов компонентов, без разводки/травления плат и пайки. Сразу оговорюсь, что описанные мною действия носят ознакомительный характер и никому не причинили вреда, ни морального, ни физического… разве что мошенникам.

В предыдущей статье я рассказал об Intel VT-x и расширениях данной технологии для увеличения эффективности виртуализации. В этой статье я расскажу о том, что предлагается тем, кому готов сделать ещё один шаг: запускать ВМ внутри ВМ — вложенная виртуализация.


^{Источник изображения}

Данная статья скорее логическое продолжение моей статьи о балансере: «Создание робота балансера на arduino».
В ней будут очень кратко освещены: простая модель угловой стабилизации квадрокоптера с использованием кватернионов, линеаризация, построение управления для объекта и проверка его в Matlab Simulink, а так же проверка на реальном объекте. В качестве подопытного будет выступать Crazyflie 1.0.

Сейчас оно летает так (на момент съемок я не очень правильно выставил управление):

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

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

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

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

Введение

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

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

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

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

Осторожно, персистентность

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

Шёл уже последний час этого воскресенья, я уже думал идти спать, но добрый sourcerer прислал мне картинку с моего заброшенного сайта, которую можно увидеть ниже, и текст «красиво!». Эти картинки я рисовал лет пять назад, с помощью т. н. алгоритма времени убегания, но для применимости данного алгоритма, нужно уметь для заданного набора преобразований разбивать плоскость на регионы, тогда я не придумал, как это сделать, и больше к этому алгоритму не возвращался. Но сейчас я сразу сообразил, что делать, и написал Диме: «Сначала Random IFS, потом kNN, а затем Escape-Time Algorithm!»



Под рукой у меня был только старый нетбук, который мне дали друзья на время, пока мой ноутбук в ремонте. Дима мне ещё что-то говорил, я ему что-то отвечал, но у меня уже в голове писался код, и я искал на нетбуке хоть какой-нибудь компилятор или интерпретатор и нашёл C++ Builder 6! После этого я понял, что утро я встречу наедине с борландовским компилятором. Через пять часов я отправил Диме новых картинок, но он, как нормальный человек, давно спал…

На конференции Ruxcon в Мельбурне двое австралийских хакеров показали самодельное устройство на Arduino, которое подбирает комбинации на механических замках в некоторых сейфах.

Пентестеры Джей Дэвис (Jay Davis) и Люк Янке (Luke Jahnke) объясняют, что оборудование для взлома таких замков стоит дорого и отсутствует в свободной продаже. Они же с помощью 3D-печати и Arduino изготовили «устройство автонабора» из совсем дешёвых деталей общей стоимостью всего $150. Устройство способно подобрать код к механическому замку стандарта UL Group 2, где комбинация состоит из трёх чисел от 0 до 99, с допустимостью ошибки ±1 в каждом числе.