67260

ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ПРОЦЕДУРЫ ИХ МАШИННОЙ ГЕНЕРАЦИИ

Лекция

Экономическая теория и математическое моделирование

Количество случайных чисел используемых для получения статистически устойчивой оценки характеристики процесса функционирования системы S при реализации моделирующего алгоритма на ЭВМ. Количество случайных чисел колеблется в достаточно широких пределах в зависимости от...

Русский

2014-09-06

127 KB

13 чел.

Лекция № 10

ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ПРОЦЕДУРЫ ИХ МАШИННОЙ ГЕНЕРАЦИИ

При статистическом моделировании систем одним из основных вопросов является учет стохастических воздействий. Количество случайных чисел, используемых для получения статистически устойчивой оценки характеристики процесса функционирования системы S при реализации моделирующего алгоритма на ЭВМ. Количество случайных чисел  колеблется в достаточно широких пределах  в зависимости от:

1 класса объекта моделирования;

2.вида оцениваемых характеристик;

3необходимой точности и достоверности результатов моделирования. Результаты статистического моделирования существенно зависят от качества исходных (базовых) последовательностей случайных чисел.

На практике используются три основных способа генерации случайных чисел:

  •  аппаратный (физический);
  •  табличный (файловый);
  •  алгоритмический (программный).

Аппаратный способ. Генерация случайных чисел вырабатываются специальной электронной приставкой — генератором (датчиком) случайных чисел,— служащей в качестве одного из внешних устройств ЭВМ. Реализация этого способа генерации не требует дополнительных вычислительных операций ЭВМ по выработке случайных чисел, а необходима только операция обращения к внешнему устройству (датчику). В основе лежит физический эффект, лежащего в основе таких генераторов чисел, чаще всего используются шумы в электронных и полупроводниковых приборах, явления распада радиоактивных элементов и т. д.

Достоинства:

Запас чисел не ограничен;

Расходуется   мало   операций;

He занимается место в памяти .

Недостатки:

Требуется периодическая проверка;

Нельзя воспроизводить последовательности;

Используется специальное устройство;

Необходимы меры по обеспечению стабильности.                                                                    

Табличный способ. Случайные числа, представленные в виде таблицы, помещаются в память ЭВМ. Этот способ получения случайных чисел  обычно используют при сравнительно небольшом объеме таблицы и файла чисел.

Достоинства:

Требуется  однократная проверка;

Можно   воспроизводить   последовательности.                        

Недостатки:

Запас чисел ограничен;                              

Много места в ОЗУ;

Необходимо время для обращения к памяти.

Алгоритмический способ. Способ получения последовательности случайных чисел основанный на формировании случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделировании системы на ЭВМ.

Достоинства:

Требуется однократная проверка;

Многократная воспроизводимость последовательности чисел;

Мало места в памяти и нет внешних устройств.

Недостатки:

Запас чисел ограничен периодом последовательности;

Затраты машинного времени.

Программная имитация случайных воздействий сводится к генерированию некоторых стандартных процессов и  их последующего функционального преобразования. В качестве базового может быть принят любой удобный для моделирования конкретной системы S процесс (например, пуассоновский поток при моделировании Q-схемы). При дискретном моделирований базовым процессом является последовательность чисел , которые представляют реализации независимых, равномерно распределенных на интервале (0, 1) случайных величин . В статистических терминах -  повторная выборка из равномерно распределенной на интервале (0, 1) генеральной совокупности значений величины .

Непрерывная случайная величина имеет равномерное распределение в интервале (а, Ь), если ее функции плотности (а) и функция распределения (б) примет вид (Рис. 1):

Рис.1

Числовые характеристики случайной величины , принимающей значения х— это математическое ожидание, дисперсия и среднее квадратическое отклонение соответственно:

При моделировании систем на с случайными числами интервала (0, 1), где границы интервала соответственно а=0 и б = 1. Частным случаем равномерного распределения является функция плотности и функция распределения, соответственно имеющие вид:

Такое распределение имеет математическое ожидание М [] = 1/2

и дисперсию D[] = 1/12.

Это распределение требуется получить на ЭВМ. Но получить его на цифровой ЭВМ невозможно, так как машина оперирует с п-разрядными числами. Поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала  (0,   1)  используют дискретную последовательность 2" случайных чисел того же интервала. Закон распределения такой дискретной последовательности называют квазиравномерным  распределением.

Случайная величина , имеющая квазиравномерное распределение в интервале (0, 1), принимает значения  с вероятностями , .

Математическое ожидание и дисперсия квазиравномерной случайной величины соответственно имеют вид


На ЭВМ невозможно получить идеальную последовательность случайных чисел хотя бы потому, что на ней можно оперировать  только с конечным множеством чисел. Кроме того, для получения значений х случайной величины используются формулы (алгоритмы). Поэтому такие последовательности, являющиеся по своей сути детерминированными, называются псевдослучайными.

Требования к генератору случайных чисел.

Требованиями, к идеальному генератору случайных чисел формулируются следующим образом. Полученные с помощью идеального генератора псевдослучайные последовательности чисел должны:

  •  состоять из квазиравномерно распределенных чисел;
  •  содержать статистически независимые числа;
  •  быть воспроизводимыми;
  •  иметь неповторяющиеся числа;
  •  получаться с минимальными затратами машинного времени;
  •  занимать минимальный объем машинной памяти.

В практике моделирования применяются генерации последовательностей псевдослучайных чисел находят алгоритмы вида (1)

                                                      (1)

Данные алгоритмы представляют рекуррентные соотношения первого порядка, для которых начальное число х0 и постоянные параметры  уже заданы.

Метод серединных квадратов

Пусть имеется 2n-разрядное число, меньшее 1:

 1.Возведем его в квадрат:

2. Отберем средние 2n разрядов  которые будут являться очередным числом псевдослучайной последовательности.

Пример, если начальное число х0=0,2152, то (х0)2=0,04631104,

т. е. Xj=0,6311, затем (х1)2=0,39828721, т. е. х2=0,8287, и т. д.

Недостаток метода:

Наличие корреляции между числами последовательности, в некоторых случаях может отсутствовать.

Конгруэнтные процедуры генерации.

Конгруэнтные процедуры представляют собой арифметические операции, в основе которых лежит фундаментальное понятие конгруэнтности.

Два целых числа и конгруэнтны или сравнимы по модулю m,  m — целое число, тогда и только тогда, когда существует такое целое число k, что  т. е. разность  делится на m и  числа и  дают одинаковые остатки от деления на абсолютную величину числа m.

Например,

Конгруэнтные процедуры являются чисто детерминированными, так как описываются в виде рекуррентного соотношения (1), и имеют вид.

где   — неотрицательные целые числа.

Раскроем рекуррентное соотношение (2):


Если заданы начальные числа (3) последовательность целых чисел {Xi}, составленную из остатков от деления на М членов

последовательности

 

Таким образом, для любого i>=1 справедливо неравенство Xt<M, получится последовательность рациональных чисел из единичного интервала (0,1)  

Мультипликативный метод.

Задается последовательность неотрицательных целых чисел {Xt}, не превосходящих М, рассчитанных по формуле

т. е. это частный случай соотношения (2) при =0.

В силу детерминированности метода получаются воспроизводимые последовательности..

В машинной реализации наиболее удобна версия M=pg, где р — число цифр в системе счисления в ЭВМ; g -— число битов в машинном слове. Тогда вычисление остатка от деления на М сводится к выделению g младших разрядов делимого. Преобразование целого числа Xt в рациональную дробь из интервала  осуществляется подстановкой слева от Xi двоичной или десятичной запятой.

Алгоритм построения последовательности для двоичной машины M=pg сводится к выполнению таких операций:

1. Выбрать в качестве X0 произвольное нечетное число.

2. Вычислить коэффициент  где t — любое целое положительное число.

3. Найти произведение , содержащее не более 2g значащих
разрядов.

4. Взять g младших разрядов в качестве первого члена последовательности X1 а остальные отбросить.

5. Определить дробь  из интервала (0, 1).

6. Присвоить .

7. Вернуться к п. 3.

Смешанный метод.

Позволяет вычислить последовательность неотрицательных целых чисел {Xi}, не превосходящих М, по формуле

Отличием от мультипликативного метода является .

С вычислительной точки зрения смешанный метод генерации сложнее мультипликативного на одну операцию сложения. При этом возможность выбора дополнительного параметра позволяет уменьшить возможную корреляцию получаемых чисел.


 

А также другие работы, которые могут Вас заинтересовать

29326. Технологические преимущества и недостатки сканеров различных типов 44 KB
  Высокая разрешающая способность которая может быть осуществлена на этих сканерах. Необходимость использования выносных барабанов и их прицензионности сильно увеличивает стоимость сканера. Это главный недостаток сканера. Если разрешение сканера RCK равно 5 тысяч ppi а число элементов в линейке N равно 8 тысяч p то: Планшетные сканеры требуют правильного размещения информации на оригиналодержателе.
29327. Технологическая настройка сканера по оригиналу процесса 59.5 KB
  Если необходимо сканировать штриховые изображения то в этом случае RC выбирают по следующим законам. Это значит что при такой частоте изображения функции передачи модуляции объекта приходят практически к нулевому значению. Это приводит к более грубому квантованию оригинала что может стать заметным в процессе дальнейшей обработки изображения то есть возможно проявление эффекта пастеризации появление следов квантования. Для этого предварительно строят гистограммы изображения по ним находят черную и белую точки и к этим точкам привязывают...
29328. Классификация по организации светового пучка 68 KB
  В принципе световым пучком можно управлять путем импульсного управления попиксельная запись и возможно осуществлять запись методом строчной записи когда не каждый пиксель пишется отдельно. Поскольку в этих системах осуществляется сканирование то соответственно в этих системах записи формируются строки с помощью записывающего пятна следовательно используется кадровая развертка. Чтобы обеспечить сплошность записи строки должны частично перекрываться диметр пятна должен быть больше периметра записи на 20 то есть диметр пятна...
29329. Лекция 11 Формирование углов поворота растра при электронном растрировании В качестве стандартных угло 61.5 KB
  Проблем совмещения пиксельной и растровой сетки нет только для желтой краски потому что угол поворота растра для нее равен 0. Что бы получить рациональный угол линия растровой решетки должна проходить через вершины ячеек пиксельной сетки. Использование рациональных углов растрирования а также идея необходимости совмещения узлов растровой и пиксельной сетки приводит к тому что растровая структура отличается от традиционной ранее применяемой по углам поворота и линиатуре. Первая идея заключается в том что чем больше разность между...
29330. Химико-фотографическая обработка 56 KB
  Для современных ФВУ используются пленки с контрастностью не менее 6. Технологическая настройка ФВУ Технологическая настройка ФВУ в себя включает: настройку фокусировки экспонирующей головки подбор оптимальной экспозиции для обеспечения необходимой оптической плотности фона процесс линеаризации ФВУ Необходимость фокусировки экспонирующей головки может возникнуть в связи со сменой сорта пленки если при этом меняется толщина этой пленки. При этой операции обеспечиваются условия экспонирования при которых будет обеспечена необходимая...
29331. Формула Юлла-Нильсена 38.5 KB
  Чем больше линиатура растра тем ближе расположены точки тем хуже функция размытия. ∆S получила название растискивания точки. На самом деле в этом значении растискивания точки значительную долю вносит рассеивание света в процессе визуального рассмотрения оттиска. Конечно в это ∆S удобно внести все искажения которые возникают не только в процессе визуального восприятия рассеивания света а также реальное растискивание в процессе печати и изменение размера растровой точки в копировальноформном процессе.
29332. Технологическая настройка системы обработки под реальный технологический процесс 54 KB
  Имеется специальный тестобъект который по сути дела представляет собой шкалу цветового охвата которая доступна в виртуальном виде то есть в виде информации записанной на магнитный носитель. Однако в некоторых случаях получение такой информации не оправдано изза разовых тиражей или если часть информации не доступна. Второй метод основан на использовании некоторой стандартной информации которая включается в состав программного обеспечения обработки изобразительной информации фирмой изготовителем. Эта информации по сути своей позволяет...
29333. Цветовые системы, используемые в обрабатывающей станции 58 KB
  Недостатки такого выражения: неоднозначность системы координат RGB и аппаратная зависимость неясное представление о цвете на основе соотношения этих сигналов Воздействие на один из каналов приводит к изменению цвета которое трудно предсказать. Если хотим получить насыщенные цвета должны работать в пределах 50 светлоты По координате а цвет меняется от Зеленого до Пурпурного. У нас имеются две группы основных цветов: цвета аддитивного синтеза однозональные цвета: Красный Зеленый Синий двузональные цвета субтрактивного синтеза:...
29334. Калибровка монитора без использования специальных аппаратных средств (по разработкам фирмы Gretag) 56 KB
  Однако для более точной коррекции цвета на экране монитора и корректного представления его в колориметрических координатах необходимо провести стадию технологической калибровки монитора. Это приводит к тому что если не принять специальных мер коррекции голубая краска выделится на синефильтровой и зеленофильтровой фотоформе будет запечатываться соответственно желтой и пурпурной краской. По сути дела при правильной настройки системы и правильной работе в соответствующих цветовых пространствах задача базовой коррекции решается автоматически...