Алгоритмы *

Перед прочтением статьи рекомендую посмотреть посты про splay-деревья (1) и деревья по неявному ключу (2, 3, 4)

Динамические деревья (link/cut trees) мало освещены в русскоязычном интернете. Я нашел только краткое описание на алголисте. Тем не менее эта структура данных очень интересна. Она находится на стыке двух областей: потоки и динамические графы.

В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. Улучшенные алгоритмы Диница и проталкивания предпотока работают за и соответственно. Если вы не знаете, что такое поток, и на лекциях у вас такого не было, спешите пополнить свои знания в Кормене.

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

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

Вступление

Существует множество игр, где игроку необходимо искать слова из определенного набора букв. Вот две наиболее популярные из них.
1. 4 фото 1 слов (4 Pics 1 Word) AppStore, Google Play
У этой игры довольно много реализаций, но идея у всех одна.
2. Словомания (Wordsmania) AppStore, Google Play

Довольно-таки часто встречается задача: проверить, совпадает ли строка с другими строками из набора. Например, вам нужно проверить каждое слово из сообщения на форуме на предмет того, не содержится ли оно в списке запрещённых. Распространённое решение: создать массив со списком запрещённых слов, а затем с помощью функции in_array() делать проверку. Есть способы повысить производительность такого алгоритма.

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

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

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

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



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

Начать рассказ стоит с истории о том, как на Малом мехмате двум группам учеников – восьмиклассникам и одиннадцатиклассникам дали решать одну и ту же задачу. Четыре деревни расположены в вершинах квадрата со стороной четыре километра. Существует ли система дорог, которая связывала бы все эти деревни между собой и имела бы суммарную длину не превосходящую 11 километров.

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

Алгоритм Коха-Жао для встраивания информации использует частотную область контейнера и заключается в относительной замене величин коэффициентов дискретного косинусного преобразования (ДКП). Изображение разбивается на блоки размерностью 8×8 пикселей и к каждому блоку применяется ДКП. Каждый блок пригоден для записи одного бита информации.

От переводчика:

Доброго времени суток!
Недавно я искал способы повышения скорости работы детектора Виолы-Джонса и натолкнулся на интересную статью 2013 года «RASW: a Run-time Adaptive Sliding Windowto Improve Viola-Jones Object Detection». В ней представлен эффективный подход к улучшению работы детекторов, основанных на принципе сканирующего окна и каскадных классификаторах. Я не нашел описания данного подхода на русском языке и решил восполнить этот пробел. В данном переводе я опустил описание алгоритма Виолы-Джонса, так как о нём уже много рассказано, в том числе и на хабре habrahabr.ru/post/133826.

Однажды для презентации мне понадобились анимированные графики. С графиками, собственно, проблем не возникло, а для их анимации пришлось воспользоваться еще одним пакетом animation, который можно установить из CRAN.

Здравствуй хабрачитатель! Меня зовут Константин и я программист, а именно занимаюсь программированием систем «Умный дом».
За четыре года работы в этой области, довелось попробовать много интересных контроллеров и ПО для решения задач домашней автоматизации. Одними из интереснейших устройств с которыми мне приходилось иметь дело — это устройства компании Global Cache серии IP2IR. Их предназначение состоит в том что-бы принять текстовую команду от клиента и излучить ее через светодиод ик-спектра.
Использование подобных устройств упрощает жизнь пользователям сразу по нескольким направлениям:

• в качестве ПДУ можно использовать планшеты, телефоны и ПК (с небольшой оговорочкой, нужен специальный софт);
• управление можно централизовать т.е. специальный софт можно поднять на сервере и обращаться к нему;
• в прицельной стрельбе нет необходимости, если с телевизором, например, таких проблем нет (мы в него и так смотрим), то вот для устройств вроде Blu-Ray проигрывателей или MediaServer'ов это может стать проблемой в случае если они заперты в шкафу или работают в режиме мультирум;
• одна кнопка ПДУ может выполнить целый макрос, например включить телевизор и Blu-Ray, затем переключить ТВ на нужный источник, например HDMI1, и пользователь может вообще не париться о том где и как у него подключены устройства.

Такая игрушка жизнь конечно упрощает, но и по карману тоже бьет, если мне не изменяет память, то GlobalCache для управления тремя устройствами стоит порядка 6000-7000 деревянных рублей. Не очень гуманное ценообразование, вот и было решено сделать собственную реализацию подобного устройства.

Материалы этого поста задержались с выходом в свет на 4 месяца. Мы — молодая команда разработчиков, и только учимся нарушать dead-лайны, но кажется, что получается уже неплохо. Предыстория в этой статье, где мы и обещали выложить продолжение. Рассказ пойдёт о том, как же наше приложение работает (или не работает, решать читателю).

Какое приложение? Мы — команда проекта Viewaide (бывший EyeDoc) и пишем софт, который при помощи веб-камеры определяет параметры усталости глаз и выводит уведомления, задача которых снизить риск ухудшения зрения вследствие долгой работы у монитора. Чем 100 раз услышать, лучше 1 раз увидеть.



Скачать и попробовать можно по этой ссылке, как говорится, “бесплатно, без смс”. Кроме софта, у нас имеется ещё и часть web-сервиса, но обо всём по порядку.

На сайте TopCoder размещён новый конкурс NASA Asteroid Grand Challenge Series. Задача конкурса — помочь в решении проблемы астероидов, которые могут врезаться в Землю и уничтожить человеческую расу. Конкретно, от программистов требуется разработать новые алгоритмы распознавания астероидов на изображениях с земных телескопов.

Доброго времени суток, читатель. Random Forest сегодня является одним из популярнейших и крайне эффективных методов решения задач машинного обучения, таких как классификация и регрессия. По эффективности он конкурирует с машинами опорных векторов, нейронными сетями и бустингом, хотя конечно не лишен своих недостатков. С виду алгоритм обучения крайне прост (в сравнении скажем с алгоритмом обучения машины опорных векторов, кому мало острых ощущений в жизни, крайне советую заняться этим на досуге). Мы же попробуем в доступной форме разобраться в основных идеях, заложенных в Random Forest (бинарное дерево решений, бутстреп аггрегирование или бэггинг, метод случайных подпространств и декорреляция) и понять почему все это вместе работает. Модель относительно своих конкурентов довольно таки молодая: началось все со статьи 1997 года в которой авторы предлагали способ построения одного дерева решений, используя метод случайных подпространств признаков при создании новых узлов дерева; затем был ряд статей, который завершился публикацией каноничной версии алгоритма в 2001 году, в котором строится ансамбль решающих деревьев на основе бутстреп агрегирования, или бэггинга. В конце будет приведен простой, совсем не шустрый, но крайне наглядный способ реализации этой модели на c#, а так же проведен ряд тестов. Кстати на фотке справа вы можете наблюдать настоящий случайный лес который произрастает у нас тут в Калининградской области на Куршской косе.

Предыстория

В свободное от работы время решил поразмыслить, а нельзя ли создать алгоритм соритировки который имел бы сложность O(n) не занимал бы много дополнительной памяти и мог бы быть легко распараллелен. И добился некоторого результата.

Думаю, всем читателям хабра хорошо известны алгоритмы энтропийного сжатия с использованием префиксных кодов (алгоритмы Шеннона-Фано, Хаффмана и др.). Особенностью этих алгоритмов является тот факт, что длина кода определённого символа зависит от частоты этого символа в закодированном сообщении. Соответственно при декодировании сообщения необходимо иметь таблицу частот. Данная статья посвящена рассмотрению малоизученной, но важной задачи – передаче частот исходного алфавита.

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

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



Лекцию читает старший научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доцент кафедры математических основ управления МФТИ, кандидат физико-математических наук Михаил Вялый.

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

На прекрасной Coursera скоро снова начинается курс по Алгоритмам от Тима из Стэнфорда. И я не могу про него не написать. А в свете вот этого поста про дистанционное образование так тем более.

Начну с того, что это самый интересный курс, который мне вообще когда-либо приходилось брать. А я провела во всяких не самых худших университетах немало лет. Курс называется Algorithms: Design and Analysis. Рассказывается в курсе про разные алгоритмы для графов, обсуждаются подходящие структуры данных для каждого алгоритма, присутствует теория и краткие доказательства этих алгоритмов. Во второй части рассказывается в том числе про P=NP проблему и алгоритмы с неполиномиальным временем.

Почему этот курс мне так понравился. Потому что лектор невероятно классный! Он настолько вовлечен, он так все это рассказывает. И потом каждую неделю надо запрограммировать новый алгоритм (на языке по собственному выбору) и найти с помощью своей имплементации ответ на вопрос. Ответ на вопрос засабмитить на сайте, и еще раз, пока не получится правильный ответ. Каждую неделю, как я сказала, новый алгоритм. И соответственно дедлайны. Мотивировало меня это просто сумасшедше: я бежала домой с работы и я не расставалась с алгоритмами по выходным, я ездила в отпуск, сидела на вершине самой высокой точки страны и программировала merge sort.

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

Здравствуйте.

Знаете, иногда я вижу, что группе людей нужно выбрать некий случайный объект. Например, дежурного, если нет графика, или он запутался (по поводу «правильных» графиков дежурств я бы тоже рассказал). Или же, что меня начало в последнее время раздражать, победителя в каком-либо конкурсе репостов.

Проблема следующая. Организаторы конкурса заявляют, что вот вам последовательность действий, совершите её для участия в конкурсе (например, сделайте репост этой записи), а затем мы такого-то числа выберем случайного победителя из репостнувших. Люди совершают все эти действия, приходит долгожданный день и мы получаем…

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

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

Я же считаю, что системы должны быть спроектированы таким образом, чтобы совершить нечто неправильное в них не было возможно, поэтому…

Если помните, Рей Курцвейл обещал приход сингулярности уже в 30 годах этого века. Похоже, что первые предвестники уже появляются: два бывших наших соотечественника, Алексей Лисица и Борис Конев, работающие в Ливерпульском университете, запустили на расчет задачу несоответствия Эрдеша. Задача считается неразрешенной, и программа, запущенная исследователями с задачей справилась. Но! Проблема в том, что доказательства решения сами по себе занимают 13 Гб (еще раз, текстовый лог-файл, по сути и являющийся доказательством, занимает 13 Гб) и с трудом поддается верификации. Отсюда напрашивается простой вопрос – можем ли мы доверять решению компьютера, если не в состоянии проверить его выкладки?

Предисловие

Доброго времени суток! Сегодня решил поделиться с Вами сокровенным — одним из своих любимых велосипедов.

Начну издалека — довольно долго я работал на одном радиозаводе в Челябинске, и был у нас (вообще и сейчас есть, просто я уже не там) один мега-проект: оптико-электронный модуль для охраны физических объектов. Это такая здоровая штука на поворотной установке, с тремя камерами на все случаи жизни (цветная — дневная, ЧБ светочувствительная — для сумерек, и тепловизор — для ночного наблюдения). Берётся такой модуль, ставится на вышку высотой метров 50 — и можно днём и ночью держать под наблюдением территорию в радиусе 4-5 километров. Подробности писать не стану, не о том пост. Кому интересно — сами найдут.

Разумеется, интересных задачек по обработке изображений было много. Об одной из таких я и хочу рассказать. А именно — как использовать массивно-парралельные вычисления для компенсации дрожания камеры в реальном времени, или почему SURF подходит не всегда. Добро пожаловать под кат.

Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

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

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