Введение

Задача о максимальном потоке является классической и имеет множество применений. Напомню постановку проблемы. Дан взвешенный ориентированный граф с неотрицательными весами (пропускными способностями). Выделены две вершины: исток S и сток T такие, что любая другая вершина лежит на пути из S в T. Потоком назовем функцию F: V x V с такими свойствами

1. Ограничение пропускной способности. Поток по ребру не может быть больше его (ребра) пропускной способности.
2. Антисимметричность. Для каждого ребра (u, v): F(u, v) = -F(v, u).
3. Сохранение потока. Для каждой вершины (кроме S и T), количество входящего потока (отрицательного) равен количеству исходящего потока (положительного). Тоесть, алгебраическая сумма потоков для каждой вершины (кроме S и T) равна нулю.

В этом посте вы можете ознакомиться с реализацией поставленной проблемы.

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

Когда-то, давным-давно, тут пиарился один удивительный и абсолютно чистый от рекламы сервис по сиськам OpenBoobs.
Он мне понравился еще тогда, но вот недавно я решил сделать для него маленький виджет. Итак, встречайте OpenBoobs Reader!

Он вам поможет:

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

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

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

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

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

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

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

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

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

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


Если вы начинающий разработчик под iPhone (или другую мобильную платформу) и вам в голову пришла идея вроде «а не сделать ли мне вот эту игрушку из моего детсва», то статья может оказаться полезной для вас.

Если вы просто любите читать о фейлах других, тоже добро пожаловать под кат.

Недавно команда разработчиков MonoDroid через твиттер объявила, что первые 250 тестеров получили доступ к набору инструментов MonoDroid.

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

Ниже представлено видео, в котором по шагам рассказывается как настроить среду MonoDroid с интеграцией в Visual Studio 2010 и написать первое android-приложение на Mono.



Набор инструментов MonoDroid будет доступен разработчикам как под Windows, так и под Linux и MacOS X.

LLVM (Low Level Virtual Machine) — это универсальная система анализа, трансформации и оптимизации программ или, как её называют разработчики, «compiler infrastucture».

LLVM — не просто очередной академический проект. Его история началась в 2000 году в Университете Иллинойса, а теперь LLVM используют такие гиганты индустрии как Apple и Adobe. В частности, на LLVM основана подсистема OpenGL в MacOS X 10.5, а iPhone SDK использует GCC с бэкэндом на LLVM. Apple является одним из основных спонсоров проекта, а вдохновитель LLVM — Крис Латтнер — теперь работает в Apple.

В основе LLVM лежит промежуточное представление кода (intermediate representation, IR), над которым можно производить трансформации во время компиляции, компоновки (linking) и выполнения. Из этого представления генерируется оптимизированный машинный код для целого ряда платформ, как статически, так и динамически (JIT-компиляция). LLVM поддерживает генерацию кода для x86, x86-64, ARM, PowerPC, SPARC, MIPS, IA-64, Alpha.

LLVM написана на C++ и портирована на большинство *nix-систем и Windows. Система имеет модульную структуру и может расширяться дополнительными алгоритмами трансформации (compiler passes) и кодогенераторами для новых аппаратных платформ. Пользовательский фронтенд, как правило, линкуется с LLVM и использует C++ API для генерации кода и его преобразований. Однако LLVM включает в себя и standalone утилиты.

Для тех, кто не без оснований считает C++ не лучшим языком для написания компиляторов, с недавних пор в LLVM включена обертка API для OCaml.

Чтобы понять, что можно сделать с помощью LLVM, и на каком уровне придётся работать, давайте разберёмся,

Приветствую хабраюзеров, в этой статье пойдет речь о внутреннем устройстве компилятора LLVM. О том, что LLVM вообще такое, можно прочитать здесь или на llvm.org. Как известно, LLVM (условно) состоит из трех частей — байткода, стратегии компиляции и окружения aka LLVM infrastructure. Я рассмотрю последнее.

Содержание:

• Сборка LLVM
• Привязка к Eclipse
• Архитектура окружения
• LLVM API
• Оптимизация Hello, World!

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

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

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

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

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

Ищем индекс

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

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

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

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

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

Введение

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

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

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

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

На волне повышенного внимания к мобильному софту, и в частности к App Store, мы тоже решили попробовать свои силы в этой хаотичной, на первый взгляд, массе. iPhone есть, MacBook есть, остается только выбрать что написать. Требования простые: это должно быть просто, это не должно занять много времени и это должно быть дешево. И еще очень хотелось написать такое, что и самим пригодится. Но все пошло не совсем так, как мы предполагали.

Начав программировать под iPad, я не нашёл компонента, подобного полосе прокрутки в приложении iPhoto для iPad.

Я попробовал реализовать что-то подобное.

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

Наверняка многие из вас слышали об ужасно сложных интервью для желающих работать в компаниях типа «Microsoft», «Google» или «Apple» (на самом этот список можно продолжать и продолжать). Еще бы — общеизвестно, что Google каждый день получает порядка 1000 резюме, все именитые компании рассказывают направо и налево, что они ищут не меньше, чем гениев, а на просторах безграничного интернета время от времени появляются вопросы, которые задавались на интервью вроде «Как вы сдвинете гору Фудзи?» или «Сколько мячиков влезет в автобус?» или даже «Как создать хорошую поисковую систему, вроде Google?».

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

Итак, допустим цель «получить работу мечты» поставлена. Что же делать дальше?

Здравствуй, Хабр!
Предлагаю твоему вниманию простой и в то же время эффективный метод борьбы с http DDoS. На основе сервера Xeon 2.5GHz / 4Gb RAM / SAS можно отражать атаку примерно до 300 Мбит/с (значение получено методом экстраполяции).

Способ реализация

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

Область применения

Борьба с Http DDoS на выделенном сервере или ВПС. Максимальная возможная мощность сдерживания DDoS атаки ограничивается физическими возможностями сервера и пропускной способностью канала.

SEO под DDoS-ом

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

Стоимость и эффективность

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

Возможно в Вашем проекте и не пишут try { /* code */ } catch(...) { } для того чтобы избежать исключений при работе с памятью, умеют закрывать хендлы и знают о виртуализации Windows Vista, а программы никогда не падают по непонятным и редко повторяемым причинам.

Тогда Вам повезло, можете переходить к следующему топику.

Экспрессивное и впечатляющее выступление под заголовком Unlearn your MBA, главной темой которого явилось, что начинающему предприятию вредны деньги инвестора. И вот почему:

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

Мне нравятся стоковые фотографии. Но мы должны оставить в прошлом людей в костюмах, пожимающих руки. Пришло время покончить с пресными  и вежливыми фотографиями.

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



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

Года два назад я поднимал знакокому сервер для трекера местной локалки. Вопрос выбора ОС не стоял в принципе, естественно FreeBSD, а версия была взята актуальная на тот момент — 6.2 i386. Но вот состоялся релиз FreeBSD 8.0, и я решил попробовать обновиться до 8-й версии на этом сервере, все равно трекер уже полмесяца не работал из-за битой базы при очередном внезапном отключении питания, а за сервером никто не следил, поэтому пару часов даунтайма никому не помешают.

Питер Шульц, в то время президент компании Porsche, рассказывал как-то историю, которая приключилась вскоре после того, как он попал на эту должность. Его пребывание в компании началось с детального знакомства с ней: он обходил все отделы, чтобы представиться и вникнуть в работу каждого подразделения.



В конструкторском отделе он спросил, участвует ли Porsche в гоночных соревнованиях Le Mans (считается главной гонкой для компаний, производящих спортивные машины). «Нет, — ответили ему, — не участвуем». Это было странно, ведь Porsche — один из лидеров в производстве гоночных машин. Тогда Питер поставил перед ними амбициозную задачу: «Давайте сконструируем машину, которая победит в гонке Le Mans!».