Разработка и реализация алгоритмов для работы с FLINSPACE конструктивными вещественными числами и алгоритмическими функциями над ними

• Автор: Яхонтов, Сергей Викторович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 167 с.

Оглавление
Введение

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

Цели работы

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

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

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

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

Публикации

Структура и объем работы.

1 Обзор литературы

1.1 Вычислимый математический анализ.
1.1.1 Конструктивный анализ Маркова.
1.1.2 Рекурсивный анализ Гудстейна
1.2 Сведения из теории вычислительной сложности
1.2.1 Машина Тьюринга.
1.2.2 Машина Тьюринга с оракульной функцией.
1.2.3 Классы вычислительной сложности.
1.2.4 Классы и I.
1.3 Монография . i
1.3.1 Вычислительная модель
1.3.2 Конструктивные вещественные числа и функции.
1.3.3 Представление рациональных чисел
1.3.4 Вычислительная сложность чисел и функций
1.4 Работы К. Ко.
1.4.1 Двоичнорациональные числа
1.4.2 конструктивные вещественные числа
1.4.3 конструктивные вещественные функции
1.4.4 Определение конструктивных чисел.
1.4.5 Определение конструктивных функций.
1.4.6 Свойства конструктивных объектов.
1.5 Вычисление значений констант и функций
1.5.1 Арифметикогеометрическое среднее.
1.5.2 Разложения и ряды с рациональными коэффициентами
1.6 Выводы к главе 1
2 Множества РЬШЗРАСЕсг и РЫАгЗРАСЕса,ь
2.1 Двоичнорациональные числа
2.2 Определение и основные свойства.
2.2.1 РЬШЗРАСЕ конструктивные числа.
2.2.2 РЬШЗРАСЕ конструктивные функции.
2.2.3 Арифметические операции на РЬШЗРАСЕыг.
Сложение и вычитание
Умножение.
Обратное значение.
Деление.
2.2.4 Суперпозиция конструктивных функций.
2.3 Вычисление значений полиномов
2.4 Вычисление частичных сумм степенных рядов
2.4.1 Схема с коэффициентами вида
2.4.2 Схема с составными коэффициентами
2.5 Аналитические функции.
2.5.1 Вычисление степенных рядов .
2.5.2 Разложение в ряд Тейлора
2.6 Выводы к главе 2 .
3 РЬШЗРАСЕ конструктивные числа и функции
3.1 Конструктивные числа
3.1.1 Целые и рациональные числа
3.1.2 Иррациональные алгебраические числа.
Операции над полиномами.
Вычисление аппроксимаций корней.
3.1.3 Некоторые трансцендентные числа тг и е
3.2 Элементарные функции
3.2.1 Алгебраические функции
Рациональные функции
Иррациональные функции
3.2.2 Тригонометрические функции
3.2.3 Обратные тригонометрические функции.
3.2.4 Показательная функция
3.2.5 Логарифмическая функция
3.3 Выводы к главе 3.
4 Библиотека классов на языке программирования С
4.1 Иерархия классов.
4.2 Вспомогательные классы.
4.2.1 Двоичнорациональные числа
Нормализованное представление
Основные методы
Конструкторы.
Класс 1МитРа1г.
Операции сравнения.
Операции сложения, вычитания и умножения.
Операции обращения и деления.
Дополнительные операции
Двоичнорациональный интервал
4.2.2 Полиномы .
Представление массивом коэффициентов.
Основные методы
Конструкторы.
Операции сложения и умножения
Дополнительные операции
4.3 Вычисление полиномов и степенных рядов.
4.3.1 Реализация алгоритма из 2.3
4.3.2 Реализация алгоритмов из 2.4
4.3.3 Определение рядов для чисел и функций
4.4 Конструктивные числа.
4.4.1 Класс СотрЯеаШитЬег
Отношение порядка
Арифметические операции
4.4.2 Целые и рациональные числа
4.4.3 Иррациональные алгебраические числа.
Псевдоделение с остатком
Вычисление набора отделяющих интервалов
Представление алгебраических чисел.
Вычисление аппроксимаций корней
4.4.4 Трансцендентные числа тг и е
4.5 Конструктивные функции.
4.5.1 Класс СотрЯеаПчтс.
4.5.2 Элементарные функции
4.6 Результаты пробных вычислений
4.7 Выводы к главе
Заключение
Основные результаты
Список литературы


Арифметические операции для рекурсивных вещественных чисел строятся па основе арифметических операций над членами последовательностей. Например, сумма чисел s и t — это рекурсивно сходящаяся последовательность s(n) + t(n). Проводится построение рекурсивных аналогов основных понятий математического анализа — непрерывности, дифференцирования, интегрирования. В данном разделе приводятся необходимые сведения из [4. Тыоринга как базовый вычислительной модели в дальнейших рассмотрениях и сведения об основных классах вычислительной сложности. Машина Тьюринга является вычислительным устройством общего характера: известно, что машина Тыоринга эквивалентна другим вычислительным моделям таким, как нормальные алгорифмы, рекурсивные функции. Будут рассмотрены две разновидности машины Тыоринга: детерминированная машина Тыоринга и детерминированная машина Тыоринга с оракульной функцией. В самом общем случае детерминированная машина Тыоринга состоит из двух частей — управляющего устройства и ленты с данными. Такое устройство может находиться в одном из состояний из конечного набора Q, включающего набор F конечных состояний. Лента состоит из одинаковых ячеек, в которых записываются символы из входного алфавита Е и специальные символы из алфавита Г; на ленте размещаются входные, выходные и промежуточные данные. Управляющее устройство содержит программу, которая является функцией перехода из текущего состояния машины Тыоринга к следующему состоянию. Чтение и запись на ленту осуществляются с помощью головки, которая может перемещаться по ленте на позицию влево или вправо за один такт. Машина Тыоринга начинает работу с некоторого начального состояния д0) входная строка записывается на ленту в последовательных ячейках; головка указывает на ячейку, находящуюся непосредственно перед входной строкой. Если машина Тьюринга М останавливается на входной строке го в конечном состоянии q) то говорят, что М допускает строку гв. Если М не останавливается на входной строке т или останавливается в некотором состоянии д <р . Р, то считается, что М не допускает строку ги. С помощью Ь(М) (язык Ь) обозначается множество всех строк ги € допускаемых машиной Тыориига М. Для изучения свойств алгоритмов удобнее пользоваться многоленточной машиной Тьюринга. В таком устройстве лента с данными может быть разделена, например, на три ленты — входную, выходную и промежуточные ленты. Входная лента работает только па чтение, выходная лента-только на запись, а рабочие лепты позволяют читать и записывать данные. Каждая лента неограниченна но длине, имеет свою головку; все ленты управляются одним центральным устройством. Известно, что одноленточная машина Тьюринга и многоленточная машина Тьюринга являются эквивалентными вычислительными моделями. Детерминированная машина Тыориига с оракульной функцией —это обычная детерминированная машина Тыориига, но которая в процессе работы может обращаться к дополнительной функции /, определенной на Е* и называемой оракульной функцией. Детерминированная машина Тыориига с оракулом / обозначается через МЛ Такая машина снабжена дополнительной лентой, называемой лентой запроса, и двумя дополнительными состояниями — состоянием запроса и состоянием ответа. М* работает в точности так же, как и обычная машина Тьюринга, до момента, когда она переходит в состояние запроса. В этом состоянии подготавливает на ленте запроса строку запроса и передает управление оракульной функции. Затем считывается строка с ленты запроса, вычисляется оракульная функция / и на ленту помещается строка /(у) М* переходит в состояние ответа и затем вычисления продолжаются как для обычной машины Тьюринга. Пусть М — детерминированная машина Тьюринга. Время работы М на входной строке х определяется как количество тактов М, начиная с начального состояния вплоть до конечного состояния, и обозначается как Итсм{х). Память, требуемая для работы М на входной строке х — это количество ячеек ленты, которые головка М хоть раз посещает в процессе вычислений; обозначается через врасем(х). Для многоленточных машин Тьюринга при оценке зрасем(х) удобно учитывать только память рабочей ленты.