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

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

Оглавление диссертации кандидат наук Соловьев, Александр Анатольевич

ОГЛАВЛЕНИЕ

Введение

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

1.1. Введение

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

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

1.4. Выводы

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

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

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

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

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

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

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

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

2.7 Выводы

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

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

3.1. Введение

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

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

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

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

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

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

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

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

3.3.4. Выводы

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

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

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

3.4.3. Пояснения

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

3.6. Выводы

Заключение

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

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

Приложение

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

МНИТ»

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

Введение диссертации (часть автореферата) на тему «Анализ случайных дискретно-точечных полей с использованием аналитических преобразований на ЭВМ»

Введение

Актуальность темы. В 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. История аналитических преобразований на ЭВМ

Несмотря на то, что счетные устройства существовали задолго до первых ЭВМ (например, Герман Холлерит сконструировал первую электромеханическую счетную машину еще в 1888 г.), они использовались только для численных расчетов.

В Советском Союзе первая электронная цифровая вычислительная машина - «МЭСМ» была разработана в 1950 году под руководством академика С. А. Лебедева.

Именно с этого времени берет свое начало история аналитических вычислений на ЭВМ [17].

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

для разгона космического аппарата с малой тягой [18], проделаны другие работы.

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

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

Серьезным отличием ЭВМ второго поколения от первого являлось то, что в них была возможность программирования на языках высокого уровня: Фортран, Алгол, Кобол. Это позволило значительно упростить и ускорить написание программ для компьютеров.

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

В 1966 году была создана «БЭСМ-6», лучшая отечественная ЭВМ 2-го поколения. На тот момент она была самой быстрой не только в СССР, но и в Европе. На БЭСМ-6 было создано несколько специализированных систем для проведения аналитических преобразований [19-20].

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

вычислений, разработанная в начале 60-х годов XX века, носила название «Schoonchip» и имела специализированное назначение - обсчет нескольких задач физики быстрых частиц [21].

Примерно в это же время в СССР в Институте кибернетики Академии наук УССР под руководством академика В.М.Глушкова была начата разработка системы «АНАЛИТИК» - специализированной программной среды для проведения аналитических вычислений в области математического анализа [22-23]. Позднее была разработана версия Аналитик-74, реализованная на машинах «МИР» [24]. Развитие системы не прекращается и в наши дни: последняя версия носит название «АНАЛИТИК-2010» (совместно разрабатывается Институтом проблем математических машин и систем НАН Украины и Полтавским национальным техническим университетом имени Юрия Кондратюка).

Но наибольшую популярность в научном мире получила система для аналитических вычислений «Reduce», которая была разработана специалистом по теоретической физике из США Энтони Херном [25]. Система была реализована на языке высокого уровня Лисп и приобрела всемирную известность в кругах исследователей, которые создали огромное количество дополнительных модулей и интерфейсов для нее [26-27]. Это позволяло запускать Reduce не только на ЭВМ, но и на микрокомпьютерах. Более того - проводились работы по использованию этой системы для параллельных вычислений [28]. С помощью системы Reduce было решено большое количество различных задач. Она оказалась удобным инструментом для осуществления широкого набора выкладок, требующих при проведении аналитических преобразований на ЭВМ: решения дифференциальных уравнений [29-30], работы с системами линейных уравнений [31], изучения физики элементарных частиц [32] и многих других.

Система Reduce до сих пор поддерживается и развивается наряду с другим современным математическим программным обеспечением.

Интересной главой в истории развития аналитических преобразований на ЭВМ является язык программирования Рефал, который разработал В.Ф.Турчин [33,34]. Автор создал его для решения собственных задач ядерной физики [35], поэтому этот язык не был ориентирован на массовое использование. Потребовались серьезные усилия программистов, чтобы сделать Рефал более удобным для работы с другими задачами.

На основе языка Рефал были созданы специальные системы символьно-аналитических преобразований SANTRA и DISLAN, разработанные И.Б.Щенковым и М.Ю.Шашковым [36-38].

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

Одним из первых примеров такой системы стала программа MATLAB. Автором этой системы является Клив Моулер [39], который в конце 1970-х годов искал способы обучить студентов программированию с использованием программных библиотек, но без необходимости изучения Фортрана. В начале 80-х г.г. была разработана версия системы PC MATLAB для компьютеров класса IBM PC, VAX и Macintosh. В дальнейшем программа была написана и для других типов больших и малых ЭВМ. Сейчас практически все компьютерные платформы могут работать с программой MATLAB, и ее используют более миллиона человек по всему миру.

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

Это привело к упрощению процесса программирования и его бурному развитию. К концу 80-х годов были созданы десятки систем аналитических преобразований. Они позволяли не только решать задачи на конкретных ЭВМ, но и проводить перенос программ на другие компьютерные системы. Выпускались книги с методами и программами для аналитических вычислений [40].

Так как в рамках диссертационной работы нет возможности подробно описать все разработанные системы для аналитических вычислений, укажем лишь некоторые из них: «АЛЬКОР», «СРМ», «КАПСУЛА» (г. Москва), «GRATOS», «СПИН», «АММУСТ» (г. Ленинград), «АРАП», «АУМ» (г. Новосибирск), «МАРС», «БОРА» (г. Томск), «КИДИМ» (г. Харьков), «КЕНТАВР» (г. Минск).

Большой вклад в развитие систем аналитического манипулирования внесли многие советские и российские ученые: H.H. Яненко, В.М.Глушков, В.А.Брумберг, Л.В. Канторович, И.В. Поттосин, Д.В. Ширков и другие [4149].

Всего более чем за 60 лет развития методов аналитического программирования на ЭВМ в СССР и России было создано более 50 систем аналитических преобразований [50]. Для их разработки использовались самые разные языки программирования: Рефал, Алгол, Фортран, Паскаль, PL-2, Ассемблер и другие.

Из систем, которые развивались за рубежом, отметим такие крупные проекты, как «MACSYMA», «muMATH» , «Mapple», «MATHEMATICA» [5153].

Более подробную и хорошо структурированную информацию о системах символьно-аналитических преобразований для ЭВМ можно найти в работах [50-54].

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

Системы для аналитических вычислений обычно делят на специализированные и общего назначения [17]. Практически все системы для первых ЭВМ были специализированными. Каждая программа была написана под какую-либо конкретную задачу и не могла быть использована где-то еще. Системы общего назначения, напротив, ориентированы на решение широкого класса задач. В конце 80-х годов появилось большое количество систем общего назначения, многие из которых входили в состав больших программных пакетов и были ориентированы на массового пользователя.

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

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

Аналитические вычисления также можно проводить на специализированных суперкомпьютерах - «кластерах». Сегодня самые мощные суперкомпьютеры мира могут выполнять более триллиона операций в секунду. Быстрыми темпами развиваются языки и системы параллельного программирования, которые в совокупности с системами аналитического манипулирования могут давать огромный прирост скорости аналитических вычислений [55].

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

1.4. Выводы

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

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

Разработанные алгоритмы проведения на ЭВМ эквивалентных аналитических преобразований были успешно применены при изучении следующих научных проблем [56-66]:

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

построение асимптотически оптимальных декоррелирующих преобразований сигналов различной степени гладкости;

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

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

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

Список литературы диссертационного исследования кандидат наук Соловьев, Александр Анатольевич, 2013 год

Литература

[1] Резник A.JL, Ефимов В.М., Соловьев А.А. Оценивание надежности считывания случайных дискретных изображений с применением средств компьютерной аналитики // Вестник НГУ. Серия: Физика, 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 2126, 2011). P. 244-245.

[8] Соловьев A.A., Резник A.JI., Торгов А.В. Специализированные программные системы для проведения аналитических выкладок как инструмент решения вероятностных задач со случайным разбиением интервала // Международная конференция «Современные проблемы математики, информатики и биоинформатики», посвященная 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 Descrete Images Reading Estimation Based on Computer Analitical Calculations // Neural Networks and Artificial Intelligence (ICNNAI - 2012): Proceedings of th 7th International Conference (Minsk, Belarus 10-12 October 2012) - Minsk: BSUIR, 2012. p.163-167.

[13] Shannon С. E. A Mathematical Theory of Communication // Bell System Technical Journal. — 1948. — T. 27. — C. 379—423, 623—656.

[14] Шеннон К. Работы по теории информации и кибернетике. — М.: Изд-во иностранной литературы, 1963. — 830 с.

[15] Turing, A.M. (1950). Computing machinery and intelligence // Mind, 59, 433460.

[16] H. Винер. Кибернетика, или Управление и связь в животном и машине // М.: Советское радио, 1958

[17] Климов Д.М. Компьютерная алгебра и ее применение в задачах механики // Вести. АН СССР. №9, 1987.

[18] Ефимов Г.Б. Оптимальный разгон в центральном поле до гиперболических скоростей // Космич. исслед., 1970, т.8, №1, с.26-47, РЖ Мех, 1970, 7А28.

[19] Марков Ю.В. Реализация языка аналитических преобразований на ЭВМ БЭСМ-6//Димитровград, препринт НИИАР 17(376), 1979.

[20] Бычков С.П., Хорошилов А.И. и др. Язык СИМУЛА в мониторной системе ДУБНА для БЭСМ-6 // Препринт №118 ИПМ АН СССР

[21] М. Veltman, SCHOONSCHIP // CERN preprint, 1967

[22] Глушков В.М., Гринченко Т.А., Дородницына А.А., Клименко В.П., Летичевский А.А., Погребинский С.Б., Стогний А.А., Фишман Ю.С. АНАЛИТИК (язык для описания вычислительных процессов с применением аналитических преобразований). // Теория автоматов и методы формализованного синтеза вычислительных машин и систем: Труды семинара. - Вып. 1.-Киев, 1968. - С.3-105.

[23] Л. А. Осипов «Язык АНАЛИТИК и его сравнение с языками АЛГОЛ и ФОРТРАН». — Москва «Наука» 1982.

[24] В.М.Глушков, Т.А.Гринченко, А.А.Дородницына и др. АНАЛИТИК-74// Кибернетика, т.5, 1978, с.114-147.

[25] А.С. Hearn, REDUCE: The First Forty Years // Proceedings of the A3L 2005, BoD, Norderstedt, Germany,: pp. 19-24, 2005

[26] T. W. Appelquist and S. J. Brodsky. A TeX-REDUCE-interface. // SIGSAM Bulletin 23 no. 2, pages 26-33, February 1989.

[27] REDUCE 2 for CP/M. // SIGSAM Bulletin 17 no. 1, pages 26-27, February 1983.

[28] J. P. Fitch. Can REDUCE be run in parallel?. In: Proc. of ISSAC '89, pages 155-162. ACM Press, New York, 1989.

[29] A. Billoire, R. Lacaze, A. Morel, and H. Navelet. A REDUCE program for the integration of differential polynomials // Computer Physics Communications 71 no. 3, pages 263-268, September 1992.

[30] M. A. H. MacCallum and S. Т. C. Siklos. An ordinary differential equation solver for REDUCE // Proc. of ISSAC '88, volume 358, pages 196-205. SpringerVerlag, 1988.

[31] M. L. Griss. The algebraic solution of large sparse systems of linear equations using REDUCE 2 // Proc. ACM 74, pages 105-111, 1974.

[32] А. Г. Грозин. Система REDUCE в физике элементарных частиц: Введение, 53 с. ил. 21 см, Новосибирск // ИЯФ 1990

[33] Турчин В.Ф. Алгоритмический язык рекурсивных функций (Рефал). - М., Изд-е ИПМ АН СССР, 1968.

[34] Турчин В.Ф., Сердобольский В.И. Язык Рефал и его использование для преобразования алгебраических выражений // Кибернетика, 1969, №3,

[35] Будник А.П., Гай Е.В., Работнов Н.С., Климов Анд.В., Турчин В.Ф., Щенков И.Б. Базисные волновые функции и матрицы операторов в коллективной модели ядра//Ядерная физика, 1971, т.14, вып.2, с.304-314

[36] Шашков М.Ю., Щенков И.Б. Система DISLAN для построения разностных операторов // Препринт № 23 ИПМ им.М.В.Келдыша АН СССРД985.РЖ Мат. 1985 9Г910.

[37] Щенков И.Б. Система символьно-аналитических преобразований SANTRA-2. Описание формальной части входного языка // Препринт N 1

ИПМ им.М.В.Келдыша, 1989 г.

[38] Шашков М.Ю., Щенков И.Б. Использование символьных преобразований для построения разностных операторов // Препринт N48 ИПМ им. М.В.Келдыша АН СССР, 1983.

[39] Forsythe, George Е., Malcolm, Michael A., Moler, Cleve В., Computer methods for mathematical computations // Prentice-Hall Series in Automatic Computation, Prentice-Hall., Englewood Cliffs, N.J., 1977.

[40] А.А.Самарский. Пакеты прикладных программ: аналитические преобразования // Сб.науч.тр. АН СССР, Вычислительный центр, М. : Наука, 1988. - 155 с

[41] Л.В.Канторович. О проведении численных и аналитических вычислений на машинах с программным управлением // Изд.АН Арм.ССР, серия физ.-мат, 10, №2, 1957.

[42] В.А.Шурыгин, Н.Н.Яненко. О реализации на ЭВМ алгебраическо-дифференциальных алгоритмов // Проблемы кибернетики, вып.6, М., Физматгиз, 1961.

[43] В.П.Гердт, О.В.Тарасов, Д.В.Ширков. Аналитические вычисления на машинах в приложении к физике и математике // Успехи физических наук, 1980, т. 130, №.1,с.113-147.

[44] М.М.Бежанова, В.Л.Катков, И.В.Поттосин. Работы по аналитическим преобразованиям в ВЦ СО АН СССР // Сб. "Вычислительная математика и вычислительная техника", вып.З, ФТИНТ АН УССР, Харьков, 1972.

[45] Н.А.Калинина, И.В.Поттосин, А.Л.Семенов. Универсальная система проведения аналитических вычислений АУМ // Аналитические вычисления на ЭВМ и их применение в теоретической физике. Дубна, 1983, с.7-18.

[46] Долгов Г.А., Трошева М.В., Ефимов Г.Б., Брумберг В.А., Бабаев И.О., Чубаров М.А. и др. Системы аналитических вычислений на ЭВМ. Аналитические пакеты прикладных программ. // Препринт ИПМ им. И.В.Келдыша АН СССР. - М.: 1983. - Информатор N 1. - 86с.

[47] Т.Н. Величко, В.Я. Галин, Ю.С. Макушкин, Вл.Г. Тютерев, Аналитические вычисления на ЭВМ в молекулярной спектроскопии // Н-ск, Наука, 189 с. 1986.

[48] Ганжа В.Г. Применение символьных преобразований на ЭВМ для нахождения дифференциальных приближений разностных схем. Численные методы механики сплошной среды. Новосибирск, Б.и., 1983, т.14, с.39-44.

[49] В. В. Тумасонис, Система эквивалентных преобразований выражений // Ж. вычисл. матем. и матем. физ., 11:5 (1971), 1272-1281

[50] Г.Б. Ефимов, М.В.Грошева. Из истории отечественной компьютерной алгебры // Математические машины и системы. Киев. 2009. № 2. С.61-67.

[51] David D. Shochat, A Symbolic Mathematics System // Creative Computing, Oct. 1982, p. 26

[52] Joel Moses, Macsyma: A personal history // Journal of Symbolic Computation №47, 2010, pp.123-130

[53] Stephen Wolfram. Mathematical A System for Doing Mathematics by Computer, First Edition // Addison-Wesley Pub. Co., 1988

[54] Wen-Lang Tsai and Noboru Kikuchi. Application of Symbolic and Algebraic Manipulation Software in Solving Applied Mechanics Problems //NASA Contractor Report 4544

[55] Белоцерковский O.M., Математическое моделирование на суперкомпьютерах (опыт и тенденции) // ЖВМ и МФ, том 40, № 40, 2000

[56] В.М.Ефимов, A.JI.Резник. Аналитическое вычисление на ЭВМ объемов, ограниченных системой гиперплоскостей в /7-мерном пространстве.//Автометрия, 1976, №1, с.116-119.

[57] В.М.Ефимов, А.Л.Резник. Аналитическое определение с помощью ЭВМ статистических характеристик процесса щелевого сканирования потока Бернулли. //Автометрия, 1977, №4, с.49-51.

[58] В.М.Ефимов, А.А.Нестеров, А.Л.Резник. Алгоритмы оптимального по быстродействию поиска точечных световых объектов.// Автометрия, 1980, №3, с.72-76.

[59] А.Л.Резник. Моделирование на ЭВМ непрерывного считывания изображений дискретной структуры.// Автометрия, 1981, №6, с.3-6.

[60] В.М.Ефимов, Ю.Н.Золотухин, А.Л.Резник. Асимптотически оптимальная декорреляция стационарной последовательности равноотстоящих отсчетов сигнала.//Автометрия, 1991, №5, с.104-107.

[61] А.Л.Резник. Программы для аналитических вычислений в задачах

локализации точечных объектов.// Автометрия, 1991, №6, с.21-26.

[62] А.Л.Резник. О распределении разности порядковых статистик при случайном разбиении интервала.// Автометрия, 1995, №1, с.46-52.

[63] A.L.Reznik "Analytical Operations Using Computer in Topical Probabilistic Problems Related to an Analysis of Discrete Structures" // Pattern Recognition and Image Analysis, 1996, vol. 6, no. 1, pp.52-53.

[64] A.L.Reznik "Analytical Solution of Probabilistic Problems Resulting from Random Partitioning of an Interval with the Use of Computer" // Pattern Recognition and Image Analysis, 1996, vol. 6, no. 4, pp.657-661.

[65] A. L. Reznik and V. M. Efimov. Analytical Computer Calculations in Analysis of Discrete-Point Images // Pattern Recognition and Image Analysis, vol.10, no 1, 2003, pp.158-160.

[66] Alexander L. Reznik, Vitaly M. Efimov. Analytical computer calculations in image analysis: correct reading of random discrete-point fields // Proc. of the IASTED International Conference on Signal Processing, Pattern Recognition, and Applications, June 30 - July 2, 2003, Rhodes, Greece, pp.6-10.

[67] С.Уилкс. Математическая статистика // M., Мир, 1967, 632 с.

[68] Parzen, Е., Modern Probability Theory and Its Applications // John Wiley and Sons, Inc., New York-London, 1960.

[69] В.М.Ефимов, А.М.Искольдский, З.А.Лившиц, Ю.М.Крендель. О характеристиках различных методов считывания изображений дискретных структур // Автометрия, 1973, №1.

[70] Darling, D.A., On Class Problems Related to the Random Division of an Interval // Ann. Math. Stat., 1953, vol.24: p. 239-253.

[71] Barton, D.E., and David, F.N., Combinatorial Extreme Value Distributions // Mathematika, 1959, no 6: p.63-76.

[72] Naus, J.I., Some Probabilities, Expectations, and Variances for the Size of Largest Clusters and Smallest Intervals // J. Am. Statist. Assoc., 1966, vol.61: p.1191-1199.

[73] Г.Дэйвид. Порядковые статистики // M.: Наука, 1979, с.336.

[74] Официальная информация Информационно-вычислительного центра НГУ // http://www.nusc.ru/wiki/doku.php/doc/openmp/openmp

[75] Рейтинг суперкомпьютеров СНГ // http://top50.supercomputers.ru/?page=archive&rating=9

[76] Programming parallel algorithms // Communications of the ACM, v.39 n.3, p.85-97, March 1996

[77] Легалов А. Построение параллельных алгоритмов // Открытые системы. - 2004. - N 9. - С. 64-68С

[78] Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем // Учебное пособие - Нижний Новгород; Изд-во ННГУ им. Н.И.Лобачевского, 2010

[79] В.Феллер. Введение в теорию вероятностей и ее приложения // М.: Мир,

1966.

[80] А.Л.Резник. Моделирование на ЭВМ непрерывного считывания изображений дискретной структуры.// Автометрия, 1981, №6, с.3-6.

[81] The On-Line Encyclopedia of Integer Sequences™ (OEIS™) // http://oeis.org/

[82] Leonhard Euler, letter to Christian Goldbach, 1751

[83] Гарднер M. Путешествие во времени // Мир, 1990, стр. 284 - 300

[84] Brian Hayes, "A Question of Numbers" // American Scientist, №1, 1996

[85] Sriram Pemmaraju, Steven Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica // Cambridge University Press, 2003

[86] Fred S. Roberts, Barry Tesman, "Applied Combinatorics", Second Edition // CRC Press, New York, 1990

[87] Ландо C.K. Комбинаторика // M.: Изд. Независимого моек, ун-та, 1994. 78 с.

[88] Stanley, Richard P., Enumerative combinatorics. Vol. 2 // Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, 1999

[89] André, D. "Solution directe du problème résolu par M. Bertrand." // Comptes Rendus Acad. Sci. Paris 105, 436-437, 1887

[90] А.П.Прудников, Ю.А.Брычков, О.И.Маричев. Интегралы и ряды // М., Наука, 1981, 800 с.

[91] Jim Pitman Some Probabilistic Aspects of Set Partitions // The American Mathematical Monthly, Volume 104, Issue 3, p.p. 201 - 209

[92] Winifred D. Ashton, Theory of Road Traffic Flow // The Annals of Mathematical Statistic, Volume 39, Number 1, 1968

[93] Irwin, J. O. (1955), A unified derivation of some well-known frequency distributions of interest in biometry and statistics // J. Roy. Statist. Soc. Ser. A, 118,389-404.

[94] Vincent E. Cook And Robert K. A quantitative model of DNA fragments generated by ionizing radiation, and possible experimental applications // Radiation Research, 1991 Jan; №l,p.p. 102-106

[95] Fred Brauer, Pauline Van Den Driessche, Jianhong Wu, Linda J. S. Allen // Mathematical Epidemiology, Springer, New York, 2008

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

Автор благодарит весь коллектив Лаборатории №12, а также персонально научного руководителя Александра Львовича Резника за помощь в работе над Диссертацией.

Также автор благодарит Информационно-вычислительный центр НГУ за предоставленную возможность проводить аналитические вычисления на кластере.