Введение

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

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

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

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

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

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

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

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

Введение

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

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

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

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

Первая статья цикла

Интро

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

Приветствую!

В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.

Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.

По собственной инициативе выкладываю на суд сообщества проект моего друга, со сложно выговариваемым именем Mircea Piturca.

Встречайте: Type Folly — очень простой и удобный онлайн редактор CSS. Для новичков самое оно.

UPD: Автор внес изменения и поправил баги. Спасибо Хабрасообщству.

Преамбула.

В связи с бурным развитием мобильных устройств и ОС Google Android в частности, интерес к разработке программного обеспечения под данную платформу весьма закономерное явление. Как оказалось, он мало чем отличается от обычной разработки на Яве под десктоп/веб, а с учетом возможности использования «стандартного» IDE (Eclipse) путем скачки и встраивания SDK Андроида, а также наличия исчерпывающей документации многие технические вопросы снимаются сами собой. Концептуальный аспект (т.е. идея для реализации в виде ПО) также не заставила себя ждать, благо платформа сравнительно новая, не смотря на недавно вышедшую уже версию 2.1, и конкурентная среда соответственно не такая насыщенная, если взять, к примеру, разработку под тот же iPhone. (Тут могла бы быть развернутая часть о самом ПО, но ввиду некоторых нюансов, таких как незаконченность проекта и отсутствие конкретных результатов, пока ее пропустим).
Оставался последний, и, естественно, самый интересный (логично, не правда ли?) вопрос – денежный, а конкретно – как правильно вывести честно заработанные дензнаки, полученные от продажи ПО на Android Market.

Вдаваться подробности не буду, все-таки статья ориентирована на тех, кто примерно ориентируется в данной теме, скажу коротко — в данном случае под прицелом оказывается сервис обработки онлайновых платежей Google Checkout, который с нерезидентами США изначально не работает. Насколько мне известно, прямых путей решения данной проблемы нет, поэтому пришлось искать обходные дорожки.

Пытались снять жилье без посредников, просмотрели массу сайтов, прозвонили массу объявлений. Каждый раз радовала фраза в объявлении — «агентам просьба не беспокоить» или «посредникам просьба не беспокоить», а на деле выяснялось, что это и есть агенты.
И вот, после нескольких страниц поиска в гугле, в попытке найти хоть один сайт с объявлениями от настоящих собственников (понятно, что предложения заплатить за базу телефонов собственников были закрыты сразу же), нервы сдали и родился сайт www.etoagent.ru. Этот сайт — это проверка телефонов агентств недвижимости для тех, кто хочет снять жилье без посредников. Любые указанные в объявлениях телефоны можно проверить: действительно ли указанный телефон не принадлежит риэлтору.
Может кому-то пригодится и сэкономит время.

Кирпичёв правильно пишет про небрежность интуитивного понимания императивных языков: http://antilamer.livejournal.com/300607.html.

Однако, мне кажется, что важно было бы озвучить, что всё то, что сейчас скрывается под именем «монада» — само по себе достаточно спутанно в плане педагогики и евангелизма.  Классическая шутка SPJ/Вадлера звучит как «нам следовало назвать ЭТО warm fuzzy things, чтобы не пугать людей теоркатом».  Шутка поразительно недальновидная.   Проблема лежит в той же плоскости, что и называние стоящих перед тобой задач словом «stuff» (это то, с чем борется Аллен в своём GTD).  
Монады в настоящий момент являются миру как сложный ком из исторически обусловленных причин, проблем, решений, технических возможностей и теоретических основ (как алгебраических, так и аспектов теории вычислений). 
Все эти наслоения можно (и нужно) расщепить в первом приближении так (порядок приблизительно случайный):

• стремление к экспликации эффектов (чистое внедрение императивно-подобных моментов в вычисление), (см. труды Вадлера);  здесь мы включаем ввод-вывод, STM, параллельные вычисления и проч.)
• удобный механизм для материализации базовых микро-стратегий вычисления — вызов функции (call-by-name/call-by-value), многозначность, смена состояния (присваивания!), обработка исключений, останов при неудаче, continuations, бэктрекинг;

• typeclasses как механизм внесения монад в язык, и как следствие — удобный механизм для мета-перехвата вычисления (невероятно удобно для domain-specific embedded languages);
• строгая проверка типов, проистекающая из использования typeclasses, и позволяющая механически проверять корректность использования объектов;
• существование монадических законов, в которые укладываются монады, что позволяет материализовывать абстрактные комбинаторы; это позволяет находить порой неожиданные изоморфизмы между различными предметными областями, а также помогает при оптимизации и верификации программ;
• проработанная теоретическая основа (теория категорий), на которой базируются монады; это облегчает жизнь создателям базовых библиотек, на которых потом базируется всё реальное программирование;
• монады — лишь один из классов в длинной цепочке интересных алгебраически обусловленных классов, некоторые из которых слабее монад, а некоторые — сильнее: Functor, Applicative, Monoid, Traversable, Foldable, Monad со товарищи, Arrow со товарищи;
• стремление к материализации некоторых видов вычислений в алгебраическую структуру (моноидальные вычисления); это открывает широкий простор для оптимизаций, верификации программ, создания абстрактных комбинаторов, а также устранение unbounded recursion — по мощности результатов это похоже на то, как когда-то ввод-вывод был надежно изолирован в IO Monad;

Потратим по паре абзацев на каждый пункт.

Доброго времени суток, хабрапользователи!

После моих постов:
Дистанционное управление по ИК
Ant-bot. Ворклог. Часть 1
Создаем робота в домашних условиях
Меня довольно часто стали спрашивать о том, какую литературу можно почитать по данному предмету. Чтобы помочь всем и сразу, я решил написать данный пост. =)
Под катом вы можете посмотреть — какую литературу использую я в процессе своих работ.

О визуализация графов в вебе говорили здесь, навеяно этой статьей.

Под катом обзор JavaScript библиотек для рисования графов, диаграмм и прочей красоты.

Разрешите представить вашему вниманию новый проект (стартап) www.livebase.ru — социальную сеть по аренде квартир «Живая база».
Главная страница сайта www.livebase.ru (регистрация не обязательна)
Страница базы данных по аренде квартир — www.livebase.ru/estates

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

Довольно часто при верстке сайта возникает необходимость размещать блоки одинаковой ширины, но разной высоты в контейнере с переменной шириной (читай резиновом). Плюс на этот список может применяться фильтр, который JS-ом скрывает или показывает элементы списка, при этом он не должен разрушать «строки», верстку, или образовывать дыры, поэтому решения на таблицах не катят сразу. Простейший пример — каталог товаров:

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

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

Стэнфордский курс по основам языков программирования выложен на YouTube.



27 лекций минут по 20 каждая ведут стэнфордский преподаватель Джерри Кейн (экс-Стэнфорд, нынче Facebook), последняя лекция по Haskell преподается Сашей Рашем (Facebook). Рассматриваются концепции и основы C (куда ж без него), ассемблера, C++, Scheme, Python и Haskell.

Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Под катом очень-очень много текста, т.к. рассказывается один из вариантов решения данной задачи «в картинках» для тех, кто мало знаком с графами. Листинг прилагается.

0. Присказка

В некотором царстве, в некотором государстве жил-был программист. Звали его, как полагается, Иван. Был он настоящим спецом, обладал всеми Тремя Великими Добродетелями Программиста, то есть был ленив, спесив и нетерпелив. Случилась в том царстве печаль великая: кризис. И выгнали Ваню с работы без выходного пособия. Горевал Ваня долго, а потом собрался с духом и разослал резюме по всему белу свету. Долго ли, коротко ли, вызвали Ваню на собеседование. Требований к соискателю было много, но главное — требовалось хорошо владеть регулярными выражениями. До собеседования — почти месяц, готовься — не хочу. Будучи человеком серьёзным, готовиться Иван решил обстоятельно. 3 недели и 3 дня он лежал на печи, почитывал Хабр и думал, как же неслыханно обстоятельно он будет готовиться. До собеседования остался 1 день. Ванюша мысленно обругал работодателей, которые назначают собеседование так скоро, что совсем подготовиться не успеваешь, слез с печи, сдал пивные бутылки и на вырученные деньги купил книжку по регексам. Читал он её до полного изнеможения, пока не отключился. Утром мы найдём сонную физиономию Ванюши лежащей, как на подушке, на этой самой книжке под Хабракатом.

Язык PHP очень легок для изучения. Это, а так же обилие литературы «Освой _что_угодно_ за 24 часа» породило большое количество, мягко говоря, некачественного кода. Как следствие, рано или поздно любой программист, который выходит за рамки создания гостевой книги или сайта-визитки сталкивается с вопросом: «а если я здесь немножко добавлю, все остальное не ляжет?» Дать ответ на этот вопрос и на многие другие может юнит-тестирование.

В самом начале хочется оговориться — здесь речь не будет идти о TDD и методологиях разработки ПО. В данной статье я попробую показать начинающему PHP-разработчику основы использования модульного тестирования на базе фреймворка PHPUnit

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





Основная задача игры: помочь гитаристу быстро, эффективно, наглядно и в игровой форме преодолеть «нотный барьер» и приобрести навык быстрого нахождения ладов на грифе гитары.

В комментариях Хабра упоминались вопросы по использованию представлений. Данный топик является обзором представлений, появившихся в MySQL версии 5.0. В нем рассмотрены вопросы создания, преимущества и ограничения представлений.

Что такое представление?

Представление (VIEW) — объект базы данных, являющийся результатом выполнения запроса к базе данных, определенного с помощью оператора SELECT, в момент обращения к представлению.

Представления иногда называют «виртуальными таблицами». Такое название связано с тем, что представление доступно для пользователя как таблица, но само оно не содержит данных, а извлекает их из таблиц в момент обращения к нему. Если данные изменены в базовой таблице, то пользователь получит актуальные данные при обращении к представлению, использующему данную таблицу; кэширования результатов выборки из таблицы при работе представлений не производится. При этом, механизм кэширования запросов (query cache) работает на уровне запросов пользователя безотносительно к тому, обращается ли пользователь к таблицам или представлениям.