Введение к работе
Актуальность темы. Исследавания популярных датчиков случайных чисел, включенных в состав математического обеспечения многих вычислительных машин, показал неправомерность их мсполь-зования в качестве моделей последовательностей независимых случайных величин. Были обнаружены [13] и [2 из списка работ автора] закономерности их поведения, могущие существенно исказить результаты исследований, в которых они применяются. Это легко объяснимо с точки зрения хорошо известных фактов сложностного подхода алгоритмической теории вероятности, так как вычислимая последовательность имеет конечную сложность, следовательно в ней содержится бесконечно много закономерностей. Более того, чем дольше будет работать датчик, тем худший результат получится, так как, чем более длинные фрагменты псевдослучайной последовательности будут исследованы, тем большее число нетривиальных закономерностей можно будет в ней обнаружить, что плохо согласуется с интуитивным понятием случайной последовательности.
Однако во многих задачах прикладной математики (например, имитационном моделировании) необходимо использование таких "датчиков случайных последовательностей".
Встает вопрос, нельзя ли, пользуясь аппаратом алгоритмической теории вероятностей, построить алгоритм — датчик таблиц псевдослучайных чисел, позволяющий получать сколь угодно длинные конечные таблицы, что достаточно для реального машинного эксперимента, обладающие обычными, в смысле согласования с распределением, свойствами датчика, но свободные от закономерностей, ис-
кажающих результаты исследований. То есть, для дискретных данных ЭВМ достаточно моделировть величины, принимающей значения »'/2т, і = 0,... ,2m с вероятностью 1/2т, где т — разрядность данной машины, Lm(r). Чтобы строить датчики такого вида, достаточно научиться получать последовательности нулей и единиц, соответствующие закону Бернулли с р = 1/2.
. Цель работы. Исследовалась возможность построения алгоритмов, генерирующих конечные двоичные таблицы псевдослучайных чисел.
Научная новизна. Доказано существование вычислимой последовательности двоичных слов, в некотором смысле приближающих случайную УЗ-последовательность из примера, построенного П. Мартин-Лефом.
Построены алгоритмы получения асимптотически сложных вычислимых объектов и сколь угодно длинных слов с заданными свойствами, основанные на поиске в двоичном дереве с пометками.
Практическая значимость. Получены результаты позволяют писать программы для реальных вычислительных машин, вырабатывающие последовательность таблиц, которые с точки зрения выбранного класса статистических приложений могут рассматриваться как модели отрезка бернулпиевской последовательности достаточно хорошего качества.
Алгоритм может иметь также применение для построения конечных последовательностей произвольной длины с заданным набором свойств.
Апробация работы. 1. Седьмая всесоюзная конференция по математической логике. Новосибирск, 1984, секционный доклад.
2. Восьмая всесоюзная конференция по математической логике.
Москва, 1986, секционный доклад.
3. Семинар "Временные поля" кафедры математической ста
тистики и случайных процессов м/м факультета МГУ, 1988, 1989.
-
Межвузовская научная конференция, Математические чтения, Иваново, 1991. Доклад и демонстрация программы.
-
Семинар "Дискретные системы", Институт математики Сибирского отделения РАН, 1992.
Публикации. Все результаты диссертации опубликованы. Ниже приведен список из 9 работ автора по теме диссертации. Из них 4 работы выполнена в соавторстве с И.Г. Журбенко и И.А. Кожевниковой. Основные результаты с доказательствами содержатся в работах [5] и [7-9].
Научная новизна. Основные результаты диссертации являются новыми.
Структура и объем работы. Диссертация состоит из введения, двух глав и приложения. Общий объем работы составляет 91 страницу. Список литературы включает 22 наименования.