Алгоритмы *

На написание статьи, подтолкнула публикация Прогнозирование временных рядов.

Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).

Введение

В 1965 г. в журнале «Information and Control» была опубликована работа Л.Заде под названием «Fuzzy sets». Это название переведено на русский язык как нечеткие множества. Побудительным мотивом стала необходимость описания таких явлений и понятий, которые имеют многозначным и неточный характер. Известные до этого математические методы, использовавшие классическую теорию множеств и двузначную логику, не позволяли решать проблемы этого типа.

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

Для начала вкратце о задаче и о самом алгоритме:

Предисловие

— Кибердворник дядя Федя силой ровно в три медведя, — сообщил Поль, извлекая из недр кибердворника блок регулировки. — Я тут уже знаю одного Федю. Приятный такой, веснушчатый. Очень, очень асептический молодой человек. Это не твой родственник?

Аркадий и Борис Стругацкие (Полдень. ХХII век).

Статья посвящена вопросу применимости генетических алгоритмов к проблеме идентификации динамической системы.
Обновлено: опубликовано продолжение ТАУ-Дарвинизм: реализация на Ruby

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



Конечно, для современных видеокарт такая задача является примитивной, однако в те времена на 3.5 мегагерцовом «Cпектруме» о подобных мощностях можно было лишь помечтать. Так что забудьте о графических процессорах, матрицах вращения и нереально ресурсоёмких вычислениях и попробуйте хотя бы примерно прикинуть, каким образом можно реализовать вот такую красивость.

Любопытно? Тогда добро пожаловать под кат!

Вместо предисловия

Урок русского языка в грузинской нерусской школе.
Учительница:
— Дэти, это нэльзя понять, это надо запомнить: ОТ ВАС пишется раздельно, а
КВАС — вместе.

Анекдот взят тут.

Введение

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

Предисловие

На написание статьи вдохновили две публикации:

• Живые графы
• Обзор методов эволюции...

Захотел изложить свои мысли и свой взгляд на этот вопрос именно как практик от программирования «с математическим бэкграундом». Это будет повествование «на пальцах». Специалистом в генной инженерии не являюсь и сужу по поверхностным описаниям механизмов функционирования живых клеток и ДНК.

Как находить тексты похожие по смыслу? Какие есть алгоритмы для поиска текстов одной тематики? – Вопросы регулярно возникающие на различных программистских форумах. Сегодня я расскажу об одном из подходов, которым активно пользуются поисковые гиганты и который звучит чем-то вроде мантры для SEO aka поисковых оптимизаторов. Этот подход называет латентно-семантический анализ (LSA), он же латентно-семантическое индексирование (LSI)

Введение
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок

, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» с сложностью временной сложностью O(N) в худшем случае.

На данный момент происходит лавинообразное увеличение числа мультимедиа-ресурсов, в частности ­ изображений. Как следствие, возрастают требования к средствам систематизации и поиска подобных ресурсов. Большинство существующих на данный момент систем,
осуществляющих поиск информации по описанию (англ. Description-Based Image Retrieval, DBIR), уже не могут в полной мере удовлетворить потребности человека. Поэтому все больше растет интерес к поиску объектов по содержанию (англ. Content-Based Image Retrieval, CBIR).

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

С 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 млн. лет. Именно для таких сложных задач и используются эвристики. Если вам интересно, милости прошу под кат.

Введение

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

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

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



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

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

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

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

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

Введение

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