автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Анализ случайных дискретно-точечных полей с использованием аналитических преобразований на ЭВМ

005534387

На правах рукописи

Соловьев Александр Анатольевич

АНАЛИЗ СЛУЧАЙНЫХ ДИСКРЕТНО-ТОЧЕЧНЫХ ПОЛЕЙ С ИСПОЛЬЗОВАНИЕМ АНАЛИТИЧЕСКИХ ПРЕОБРАЗОВАНИЙ

НА ЭВМ

05.13.18. "Математическое моделирование, численные методы и комплексы программ"

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1 О ОПТ 2013

Новосибирск - 2013

005534387

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте автоматики и электрометрии Сибирского отделения Российской академии наук (ИАиЭ СО РАН)

Научный руководитель: Резник Александр Львович

доктор технических наук, заведующий лабораторией

Официальные оппоненты: Нежевенко Евгений Семенович

доктор технических наук, Федеральное государственное бюджетное учреждение науки Институт автоматики и электрометрии Сибирского отделения Российской академии наук, ведущий научный сотрудник

Курносов Михаил Георгиевич

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

Ведущая организация Федеральное государственное бюджетное

учреждение науки Институт систем информатики им. А.П. Ершова Сибирского отделения Российской академии наук

Защита состоится 1 ноября 2013 г. в 10-00 на заседании диссертационного совета Д 003.005.01 при Федеральном государственном бюджетном учреждении науки Институте автоматики и электрометрии СО РАН по адресу: 630090, Новосибирск, проспект Академика Коптюга, 1.

С диссертацией можно ознакомиться в библиотеке ИАиЭ СО РАН.

Автореферат разослан «27» сентября 2013 г

Ученый секретарь диссертационного совета д.ф.-м.н.

Насыров К. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

В XXI веке компьютеры стали привычной частью жизни. За относительно короткий отрезок времени мощность обычного настольного компьютера выросла многократно - он намного превосходит лучшие ЭВМ тридцатилетней давности по своим характеристикам, а современные суперкомпьютеры могут совершать миллиарды операций в секунду.

Именно это сделало возможным получение тех результатов, о которых пойдет речь в представленной диссертационной работе, которая описывает исследования в области обработки случайных полей и изображений. Изучение этих задач было начато в Институте автоматики и электрометрии СО РАН более 30 лет назад, но основные результаты, представленные в работе, получены в течение последних нескольких лет.

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

Программные системы, использующие аналитическое манипулирование на ЭВМ, были успешно применены для научных исследований многими российскими и советскими учеными, такими как В.М.Глушков, В.А.Брумберг, JI.B. Канторович, И.В. Поттосин, H.H. Яненко, Д.В. Ширков и другими. Разработанные алгоритмы были предназначены для решения проблемных и трудоемких задач математики, теоретической физики, механики и других дисциплин.

Второй отличительной особенностью описываемых в диссертации методов является то, что с их помощью удалось в чистом виде реализовать идею, высказанную в свое время Дж. фон Нейманом: исследователь сталкивается с задачей, которую не в состоянии решить, привлекает ЭВМ для проведения трудоемких расчетов, которые способны натолкнуть его на «правильный» ответ, и в случае удачи (т.е. зная «подсказанное» компьютером решение) проводит строгое и конструктивное доказательство. В диссертации удалось, используя компьютерные расчеты, сначала установить, а затем математически строго доказать ряд точных аналитических формул, описывающих вероятность безошибочного считывания случайных дискретно-точечных

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

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

Цель и задачи работы

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

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

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

3. С помощью построенных программно-аналитических систем и с применением обобщенных чисел Каталана последовательно выполнить трехэтапную доказательную схему: на первом этапе рассчитать максимально широкий набор частных решений задачи многопорогового считывания; на втором этапе на основе системного анализа полученных частных решений сформулировать непротиворечивую гипотезу-предположение об аналитическом виде общего решения; на третьем этапе математически строго доказать выдвинутую гипотезу.

Научная новизна

1. Предложена комплексная методика решения трудоемких математических задач с использованием аналитических преобразований на ЭВМ. Разработанные на ее основе три программно-алгоритмические системы успешно применены для изучения процесса считывания дискретно - точечных полей.

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

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

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

Практическая значимость

К числу практически важных результатов работы относится создание программной системы «АПП-МНИТ», предназначенной для вычисления вероятности безошибочного считывания случайных дискретно-точечных полей и изображений с использованием параллельных вычислений. Данная система основана на методе аналитического вычисления многомерных интегралов (зарегистрирована в Роспатенте под номером 2013612764).

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

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

Еще одним существенным практически значимым результатом является развитый в диссертации подход к использованию предварительных компьютерных расчетов для отыскания частных решений задачи (в частности, создание методов и алгоритмов для проведения аналитических преобразований на ЭВМ, способ их

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

Значительная часть вошедших в диссертацию исследований была проведена в рамках Государственной программы IV.29.1- «Теоретические основы и методы информационных и вычислительных технологий проектирования и принятия решений». Исследования были поддержаны грантами РФФИ (№ 13-01-00361 «Интеллектуальный анализ случайных дискретных полей на основе компьютерных аналитических вычислений», № 10-01-00458 «Цифровые методы оптимального анализа случайных полей дискретной структуры»); программой Президиума РАН № 15/20122014 г.г. (проект «Интеллектуальная программная поддержка в задачах оптимальной цифровой обработки случайных полей и изображений дискретной структуры»); программой совместных фундаментальных исследований СО РАН с НАН Беларуси 2012-2014 г.г. (проект «Методы, алгоритмы и программно-аппаратные системы реконструкции, улучшения качества и повышения разрешающей способности сигналов и изображений видимого и ИК диапазонов»).

Основные положения, выносимые на защиту

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

2. Создание и использование программной системы «АПП-МНИТ» (с применением параллельных вычислений) для нахождения частных решений при фиксированных значениях параметров сканирования.

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

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

Методы исследований

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

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

Апробация работы

Основные научные и практические результаты работы докладывались и обсуждались на следующих международных конференциях и семинарах: «Распознавание образов и анализ изображений: новые информационные технологии - РОЛИ-10-2010», Санкт-Петербург; «Automation, Control, and Information Technology (ACIT 2010), Новосибирск; «Современные проблемы математики, информатики и биоинформатики», посвященная 100-летию со дня рождения А. А Ляпунова, Новосибирск, 2011 г.; «7 VIII German-Russian Workshop "Pattern Recognition and Image Understanding"», Нижний Новгород, 2011 г.; «Neural Networks and Artificial Intelligence (ICNNAI - 2012)», Минск, 2012 г.; «Euro-American Conference for Academic Disciplines», Париж, 2013 г.

Публикации

По материалам диссертации опубликовано 12 научных работ [1-12], из них 6 статей в рецензируемых журналах, входящих в перечень ВАК.

Структура и объем диссертации

Диссертационная работа состоит из введения, трех глав и заключения. Работа изложена на 136 страницах машинописного текста, содержит 8 рисунков, 2 таблицы, список литературы (95 наименований) и приложение.

Личный вклад автора

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 диссертационной работы является обзором литературы по теме работы и посвящена целям и основным направлениям развития систем аналитических преобразований на ЭВМ. В начале главы уделено внимание истории развития таких систем - начиная с самых первых специализированных программ для больших ЭВМ до современных прикладных пакетов общего назначения для персональных компьютеров. Кратко описаны такие проекты, как «Schoonchip» (система расчета задач физики быстрых частиц Мартина Велтмана), «Reduce» (программная среда для аналитических вычислений, разработанная Энтони Херном), «АНАЛИТИК» (система для аналитических вычислений в области математического анализа, созданная под руководством В.М.Глушкова), и ряд других.

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

В заключительной части главы описаны созданные в лаборатории №12 Института автоматики и электрометрии СО РАН уникальные программные системы аналитических преобразований для изучения различных научных проблем (в частности, для нахождения асимптотически оптимальных декоррелирующих преобразований сигналов различной степени гладкости и для построения эффективных алгоритмов локализации импульсно-точечных объектов со случайным временем генерации бесконечно коротких дельта-импульсов).

Глава 2 диссертации содержит постановку задачи, а также описание разработанных для ее решения специализированных алгоритмов аналитического манипулирования на ЭВМ.

¡«— е—

т Е 1

<-1.-»

! Рис.1. Схема телевизионного

|; считывания случайного

| "пуассоновского " поля размером

¡1 ¿X/.

г

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

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

На начальном этапе решения двумерная задача определения вероятности безошибочного считывания сводится к следующей эквивалентной одномерной задаче: "Пусть п точек Х\, Хг,..., х„ случайно брошены на интервал (0,1), т.е. имеется п независимых испытаний случайной величины, равномерно распределенной на интервале (0,£).

Необходимо найти вероятность Р„к того, что внутри интервала (О,/,) не содержится ни одного подынтервала длиной е, содержащего более к точек."

Аналитическое решение этой задачи на данный момент известно лишь для случая, когда к =1:

РпЛ{е91) = {Ь-{п-\)еУИ\ ф<е<Ы(п-\)).

Существующие методы решения поставленной задачи не позволяют вычислить вероятности РПък при произвольных значениях пик,

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

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

Искомая вероятность представляется в следующем виде

Рпк{£) = П\\. . . |й6с, ...<&„,

где область интегрирования Опк{е) с 1С описывается системой линейных неравенств

О < х1 <х2 <...< хп_х < хп < 1,

хЛ + 1 — > Е> " Хк+2 ~ Х2 > £'

х„ — хп_/1 > £.

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

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

решает задачу нахождения вероятности Р„,к(е) Для конкретных значений п и к.

Вышеописанный алгоритм, основанный на методе аналитического вычисления многомерных интегралов, лег в основу разработки программной системы «АПП-МНИТ», использующей параллельные вычисления (версия для кластера ИВЦ НГУ). С помощью этой системы удалось значительно продвинуться в нахождении частных решений и получить формулы Р„^е) до п=14 включительно.

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

Второй программно реализованный алгоритм основан на рекурсивных комбинаторно-аналитических вычислениях. Использовалась следующая комбинаторная модель. Интервал (0,Ь) интерпретировался как совокупность г равных дискретов. Случайное бросание п точек на интервал (0,£) интерпретировалось как случайное бросание п неразличимых шаров по г ящикам. Множество из / смежных ячеек служило аналогом подынтервала длиной е. Исход бросания, когда ни один из таких / - подынтервалов, содержащихся внутри исходного г - интервала (0,£), не имел более 2 точек, считался "успешным", а отношение общего числа "успешных" бросаний (г,п,1) к общему числу исходов опыта<2{г,п) принималось в качестве аналога вероятности Рп,г(е). На этом пути удалось существенно продвинуться в вычислении вероятностей Р„2 (е ), т.е. для случая к=2.

Третьим реализованным алгоритмом аналитического манипулирования является метод дифференцирования многомерных интегралов по параметру. Алгоритм основан на том, что любой полином Р{е) степени п может быть однозначно восстановлен по своему значению

х2 > а,

х2 > а, х2 >/?,

а > р.

=> [х2 > Р,

=>СРи-1

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

Также в главе 2 приведен перспективный метод многомерного интегрирования. Его основная идея состоит в том, что с помощью прямого интегрирования непосредственно в общей аналитической форме последовательно отыскиваются формулы для вероятностей P„„.\(s), Рпд. г(е), Р„.„.з(е) и т.д. В отличие от всех алгоритмов, приводившихся ранее, в этой схеме свободными остаются уже две переменные - не только непрерывный параметр е, но также целочисленный параметр п.

В результате работы всех вышеперечисленных алгоритмов был получен широкий набор частных решений Р„к (s) при различных значениях параметров пик.

В частности, для четных п были установлены следующие соотношения:

Р42(г) = 2(1-е)4, (1/2)<г<1) />6,2(Ю = 5(1-2г)6, (1/3) < г <(1/2) Р82(*) = 14(l-3i)8, (1/4) < г <(1/3) РЮ2(е) = 42(1-4е)'°, (1/5) < г <(1/4)

Рп г (s) = 132 (1 - 5sf, (1/6) < г < (1/5)

Анализ этих «компьютерных» формул позволил усмотреть общую закономерность и высказать гипотезу, заключающуюся в том, что при двух пороговых уровнях (т.е. когда к = 2) для четных п на интервале 1/(п/2<е< 1 /((«/2) — 1) справедлива формула

РпЛ (¿0 = (2 / «)С <"/2Н (1 - ((«/ 2) -1)*)".

Данная формула была «подсказана» компьютером и опубликована еще в 19В1 году, а вот ее строгое доказательство удалось получить сравнительно недавно - в 2011 году [5].

Кроме того, в результате проведенных расчетов было установлено, что для случая телевизионного считывания, проводимого с двумя пороговыми уровнями, при произвольных и на участке 0<£<\/(entire((n + l)/2)) вероятность безошибочного считывания Р„2(е) представляется в виде

Р„2(е) = С°+ С2(-и + 2)ег + С3(4и- 10)г3 + С4„(3п2 -Ъ1п + 86)г4 +

+ С*(-40и2 + 394и —922)г5 +С^(-15л3 +625я2 -5171л-12086)г6 + С 1(420я3 -10724и2 + 79996п-187002)^7 + С'(105л4 -10570и3 + + 205499 л2 -1426841 п + 3336406) е8 + С'(5040я4 -155708 л3 + + 2267664 п1 -17317506 п + 52315558) е9 + С ^°(-945«5 +189000 п* -

-15794625л3 +389687181 п2 -3798029823 л + 12998966646)г;'0 +о(г10).

Данное соотношение также является «компьютерной» гипотезой. Хотя ей не противоречит ни один из полученных компьютерных результатов, тем не менее, соотношение требует своего строгого математического доказательства. Компьютерные расчеты лишь помогают в поиске общей замкнутой аналитической зависимости, описывающей поведение функций Р„А£) в диапазоне изменения параметра е, включающем точку е = 0, но точный характер этой зависимости пока еще остается невыясненным.

Глава 3 посвящена математически строгому доказательству полученных с помощью ЭВМ новых замкнутых аналитических соотношений, описывающих вероятность безошибочного

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

Первая часть главы посвящена доказательству полученной с помощью ЭВМ (см. главу 2) формулы-гипотезы для четных п на интервале 1/(л/2«г<1/((л/2)-1)

Рп1(г) = {21п)С1п12)-\\-({п12)-\)е)\

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

«Имеется интервал (0,1), на который случайно брошены п = 2т точек. Требуется найти вероятность Р события, заключающегося в том, что

внутри интервала (0,1) не существует ни одного подынтервала ^с длины е (~<е<~~[ \ содержащего более 2 точек».

Схема размещения точек, удовлетворяющая формулировке задачи, показана на рис. 3.

Рис.3. Схема размещения четного (п = 2 т) числа случайных точек на интервале (0,1), обеспечивающая возможность их безошибочного «одномерного» считывания интегратором, имеющим апертуру е и два пороговых уровня.

Краткая схема доказательства такова:

1. На первом этапе определяется вероятность Р0 того, что все п=2т точек при их случайном бросании на интервал (0,1) попадут в заштрихованную зону, причем в каждый заштрихованный интервал попадет ровно 2 точки

2. Далее учитывается, что в рассматриваемом случае двухпорогового считывания (£=2) все ближайшие члены с четными номерами и все ближайшие члены с нечетными номерами в ранжированной последовательности <х2 <■■■<*„_[ <хп должны быть удалены друг от друга на расстояние, большее е

Р = р. х = п-(т- \)е)1т х-^-= Ытх{\-(т- 1)гг)2™

0 Ат 2т К К ' ' (2т)\/2т т V ^ ' ' ■

3. Третьим этапом является решение задачи подсчета количества различных «правильных» ЬЫ-слов (Ьей-Ш§Ь1-слов), имеющих длину 2т

д, пМ+1 ы* Гм+\ гм __±_гм+\

ММ+1 = с2М+2 - "М+\ = с2М+2 - с2М+2 = ,, , 0 с2М+2

М + 2

На финальном этапе, делая подстановку и заменяя 2т на п, окончательно получаем требуемую формулу для вероятности Р события, заключающегося в том, что внутри интервала (0,1) не существует ни

1 1

одного подынтервала ¡¡, длиной е содержащего более 2

точек:

Р = мт X (1 -(т - \)е)2т = (1 -(т -\)е)2т =

т +1

= ■~ (1-- («■- = (2 / «)С<"/2Н (1-- ((и/2).-1)*)". т

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

Далее в главе 3 изложено расширение классической последовательности Каталана, которое потребовалось для доказательства формул, описывающих вероятность безошибочного двухпорогового считывания Р„,к(Е) для нечетных значений п =2т+ 1 на участке \/(т+1 )<£ <\/т. Приведены некоторые задачи, приводящие к числам Каталана: задача расстановки скобок, задача разбиения выпуклого многоугольника, количество путей в квадрате, не пересекающих главную диагональ, задача о рукопожатиях и ряд других.

Трехмерное обобщение чисел Каталана и приводящая к ним комбинаторно-«лингвистическая» задача формулируется следующим образом: «Из символов "а", Мь символов "¿>" и Л^ символов "с" составляются различные слова длиной (Л^+Л^+Лу. Нужно определить, сколько среди всех этих слов таких, что при просмотре слова слева направо количество встреченных символов "Ь" никогда не превышает количества встреченных символов "а", а при просмотре слова справа налево количество встреченных символов "с" никогда не превышает количества встреченных символов "а" (естественным образом предполагается, что < /Ч,)».

Показано, что число таких слов

(Мв+М„+Ыс)\

МаШ„Шс\

1-

N„+1 (Ма+Ша+2)^

Числа 1Г(Ма,Мь,Ыс) получили название «обобщенных трехмерных чисел Каталана». Представленная формула действительно обобщает известную по многим приложениям одномерную последовательность Каталана, которая получается из ,ИЬ,ИС) при Л'с= 0 и Л« =Ма.

Далее в главе 3 описано применение обобщенных чисел Каталана для доказательства замкнутого аналитического соотношения, описывающего надежность Рпл(£) двухпорогового (т.е. для к=2) считывания случайных

15

дискретных изображений при нечетных значениях п -2т+ 1 на участке \/(т+\)<Е<\/т.

Решаемая задача формулируется следующим образом: "Пусть п =2т+ 1 точек случайно брошены на интервал (0,1). Требуется указать вероятность Р1т+1,г(е)события, состоящего в том, что внутри интервала (0,1) не существует ни одного подынтервала а, длиной е, содержащего более 2 точек, если 1/(т+1) < е< 1 /от."

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

Перемножая вероятности Р,, соответствующие этим утверждениям, и осуществляя суммирование

т т-р

£ хор, хР2 хР3хР4 хР5 хР6 хРп)

р=о 9=0 '

после всех преобразований получаем формулу для вероятности ^2^+1,2

(е)

на участке 1/ {т + 1) < е < 1 /т\

Рг^,г (Ю = С^ (1 - те)*« (1 - (т - 1)е)т -

+ С™:11(\-теТ+\\-{т-Х)еГ2

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

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

Основные результаты

1. Разработаны специализированные алгоритмы и на их основе созданы программные системы (в том числе система расчета многомерных интегралов в n-мерном пространстве на основе параллельных вычислений «АПП-МНИТ»), ориентированные на проведение аналитических преобразований, требующихся при обработке и анализе случайных дискретно-точечных изображений.

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Резник А.Л., Ефимов В.М., Соловьев А.А. Оценивание надежности считывания случайных дискретных изображений с применением средств компьютерной аналитики // Вестник НГУ. Серия: Физика, 2010, т. 5, вып. 2. С. 104-110.

[2] Alexander L. Reznik, Vitaly М. Efimov, Alexander A. Soloview.

Reliability of random discrete image reading estimated with computation analysis // Proceedings of the IASTED International Conferences on Automation, Control, and Information Technology. Novosibirsk, Russia, 2010, June 15-18, pp. 86-89.

[3] A.L. Reznik, V.M. Efimov, A.V. Torgov, A.A. Soloview. Computer analytical calculations for the random discrete structures analysis // 10th Int. Conf. Pattern Recognition and Image Analysis: New Information Technologies PRIA-10-2010, St.-Petersburg, December 5-12, 2010. Conference Proceedings, vol. 1, pp.251-254.

[4] Reznik A.L., Efimov V.M., Torgov A.V., and Solov'ev A.A. Computer

Analytics in Problems with a Random Partition of the Interval // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications, 2011, vol. 21, № 2. P. 202-205.

[5] АЛ.Резник, В.М.Ефимов, А.А.Соловьев. Компьютерно-аналитический расчет вероятностных характеристик процесса считывания случайных точечных изображений // Автометрия, 2011, т.47, №1, с.10-16.

[6] Резник А.Л., Ефимов В.М., Соловьев А.А., Торгов А.В. Обобщенные числа Каталана в задачах обработки случайных дискретных изображений // Автометрия, 2011, т. 47, № 6. С. 11-16.

[7] Reznik A., Efimov V., Soloview A., Torgov A. On reliability of random discrete images sensing // Proc. of the VIII German-Russian Workshop "Pattern Recognition and Image Understanding" (Nizhni Novgorod, Russia, November 21-26, 2011). P. 244-245.

[8] Соловьев A.A., Резник А.Л., Торгов А.В. Специализированные программные системы для проведения аналитических выкладок как инструмент решения вероятностных задач со случайным разбиением интервала // Международная конференция «Современные проблемы математики, информатики и биоинформатики», посвященная 100-летию со дня рождения А.А. Ляпунова (г. Новосибирск, 2011). С. 63-64.

[9] A. L. Reznik, V. М. Efimov, А. V. Torgov, and A. A. Solov'ev. Analytical Computer Calculations in Problems with Random Division of an Interval // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications, 2012, Vol.22, No.2, pp.354-359.

[10] Резник А.Л., Ефимов B.M., Соловьев А.А., Торгов А.В. О безошибочном считывании случайных дискретно-точечных полей // Автометрия, 2012 т. 48, № 5. С. 93-103.

[11] A.L.Reznik, V.M. Efimov, A.V.Torgov, A.A.Soloview. Random Descrete Images Readout and Generalized Catalan Numbers // Neural Networks and Artificial Intelligence (ICNNAI - 2012): Proceedings of th 7th International Conference (Minsk, Belarus 10-12 October 2012) - Minsk: BSUIR, 2012. p.160-163.

[12] A.L.Reznik, V.M. Efimov, A.V.Torgov, A.A.Soloview. Reliability of Random Discrete Images Reading Estimation Based on Computer Analytical Calculations // Neural Networks and Artificial Intelligence (ICNNAI - 2012): Proceedings of 7th International Conference (Minsk, Belarus 10-12 October 2012) - Minsk: BSUIR, 2012. p.163-167.

Подписано в печать 25.09.2013 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. печ. л. 2 Тираж 100 экз. Заказ № 176.

Отпечатано в типографии «Срочная полиграфия» ИП Малыгин Алексей Михайлович 630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф. 104 Тел. (383) 217-43-46, 8-913-922-19-07

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ АВТОМАТИКИ И ЭЛЕКТРОМЕТРИИ

На правах рукописи 04201 363377 ^^^

СОЛОВЬЕВ АЛЕКСАНДР АНАТОЛЬЕВИЧ

АНАЛИЗ СЛУЧАЙНЫХ ДИСКРЕТНО-ТОЧЕЧНЫХ ПОЛЕЙ С ИСПОЛЬЗОВАНИЕМ АНАЛИТИЧЕСКИХ ПРЕОБРАЗОВАНИЙ НА ЭВМ

Специальность: 05.13.18. Математическое моделирование, численные методы и комплексы программ

Научный руководитель Доктор технических наук Резник А.Л.

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Новосибирск 2013

ОГЛАВЛЕНИЕ

Введение.................................................................................... 4

Глава 1. Цели и основные направления развития систем аналитических преобразований на ЭВМ............................................................. 11

1.1. Введение..............................................................................11

1.2. История аналитических преобразований на ЭВМ........................... 12

1.3. Современное состояние систем аналитических преобразований......... 17

1.4. Выводы................................................................................ 18

Глава 2. Определение надежности считывания случайных дискретных полей с помощью аналитических преобразований на ЭВМ................20

2.1. Происхождение задачи............................................................20

2.2. Оценивание надежности считывания случайных дискретных полей путем аналитического вычисления на ЭВМ многомерных интегралов по выпуклым многогранникам в п-мерном пространстве..........................................25

2.2.1 Увеличение быстродействия алгоритма с помощью параллельных вычислений.............................................................................29

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

2.4. Программное вычисление вероятностных формул методом дифференцирования многомерных интегралов по параметру..................41

2.5. Метод многомерного интегрирования.........................................44

2.6. Результаты...........................................................................47

2.7 Выводы...............................................................................50

Глава 3. Доказательство «компьютерных формул» с использованием

классических и обобщенных чисел Каталана..................................51

3.1. Введение...............................................................................51

3.2. Надежность считывания случайных изображений двухпороговыми интеграторами. Доказательство замкнутых аналитических формул на основе предварительных программных расчетов...........................................52

3.2.1 Расчет частных вероятностных формул с помощью программ машинной аналитики................................................................52

3.2.2 Доказательство общей формулы («компьютерной» гипотезы)......55

3.2.3. Анализ результатов...........................................................62

3.3. Числа Каталана и их трехмерное обобщение.................................63

3.3.1. Появление чисел Каталана в комбинаторике...........................64

3.3.2. Доказательство формулы чисел Каталана...............................68

3.3.3 Числа Каталана - трехмерное обобщение................................69

3.3.4. Выводы..........................................................................75

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

3.4.1. Постановка задачи............................................................76

3.4.2. Утверждения..................................................................77

3.4.3. Пояснения......................................................................83

3.5. Результаты...........................................................................91

3.6. Выводы................................................................................92

Заключение...............................................................................93

Список литературы..............................................................95

Благодарности...........................................................................107

Приложение.............................................................................. 108

Свидетельство о государственной регистрации программы для ЭВМ «АПП-

МНИТ»....................................................................................108

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

Введение

Актуальность темы. В XXI веке компьютеры стали привычной частью жизни. За относительно короткий отрезок времени мощность обычного настольного компьютера выросла многократно - он намного превосходит лучшие ЭВМ тридцатилетней давности по своим характеристикам, а современные суперкомпьютеры могут совершать миллиарды операций в секунду.

Именно это сделало возможным получение тех результатов, о которых пойдет речь в представленной диссертационной работе, которая описывает результаты исследований в области обработки случайных полей и изображений. Изучение этих задач было начато в Институте автоматики и электрометрии СО РАН более 30 лет назад, но основные результаты, представленные в работе, получены в течение последних нескольких лет.

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

Программные системы, использующие аналитическое манипулирование на ЭВМ, были успешно применены для научных исследований многими российскими и советскими учеными, такими как В.М.Глушков, В.А.Брумберг, JI.B. Канторович, И.В. Поттосин, H.H. Яненко,

Д.В. Ширков и другие. Разработанные алгоритмы были предназначены для решения проблемных и трудоемких задач математики, теоретической физики, механики и других.

Второй отличительной особенностью описываемых в диссертации методов является то, что с их помощью удалось в чистом виде реализовать идею, высказанную в свое время Дж. фон Нейманом: исследователь сталкивается с задачей, которую не в состоянии решить, привлекает ЭВМ для проведения трудоемких расчетов, которые способны натолкнуть его на «правильный» ответ, и в случае удачи (т.е. зная «подсказанное» компьютером решение) проводит строгое и конструктивное доказательство. В диссертации удалось, используя компьютерные расчеты, сначала установить, а затем математически строго доказать ряд точных аналитических формул, описывающих вероятность безошибочного считывания случайных дискретно-точечных изображений, что сделать без серьезной программной поддержки было бы невозможно либо весьма затруднительно. Дополнительная сложность в данном случае заключалась в том, что компьютерные вычисления были связаны не с численными расчетами, а со специально разработанными программными системами для проведения аналитических выкладок.

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

Цель и задачи работы

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

Для достижения поставленной цели потребовалось решить следующие задачи:

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

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

3. С помощью построенных программно-аналитических систем и с применением обобщенных чисел Каталана последовательно выполнить трехэтапную доказательную схему: на первом этапе рассчитать максимально широкий набор частных решений задачи многопорогового считывания; на втором этапе на основе системного анализа полученных частных решений сформулировать непротиворечивую гипотезу-предположение об аналитическом виде общего решения; на третьем этапе математически строго доказать выдвинутую гипотезу.

Научная новизна работы

1. Предложена комплексная методика решения трудоемких математических задач с использованием аналитических преобразований на ЭВМ.

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

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

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

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

Практическая ценность работы

К числу практически важных результатов работы относится создание программной системы «АПП-МНИТ», предназначенной для вычисления вероятности безошибочного считывания случайных дискретно-точечных полей и изображений с использованием параллельных вычислений. Данная система основана на методе аналитического вычисления многомерных интегралов (зарегистрирована в Роспатенте под номером 2013612764).

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

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

другие).

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

Значительная часть вошедших в диссертацию исследований была проведена в рамках Государственной программы IV.29.1. «Теоретические основы и методы информационных и вычислительных технологий проектирования и принятия решений». Исследования были поддержаны грантами РФФИ (№ 13-01-00361 «Интеллектуальный анализ случайных дискретных полей на основе компьютерных аналитических вычислений», № 10-01-00458 «Цифровые методы оптимального анализа случайных полей дискретной структуры»); программой Президиума РАН № 15/2012-2014 г.г. (проект «Интеллектуальная программная поддержка в задачах оптимальной цифровой обработки случайных полей и изображений дискретной структуры»); программой совместных фундаментальных исследований с HAH Беларуси 2012-2014 г.г. (Проект «Методы, алгоритмы и программно-аппаратные системы реконструкции, улучшения качества и повышения разрешающей способности сигналов и изображений видимого и PIK диапазонов»).

Положения, выносимые на защиту

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

2. Создание и использование программной системы «АПП-МНИТ» (с применением параллельных вычислений) для нахождения частных решений при фиксированных значениях параметров сканирования.

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

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

Методы исследований

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

Апробация работы

Основные научные и практические результаты работы докладывались и обсуждались на следующих международных конференциях и семинарах: «Распознавание образов и анализ изображений: новые информационные технологии - РОАИ-10-2010», Санкт-Петербург; «Automation, Control, and Information Technology (ACIT 2010), Новосибирск; «Современные проблемы математики, информатики и биоинформатики», посвященная 100-летию со дня рождения А.А.Ляпунова, Новосибирск, 2011 г.; «7 VIII German-Russian Workshop "Pattern Recognition and Image Understanding"», Нижний Новгород,

2011 г.; «Neural Networks and Artificial Intelligence (ICNNAI - 2012) », Минск,

2012 г.; «Euro-American Conference for Academic Disciplines», Париж, 2013 г.

Публикации

По материалам диссертации опубликовано 12 научных работ [1-12], из них 6 статей [1, 4, 5, 6, 9, 10] в рецензируемых журналах, входящих в перечень ВАК.

Структура и объем диссертации

Диссертационная работа состоит из введения, трех глав, заключения и приложения. Работа изложена на 136 страницах машинописного текста, включающего 8 рисунков и 2 таблицы, списка литературы, включающего 95 наименований, и приложения.

Личный вклад автора

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

Глава 1

Цели и основные направления развития систем аналитических преобразований на ЭВМ

1.1. Введение

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

Основателями всей компьютерной индустрии и первых идей аналитических преобразований на ЭВМ можно считать нескольких известных исследователей 20-го века.

Имя Клода Шеннона известно практически всем - создатель теории информации, внесший огромный вклад в кибернетику, теорию автоматов и систем управления [13-14]. Именно он предложил использовать слово «бит» для обозначения единицы информации.

Математик Алан Тьюринг разработал теорию программ и алгоритмов. Он создал знаменитый «Тест Тьюринга» — тест, проверяющий, является ли компьютер разумным в человеческом смысле слова [15].

Математик Джон фон Нейман - автор архитектуры вычислительных

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

Также нельзя не упомянуть об американском математике Норберте Винере, которого считают основателем кибернетики и искусственного интеллекта [16].

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

Далее будут описаны основные этапы развития систем аналитических преобразований на ЭВМ.

1.2. История аналитических преобразований на ЭВМ

Несмотря на то, что счетные устройства существовали задолго до первых ЭВМ (например, Герман Холл