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

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

Тема сегодняшней лекции

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

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

Ищем индекс

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

Сейчас наличие нескольких подключений к интернет на одном, в том числе и домашнем сервере — не редкость. Городские локалки, ADSL, 3G модемы… Добавим к этому сети домашние локальные и внешние виртуальные (VPN), и получим ядрёную смесь интерфейсов, между которыми необходимо роутить трафик, балансировать трафик между разными каналами в интернет (когда они есть), и переключаться с нерабочих каналов на рабочие (когда они отваливаются).

Судя по постам в инете, большинство людей, столкнувшихся с этой ситуацией, очень плохо представляет себе, как это настраивается. Надо отметить, что в линухе действительно управление роутингом весьма сложное и запутанное — следствие эволюционного развития и поддержки (частичной) совместимости. Я хочу описать принципы настройки роутинга multihomed серверов на конкретном, достаточно сложном, примере: на сервере три физических сетевых интерфейса (один в домашнюю локалку и два к ADSL-модемам), два ADSL-подключения (ADSL-модемы в режиме bridge, так что pppd поднимает этот же сервер) к разным провайдерам (одно со статическим IP, второе с динамическим), плюс VPN на сервер компании — итого шесть интерфейсов.

Тема достаточно сложная, поэтому для понимания материала потребуется хотя бы минимальное понимание работы роутинга (что такое default route и gateway), файрвола (маркировка пакетов, отслеживание соединений, связь между разными таблицами и цепочками файрвола и роутингом), pppd (скрипты ip-up/ip-down) и протоколов IP и TCP.

Прелюдия

Доброго времени суток, уважаемые читатели.
Скорее всего, большинству из вас известно, что из себя представляет асимметричный алгоритм шифрования RSA. В самом деле, этому вопросу по всему рунету и на этом ресурсе в частности посвящено столько статей, что сказать о нем что то новое практически невозможно.
Ну что там, ей богу, можно еще придумать и так все давным-давно понятно. Рецепт приготовления прост:
Два простых числа P и Q.
Перемножить до получения числа N.
Выбрать произвольное E.
Найти D=E^-1(mod(P-1)(Q-1)).
Для шифрования сообщение M возводим в степень E по модулю N. Для дешифрования криптотекст C в степень D по все тому же модулю N. Все криптопримитив готов. Берем и пользуемся, так? На самом деле, не так. Дело все в том, что это и в самом деле не более чем криптопримитив и в реальном мире все самую чуточку сложнее.

Предисловие

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

Единственное, что меня напрягало, — необходимость постоянного переключения раскладки для того, чтобы полноценно работать в Vim. Да, конечно, можно делать маппинги для клавиш, но это далеко не всегда работает.

Итак, мы все знаем про подлых пользователей c UID=0 в unix, которых может быть больше одного.

Посмотрим, как такое же (а на самом деле, даже более страшное) организовывается в инфраструктуре Windows. Разумеется, мы говорить будем не про локальные виндовые учётные записи, а про Active Directory, т.е. говорить будем об администраторе домена. Или, даже, хуже, об enterprise administrator.

Итак, истина номер один: у объектов в active directory есть атрибуты и права доступа.
Истина номер два: эти атрибуты можно менять.

Как легко понять, мы МОЖЕМ сделать учётную запись с фантастическими правами, к которой не будет доступа НИ У КОГО. Однако, он сможет логиниться, блокировать, разблокировать, менять свои атрибуты и атрибуты чужих людей.

В самом страшном случае, это будет пользователь с волшебным SID-*500, которого не позволяет удалить уже сама винда. (Для этого нужно переименовать, а на его место положить другого пользователя с ником Administrator и с полными правами).

Повсеместное распространение NAT казалось препятствует свободному обмену трафиком между компьютерами, находящимися за одним из них, и практически делает это невозможным, если оба компьютера скрыты за разными NAT серверами, естественно если вы не администратор обоих NAT серверов. Однако Samy Kamkar легко и непринужденно не только преодолел это, но и сделал программу которая позволяет преодолевать подобные препятствия. В настоящее время данная программа доступна только пользователям *nix подобных систем.

Pwnat — этот инструмент позволяет любому количеству клиентов, находящихся за одним NAT-сервером, соединяться с сервером стоящим за другим NAT, при этом никакой проброски портов на серверах не требуется и никаких прочих инструментов не используется. Серверу не надо ничего знать о клиенте который с ним соединяется. Проще говоря это такой прокси сервер, который стоит за одним NAT и работает с клиентами, стоящими за другим NAT, между ними нет никакого дополнительного посредника, никаких DNS-фокусов и никакого пива админам. Скажу честно — я тоже в это сначала не поверил.

Клиент может подключаться через такой сервер к любым ресурсам, либо только тем что ограничены сервером pwnat. Данный инструмент основан на построении UDP-тоннеля. Принцип работы весьма оригинальный и прекрасно описан автором, рекомендую ознакомиться, ибо решение данного вопроса оказалось весьма интересным и неожиданным. Давно не встречал ничего подобного.

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

Недавно прошла 82-я церемония вручения всем известной премии «Оскар». Все удостоившиеся наград фильмы вы, скорее всего, уже видели. А короткометражный мультфильм «Логорама» говорит вам о чем-нибудь? Мне ни о чем не говорил, пока не рассказал друг.

 

Недавно на профильном ресурсе один программист задал вопрос: «Что использовать в сервере ММО для работы с потоками?». Программист склонялся к Intel TBB, но даже не к базовым примитивам, а к кастомному планированию задач (task scheduling). Ну нравится TBB — ну и ладно. А немного позже я увидел исходники сервера ММО другого программиста, который недавно начал переписываться его с нуля для улучшения архитектуры. И там было очень много велосипедов, которые писались самим программистом вместо того что бы использовать сторонние компоненты такие как boost (к примеру класы обертки над pthread-ом, и это в 2010 году, когда boost.thread уже почти в стандарте). Была там реализована и поддержка пула потоков с планировщиком задач. Тема эта мне очень интересна и я начал копать информацию о готовых решениях планировки задач (как в TBB) и нашел boost.task, про что и решил написать.

Итак, в новостях снова пишут, что кто-то еще умер из-за игромании. Да, опять Корея.

Какого ...? послушайте, я не пытаюсь доказать что видео игры — это героин. Я полностью понимаю, что в данном случае у жертвы было много проблем в жизни. Но, половина из вас знает что World of Warcraft затягивает и что доктора считают игровую зависимость серьёзной проблемой. А вопрос вот в чем: может быть какие-то игры намеренно разрабатывались, чтобы заставлять вас играть в них, даже если вы не получаете от этого удовольствия?

Цель моей статьи — дать начальное представление читателю о том, как работать с памятью в Objective C, рассказать о работе с KeyChain и показать новую версию своего приложения для монтирования SSHFS, которая была написана всего за несколько дней (в сумме), но уже вполне может составлять конкуренцию громоздкому Macfusion.app, и которая работает без напильника и не пишет ваши пароли в открытом виде в системный лог.

Многие достаточно часто сталкиваются с необходимостью создания различных диаграмм, графов, деревьев для удобного представления информации. Особенно важным этот вопрос может оказаться при создании презентаций. Большинство офисных пакетов предоставляют возможность создавать красивые диаграммы при помощи интерактивного интерфейса. А если нужно создать большую диаграмму? Или записать в ней математические формулы? Сосредоточиться на содержании, а не оформлении и расположении элементов на экране?

Преимущества использования LaTeX уже неоднократно обсуждались. Так же как и способы создания презентаций при помощи beamer и векторная графика из пакета PGF/Tikz. Но возможно ли получить в LaTeX диаграммы, не уступающие по внешнему виду полученным в больших и сложных пакетах? Один из способов предложен ниже.

bpython — это красивый и функциональный интерфейс к стандартному интерпретатору Python для *nix. Он распространяется под Лицензией MIT и обладает следующими интересными возможностями:

• In-line подсветка синстаксиса
• Автодополнение кода с предложениями
• Автовыравнивание кода
• Pastebin
• Сохранение введённого кода в файл
• Восстановление удалённой строки («Rewind»)
• Предложение параметров для функций

Я, как и многие программисты, после знаменитого выступления Линуса Торвальдса о Git на Google Talks заинтересовался распределенными системами управления версиями, а в особенно Git.

Я довольно таки свободно читаю на английском, но мне приятнее читать на русском языке, при условии нормального перевода.
Существует замечательная книга «Git Magic» Бена Лина (Ben Lynn).
Благодаря труду многих людей вышел первый черновой вариант этой книги. Всех желающих улучшить перевод — приглашаю под кат.

Обратите внимание на вот эту иллюстрацию:



Красиво, правда?

Плазмоид (plasmoid) — это виджет рабочего стола в KDE4 Desktop. Любой видимый элемент управления на рабочем столе является плазмоидом, будь то часы, системный трей, монитор загруженности процессора или окошко с прогнозом погоды.

Этот урок описывает создание плазмоида, умеющего делать запросы к некоему серверу и показывать полученный результат. Так как сервер требует авторизации пользователя, будет разобран процесс хранения данных учетной записи пользователя в KWallet. Язык разработки: Python.

Антивирусное программное обеспечение, которое предлагалось в качестве публичной бета-версии с апреля 2009, получило более широкую огласку в прессе, чем обычные бесплатные антивирусные программные продукты, благодаря своей облачному подходу. Информация из всех компьютерных систем, с которыми работает Cloud Panda Antivirus, автоматически делится со всеми другими пользователями.



И версия 1.0 вводит дополнительные усовершенствования по сравнению с бета-версиями и обычными антивирусными программами.

Оригинал статьи на английском. Перевод: Boten, Deniska, MaxElc

Несколько дней назад я (здесь и далее — автор оригинальной статьи — Прим. пер.) написал о книгах, которые могут скачать начинающие пользователи, и прочитать их, чтобы изучить Linux самостоятельно. Сегодня в секции о Linux у нас есть кое-что и для опытных пользователей. Перед вами несколько советов, которые вы должны попробовать, если вы опытный пользователь Ubuntu Linux

Год назад Ян Кларк, известный как создатель распределённой сети Freenet, выступил с ещё одной революционной инициативой. Он предложил создать новый язык программирования для распределённых вычислений, логика которого будет идти «не от данных, а от вычислений», чтобы любые написанные на таком языке программы можно было естественном образом распараллеливать по неограниченному количеству процессоров и серверов. Это очень важная задача, если учитывать повсеместный переход на распределённые вычисления. И до сих пор нет нормального фреймворка для создания распределённых программ.

Як Кларк сделал на базе Scala 2.8 первый прототип языка Swarm. Вот исходные коды и инструкция по установке.

META-теги

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

META-теги имеют два возможных атрибута

— <META HTTP-EQUIV="имя" CONTENT="содержимое">
— <META NAME="имя" CONTENT="содержимое">
META-теги должны находиться в заголовке HTML-документа между <HEAD> и </HEAD> (особенно это важно для документов, использующих фреймы).

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