Введение к работе
Актуальность темы. Областью, начавшей развиваться с самого начала кибернетических исследований, и в существенной степени вызвавшей к ним интерес, является вычисление "дискретными" устройствами "непрерывных" функций. Вычисление это с необходимостью будет приближенным.
Предложенный Колмогоровым*^ и развитый впоследствии его учениками**' подход к определению сложности -приближения непрерывных функций .дискретными основан на следующей конструкции.
Пусть { : ]_о, і) -» [о, ±) - непрерывная функция, приближение которой дискретными исследуется.
Пусть а : [о, і) -р- [о, і ) - кусочно-постоянная функция,которая непрерывна на полуинтервалах вида [ г. , (i+i)- / и
- /и.
принимает значения вида j Я, , где і и j - неотрицательные целые числа, а п и т - фиксированные для данной функции q натуральные числа. Будем говорить, что q с -
приближает / , если ?u.p , !f(x)'3(x)| 4= - .Закодировав
ХЄІО.І)
указанные хЛ полуинтервалов и іГ' значений булевыми наборами, мы получим булев (к, т.) - оператор. Тогда колмогоровской сложностью -приближения функции f назовем минимальную сложность реализации***' операторов, реализующих ' -приближающие / ФУНКЦИИ q .
*' Колмогоров А.Н. Различные подходы к оценке трудности приближенного задания и вычисления функций // Ргос-Intern.. Co^r. Ma-lk StockltoU- - 1963. - P.230-250.
**' См., напр..работы: Офман Ю. О приближенной реализации непрерывных функций на автоматах // ДАН СССР. - 1963. - 152, № 4. - С.823-826; Тогер А.В. О сложности некоторых функциональных классов // ДАН СССР. - 1971. - 199, й 4. - С.789-791; Аса-рин Е.А. О сложности равномерных приближений непрерывных функций // УМН. - 1984. - 39, № 3. - С.157-169, и др.
зШ?'Лупанов О.Б. О синтезе некоторых классов управляющих систем //Сб."Проблемы кибернетики". - 1963. -Вып.10.-С.63-97.
Однако, такой подход обладает одним заметным недостатком, а именно, те .дискретные операторы и классы операторов, с помощью которых осуществляется приближенное вычисление непрерывных функций, определяются исключительно как "хорошие приближения" последних, т.е. весьма неявно и неконструктивно. В частности, ответ на вопрос, -приближает ли заданный булев оператор какую-либо непрерывную функцию из заданного класса |<, , требует в принципе проверки бесконечного множества потенциально приближаемых функций -f из К , что затруднительно и заведомо требует большого времени.
Преодоление этой трудности, т.е. явное определение дискретных классов, осуществляющих -приближение соответствующих непрерывных, и исследование сложности реализации составляющих их функций являются предметом диссертации.
Цель работы. I. Явное (через внутренние свойства) определение классов дискретных функций, осуществляющих приближение классов непрерывных функций различной гладкости.
2. Исследование сложности точной и приближенной реализации схемами из функциональных элементов функций из указанных дискретных классов.
Нагчная новизна. Все основные результаты работы новые. Некоторые результаты (это относится главным образом к нижним оценкам) являются аналогами и обобщениями ранее известных оценок .-энтропии и колмогоровской сложности.
Разработана методика построения дискретных аналогов различных классов непрерывных функций, характеризуемых их дифференциальными свойствами; при зтом определения указанных дискретных классов строятся на основе внутренних свойств дискретных функций. На основе этого общего принципа построены дискретные аналоги функций конечной гладкости (с ограничением на
і»- -ю производную в вице условия Липшица, условия Гель дера или мажоранты модуля непрерывности), аналитических функций (периодических z непериодических), а также функций из некоторого промежуточного класса бесконечно дифференцируемых, но не аналитических функций.
Для построенных классов получены оценки мощности минимальных I-приближайших множеств (множеств, содержащих для каждой функции из исследуемого класса ее приближение с точностью ^. 1 ). Показано, что эта. величина для классов дискретных
функций аналогична и тесно связана с -энтропией классов непрерывных функций.
Наконец, для классов дискретных функций конечной гладкости разработан метод синтеза схем из функциональных элементов, реализующих I-приближение дискретных функций с близкой к минимально возможной сложностью.
Практическая ценность. Полученные результаты о связи дискретных классов с непрерывными могут быть использованы как в теории дискретных управляющих систем, так и в теории приближений. Разработанный метод синтеза схем для дискретных функций может найти применение при оценке времени вычисления различных функций, а также при создании программного и аппаратного обеспечения вычислительной техники.
Методика исследования. В диссертации используются методы дискретной математики и математической кибернетики, комбинаторики, теории функций действительного и комплексного переменного, теории приближений и математического анализа.
Апробация. Основные результаты диссертации докладывались на Школе-семинаре по синтезу и сложности управляющих систем (Нижний Новгород, 1992), а также на научных семинарах в МГУ им. М.В.Ломоносова.
Публикации. По теме диссертации опубликовано 2 работы, список которых приведен в конце реферата.
Структура и объем работы. Диссертация состоит из списка кратких обозначений, введения, двух глав, разбитых на 13 параграфов, дополнения, содержащего вспомогательные утверждения, и списка литературы, включающего 14 названий. Объем работы составляет 217 страниц машинописного текста. Изложение проиллюстрировано 4 рисунками.