В статье я расскажу небольшую историю про маленькую техническую задачку и о том, как её решали разные люди вокруг. Быть может этот рассказ поможет читателю вынести несколько уроков о том, какие временами встречаются ошибки.
Немножко матана инклудэд.
Идея распознавать людей по радужной оболочке появилась в далёком 1987 у доктора Джона Доугмана и была запатентована в 1989. Примерно тогда же появился прототип. На тот момент это была вершина технологии. Пару лет до первой коммерческой цифровой камеры + алгоритм обработки изображения на компьютерах уровня i386/i486. До сих пор я не представляю, как можно получать на таком оборудовании стабильный результат.
Задачка о которой я хочу рассказать появилась на свет где-то в 2006-2009 годах. Процессоры к этому времени несколько ускорились, появились хорошие камеры, патент 1989 года истёк и системы распознавания по глазам теперь получил право делать каждый. Люди, которые решили сделать клон системы захотели использовать современные технологии и улучшить алгоритм. Самое первое, что бросалось в глаза — старый алгоритм сравнения глаз использовал изображение глаза в близком ИК диапазоне. То, что глаза бывают цветными не учитывалось.
Читать полностью »
Рубрика «Алгоритмы» - 280
Немножко философский пост про то, как мы в глаза смотрели
2013-02-07 в 7:38, admin, рубрики: Алгоритмы, биометрия, научный подход, обработка изображений, принятие решений, метки: биометрия, научный подход, принятие решенийЖизнь на плоскости Лобачевского
2013-02-05 в 20:25, admin, рубрики: game development, game of life, Алгоритмы, игра жизнь, математика, метки: game of life, игра жизнь 
Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.
Эволюция агентов управляемых нейронной сетью
2013-02-04 в 19:15, admin, рубрики: machine learning, Алгоритмы, генетические алгоритмы, искусственный интеллект, нейронные сети, Программирование, метки: machine learning, генетические алгоритмы, нейронные сетиДавайте рассмотрим среду: в ней могут существовать частицы «еды» и агенты. С помощью сенсоров агенты могут получать информацию о среде. Если агент находится достаточно близко к частице пищи, то она считается «съеденной» и исчезает, а в тот же самый момент в случайном месте среды появляется новая частица еды. Задача группы агентов — собирать пищу. Эффективность рассматривается исходя из суммарного количества собранной пищи.
Давайте смоделируем конкурентную среду для автоматического поиска оптимального поведения группы агентов. Алгоритм поведения агентов будем конструировать в виде нейронной сети.
Читать полностью »
Искусственный интеллект. Моделируем спасательную операцию
2013-02-01 в 19:29, admin, рубрики: canvas, javascript, Алгоритмы, искусственный интеллект, метки: Canvas, javascript, Алгоритмы, искусственный интеллект Возможно заголовок слишком кричащий, муза по заголовкам меня покинула. И, да, здесь не будет японских роботов и сюжета фильмов где эти же роботы захватывают мир. Но здесь будет искусственный интеллект (ИИ), так как ИИ можно считать присутствующим, если при принятии решения используется оценочная функция. А она будет в нашем алгоритме поиска пути. И, да, это будет моделирования спасательной операции, заключаться будет в том, что команде спасателей нужно обойти всё здания (все комнаты), найти там людей (который по задумке автора сами спастись не могут) и вывести их из здания. Реализовано все будет на JavaScipt, Canvas, и немного PHP для работы с базой. Думал сначала сделать статью в стиле своей последней, то есть обсуждаем именно JavaScript, но не хочу повторятся, так что здесь скорее всего пройдемся по архитектуре самой программы (да, зразу скажу, если может кто очень ждет вторую часть змейки, она в процессе, в комментариях по этому поводу ничего нового не скажу). С бюрократией вроде бы все, приступим.
Читать полностью »
Поиск часто встречающихся элементов в массиве
2013-01-31 в 10:24, admin, рубрики: computer science, data mining, Алгоритмы, высокая производительность, обработка сигналов, метки: computer science, обработка сигналовЗадача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.
Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?
Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?
К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву. Читать полностью »
Сотовый маляр
2013-01-30 в 17:50, admin, рубрики: Алгоритмы, визуализация, гексагональная сетка, информационная безопасность, метки: визуализация, гексагональная сетка Известно, что набором правильных шестиугольников можно описать практически любой контур и создать тем самым фигуру произвольной формы. Такой принцип можно применить при построении топографических карт на подобие тому, как это реализовано в Sid Meier’s Civilization V, или же использовать в системах, основой которых являются те самые шестиугольники (сотовые операторы). Для придания информативности, каждой ячейке карты можно присваивать контрольное значение, будь то уровень сигнала сети, высота, глубина, наличие определенного вида ресурсов и т.п., характеризующее участок карты — соты. Это может выглядеть примерно так. Однако для глаз данное представление является не вполне презентабельным, и его можно визуализировать, добавив каждой ячейке соответствующий цвет.
Читать полностью »
Жеребьевка — нажатием кнопки
2013-01-29 в 16:11, admin, рубрики: алгоритм, Алгоритмы, метки: c++, алгоритм Для решения одной, как я считаю, амбициозной задачи, связанной с проведением футбольного турнира, мне необходимо было использовать процедуру формирования соревновательных пар, т.е. провести жеребьевку. Но произвести ее нужно не обычным «человеческим» способом, а автоматизировано. Поискав готовые решения аналогичной задачи, нашел только формирование корзин участников при наличии сеянных и несеянных команд (Пример), что меня не устроило и не решало поставленной задачи. В итоге проанализировав процедуру обычной однокруговой жеребьевки, сформировал следующий алгоритм и условия:
Входные условия жеребьевки:
- Имеется N команд – участников.
- Каждая команда за первый круг сыграет N-1 матчей.
- Команда N ни в каком из туров не может сыграть сама с собой.
- В каждом туре соперники образуют уникальные, не повторяющиеся ранее пары.
- Если в каком-то из туров команда N играет с командой M, то соответственно в этом же туре команда M играет с командой N.
Сопоставив процесс формирования случайных пар соперников процедуре заполнения двумерного массива DrawTable[i, j] случайными величинами, получил следующее (язык C#, .Net 4.0):
Читать полностью »
Напиши алгоритм для МКС и выиграй 10 тыс. долларов
2013-01-23 в 19:41, admin, рубрики: Topcoder, Алгоритмы, конкурс, Совершенный код, Спортивное программирование, метки: Topcoder, конкурс 
Международная космическая станция
НАСА объявило конкурс на оптимизацию алгоритмов движения солнечных панелей для Международной космической станции. Конкурс ISS Longeron Challenge проводится совместно с порталом TopCoder.
Читать полностью »
Степени — ключ к быстрой иерархии в реляционной БД
2013-01-22 в 19:10, admin, рубрики: django, Алгоритмы, базы данных, деревья, иерархические структуры, иерархия, Программирование, метки: Django, базы данных, деревья, иерархические структуры, иерархия После публикации на Хабре своей первой статьи, об одном из способов организации иерархии в реляционной БД, у меня осталось чувство не доведенного до конца дела.
Судя по комментариям, кто-то принимал предложенный метод за другой, спрашивали чем не устраивает “django-mttp”, рассказывали о поддержке деревьев в PostgreSQL…
Спасибо всем отписавшимся, но из-за сумбурного изложения в самой статье, думаю, что я не сумел донести до читателя то, что хотел. А “если я чего решил, то выпью обязательно”(с)
Поэтому, я решился на еще одну попытку изложения интересующего меня подхода. А именно — хранение иерархии в числовом коде, вычисляемом на основании данных о размерности дерева. То есть, заранее определены максимальные количество Уровней и количество Детей у каждого Родителя (возможные диапазоны достаточно велики, поэтому, заранее пугаться этого не стоит). При таких вводных, код, каждого иерархического элемента, будет являться и путем до него, и включать диапазон всех Детей. А это сулит скорость, и много еще чего…
Далее — с картинками и таблицами, без привязки к какой-либо БД (ибо это не важно). В конце статьи есть ссылки на реализацию на Django. Читать полностью »