Кривцов В.Е., Бачурин А.И. (сост.), Дружинина В.А., Волкова И.А., Котова О.П., Себова Л.В. (ред.) и др. Труды 53-й научной конференции МФТИ: Современные проблемы фундаментальных и прикладных наук. Часть IX. Инновации и высокие технологии

Подождите немного. Документ загружается.

Секция интеллектуальной собственности и экономики в Интернете: модели, инструментальные средства и измерения

для решения не формулируется задача оптимизации со всеми ограни-

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

для перемещения в направлении наибольшего предпочтения в про-

странстве ставок роялти.

Литература

1. Козырев А.Н., Неволин И.В. Моделирование лицензионных пе-

реговоров с достижением оптимальной ставки роялти // Вестник

ГУУ. — 2010. — № 2. — С. 50--53.

2. Половинкин Е.С., Балашов М. В . Элементы выпуклого и силь-

но выпуклого анализа. — М.: Физматлит, 2004. — 416 с.

3. Поляк Б.Т. Введение в оптимизацию. — М.: Наука, 1983. —

384 с.

УДК 304.2

Д.П. Пигорев

DPigorev@gmail.com

Центральный экономико-математический институт РАН

Модель кинотеатральных сборов

Целью данной работы является анализ данных о недельных сбо-

рах 650 наиболее кассовых фильмов за период с 2006--2010 гг. (по дан-

ным, представленным на портале ﬁlm. ru) и построение на их основе

модели кинопроката, позволяющей прогнозировать кинотеатральные

сборы.

В работе анализируется динамика кинотеатральных сборов в

недельном временном срезе, восстанавливаются параметры, опреде-

ляющие качество фильма и уровень информационной асимметрии.

Профиль кинотеатральных сборов можно описать следующим обра-

зом

1. Сборы в первую неделю показа максимальны.

2. Существенное падение сборов от недели к неделе.

Для описания динамики кинотеатрального показа использовано урав-

нение парной экспоненциальной регрессии: s

= e

ak+b

,гдеk — неделя

42 53-я научная конференция МФТИ ФИВТ

кинопоказа фильма, s

— сборы в k-ю неделю кинопоказа фильма.

После некоторых преобразований уравнение регрессии примет следу-

ющий вид: s

= e

pk+1

p+1

,гдеs

= e

. q — параметр определяющий

сборы в первую неделю кинофильма, p — параметр определяющий

динамику кривой.

Параметр q определяет сборы первой недели, поскольку сборы в

первую неделю показа составляют в среднем более половины (57%

по 650 кинофильмам) совокупных сборов кинотеатрального показа.

Данный параметр характеризует эффективность рекламы фильма и

качество кинофильма.

Параметр p характеризует качество кинофильма, а также состав-

ляющую информационной асимметрии, которая эксплуатировалась

в полной мере во время первого периода.

Подобрав схожую по качеству и маркетинговому бюджету кино-

картину, полученную модель можно применить для прогнозирования

объема кинотеатральных сборов.

Литература

1. Долгин А.Б. Экономика символического обмена. — М: Инфра —

М, 2006. — 525 с.

2. Лессиг Л. Свободная культура. — М.: Прагматика Культуры,

2007. — 270 c.

3. Kinsella N.S. Against intellectual property // J. of Libertarian

Studies. — 2001. — V. 15, N. 2. — P. 1--53.

УДК 304.2

Д.П. Пигорев

DPigorev@gmai.com

Центральный экономико-математический институт РАН

Расширение культурного многообразия

посредством создания социальной сети

Целью данной работы является демонстрация возможностей, ко-

торые открывает Интернет перед представителями музыкального

сектора культуры. Предлагается создание социальной сети исполни-

телей, авторов песен, музыкантов, аранжировщиков и т.д.

Создание подобной сети имеет существенный ряд положительных

эффектов:

1. Устраняется потребность в промежуточном звене — медиаком-

паниях.

2. Расширение культурного многообразия.

3. Предоставляется возможность привлечения аудитории к произ-

ведениям малоизвестных исполнителей, которых медиакорпора-

ции не пустили на рынок.

4. Возможность получать вознаграждения напрямую от благодар-

ных слушателей посредством donations и в результате приобре-

тения музыкальных композиций через Интернет.

5. Стимулируется появление новых творческих коллективов.

6. Возможность получать отзывы напрямую от потребителей.

Актуальность создания подобной социальной сети для российской

культуры чрезвычайно высока. Россия является культурным доно-

ром и коммуникация талантливых людей должна привести к созда-

нию устойчивой национальной отрасли.

Литература

1. Долгин А.Б. Экономика символического обмена. — М: Ин-

фра–М, 2006. — 525 с.

2. Лессиг Л. Свободная культура / пер. с англ. — М.: Прагматика

культуры, 2007. — 270 с.

Секция информационных

технологий и распределённых

вычислений

УДК 004.942

А.С. Антонов, А.С. Воронцов, Е.И. Эйсымонт,

Е.Т. Горячева

antonov-69@tut.by, difender@tut.by, gffh@mail.ru, frezaz@yandex.ru

Гродненский государственный университет им. Янки Купалы

Реализация CALS-технологий в решении задач

создания оптимизированных конструкций

машиностроительных изделий на базе

высокопроизводительных кластерных систем

В современном информационном обществе стабильность развития

и гибкость любого машиностроительного предприятия определяют-

ся его инновационной политикой, технической оснащенностью, нали-

чием передовых технологий, систем компьютерного инжиниринга и

средств имитационного моделирования, осуществлением консалтин-

говых услуг и реализацией информационно-логистической поддерж-

ки изделий на постпроизводственных стадиях жизненного цикла про-

дукции. Инновационное развитие и повышение эффективности управ-

ления инновационной деятельностью на современном предприятии,

создание конкурентоспособной продукции в условиях жестких фи-

нансовых и временных ограничений без внедрения CALS-технологий

сегодня невозможны [1]. Эффективное использование CALS-техноло-

гий на машиностроительных предприятиях в условиях необходимо-

сти выполнения сложных расчетов и обработки больших массивов

информации стало возможным благодаря широкому распростране-

нию высокопроизводительных кластерных систем, появлению супер-

компьютеров [2].

Секция информационных технологий и распределённых вычислений

В связи с быстроменяющимися требованиями потребителей к ка-

честву и надежности продукции машиностроительного производства

целью данной научной работы явилась конструкторско-технологи-

ческая и материаловедческая оптимизация конструкций различных

технических объектов с применением CALS-технологий на базе мно-

гопроцессорной вычислительной техники. В качестве объектов ис-

следований были выбраны типовые конструкции карданных валов,

выпускаемых на ОАО Белкард» (г. Гродно), и токарных патронов

производства РУП «БелТАПАЗ». Создание 3D-моделей осуществ-

ляли в системах компьютерного моделирования Pro / ENGINEER,

SolidWorks, Unigraphics. Моделирование напряженно-деформирован-

ного состояния выполняли методом конечных элементов в среде про-

граммного пакета ANSYS LS-DYNA с помощью высокопроизводи-

тельного вычислительного кластера ВМ 5100 семейства суперком-

пьютеров «СКИФ». Проанализировав результаты виртуальных испы-

таний исследуемых объектов, определили направления их дальней-

шей конструкторско-технологической и материаловедческой оптими-

зации [3, 4].

Литература

1. Авдейчик О.В. Экономическая эффективность инновацион-

ных проектов: методологический и прикладной аспекты. — Гомель:

ИММС НАНБ, 2005. — 114 c.

2. Ли К . Основы САПР (CAD / CAM / CAE). — СПб.: Питер,

2004. — 560 c.

3. Антонов А.С., Струк В.А., Кравченко В.И., Кравченко К.В.,

Кипнис М.Е. Моделирование стендовых испытаний технических объ-

ектов с применением CALS-технологий // Сборник трудов XV Меж-

дународной научно-технической конференции «Машиностроение и

техносфера XXI века». — 2008. — Т. 3. — С. 69--73.

4. Горячева Е.Т. Оптимизация конструкции прецизионной техно-

логической оснастки с применением CALS-технологий // Тезисы до-

кладов XVIII Республиканской научной конференции аспирантов, ма-

гистрантов и студентов по физике конденсированного состояния. —

2010. — С. 34--35.

46 53-я научная конференция МФТИ ФИВТ

УДК 519.622.2

С.Ю. Волков

fizteh.volkov@gmail.com

Московский физико-технический институт

(государственный университет)

Исследование систем обыкновенных

дифференциальных уравнений

с полиномиальными правыми частями

В данной работе проводится исследование систем обыкновенных

дифференциальных уравнений с полиномиальными правыми частя-

ми, то есть векторных систем дифференциальных уравнений вида

˙x(t)=P (x),гдеx и P являются n-мерными столбцами, причем эле-

ментами столбца P являются полиномы от n переменных.

Изучение систем дифференциальных уравнений такого вида поз-

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

правые части можно будет свести к полиномам с помощью разложе-

ния их в ряд Тейлора с необходимой точностью.

В случае полиномиальной правой части решение будет выписы-

ваться в виде ряда Тейлора с заданной точностью. Однако коэффи-

циенты ряда Тейлора будут в свою очередь представлять собой зна-

чения полинома, вычисленные в некоторой точке.

Вычисление этих значений является отдельной задачей. Простая

подстановка чисел в полином не является разумным решением в силу

того, что степень полинома может быть очень существенной. Поэтому

предлагается решать данную проблему распределенно, то есть неко-

торым образом разбивая ее на более простые подзадачи. В результате

будет получено более эффективное вычисление значений полиномов

в некоторой точке по сравнению с простой подстановкой чисел в по-

лином.

Литература

1. Афанасьев А.П., Белевцев А.А., Волошинов В.В., Крив-

цов В.Е., Рогов С.В., Сухорослов О.В. Проблемы вычислений в рас-

пределенной среде: организация вычислений в глобальных сетях //

Труды института системного анализа Российской академии наук

(ИСА РАН). — М.: Рохос, 2004. — 176 c.

Секция информационных технологий и распределённых вычислений

2. Афанасьев А.П. Продолжение траекторий в оптимальном

управлении // Труды института системного анализа Российской ака-

демии наук (ИСА РАН). — М.: КомКнига, 2005. — 208 с.

УДК 004.925.82

А.Д. Джумаев

almir.dzhumaev@phystech.edu

Московский физико-технический институт

(государственный университет)

Построение каркасной модели объекта по двум

проекциям

Требуется построить каркасную модель объекта, проекции кото-

рого по двум направлениям совпадают с заданными проекциями. За-

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

несколько решений, тогда строится одно из возможных решений. Рас-

смотрим следующие случаи:

а) построение объекта, который задан двумя ортогональными про-

екциями,

б) построение объекта, который задан двумя перспективными про-

екциями, также заданы центры проекций.

Решим сначала простейшую задачу — построим объект, заданный

двумя отрезками.

Пусть отрезки A

, A

заданы следующими точками:

;0;z

), B

;0;z

), A

(0; y

; z

), B

(0; y

; z

). Тогда искомым

объектом является отрезок AB: A(x

; y

; z

), B(x

; y

; z

).Заметим,

что проекции отрезков A

, A

на ось Oz совпадают.

Алгоритм построения объекта, заданного ортогональными проек-

циями:

1. Получить набор отрезков, задающих проекции.

2. Разбить каждый отрезок на составные части, так как некоторые

из отрезков будут иметь пересекающиеся проекции на ось Oz.

3. Для каждых двух отрезков из проекций получить, если возмож-

но (отрезки имеют одинаковые проекции на ось Oz), отрезок

объекта.

48 53-я научная конференция МФТИ ФИВТ

Алгоритм построения объекта, заданного перспективными проекция-

ми:

1. Обратным перспективным преобразованием [1]:

⎡

⎢

⎣

∗

⎤

⎥

⎦

⎡

⎢

⎣

1000

0100

0010

ab01

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

, где центры проекций A(a;0;0) и

B(0; b;0), получить ортогональные проекции объекта.

1. Получить объект, заданный ортогональными проекциями.

2. Перспективным преобразованием [1]:

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

1000

0100

0010

−a −b 01

⎤

⎥

⎦

⎡

⎢

⎣

∗

⎤

⎥

⎦

получить искомый объект (рис. 1).

Рис. 1. Построение объекта по 2-м отрезкам

Литература

1. Роджерс Д., Адамс Дж. Математические основы машинной

графики. — М.: Мир, 2001. — 604 с.

Секция информационных технологий и распределённых вычислений

УДК 514.113

Н.О. Ермилов

nermilov@mail.ru

Институт системного анализа РАН

Алгоритмический способ проверки реализуемости

полных графов в R

с данным набором длин рёбер

Рассмотрим в R

множество из n точек и набор из

n·(n−1)

положи-

тельных чисел. Будем принимать эти числа за длины рёбер полного

графа, состоящего из n вершин. Без знания распределений этих чисел

по рёбрам полного графа существует большое количество возможных

реализаций полных графов, с данным набором длин рёбер. В работе

[1] автором получены точные верхние оценки максимального числа

тетраэдров с данным набором длин рёбер (n =4).

Таким образом, можно поставить следующий вопрос: сколько су-

ществует различных метрических реализаций полных графов в R

с данным набором длин рёбер? Ответ на поставленный вопрос будет

приведён в виде алгоритма. Предложенный алгоритм будет являться

конструктивной проверкой на реализуемость всех вариантов решения

переборной задачи.

Алгоритм основывается на ключевой идее метода ветвей и границ,

а именно: построения всех ветвей дерева алгоритма за счёт перебора

всех возможных решений задачи и определения неких геометриче-

ских факторов, позволяющих отсекать нереализуемые ветви уже на

ранней стадии работы алгоритма. Решение данной переборной задачи

основывается на знании геометрии изучаемого объекта, которое поз-

воляет не перебирать заново заведомо конгруэнтные конструкции и

определять положение вершин графа по длинам его рёбер.

Численная реализация алгоритма была проведена на графах, со-

стоящих из 5 вершин. В результате при удачном подборе входных

данных удалось найти неконгруэнтные реализации графов с одина-

ковым набором длин рёбер.

Предложенный алгоритм является очень сложным с вычислитель-

ной точки зрения, так как в общем случае надо перебрать (

n·(n−1)

−1)!

распределений заданных длин по рёбрам графа. Поэтому в данный

момент ведётся разработка параллельной реализации предложенного

алгоритма.

50 53-я научная конференция МФТИ ФИВТ

Литература

1. Ермилов Н.О. Восстановление тетраэдров по заданному набору

длин рёбер // Международная конференция «Метрическая геомет-

рия поверхностей и многогранников». — М.: МАКС Пресс, 2010. —

С. 25--26.

2. Сабитов И.Х. Алгоритмический способ проверки изгибаемо-

сти многогранников // Третья международная конференция «Ком-

плексный анализ. Дифференциальные уравнения. Численные мето-

ды и приложения». — Уфа: 1996. — Т. 6. — С. 156--166.

3. Blumenthal L.M. Theory and applications of distance geometry. —

Oxford University Press, 1953.

4. Liberty L., Lavar C., Maculan N. A brance-and-prune algorithm

for the molecular distance geometry problem // International transaction

in operational research. — 2008. — V. 15. — P. 1--17.

УДК 004.932.2

А.В. Корх

artkorkh@gmail.com

Московский физико-технический институт

(государственный университет)

Институт системного анализа РАН

Сегментация текстур на основе алгоритма

нахождения минимального разреза на графе

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

Пусть имеется изображение, на котором можно различть два объ-

екта, причем эти объекты частично заслоняют друг друга, их осве-

щенность неравномерная. Требуется отделить один объект от друго-

во, причем участие человека в этом процессе должно быть минималь-

но.

Как уже рассматривалось в работе [1], можно предложить ал-

горитм, основанный на нахождении минимального разреза графа,

построенного на пикселях изображения, но данный подход требует

слишком много памяти для хранения матрицы смежности графа.

Секция информационных технологий и распределённых вычислений

Следовательно, для уменьшения размера графа можно вместо пик-

селей использовать более крупные структуры, например отдельные

сегменты изображения, и проводить анализ на основе сравнения их

текстурных признаков. В качестве быстрого алгоритма сегментации,

можно предложить изопериметрический алгоритм сегментации изоб-

ражения [2]. Недостатком этого алгоритма можно считать, что он сег-

ментирует изображения в целом с однородной тектурой. Для опреде-

ления текстурных признаков каждого из полученных сегментов про-

изведем две операции:

1. Уберем низкие частоты из изображения. Это можно сделать,

взяв первый уровень пирамиды Лапласа.

2. Применим к обработанному сегменту каждый из девяти филь-

тров Лавса [3]. Фильтры можно получить попарным перемноже-

нием таких векторов, как L5=[1,4,6,4,1] — вычисление симмет-

ричного взвешенного среднего значения, E5=[−1, − 2,0,2,1] —

обнаружение краев, S5=[−1,0,2,0, − 1] — обнаружение пятен,

R5=[1, − 4,6, − 4,1] — обнаружение образа в виде ряби.

Таким образом, для каждого пикселя обрабатываемого сегмента мож-

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

откликов на каждый фильтр Лавса. Далее емкость ребра в графе, по-

строенного на предварительном разбиении изображения, прямо про-

порциональна числу близких векторов пикселей соседних сегментов.

От пользователя требуется указать только контрольные сегменты,

принадлежацие первому и второму объектам, число пикселей, для

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

круг пикселей, где будут применяться фильтры.

Литература

1. Корх А.В. Сегментация изображений посредством разрезов на

графах // Труды 52-й научной конференции МФТИ «Современные

проблемы фундаментальных и прикладных наук». — 2009. — Т. 9. —

С. 19--21.

2. Grady L., Schwartz E.L. Isoperimetric graph partitioning for image

segmentation // IEEE Transactions on pattern analysis and machine

intelligence. — 2006. — V. 28, N. 3. — P. 469--475.

3. Шапиро Л., Стокман Дж. Компьютерное зрение. — М.: БИ-

НОМ. Лаборатория знаний, 2009. — 752 с.

52 53-я научная конференция МФТИ ФИВТ

УДК 004.75

В.А. Медведев

, В.В. Евсеечев

1,2

, П.П. Лукьянченко

victor.medvedev@phystech.edu, vitaly.evseechev@gmail.com,

lukianchenko.pierre@gmail.ru

Московский физико-технический институт

(государственный университет)

International College of Economics and Finance

Системы высокопроизводительных вычислений

как основа биржевых агентов реального времени

Торговые роботы на фондовом рынке — благо или зло? Одни бро-

керы считают, что это благо — роботы создают дополнительную лик-

видность, защищают от ошибок и повышают эффективность торгов-

ли. Другие считают, что роботы создают дополнительную нагрузку

и мешают тем, кто торгует «руками». Но большинство согласны, что

доля роботов в торговле на биржах и дальше будет расти.

Федеральная служба по финансовым рынкам (ФСФР) полагает,

что в условиях роста биржевой торговли при помощи роботов рос-

сийские биржи уделяют недостаточно внимания совершенствованию

технических систем.

Для изучения влияния роботов на состояние биржы нужно со-

здать высокочастотного агента (робота), способного в реальном вре-

мени анализировать большой объем информации, поступающий с

биржи, самостоятельно совершать сделки и анализировать поведение

других агентов. Решение такого рода задачи требует больших вы-

числительных ресурсов. Но современные программные системы про-

ведения объемных вычислительных экспериментов очень сложны и

плохостандартизованы, что проявляется в их несовместимости, слож-

ности использования и, особенно, в обслуживании. А значит, их надо

изучать (в теоретическом и технологическом аспектах) и развивать.

В работе был произведен анализ производительности нескольких

вычислительных узлов в различных конфигурациях при помощи те-

ста Linpack Benchmark на аппаратной базе кластера Лаборатории

инноватики ФИВТ МФТИ. А главное, создан прототип собственной

системы удаленного запуска вычислительных задач на кластере. Ос-

новным требованием к этой системе является простота использова-

ния без существенных потерь в производительности, так как систе-

Секция информационных технологий и распределённых вычислений

ма должна оставаться высокопроизводительной распределенной вы-

числительной системой. В прототипе используется язык Java — объ-

ектно-ориентированный, высокоуровневый, транслируемый в плат-

формо-независимый байт-код язык с большим количеством стандарт-

ных библиотек, что в сочетании с виртуальной машиной, которая

реализована для всех общеизвестных платформ, дает в плане просто-

ты очень большие преимущества, при этом оставаясь конкурентоспо-

собным решением в плане производительности. Все это дополняется

гибкой системой передачи сообщений и стандартными средствами до-

ступа к базам данных. На данном прототипе производятся тестовые

вычислительные эксперименты по анализу биржевых данных и их

сравнение с другими реализациями вычислительного процесса.

Литература

1. Таненбаум Э., ван Стеен М. Распределённые системы. Прин-

ципы и парадигмы. — СПб.: Питер, 2003. — 880 с.

2. Эндрюс Г.Р. Основы многопоточного, параллельного и распре-

деленного программирования. — М.: ИД «Вильямс», 2003. — 512 с.

3. Топорков В. Модели распределенных вычислений. — М.: Физ-

матлит, 2004. — 320 с.

УДК 004.021

О.А. Наумова

helga_13_07@mail.ru

Московский государственный университет печати

Волновой алгоритм решения задачи упаковки

Точный классический алгоритм Беллмана для задачи одномерной

упаковки может быть реализован двумя принципиально разными ал-

горитмами:

• табличным алгоритмом, опирающимся на вычисление и хране-

ние векторов оптимальной упаковки для всех последовательных

целочисленных значений объема [1];

• рекурсивным алгоритмом, непосредственно реализующим ос-

новное функциональное уравнение Белламна [1].

54 53-я научная конференция МФТИ ФИВТ

Оба алгоритма являются «медленными». Анализ данных подходов

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

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

В основе волнового алгоритма лежит идея как эффективного соче-

тания достоинств обоих классических решений, так и их комплемен-

тарности. Первый груз всегда обрабатывается рекурсивным алгорит-

мом. После расчета упаковки очередным грузом значение некоторого

параметра определяет, каким из алгоритмов лучше обрабатывать по-

следующий тип грузов.

Волновой алгоритм обеспечивает более быстрое решение за счет:

— отсутствия модуля предвычисления порога переключения;

— отсутствия повторных рассчетов целевой функции с одинако-

вым аргументом для вершин дерева рекурсии разных уровней;

— непосредственного копирования результатов работы таблично-

го алгоритма в таблицу хранения рекурсивных обращений, благодаря

идентичности структур.

Но, как известно, за все приходится платить. В случае волнового

алгоритма расплачиваться за временную эффективность приходится

дополнительными затратами оперативной памяти на хранение пол-

ных ссылок рекурсивных вызовов.

Литература

1. Ульянов М.В., Гурин Ф.Е., Исаков А. C., Бударагин В.Е. Срав-

нительный анализ табличного и рекурсивного алгоритмов точного

решения задачи одномерной упаковки // Exponenta Pro Математика

в приложениях. — 2004. — № 2(6). — С. 64–70.

Секция информационных технологий и распределённых вычислений

УДК 004.75 004.434

С.А. Смирнов

sasmir@gmail.com

Московский физико-технический институт

(государственный университет)

Применение алгебраических языков

моделирования в системе распределённого

решения задач глобальной оптимизации

Алгебраические языки моделирования, например, GAMS [1],

AMPL [2], возникли ещё в 1970-е годы. Они позволяют описывать

соотношения оптимизационных задач (целевую функцию, ограниче-

ния и т.д.), разделяя символьную модель задачи и числовые значе-

ния параметров; обеспечивают автоматическое дифференцирование

и подключение различных «солверов». Главным преимуществом ис-

пользования таких языков является унификация интерфейса между

языком и солверами. Исследователь освобождается от «низкоуровне-

вых» проблем кодирования процедур вычисления значений целевой

функции и ограничений вместе с их производными и занимается са-

мой задачей.

В докладе рассматривается язык моделирования AMPL [2]. Этот

язык обладает самым «естественным» (среди существующих алгеб-

раических языков моделирования) и достаточно общим синтаксисом.

Также AMPL — это самый популярный язык описания задач по ста-

тистике сервера NEOS [3]. Большое число коммерческих и «free open-

source» солверов совместимы с AMPL.

Будут рассмотрены возможности применения языка AMPL в про-

граммном комплексе BNB-Grid [4], который предназначен для ре-

шения задач оптимизации на распределённых системах, состоящих

как из настольных систем, так и многопроцессорных кластеров и су-

перкомпьютеров. BNB-Grid запускает и организует взаимодействие

приложений (солверов), решающих оптимизационные подзадачи па-

раллельно на различных вычислительных узлах, на основе библиоте-

ки BNB-Solver [5]. Библиотека BNB-Solver предназначена для поиска

глобального экстремума на многопроцессорных вычислительных ком-

плексах (МВК). Формируется иерархическая распределённая систе-

ма: на верхнем уровне подзадачи распределяются между параллель-

56 53-я научная конференция МФТИ ФИВТ

ными приложениями, а далее они распределяются по процессорам

МВК средствами библиотеки BNB-Solver. Библиотека разработана на

языке С++ с использованием механизма шаблонов (templates), кото-

рые позволяют эффективно реализовать «параметрический» подход.

Для распараллеливания используется MPI.

Обсуждаются следующие возможности применения AMPL в

BNB-Grid:

1. Расширение состава уже имеющихся (и заданных на C++) в

библиотеке BNB-Solver целевых функций, за счет новых — за-

даваемых и интерпретируемых с помощью AMPL (при этом

BNB-Grid использует эффективные методы автоматическо-

го вычисления производных этих функций, доступных через

AMPL / Solver interface Library API, [6]).

2. Использование солверов нелинейной локальной оптимизации,

поддерживающих AMPL, позволит существенно расширить

класс решаемых BNB-Grid задач глобальной оптимизации (от

безусловной глобальной оптимизации к общей глобальной опти-

мизации с ограничениями).

Литература

1. Bisschop J., Meeraus A. On the Development of a General

Algebraic Modeling System in a Strategic Planning Environment //

Mathematical Programming Study. — 1982. — V. 20. — P. 1–29.

2. Fourer R., Gay D.M., Kernighan B.W. AMPL: A Modeling

Language for Mathematical Programming, second edition. Duxbury Press

/ Brooks / Cole Publishing Company, 2002. — 538 p.

3. NEOS Server for Optimization. http://www-neos.mcs.anl.gov/

4. Афанасьев А.П., Волошинов В.В., Посыпкин М.А., Сигал И.Х.,

Хуторнои Д.А. Программный комплекс для решения задач оптими-

зации методом ветвей и границ на распределенных вычислительных

системах // Труды ИСА РАН. — 2006. — Т. 25. — С. 5–17.

5. Посыпкин М.А. Архитектура и программная организация биб-

лиотеки для решения задач дискретной оптимизации методом ветвей

и границ на многопроцессорных вычислительных комплексах // Тру-

ды ИСА РАН. — 2006. — Т. 25. — С. 18--25.

6. Gay D.M. Hooking Your Solver to AMPL // Technical report. —

Bell Laboratories, Murray Hill, NJ: 1997.

Секция когнитивных технологий

УДК 004.93’12

П.В. Безматерных

, С.А. Гладилин

,Д.П.Николаев

2,3

В.В. Постников

1,3

bezmpavel@gmail.com, gladilin@iitp.ru, dimonstr@iitp.ru,

vassili.postnikov@gmail.com

Институт системного анализа РАН

Институт проблем передачи информации им. А.А. Харкевича РАН

Московский физико-технический институт

(государственный университет)

Применение быстрого обобщённого

преобразования Хафа в задаче распознавания

двумерных штрихкодов

В задаче понимания документа (Document Image Analysis) возни-

кает необходимость распознавать двумерные объекты фиксирован-

ной геометрической формы, класс геометрических искажений кото-

рых ограничен сдвигом, небольшим поворотом, и, возможно, масшта-

бированием. К данному классу объектов относятся одномерные и дву-

мерные штрихкоды. В таких условиях для распознавания объектов

хорошо подходят методы, базирующиеся на быстром обобщённом пре-

образовании Хафа (ОПХ).

В рамках работы рассматривалась задача генеративного распозна-

вания двумерных штрихкодов, для которых стандартные алгоритмы

распознавания (расшифровка смысловой информации на основе ме-

таинформации из вспомогательных элементов) не дают удовлетвори-

тельного качества из-за мелкого масштаба, низкого качества печати

и заранее неизвестных параметров сканирующего или фотографиру-

ющего оборудования.

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

рых множество кодируемых значений, то есть вариантов изображе-

ний штрихкода является известным заранее и имеет не очень боль-

шую мощность (порядка миллиона). В таком случае может быть при-

менен генеративный метод, состоящий в сравнении распознаваемого

58 53-я научная конференция МФТИ ФИВТ

объекта с каждым из возможных вариантов штрихкода в поисках

наименьшего отклонения. При этом к плюсам подобного распозна-

вания можно отнести большую устойчивость при обработке изобра-

жений с низким разрешением, а к минусам — сублинейную зависи-

мость скорости работы алгоритма, что ограничивает применимость

при большей мощности множества вариантов штрихкодов.

Итак, задача сводится к поиску наиболее близкого эталонно-

го штрихкода, при этом отклонение вычисляется между входным

штрихкодом в оттенках серого и монохромным идеалом, то есть без

проведения бинаризации и вероятной потери части значимой инфор-

мации. Данную задачу можно переформулировать в виде несдвигово-

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

оптимизации вычислений полученное ОПХ может быть конвертиро-

вано в быстрое ОПХ (БОПХ) [1] и в дальнейшем использоваться при

вычислении отклонений.

В данной работе предложен алгоритм генеративного распознава-

ния двумерных штрихкодов, базирующийся на БОПХ, а также ряд

оптимизаций для данного алгоритма по памяти, что позволило ра-

ботать с большим количеством образцов. Предложенный подход был

программно реализован и протестирован на наборе из 230 000 реаль-

ных двумерных штрихкодов формата Aztec [2] размерами 15 × 15.

Для 1000 штрихкодов количество операций в рассчитанном БОПХ

оказалось в 15 раз меньше, чем в исходном варианте реализации, ба-

зирующемся на ОПХ; для 10 000 штрихкодов — в 17.2 раза, а для

полной задачи (230 000 штрихкодов) — в 21.4 раза, что обеспечило

скорость распознавания 100 штрихкодов в секунду. Также был про-

веден эксперимент по построению БОПХ для набора кодовых слов

символогии PDF417 [3]. В построенном БОПХ число необходимых

операций сократилось более чем в три раза.

Литература

1. Карпенко С.М., Николаев Д.П., Николаев П.П., Постни-

ков В.В. Общий метод построения быстрых обобщенных преобразова-

ний Хафа // Труды международной конференции. — М.: Физматлит,

2005. — Т. 2. — С. 313--318.

2. Information technology — Automatic identiﬁcation and data

capture techniques Aztec Code bar symbology speciﬁcation ISO/ IEC

24778:2008.

Секция когнитивных технологий 59

3. Trummer M., Denzler J. Reading out 2D barcode PDF417 //

Progress in pattern recognition. — 2007. — P. 179--186.

УДК 004.8

А.С. Григорьев

1,2,3

,Ю.И.Костюкевич

1,3

,Е.Н.Николаев

ansgri@gmail.com, yura542@rambler.ru, ennikolaev@rambler.ru

Московский физико-технический институт

(государственный университет)

Институт системного анализа РАН

Институт энергетических проблем химической физики РАН

Обнаружение повторяющихся фрагментов

в непрерывных сигналах с использованием

локальных корреляций

Одной из наиболее интересных задач автоматической интерпре-

тации данных и цифровой обработки сигналов является поиск по-

вторяющихся фрагментов во входном сигнале. На практике данная

задача возникает в биоинформатике, интерпретации результатов фи-

зических измерений (например, масс-спектров и спектров ядерного

магнитного резонанса), а также при анализе и предсказании динами-

ки цен на фондовых рынках.

Это задача сжатия данных. Дискретный аналог этой задачи, воз-

никающий, в частности, при сжатии данных без потерь, очень хорошо

изучен. Алгоритмы анализа непрерывных сигналов разрабатывают-

ся, в частности, для исследования структуры музыки [1, 2]. Возможна

различная постановка данной задачи: длина повторяющегося фраг-

мента может быть фиксирована или свободна, может быть необходим

учет переменного масштаба по оси интенсивности и / или по оси вре-

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

В данной работе прежде всего рассматривается следующая поста-

новка: в непрерывном сигнале s(t) найти фрагменты заданной длины

l, неоднократно встречающиеся в сигнале s(t) с точностью до некоего

случайного шума и подобия по оси интенсивностей. При этом необхо-

димо вывести усредненную форму повторяющихся фрагментов f

(t)

и все вхождения t

этих фрагментов в сигнал s. Данная задача перво-

60 53-я научная конференция МФТИ ФИВТ

начально встала перед авторами в приложении к определению формы

и положения пиков в масс-спектрах высокого разрешения.

В качестве естественной меры схожести двух фрагментов сигна-

ла используется коэффициент корреляции Пирсона [3], поскольку он

нечувствителен к масштабу по шкале интенсивности. Применяется

вариация на тему «метода грубой силы»: сравнить друг с другом все

фрагменты заданной длины и сгруппировать по попарному сходству.

Для обеспечения эффективности обработки и учета зависимости фор-

мы наиболее частых фрагментов от времени анализируется только

диагональная полоса матрицы корреляций с применением пост-обра-

ботки получившегося набора фрагментов. Таким образом, анализи-

руются только локальные корреляции, чего достаточно для многих

задач. Алгоритм достаточно надежно и эффективно справляется с

поиском повторяющихся фрагментов и успешно применен авторами

для решения исходной прикладной задачи (см. рис. 1).

Литература

1. Shiu Y., Jeong H., Kuo C.-C.J. Similar segment detection for music

structure analysis via Viterbi algorithm // Proc. of IEEE International

Conference and Expo on Multimedia. — 2006. — P. 789--792.

2. Paulus J., Klapuri A. Music structure analysis by ﬁnding repeated

parts // Proc. of the 1st ACM workshop on Audio and music computing

multimedia. — 2006. — P. 59--68.

3. Айфичер Э.С., Джервис Б.У. Цифровая обработка сигналов.

Практический подход. — М.: Издательский дом «Вильямс», 2008.

Рис. 1. Пример обнаружения в сигнале повторяющихся фрагмен-

тов. Сверху показан исходный сигнал и обнаруженный в нем повто-

ряющийся фрагмент, снизу — коррелограмма, показывающая места

вхождения данного фрагмента в сигнал