Введение к работе
Актуальность темы. ,. Задачи о сложности вычисления или построения в тоа ии ином смысле разни объектов в последнее время часто рассмагризаися во многих разделах математики: в анализе ( в теории привалений ), вычислительной математике, алгебре ( з так называемой алгебраической теории сложности ), теории чисел, геометрии (в та называемой вычислительной геометрии ), логике и теорга алгориткв и более всего - в теории сложности булевых функций. В чаяшсти, вопросы о сложности приближенного вычисления' дейстзителотх чисел, рассматривались, например в работах Bprweln J.^BorrelnL1' и Strassen V.2)
В работе изучаются задачи о сложности реализация рациональных чисел формулами в некоторых базисах, состоящих из аріфйтическЕХ операций, и о сложности приближения иррациональных чисел рациональными. В качестве базисов будем рассматривать следуете множества операций В = { пу.х-у.ху.х/у.х''1,! },BQ= { i+y.r-j/.iy^.l }, Bt = {х+у,ху,х-\Ц, Вг = іщ,х'\\},\ = {s+j/.^'WИ}-Понятие формула над базисом В и реализуемой ев функции шредзляет-ся индуктивно стандартным образом, подобно тому как определяются формулы в алгебре логике и теории сложности булевых функций 3],i) Под сложностью формулы понимается число символов перекалах и констант (в рассматриваемом случае - единиц) в формуле. Сложностью рационального числа г назнвазтся_ минимальная сложность реализущей
ВогтеШ J.M.Boireln R,P. On the complexity ої familiar Ішс- . tlons and numbers.- SIAM Review, 1938, v. 30, № 4, p.589-601.
Strassen 7. Berechmmgsn Id partiellen Algetren enulichen lyps.-Conpiting, 11 -(1973).- s.181 - 196.
Яблонский СВ. Введение в дискретную математику.- И.: Наука, 1986.
Лупанов О.Б. Асимптотические оценки сложности улравгнщих систем. - м.: изд. МГУ, 1984.
-I -
его формула к обозначается она Lg(r). Перу сложности Lg (г) =
= Lg (г) , хж будет гаизазо далее, можно интерпретировать как
наименьшее няичестБО едшчвнх сопротивлений, із которых могно построить тыедовательаншралдельнув схему Ш-схеиу) с сопротивлением пи Еаныеньсую сушу элементов" в ветвящихся цепных дробях, нредатавляаш г.(.о ветвящихся дробях са.5)).чВозькшвн и другие содершельше интерпретации. Формула образует простої и ваша подкласс схем.причем любую
Схему МОЖаО.НВ НЗКЄНЯЯ ГЛУбННЫ, ПреОбрЭЗОЕТЬ В форНУДУ. ГлубИНа
является ваши мерой сжтаости, так как она оценивает вреш вычисления функции с учетом возмозности параллельного использования многих процессоров. Изучение формул оправдывается также тем, что некоторые вин вычислительных устройств моделируются именно формулами.
Цельработн- получение точных оценок сложности реализации ряиогашшх чисел формулами в некоторых базисах, состоящих из ^яфетических операции, и нахождение условий их обращения в равенство; - получение асимптотически точных оценок сложности прйинэнной реализации иррациональных чисел формулами; - исследована: асиштотического поведения наименьшего знаменателя рациональной дроби, снприближащеи данное иррациональное число.
Методика исследовании. В работе используются метода дистетжи математики и математической кибернетики, теории чисел и вярическои теории диофантовьи приближении.
Научная новизна. Все основные результаты работы ноше. Нехотошз результаты являются уточнениями ранее известных. В работе получена во многих ваша случаях точные значения сложности реализации рациональных чисел формулами в непрерывных бази-
Скорбогатько В.Я. Теория ветвящихся цепных дробей и ее применение в вычислительной математике. - Н.: Наука, 1983. -2-
сах, и в некоторых случаях - точные значения слсзюяя црйлшен-ной реализации иррациональных чисел формулами. Вперше найдан асимптотически точные верхние оценки наименьшего знаменатея рациональной дробя, с-прибликащей данное иррациональное число, ивозникагсее в связи с этим одно свойство золотого сечения.
Прилоіения. Работа носит теоретический характерце результата могут быть использованы в некоторых вопросах тесрш диофантовых Ерибдиешй и математической кибернетики.
Апробация. Результаты работы докладавзлись на семинаре Б.Н.Чубэриксва и Г.И.Архзтова и на семинаре А.и.Аптекарега, В.В.Вавшгавз, Е.А.Рахманова в МГУ.
Публикации. По теме диссертации автором представлены к опувликовакш 2 работы,'названия которых приведены в коваз автореферата .
Структура диссертации. Диссертация состоит из введения и двух глав, состоящих каддая из трех параграфов, и. списка.литературы. Полный обьем - 9& стр.текста.