Алгоритмы *

С 4 марта по 9 апреля 2011 года в Москве Андрей Гольдберг (Microsoft Research) прочтет курс лекций «Кратчайшие пути и максимальные потоки» ([1], [2]). Курс затронет как теоретические, так и практические аспекты (например, как быстро искать кратчайшие пути в дорожных сетях).

От слушателей требуется:

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

Если вы хотите послушать курс, то вам необходимо до 31 декабря 2010 года отправить заявку на ящик ys.applications+pfa@gmail.com, в которой должны быть:

• имя и контактная информация (телефон, e-mail),
• место учебы, факультет, кафедра и курс,
• курсы по алгоритмам, которые вы прослушали, с оценками,
• информация, которая поможет отобрать именно вас в случае, если заявок будет слишком много (рекомендательные письма, дипломы олимпиад, публикации).

Занятия будут проходить на базе Школы Анализа Данных Яндекса по пятницам: с 18:00 до 20:00 лекции, а с 20:00 до 21:00 — семинары.

Подробности смотрите в Call for Participation.

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

Попробовал сделать перевод вчерашнего топика-ссылки на хабре. Заранее извиняюсь, если формулировки покажутся вам кривыми, я с удовольствием приму конструктивную критику. Поехали…

Мне кажется правильным начать этот блог с темы, которая вдохновила меня в первую очередь. Не так давно я наткнулся на статью Jamey Pittman «Pac-Man Dossier», в которой приводилось очень детальное описание механики игры Pac-Man. Она показалась мне очень интересной, поэтому этот сайт — попытка собрать такую же детальную информацию об остальных играх. Но в дань уважения я все же начну с Pac-Man, а в частности, с описания алгоритма поведения привидений. Это очень интересная тема и, надеюсь, мое объяснение будет немного более понятным и доступным, чем у Джейми, потому что я сосредоточусь лишь на поведении.

Об игре:

«В то время все доступные игры были очень жестокими — игры о войне и космических захватчиках. Не было ни одной игры для всех сразу, а особенно, которые понравились бы девушкам. Я хотел придумать «комическую» игру, которой могли бы наслаждаться даже девушки»
— Toru Iwatani, создатель Pac-Man

Добрый день, уважаемые хабрапользователи.
Да-да, заголовок вас не обманул: сегодня мы вспомним про старую добрую консольную игру Road Rash 3.


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

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

Предположим, что у нас есть 100 млн. долларов, которые нужно вложить в несколько возможных инвестиций. Каждое из этих вложений имеет различную стоимость и различный ожидаемый доход. Мы должны решить, как потратить деньги, чтобы получить максимальную прибыль.
Задачи такого типа называются задачами формирования портфеля. У нас есть несколько позиций (инвестиций), которые должны поместиться в портфель фиксированного размера (100 млн. долларов). Каждая позиция имеет свою прибыльность. Необходимо найти набор позиций, которые помещаются в портфель и дают максимальную прибыль.
Многие из вас скажут, что никакие эвристики тут не нужны, и что вполне можно обойтись полным перебором. Другие заявят, что и полный перебор не нужен, ведь существует метод ветвей и границ. Но как быть, если количество возможных инвестиций 65? Полное дерево решений содержит более 7*10^19 узлов. Предположим, что метод ветвей и границ перебирает десятую часть процента этих узлов, а компьютер проверяет миллион узлов в секунду. В этих условиях для решения задачи потребовалось бы более 2 млн. лет. Именно для таких сложных задач и используются эвристики. Если вам интересно, милости прошу под кат.

UPD. 2025. The demo of Graph Unfolding Cellular Automata (GUCA) has been re-implemented in TypeScript: https://github.com/roma-goodok/guca

Введение

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

Да и простого любопытствующего обывателя, не отягощённого подробностями органической химии, подобные вопросы не обходят стороной.

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



Такой предельно упрощённой и наглядной моделью могут оказаться «Живые графы» — конечные автоматы на графе, каждый узел которого содержит некое исполняющее устройство (автомат) с конечным числом состояний и с набором примитивных правил, управляющих созданием или изменением новых связей между узлами.

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

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

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Введение

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

Есть хорошая статья Питера Норвига, в которой он рассказывает как написать спеллчекер в 20 строк кода. В этой статье он показывает как поисковые системы могут исправлять ошибки в запросах. И делает это довольно элегантно. Однако, у его подхода есть два серьезных недостатка. Во-первых, исправление более трех ошибок требует больших ресурсов. А гугл, кстати, неплохо справляется и с четырьмя ошибками. Во-вторых, нет возможности проверки связного текста.



Итак, хочется исправить эти проблемы. А именно, написать корректор коротких фраз или запросов, который:

• умел бы выявлять три (и более) ошибки в запросе;
• умел бы проверять «разорванные» или «слипшиеся» фразы, например expertsexchange — experts_exchange, ma na ger — manager
• не требовал много кода для реализации
• мог бы достраиваться до исправления ошибок на других языках и других типов" ошибок

Остальное — под катом.

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

В статье я покажу как использовать метод динамического программирования по профилю для решения задачи о подсчёте количества гамильтоновых циклов на прямоугольной решётке размером m на n. На Хабре есть несколько статей, посвященных теме динамического программирования (например, эта), но нигде не идёт речь о более сложном применении метода. Данный подход также можно называть методом матрицы переноса, кому как нравится.

Предупреждаю, что статья содержит около 2000 слов (8 страниц А4), но дорогу осилит идущий.

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



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

Зачем использовать компрессию, почему бы не хранить все данные?

Хочется представить хабрасообществу интересный проект, который, пока что не освещался на хабре.

UnLogo

По словам разрабочиков: UnLogo это веб-сервис, который избавляет ваше видео от логотипов и прочей корпоративной атрибутики.

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

Видео под катом.

Предисловие

Совсем недавно в этом блоге была опубликована статья, посвященная алгоритму поведения роя пчел. Данная статья рассказывает о другом алгоритме роевого интеллекта, называемом муравьиным алгоритмом. Она состоит из введения, вкратце рассказывающего о заимствованном природном механизме, описания оригинального алгоритма Марко Дориго, обзора других муравьиных алгоритмов и заключения, в котором указываются области применения муравьиных алгоритмов и перспективные направления в их исследованиях.

Введение

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

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

Решая упражнения к книге «Программируем коллективный разум», я решил поделиться реализацией одного из алгоритмов упомянутого в этой книге (Глава 2 — Упражнение 1).

Исходные условия следующие: пусть мы имеем словарь с оценками критиков:

critics={'Lisa Rose': {'Superman Returns': 3.5, 'You, Me and Dupree': 2.5, 'The Night Listener': 3.0}, 
           'Gene Seymour': {'Superman Returns': 5.0, 'The Night Listener': 3.5, 'You, Me and Dupree': 3.5}}

Чем выше оценка, тем больше нравится фильм.
Надо вычислить: насколько схожи интересы критиков для того, например, чтобы можно было на основе оценок одного рекомендовать фильмы другому?

Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.

Условие

Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.

Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя.
Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).
Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

На рисунке я продемонстрирую работу такой гипотетической структуры.

Есть один замечательный сайт, посвящённый алгоритмам — наверняка многие из Вас о нём слышали и выкачивали его содержимое Teleport’ом или чем-нибудь подобным. Но совсем недавно Максим (автор сайта) создал очень удобную pdf-книжку из всех статей, что присутствовали на сайте. Я знаю, что ему будет приятно узнать, что его труды пригодились IT-сообществу, поэтому я и решил написать тут о электронной книге с алгоритмами.

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

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

Замечательный сайт www.sorting-algorithms.com позволяет увидеть, как сортируются данные разными алгоритмами. Вы сможете посмотреть анимацию в зависимости от алгоритма, исходных данных.



Все это бегает и сортируется прямо на ваших глазах!

Работает на Google App Engine, видимо, поэтому и лежит от посетителей с «Хабра».