Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

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

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

Зачастую работа «в поле» требует сбора и анализа информации на сайте заказчика в условиях наличия крайне скудного списка утилит. В частности собрать информацию об использовании системы ввода-вывода в течении дня.

В статье я попробую показать, как располагая только iostat и gnuplot можно попробовать провести анализ системы и какие выводы можно сделать.

Я не претендую на доскональное владение предметом и точное использование терминов. Более того, я постараюсь говорить «обычным» языком и не бросаться терминами.

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

Совсем недавно в публичный доступ попали базы паролей популярных почтовых сервисов [1,2,3] и сегодня мы их проанализируем и ответим на ряд вопросов о качестве паролей и возможном источнике (или источниках). Так же мы обсудим метрики качества отдельных паролей и всей выборки.

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

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

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

1. Описание данных
2. Невалидные пароли и не-пароли
3. Распределение длины паролей
4. Распределение надёжности паролей
5. Словарная атака
6. Топ паролей
7. Выборка Gmail
8. Выборка Rambler
9. Анализ открытых источников
10. Заключение

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

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

Меня настолько заинтересовал вопрос о книгах, что я решил начать новую серию статей на своём сайте catonmat о моих топ-100 книгах о программировании, программном обеспечении, науке, физике, математике и компьютерах. В каждой статье я буду размещать по пять книг, ведь разбивать огромное задачи на маленькие подзадачи — это самый простой способ их решать (GTD — get things done).

Взгляните на мою книжную полку, чтобы убедиться, что я настоящий ботаник:

Когда я начала заниматься Ардуино, мне казалось, что весь мир только и делает, что занимается тем же. На самом деле оказалось, что, как и мне, многим просто трудно начать, «въехать» в саму тему. Поэтому я решила написать быстрый гайд для того, чтобы вы сразу могли взять несколько компонентов и попробовать эту игрушку. Вероятно, после прочтения, вы даже сразу во многом поймёте что к чему и без моих будущих постов. Итак.


Если вы не попробовали Ардуино только потому, что не можете начать, не зная что к чему, я сейчас спасу вас.

Часто на собеседованиях в магистратуру СПбАУ или CS центр ребята затрудняются ответить на вопросы об элементарных понятиях как из классической, так и из дискретной математики. А эти знания требуются для освоения курсов алгоритмов, машинного обучения и прочих Computer Science дисциплин. Чтобы облегчить подготовку, Академический университет совместно с Computer Science Center этой весной запускают два онлайн-курса:

1. Ликбез по дискретной математике. Преподаватель — А.В. Омельченко (СПбАУ РАН).
2. Введение в математический анализ. Преподаватель — А.И. Храбров (СПбГУ, СПбАУ РАН, CS центр).

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

Курсы размещены на дружественной платформе Stepic.

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

Безопасность

Тактика хакера: практическое руководство по тестированию на проникновение (The Hacker Playbook: Practical Guide To Penetration Testing)

Книга написана в стиле планирования футбольной игры. Здесь подробно и пошагово разобраны проблемы и трудности, с которыми сталкиваются специалисты по безопасности, тестируя системы защиты. В частности, рассматриваются атаки на различные типы сетей, обход антивирусов и взлом систем безопасности. Автор книги — Питер Ким, специалист по IT-безопасности с многолетним опытом, CEO компании Secure Planet.

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

В Яндексе тестировщику невозможно без автоматизации. Мы даже развиваем экспериментального робота, который способен брать на себя функциональное тестирование. В какой-то момент мы поняли, что не так много людей осознают, сколько сейчас есть возможностей работать не 12 часов, а головой. Собрав весь свой опыт в тестировании и деплое, мы открыли в питерском офисе Яндекса Школу автоматизации процессов разработки. У нас получилась школа, где каждый, кто пишет код, может получить базовый набор знаний о том, как собрать, запустить и поддерживать сервис в продакшене так, чтобы это стоило недорого.



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

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

Волею судеб мне довелось разбираться с организацией многозадачности, точнее псевдо-многозадачности, поскольку задачи делят время на одном ядре процессора. Я уже несколько раз встречала на хабре статьи по данной теме, и мне показалось, что данная тема сообществу интересна, поэтому я позволю себе внести свою скромную лепту в освещение данного вопроса.
Сначала я попытаюсь рассказать о типах многозадачности (кооперативной и вытесняющей). Затем перейду к принципам планирования для вытесняющей многозадачности. Рассказ рассчитан скорее на начинающего читателя, который хочет разобраться, как работает многозадачность на уровне ядра ОС. Но поскольку все будет сопровождаться примерами, которые можно скомпилировать, запустить, и с которыми при желании можно поиграться, то, возможно, статья заинтересует и тех, кто уже знаком с теорией, но никогда не пробовал планировщик “на вкус”. Кому лень читать, может сразу перейти к изучению кода, поскольку код примеров будет взят из нашего проекта.
Ну, и многопоточные котики для привлечения внимания.

Привет, Хабр. Я знаю, что здесь уважают и любят выступления TED. Поэтому я не мог пройти мимо новости о том, что сайт ted.com после редизайна обновил плейлист «20 самых популярных выступлений на TED всех времен». Это яркий пример того, как путем послабления копирайта (все лекции TED находятся в открытом доступе, распространяются по лицензии CC, согласно которой разрешено все, кроме коммерческого использования) и организации краудсорсинга (все переводы выполняют волонтеры) можно добиться впечатляющих результатов…



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

Рейтинг составлен по количеству просмотров (в статистике учитывались данные с TED.com, Youtube, iTunes, Hulu, встроенных фреймов, количества скачиваний и т.д.)

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

23 июня 2012 года Алану Тьюрингу исполнилось бы 100 лет. И хотя эта дата осталось незамеченной в России (и на Хабре), ее широко отмечали в зарубежном научном сообществе. 2012 год бы провозглашен годом Алана Тьюринга. В праздновании юбилея приняли участие многочисленные университеты, научные лаборатории, ассоциации, коммерческие компании. Он включил в себя лекции, конференции, выставки, фильмы, книги, написание стихов, посвященных Тьюрингу, учреждение стипендий, а так же различные соревнование. Одно из соревнований особенно привлекло мое внимание: Turing100 — очень масштабный тест Тьюринга. Это было самое большое соревнование среди примерно 150 тестов Тьюринга, проведенных к сегодняшнему дню. Обычно в тесте Тьюринга участвуют четыре системы и четверо судей. В соревновании Turing100 приняли участие пять чат-ботов, 30 судей и 25 скрытых человек.


Автор изображения — Harjit Mehroke

Для тех, кто не смог посетить Курсы информационных технологий, видеоролики всех лекций выложены в свободный доступ. Это лекции по полтора-два часа на базовые темы: операционные системы; архитектура ЭВМ; устройство GNU/Linux; системы хранения данных; файловые системы; сети и протоколы; виртуализация; безопасность.

1 часть. Заземление
(общая информация, термины и определения)

2 часть. Традиционные способы строительства заземляющих устройств
(описание, расчёт, монтаж)

3 часть. Современные способы строительства заземляющих устройств
(описание, расчёт, монтаж)

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

Д. Основные способы строительства

Д1. Модульное заземление (для обычных грунтов)

Д1.1. Особенности решения

Д1.1.1. Универсальность и простота применения
Д1.1.2. Долгий срок службы
Д1.1.3. Зависимость уменьшения сопротивления заземления от увеличения глубины электрода
Д1.1.4. Суперкомпактность
Д1.1.5. Никакой сварки

Д1.2. Расчёт получаемого сопротивления заземления
Д1.3. Монтаж
Д1.4. Достоинства и недостатки

Д2. Электролитическое заземление (для вечномёрзлых или каменистых грунтов)

Д2.1. Особенности решения

Д2.1.1. Простота применения в вечномёрзлых или каменистых грунтах
Д2.1.2. Компактность
Д2.1.3. Образование талика
Д2.1.4. Никакой сварки

Д2.2. Расчёт получаемого сопротивления заземления
Д2.3. Монтаж
Д2.4. Достоинства и недостатки

Д. Основные способы строительства

Напомню о достоинствах и недостатках традиционных способов строительства заземлителей, описанных в прошлой части:

1 часть. Заземление
(общая информация, термины и определения)

2 часть. Традиционные способы строительства заземляющих устройств
(описание, расчёт, монтаж)

3 часть. Современные способы строительства заземляющих устройств
(описание, расчёт, монтаж)

2 часть. Традиционные способы строительства заземляющих устройств (описание, расчёт, монтаж)

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

Г. Основные способы строительства

Г1. Несколько коротких электродов (“уголок и кувалда”)

Г1.1. Особенности решения

Г1.1.1. Промерзание грунта зимой
Г1.1.2. Взаимное “экранирование”/ “затенение” электродов

Г1.2. Расчёт получаемого сопротивления заземления и необходимого количества заземляющих электродов
Г1.3. Монтаж
Г1.4. Достоинства и недостатки
Г1.5. Уменьшение количества электродов

Г2. Одиночный глубинный электрод (“обсадная труба”)

Г2.1. Особенность решения
Г2.2. Расчёт получаемого сопротивления заземления
Г2.3. Монтаж
Г2.4. Достоинства и недостатки

Г. Основные способы строительства

Напомню, в прошлой части я остановился на общем подходе…

Мой рассказ будет состоять из трёх частей.

1 часть. Заземление
(общая информация, термины и определения)

2 часть. Традиционные способы строительства заземляющих устройств
(описание, расчёт, монтаж)

3 часть. Современные способы строительства заземляющих устройств
(описание, расчёт, монтаж)

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

Если читатель обладает теоретическими знаниями и интересуется только практической реализацией — ему лучше пропустить первую часть и начать чтение со второй части.

Если читатель обладает необходимыми знаниями и хочет познакомиться только с новинками — лучше пропустить первые две части и сразу перейти к чтению третьей.

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

Некоторая часть текста является компромиссом между точностью и желанием объяснить “человеческим языком”, поэтому допущены упрощения, могущие “резать слух” технически подкованного читателя.

Введение

Я продолжаю серию статей посвящённую тематике pattern recognition, computer vision и machine learning. Сегодня я вам представляю обзор алгоритма, который носит название eigenface.



В основе алгоритма лежит использование фундаментальных статистических характеристик: средних (мат. ожидание) и ковариационной матрицы; использование метода главных компонент. Мы также коснёмся таких понятий линейной алгебры, как собственные значения (eigenvalues) и собственные вектора (eigenvectors) (wiki: ru, eng). И вдобавок, поработаем в многомерном пространстве.
Как бы страшно всё это не звучало, данный алгоритм, пожалуй, является одним из самых простых рассмотренных мною, его реализация не превышает нескольких десятков строк, в тоже время он показывает неплохие результаты в ряде задач.

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

Я знал про них давно, но как-то скептически относился к бизнесу на базе Ардуино, когда рядом находится Китай, e-bay, таобао — где можно напрямую и достаточно недорого заказать Ардуино и другие комплектующие.

Но вот к нам в хакспейс попал новый набор «Матрешка Z», и я понял, что Амперка не просто продаёт Ардуино — они делают качественные образовательные наборы по электронике для начинающих.

Что же внутри?

Эта заметка навеяна мелькавшими последнее время на хабре постами двух тематик — «интересные команды unix» и «как я подбирал программиста». И описываемые там команды, конечно, местами интересные, но редко практически полезные, а выясняется, что реально полезным инструментарием мы пользоваться и не умеем.
Небольшое лирическое отступление:
Года три назад меня попросили провести собеседование с претендентами на должность unix-сисадмина. На двух крупнейших на тот момент фриланс-биржах на вакансию откликнулись восемь претендентов, двое из которых входили в ТОП-5 рейтинга этих бирж. Я никогда не требую от админов знания наизусть конфигов и считаю, что нужный софт всегда освоится, если есть желание читать, логика в действиях и умение правильно пользоваться инструментарием системы. Посему для начала претендентам были даны две задачки, примерно такого плана:
— поместить задание в крон, которое будет выполняться в каждый чётный час и в 3 часа;
— распечатать из файла /var/run/dmesg.boot информацию о процессоре.

К моему удивлению никто из претендентов с обоими вопросами не справился. Двое, в принципе, не знали о существовании grep.



Поэтому… Лето… Пятница… Перед шашлыками немного поговорим о grep.