Алгоритмы *

Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

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

loop 1000000000
  loop 1000000000
    loop 1000000000
      a += 1
      b += a
    end
  end
end
end

Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.

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

Так мне указали, что для задачи классификации — нейронные сети (обучение с учителем), генетические алгоритмы (обучение без учителя) — задача кластеризации, а еще есть обучение с подкреплением (Q-обучение) — как задача агента, который бродит и что-то делает. И вот такими шаблонами многие и судят.

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

И заодно проанализируем диссертацию Бурцев М.С., «Исследование новых типов самоорганизации и возникновения поведенческих стратегий», в которой не больше не меньше красиво сделано именно применение простеньких нейронных сетей в задаче обучения с подкреплением.

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

На самом деле правильнее было бы назвать «машинное зрение», но так я думаю понятнее будет, если кто не знает то это не охранное видеонаблюдение, а распознавание или измерение чего либо c помощью камер. Существует много задач и областей, где компьютерное зрение было бы очень востребовано и могло бы использоваться повсеместно, но на практике оно используется очень редко.

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

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

В комментариях к статьям N-е число Фибоначчи за O(log N) и Еще один алгоритм вычисления чисел Фибоначчи указывалось на тот факт, что уже 100-е число Фибоначчи не помещается в 4 байта, а в «длинной» арифметике скорость выполнения умножения резко просядет. Более того, были предположения, что примитивное сложение может оказаться быстрее. Я решил сравнить 2 алгоритма — простое сложение и алгоритм с логарифмическим количеством операций — и написал тестовую программу на С. Для «длинной» арифметики использовал библиотеку GMP.

Перед прочтением статьи, решил попробовать придумать свой алгоритм c асимптотикой O(log N). Времени понадобилось не очень много. Ниже описание идеи и пример на С++.

Читая статью об устройстве на работу в ABBYY, встретил в ней упоминание задачи:

быстро – за O( log N ) арифметических операций над числами – найти N-е число Фибоначчи

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

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

PyBrain — одна из лучших Python библиотек для изучения и реализации большого количества разнообразных алгоритмов связанных с нейронными сетями. Являет собой удачный пример совмещения компактного синтаксиса Python с хорошей реализацией большого набора различных алгоритмов из области машинного интеллекта.

Предназначен для:

• Исследователей — предоставляет единообразную среду для реализации различных алгоритмов, избавляя от потребности в использовании десятков различных библиотек. Позволяет сосредоточится на самом алгоритме а не особенностях его реализации.
• Студентов — с использованием PyBrain удобно реализовать домашнее задание, курсовой проект или вычисления в дипломной работе. Гибкость архитектуры позволяет удобно реализовывать разнообразные сложные методы, структуры и топологии.
• Лекторов — обучение методам Machine Learning было одной из основных целей при создании библиотеки. Авторы будут рады, если результаты их труда помогут в подготовке грамотных студентов и специалистов.
• Разработчиков — проект Open Source, поэтому новым разработчикам всегда рады.

Делаю тут проект и возникла вот какая проблема. Получаю данные с АЦП (дельта-сигма) микросхемы в которую встроен контроллер и фильтр, но этот фильтр имеет довольно убогую АЧХ, в итоге идёт завал по ВЧ от 60Гц и далее. Выглядит это примерно так:


Т.е. такая неравномерность АЧХ нас явно не устраивает (не проходит по техническим требованиям), правда есть возможность повысить частоту дискретизации с 250Гц до 500Гц, чтобы выровнять АЧХ, однако тогда увеличивается объём данных который ещё нужно будет усреднять, что скажется на производительности (проект на STM32F103VE) системы в целом и на общем потреблении энергии (батарейное питание). Но есть и другой путь.

Вступление

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

Начнем с взаимного расположения точки относительно прямой, луча и отрезка.

Что будет, если генератор случайных фигур соединить с детектором лиц? Способен ли эволюционный алгоритм путём случайных мутаций сгенерировать человеческое лицо? Разработчик программы Pareidoloop отвечает на этот вопрос утвердительно (генератор протестирован только в Chrome 21).


^{(с) spiritedflow}

Здравствуйте, Хабравчане! Я бы хотел посвятить эту статью интересным и забавным задачам по информатике и математике.

Немного истории

Я являюсь студентом 4 курса математического факультета. Скажу Вам — я очень горжусь, что буду как математиком, так и программистом. Как сказал мне мой декан-программист:«Без математики — это программист с потолком». Так вот, каждый год на протяжении 7 лет мой вуз, а точнее факультет проводит открытую олимпиаду по математике и информатике, за что ему огромное спасибо. Принять в олимпиаде участия могут все: от школьников до студентов (вообще, главное собрать команду хоть из своих соседей).

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

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

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

"Мама мыла раму":

(предложение
    (именная гр. (сущ мама))
    (глаг. гр. (глаг мыла)
        (именная гр. (сущ раму)))
    (. .)))

Это называется синтаксическим деревом предложения. В графическом виде его можно представить следующим образом (в упрощенном виде):

В предыдущей статье я рассказывал, как можно реализовать алгоритм k-means на c# с обобщенной метрикой. В комментах можно почитать обсуждение того, насколько целесообразно использовать разные метрики, о математической природе использования разных метрик и тому прочее. Мне тогда хотелось привести красивый пример, но не было под рукой подходящих данных. И вот сегодня я столкнулся с задачей, которая хорошо иллюстрирует преимущества использования расстояния Махаланобиса в k-means кластеризации. Подробности под катом.

Программа играет в простые игры крестики-нолики, четыре в ряд (Connect 4) и гомоку — и выигрывает у человека. Казалось бы, ничего интересного, если бы не один важный нюанс — эта программа не знает правил! Точнее, она выучила их с нуля, просмотрев двухминутные видеозаписи с участием игр людей.

Лукаш Кайзер (Łukasz Kaiser) из университета Париж Дидро написал программу на C++, которая разбивает видеоряд по кадрам, убирает из них всё лишнее (руки людей) — и получает список последовательных позиций.

На основе этих данных алгоритм (на OCaml) составляет базу разрешённых ходов и список выигрышных/проигрышных/неразрешённых позиций, затем генерирует набор логических формул типа ∃x1Q(x1) ∧ ∃x0(C(x1,x0) ∧ x0 = e1). Оба модуля интегрированы в свободную программу для игры в настольные игры Toss.

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

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

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

Ниже показан результат обработки реального размытого изображения (не с синтетическим размытием). Исходное изображение было получено камерой Canon 500D с объективом EF 85mm/1.8. Фокусировка была выставлена вручную, чтобы получить размытие. Как видно, текст совершенно не читается, лишь угадывается диалоговое окно Windows 7.



И вот результат обработки:



Практически весь текст читается достаточно хорошо, хотя и появились некоторые характерные искажения.

Под катом подробное описание проблем деконволюции, способов их решения, а также множество примеров и сравнений. Осторожно, много картинок!

Хочется рассказать немного о технической части своего проекта, возможно для критики а может кто-то почерпнет что-то для себя.

Здравствуйте, уважаемые хабравчане! Это моя вторая статья, и мне хотелось бы поговорить о вычислительной геометрии.

Немного истории

Я являюсь студентом уже 4 курса математического факультета, и до того как я начал заниматься программированием, я считал себя математиком на 100 процентов.

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

Мне очень нравится подход моего преподавателя: «разберись с этой темой, а потом расскажи нам, да так чтоб мы все поняли».

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

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