Содержание к диссертации
Введение 6
Актуальность темы 6
Цели работы 7
Методы исследования 7
Научная новизна 7
Практическая ценность 7
Апробация работы 7
Публикации 8
Структура и объем работы 8
1 Обзор литературы 10
1.1 Вычислимый математический анализ 10
Конструктивный анализ Маркова 11
Рекурсивный анализ Гудстейна 12
1.2 Сведения из теории вычислительной сложности 13
Машина Тьюринга 13
Машина Тьюринга с оракульной функцией 14
Классы вычислительной сложности 14
Классы FP и FLINSPACE 16
1.3 Монография К. Weihrauch 16
Вычислительная модель 16
Конструктивные вещественные числа и функции 17
Представление рациональных чисел 17
Вычислительная сложность чисел и функций 18
1.4 Работы К. Ко 18
Двоично-рациональные числа 19
CF конструктивные вещественные числа 20
CF конструктивные вещественные функции 20
Определение FP конструктивных чисел 21
Определение FP конструктивных функций 21
Свойства FP конструктивных объектов 22
1.5 Вычисление значений констант и функций 24
Арифметико-геометрическое среднее 25
Разложения в ряды с рациональными коэффициентами 26
1.6 Выводы к главе 1 27
2 Множества FLINSPACEcf и FЫNSРАСЕС[а,щ 28
Двоично-рациональные числа 28
Определение и основные свойства 30
FLINSPACE конструктивные числа 30
FLINSPACE конструктивные функции 31
Арифметические операции на FLINSPACEcf 31
Сложение и вычитание 33
Умножение 33
Обратное значение 34
Деление 35
2.2.4 Суперпозиция конструктивных функций 36
Вычисление значений полиномов 37
Вычисление частичных сумм степенных рядов 40
Схема с коэффициентами вида ^ 40
Схема с составными коэффициентами 43
2.5 Аналитические функции 46
Вычисление степенных рядов 46
Разложение в ряд Тейлора 48
2.6 Выводы к главе 2 49
3 FLINSPACE конструктивные числа и функции 50
3.1 Конструктивные числа 50
Целые и рациональные числа 50
Иррациональные алгебраические числа 51
Операции над полиномами 51
Вычисление аппроксимаций корней 58
3.1.3 Некоторые трансцендентные числа (7Г и е) 59
3.2 Элементарные функции 61
3.2.1 Алгебраические функции 61
Рациональные функции 61
Иррациональные функции 62
Тригонометрические функции 66
Обратные тригонометрические функции 69
Показательная функция 72
Логарифмическая функция 74
3.3 Выводы к главе 3 77
4 Библиотека классов на языке программирования С# 78
Иерархия классов 79
Вспомогательные классы 79
4.2.1 Двоично-рациональные числа 81
Нормализованное представление 82
Основные методы 82
Конструкторы 83
Класс DRNumPair 84
Операции сравнения 85
Операции сложения, вычитания и умножения 86
Операции обращения и деления 87
Дополнительные операции 87
Двоично-рациональный интервал 88
4.2.2 Полиномы 88
Представление массивом коэффициентов 88
Основные методы 89
Конструкторы 89
Операции сложения и умножения 90
Дополнительные операции 90
4.3 Вычисление полиномов и степенных рядов 90
Реализация алгоритма из 2.3 91
Реализация алгоритмов из 2.4 91
Определение рядов для чисел и функций 93
4.4 Конструктивные числа 94
4.4.1 Класс CompRealNumber 94
Отношение порядка 95
Арифметические операции 96
Целые и рациональные числа 96
Иррациональные алгебраические числа 97
Псевдоделение с остатком 97
Вычисление набора отделяющих интервалов 99
Представление алгебраических чисел 101
Вычисление аппроксимаций корней 102
4.4.4 Трансцендентные числа (л- и е) 102
4.5 Конструктивные функции 103
Класс CompRealFunc 104
Элементарные функции 105
4.6 Результаты пробных вычислений 106
4.7 Выводы к главе 4
Заключение 108
Основные результаты 108
Список литературы 109
Список таблиц 112
Предметный указатель 112
А Текст программы 114
А.1 Вспомогательные классы 114
А.2 Вычисление полиномов и степенных рядов 136
А.З Конструктивные числа 142
А.4 Конструктивные функции 155
А.5 Файлы приложения 162
Введение к работе
Актуальность темы. С появлением вычислительной техники встал вопрос о вычислительной сложности объектов математического анализа, в первую очередь основных классов вещественных чисел и функций. Среди работ последних 18 лет, в которых исследовалась вычислительная сложность конструктивных вещественных чисел и функций, отметим [30,31,34]. Данные работы в значительной степени являются обобщением накопленных знаний относительно вычислимого математического анализа и отражают современное состояние исследований в данной области. Работы [30,31,34] характеризуются тем, что авторы в основном рассматривают временную вычислительную сложность проблем математического анализа. В [34] вычислительная сложность рассматривается с точки зрения времени выполнения и длины входной ленты, достаточных для получения приближенных значений вещественных чисел и функций с произвольной точностью. Здесь же приводится ряд теорем относительно вычислительной сложности арифметических операций и некоторых понятий из теории функций вещественного переменного. В [30, 31] строится система полиномиально вычислимого анализа, при этом главное внимание уделяется построению и определению свойств классов конструктивных вещественных чисел и функций, аналогичных классам из теории вычислительной сложности. Линейная емкостная сложность объектов математического анализа, для оценки которой важно знать объем промежуточных вычислений, в работах [30,31,34] почти не затронута. Вместе с тем, представляет существенный теоретический и практический интерес построение системы конструктивных вещественных чисел и функций, которая позволяла бы выполнять базовые вычисления в пределах некоторого емкостного класса сложности, подпадающего под понятие «осуществимые вычисления», как, например, класс FP, т. е. класс вычислений на машинах Тьюринга за полиномиальное время от длины исходных данных [25]. Теоретический интерес имеет место в силу неизвестной точной взаимосвязи классов временной и емкостной вычислительной сложности; практический интерес следует из того, что получающиеся алгоритмы вычисления приближенных значений относительно проще, что немаловажно для уменьшения сложности программного обеспечения, например, в области численных расчетов. В качестве такого класса в данной работе выбран FLINSPACE [25] —класс алгоритмов, для которых длина каждой промежуточной записи вычисления ограничена линейной функцией от суммарной длины входных данных. Подтверждением неформальной характеристики класса FLINSPACE как класса осуществимых вычислений с точки зрения требуемой для вычислений па-
мяти может служить то, что в настоящее время в работах по теоретической информатике для вычислений в пределах FLINSPACE утвердился термин «space-efficient evaluation». Известно, что класс FLINSPACE не совпадает с классом FP и, кроме того, если FLINSPACE С FP, то Р = NP [9]. Следовательно, результаты относительно FLINSPACE вычислимости объектов математического анализа не следуют непосредственно из FP вычислимости этих объектов и требуют отдельного доказательства в предположении Р ф NP, которое поддерживается многими специалистами в области математических основ информатики.
Введем обозначение FP//LINSPACE для класса алгоритмов, вычислимых машиной Тьюринга за полиномиальное время и на линейной зоне. Под алгоритмическими функциями (конструктивными функциями) над конструктивными числами будем понимать алгоритмы, вычисляющие приближения значений функций по приближениям аргумента.
Цели работы. Показать, что для вещественных чисел и функций математического анализа, наиболее часто используемых на практике, можно построить конструктивные аналоги, позволяющие находить приближения в пределах класса FP//LINSPACE. Разработать алгоритмы для работы с FLINSPACE вычислимыми приближениями объектов математического анализа, которые реализуемы на объектно-ориентированном языке программирования. Реализовать такие алгоритмы на языке программирования С# в среде программирования Microsoft Visual Studio 7.1.
Методы исследования. Для построения и оценки вычислительной сложности алгоритмов использовались аппарат численных методов, математический анализ, теория вычислительной сложности, аппарат конструктивного математического анализа. При реализации библиотеки классов использовались такие элементы программирования, как абстрактные классы, функторы, интерфейсы, итераторы.
Научная новизна. Новым является изучение достаточно широкого класса вещественных чисел и функций с точки зрения вычисления двоично-рациональных приближений в пределах класса FLINSPACE, как весьма важного для практических вычислений.
Практическая ценность. Практическая ценность диссертации состоит в том, что предложенные алгоритмы и библиотека классов на языке программирования С# могут использоваться в различных системах численных расчетов, требующих вычислений с вещественными числами и функциями с любой заданной точностью.
Апробация работы. Результаты работы обсуждались на следующих научных конференциях и семинарах:
V Международная конференция «Дискретные модели в теории управляющих систем» (Ратмино, 26—29 мая 2003 г.);
VIII Международный семинар «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.);
IX Международный семинар «Дискретная математика и ее приложения» (Москва, 18—23 июня 2007 г.);
семинар кафедры вычислительных методов математико-механического факультета Санкт-Петербургского государственного университета;
семинар кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета.
Публикации. По теме диссертации опубликованы тезисы [17-19] и статьи [20,21]. В [17, 20] содержатся результаты о емкостной вычислительной сложности алгоритма Штурма и FP//LINSPACE конструктивности алгебраических чисел, а также рассмотрены арифметические операции на множестве FLINSPACE конструктивных вещественных чисел. В [18,19,21] предложены алгоритмы для вычисления степенных рядов в пределах FP//LINSPACE и доказана FP//LINSPACE конструктивность некоторых элементарных функций. В статье [21] имеется описание библиотеки классов на языке программирования С# для работы с FLINSPACE конструктивными вещественными числами и функциями. Статьи [20, 21] входят в перечень изданий, рекомендованных ВАК для публикаций.
Структура И объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, списка таблиц, предметного указателя и приложения. Содержит 1 рисунок, 2 таблицы и список цитируемой литературы из 35 наименований. Текст диссертации изложен па 113 страницах. Исходные тексты библиотеки классов на языке программирования С# находятся в приложении на 54 страницах.
В главе 1 содержится обзор литературы по теме диссертации. Кратко рассматриваются конструктивный математический анализ Маркова [10] и рекурсивный математический анализ Гудстейна [3], которые можно считать наиболее важными работами по теоретическим основам вычислимого математического анализа. Затем описывается монография К. Weichrauch [34] и две работы К. Ко — монография [30] и статья [31]. В монографии К. Weichrauch в основном содержится определение вычислимости и вычислительной сложности для таких топологических понятий, как непрерывность, компактные множества. В работах К. Ко главное внимание уделяется построению и свойствам FP конструктивных объектов математического анализа. Затем рассматриваются статьи,
в которых исследуется сложность алгоритмов расчета основных объектов математического анализа. Выделяются два способа построения таких алгоритмов — арифметико-геометрическое среднее и ряды с рациональными коэффициентами. В частности, приводится ссылка на известную работу R. Brent [23], в которой показывается вычислимость элементарных функций за время М(п) log(n), где через М(п) обозначается временная сложность умножения п-битовых двоичных чисел.
