Алгоритмы *

В интернете, в том числе и на хабре, можно найти много информации про фильтр Калмана. Но тяжело найти легкоперевариваемый вывод самих формул. Без вывода вся эта наука воспринимается как некое шаманство, формулы выглядят как безликий набор символов, а главное, многие простые утверждения, лежащие на поверхности теории, оказываются за пределами понимания. Целью этой статьи будет рассказать об этом фильтре на как можно более доступном языке.
Фильтр Калмана — это мощнейший инструмент фильтрации данных. Основной его принцип состоит в том, что при фильтрации используется информация о физике самого явления. Скажем, если вы фильтруете данные со спидометра машины, то инерционность машины дает вам право воспринимать слишком быстрые скачки скорости как ошибку измерения. Фильтр Калмана интересен тем, что в каком-то смысле, это самый лучший фильтр. Подробнее обсудим ниже, что конкретно означают слова «самый лучший». В конце статьи я покажу, что во многих случаях формулы можно до такой степени упростить, что от них почти ничего и не останется.

Добрый день всем хабровчанам.

Искал на днях ТЗ для углубления знаний по программированию и наткнулся на одном сайте на задачу о взвешиваниях монет для выявления фальшивой.

У этой задачи есть несколько разновидностей:
1) определить число взвешиваний для выявления фальшивой монеты (она легче или тяжелее)
2) определить алгоритм взвешивания
3) определение тяжелее или легче фальшивая монета
ну и компоновки разновидностей.

Небольшое предисловие

Меня всегда интересовала история появлений научных понятий. Перед изучающим новый предмет сначала встает череда безликих определений. Некоторые из них таковыми и остаются, другие привлекают внимание и со временем вырастают в полноценные объекты «картины мира». В качестве недоступного идеала такого стремления можно привести высказывание Литлвуда о Рамануджане:

каждое натуральное число было его лучшим другом

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

Далее будет приведено небольшое исследование подобного рода, объектом которого является понятие регулярного выражения.

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

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

Часто на собеседованиях приходится спрашивать про функцию hashCode().
Я не буду здесь перечислять все свойства этой функции и ее связь с другой, не менее важной функцией equals(). Данная информация есть во всех учебниках по Java и я не вижу смысла ее здесь повторять. Мне бы хотелось остановиться лишь на одном свойстве: hashCode должен быть равномерно распределен на области значений функции. Я задумался: “А чем гарантировано равномерное распределение?”

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

С течением времени изменяются наши представления о способах взаимодействия с компьютером. На смену «классических» клавиатуры и мыши, в нашу жизнь прочно вошли тачпады и сенсорные экраны. Но это не последняя ступень эволюции для средств ввода информации. С появлением устройств дополненной реальности, например таких, как Google Glass, возникает необходимость в интерфейсах способных гармонично вписываться в данную концепцию. Предпосылки к возникновению таких интерфейсов имеются, так, например, появились такие устройства как Intel Creative Camera, Microsoft Kinect или Leap Motion. Основными управляющими элементами в данных устройствах являются руки пользователя. Поэтому, одной из фундаментальных алгоритмических задач, для взаимодействия с подобными устройствами, является детектирование рук и пальцев пользователя и реконструкция их пространственного расположения.
В данной статье речь пойдет о одном из способов решения задачи детектирования ладоней и пальцев.

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

В конце цикла (надеюсь, меня хватит на несколько статей) я постараюсь создать AI для защитников замка и нападающих на него, при чем он не будет знать заранее ничего о замке, не будет иметь ни каких вэйпоинтов, а нападающие будут появляться случайно.

Начнём немного не по порядку – с pathfollow, т.е. с передвижения по уже найденному пути и вообще с движения монстров/NPC. О том, как найти этот путь, мы поговорим позже… и так, поехали.

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

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

Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).

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

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

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

На хабре уже много-много-много раз писали про игру «Жизнь». Совсем недавно была удивительная статья Жизнь на плоскости Лобачевского. Но игра «Жизнь» является частным случаем т. н. клеточных автоматов. Существует много других клеточных автоматов совсем не похожих на игру «Жизнь», но тем не менее очень интересных. Про некоторые из них и хочется рассказать здесь.

Начнём с того, что рассмотрим ряд клеток, в которых, кроме одной, находятся нули:

... 0  1  0  0  0  0  0  0 ...

Рассмотри следующее правило, заменяем число в клетке на сумму этого числа и соседа слева. Получим следующую серию состояний:

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  2  1  0  0  0  0 ...
... 0  1  3  3  1  0  0  0 ...
... 0  1  4  6  4  1  0  0 ...
... 0  1  5 10 10  5  1  0 ...
... 0  1  6 15 20 15  6  1 ...

Не сложно увидеть, что это — треугольник Паскаля. А теперь вместо обычного сложения будем использовать сложение по модулю два. Известно (и даже недавно рассказывалось в хабрастатье Треугольник Серпинского и треугольник Паскаля), что получится дискретный аналог треугольника Серпинского:

... 0  1  0  0  0  0  0  0 ...
... 0  1  1  0  0  0  0  0 ...
... 0  1  0  1  0  0  0  0 ...
... 0  1  1  1  1  0  0  0 ...
... 0  1  0  0  0  1  0  0 ...
... 0  1  1  0  0  1  1  0 ...
... 0  1  0  1  0  1  0  1 ...

Интересно? Читаем дальше!

Коллеги, нужен ваш совет. Мы сейчас занимаемся переводом отличного учебника Dasgupta, Papadimitriou, Vazirani. Algorithms. McGraw-Hill. 2006 на русский язык. Так вот, хочется услышать ваше мнение на тему того, как в русских учебниках по алгоритмам должен быть оформлен псевдокод: выделять ключевые слова? переводить ключевые слова на русский? помечать конец блока ключевым словом? (Опрос — снизу). Несколько потенциальных способов оформления приведены ниже. Буду благодарен за любые советы/замечания.

Меня зовут Василий, уже более трех месяцев, как я работаю математиком в компании Surfingbird.

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

Постановка задачи рекомендательной системы уже описана Сергеем Николенко в статье Рекомендательные системы: постановка задачи.
В основе большинства рекомендательных систем лежат так называемые методы коллаборативной фильтрации. Наша рекомендательная система не исключение. Все алгоритмы коллаборативной фильтрации опираются только на информацию о рейтингах, проставляемых пользователями, и не анализируют контент ресурсов (в нашем случае веб-страниц). Поэтому, эти алгоритмы работают при достаточно большом количестве рейтингов, как правило это 10-20 рейтингов. Задача выдачи релевантных рекомендаций для новых пользователей и для новых сайтов называется проблемой холодного старта.

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

Это первый пост из блога Surfingbird, который я выношу в общие хабы алгоритмов и искусственного интеллекта; честно говоря, раньше просто не догадался. Если интересно, заходите к нам, чтобы прочесть предыдущие тексты, – я не знаю, что произойдёт, если просто добавить новые хабы к постам несколькомесячной давности.

Краткое содержание предыдущих серий о рекомендательных системах:

• рекомендательные системы: постановка задачи;
• user-based и item-based коллаборативная фильтрация;
• SVD, часть I;
• SVD и базовые предикторы;
• SVD на Perl;
• оверфиттинг и регуляризация;
• теорема Байеса и наивный Байес;
• LDA (Latent Dirichlet allocation, тематическое моделирование).

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

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

Идея распознавать людей по радужной оболочке появилась в далёком 1987 у доктора Джона Доугмана и была запатентована в 1989. Примерно тогда же появился прототип. На тот момент это была вершина технологии. Пару лет до первой коммерческой цифровой камеры + алгоритм обработки изображения на компьютерах уровня i386/i486. До сих пор я не представляю, как можно получать на таком оборудовании стабильный результат.
Задачка о которой я хочу рассказать появилась на свет где-то в 2006-2009 годах. Процессоры к этому времени несколько ускорились, появились хорошие камеры, патент 1989 года истёк и системы распознавания по глазам теперь получил право делать каждый. Люди, которые решили сделать клон системы захотели использовать современные технологии и улучшить алгоритм. Самое первое, что бросалось в глаза — старый алгоритм сравнения глаз использовал изображение глаза в близком ИК диапазоне. То, что глаза бывают цветными не учитывалось.

Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.

Давайте рассмотрим среду: в ней могут существовать частицы «еды» и агенты. С помощью сенсоров агенты могут получать информацию о среде. Если агент находится достаточно близко к частице пищи, то она считается «съеденной» и исчезает, а в тот же самый момент в случайном месте среды появляется новая частица еды. Задача группы агентов — собирать пищу. Эффективность рассматривается исходя из суммарного количества собранной пищи.

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

Не так давно я считал. что нет оправдания использованию java.util.LinkedList в качестве реализации java.util.List. Но что-то заставило меня его поискать. Давайте разберемся. Любой грамотный Java-специалист знает, что java.util.ArrayList нужно использовать тогда, когда нам нужен быстрый доступ по индексу, а java.util.LinkedList, если нам нужно вставлять или удалять элементы в середине списка. Не многие из них догадываются, что если мы будем вставлять или удалять элементы в середине списка методами remove(int index) и add(int index, E element), то на поиск нужного элемента будет затрачено время в среднем пропорциональное размеру списка O(N). Так когда же возникает выгода от использования java.util.LinkedList?