Введение к работе
Актуальность темы
Важное место в математической кибернетике занимают проблемы синтеза и сложности управляющих систем. Многие из этих проблем могут быть сформулированы в терминах порождения математических объектов функциональными системами*. В частности, большое значение имеют задачи вычисления действительных чисел при помощи алгебраических операций. К таким задачам можно отнести задачи моделирования управляемых источников случайных кодов.
Управляемые источники случайных кодов представляют собой частный случай вероятностных автоматов, которые относятся к числу основных модельных классов управляющих систем и довольно интенсивно изучаются в последнее время в математической кибернетике. Важное место в теории вероятностных автоматов, представляющих собой достаточно сложный математический объект, отводится исследованию некоторых частных случаев, возникающих в различных разделах этой теории. Управляемые источники случайных кодов играют фундаментальную роль в структурной теории вероятностных автоматов. В частности, установлено**, что любой вероятностный автомат может
См., напр.: Гашков С. Б. О сложности приближенного вычисления действительных чисел схемами и формулами в различных базисах //Дискретная математика, 1990. т. 2. N* 4. 26-46.
Бухараев Р. Г. Основы теории вероятностных автоматов. Москва, "Наука". 1985.
быть представлен в виде последовательной композиции некоторс го управляемого источника случайных кодов и подходящего кс нечного детерминированного автомата.
Случайным ходом, или булевой случайной величиной, назь вается случайная величина с двумя возможными значениями и 1. Большое значение для синтеза управляемых источников ел] чайных кодов имеет задача моделирования булевых случайны величин на основе некоторого исходного семейства элементарны случайных кодов. Центральное место в этой задаче занимает пс нятие преобразователя вероятностных распределений как некс торой управляющей системы, перерабатывающей элементарны случайные коды в другие булевы случайные величины. В диссеї тации изучаются два типа преобразователей вероятностных pax пределений, исследовавшихся ранее в научной литературе: фуні ции алгебры логики и вероятностные контактные сети. Посколі ку распределение вероятностей булевой случайной величины ох нозначно задается вероятностью принятия ею значения 1, задач моделирования булевых случайных величин допускает перефор мулировку в терминах порождения чисел в различных класса преобразователей вероятностных распределений.
В последнее время все больщее внимание уделяется пробл* мам оптимального синтеза управляемых источников случайны кодов, в том числе сложностным аспектам моделирования буле вых случайных величин. В частности, в ряде работ* решені
См., напр.: Захаров В.М., Салимов Ф.И. К теории струї турного синтеза детерминированных. преобразователей верояі ности //Problems of Control and Information Theory, Vol. 6 (2' pp. 137-148 (1977); Нурмеев Н.Н. О сложности реализации пр<
некоторые задачи, связанные со сложностью схемной реализации преобразователей вероятностных распределений как функций алгебры логики. В диссертации вводится понятие сложности порождения числа множеством чисел как для порождения в классе булевых функций, так и для порождения в классе вероятностных контактных сетей.
Цель работы
Один из основных вопросов, связанных с моделированием булевых случайных величин, состоит в описании множеств, порождаемых различными конечными системами чисел. В диссертации в качестве порождающих систем рассматриваются множества рациональных чисел. Один из путей решения поставленной задачи заключается в отыскании конечных подмножеств, порождающих различные множества в том или ином классе преобразователей вероятностных распределений. В любом классе булевых функций или вероятностных контактных сетей рациональными числами могут порождаться только рациональные числа. Поэтому в диссертации класс порождаемых множеств ограничивается множествами рациональных чисел в интервале (О, 1).
Важной целью исследования является также получение оценок сложности порождения чисел из порождаемых множеств конечными подмножествами, порождающими эти множества. Кроме того, в диссертации уделяется внимание сравнению порожде-
обраэователей вероятностей схемами из функциональных элементов //Методы и системы тех. диагностики (межвуз. сборник научных трудов), Саратов, 1993. вып. 18, 131-132.
ний в различных классах булевых функций и вероятностных хоі тактных сетей.
Научная в шэна Разработаны новые мете: л J доказательства, порождаемое] множеств рациональных чисел и получения оценок сложности п рождения рациональных чисел как в классах булевых функци так и в классах вероятностных контактных сетей. С помощь этих методов найдены необходимые условия порождаемости мн жеств рациональных чисел в классах булевых функций. Получ< ряд результатов, касающихся порождения чисел вероятностны*, контакт-', ;,<ии сетями произвольного вида.
Теоретическая и практическая ценность
Работа носит теоретический характер. Разработанные в ди сертации методы могут быть использованы для доказательст: порождаемости и оценки сложности порождения множеств рац опальных чисел в более узких классах булевых функций, а такі для получения более сильных оценок сложности порождения р циональных чисел в классе вероятностных контактных 7г-сете Примененная в диссертации методика доказательства конечні порожденности множеств пятирк -.о- и семирично-рациональнъ чисел в классе вероятностных контактных сетей произвольно вида является полезной для исследования конечной порожденн сти в этом классе множеств р-ично рациональных чисел при пр стых р, больших 7. Полученные в диссертации результаты мог; найти применение при моделировании генераторов случайных ч сел на ЭВМ.
5 Методика исследования В работе используются методы дискретной математики и математической кибернетики, теории чисел и математического анализа.
Апробация результатов
Результаты диссертации докладывались на Школе-семинаре по синтезу и сложности управляющих систем (Нижний Новгород, 1992), IV Межгосударственном семинаре по дискретной математике и ее приложениям (Москва, 1993), X Международной конференции по проблемам теоретической кибернетижи (Саратов, 1993), на научных семинарах СВ. Яблонского по математическим вопросам кибернетики и О. Б. Лупанова по синтезу управляющих систем, а также на других школах и семинарах.
Публикации Основные результаты диссертации опубликованы в работах автора, список которых приведен в конце реферата.
Объем и структура работы