Лекционный курс от Русакова (1087061), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

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

Случайные числа, представленные в виде таблицы,помещаются в память ЭВМ. Этот способ получения случайных чиселобычно используют при сравнительно небольшом объеме таблицы и файлачисел.Достоинства:Требуется однократная проверка;Можно воспроизводить последовательности.Недостатки:Запас чисел ограничен;Много места в ОЗУ;Необходимо время для обращения к памяти.Алгоритмический способ. Способ получения последовательностислучайных чисел основанный на формировании случайных чисел в ЭВМ спомощью специальных алгоритмов и реализующих их программ. Каждоеслучайное число вычисляется с помощью соответствующей программыпо мере возникновения потребностей при моделировании системы наЭВМ.Достоинства:Требуется однократная проверка;Многократная воспроизводимость последовательности чисел;Мало места в памяти и нет внешних устройств.Недостатки:Запас чисел ограничен периодом последовательности;Затраты машинного времени.Программная имитация случайных воздействий сводится кгенерированию некоторых стандартных процессов и их последующегофункционального преобразования.

В качестве базового может бытьпринят любой удобный для моделирования конкретной системы S процесс (например, пуассоновский поток при моделировании Q-схемы). Придискретноммоделированийбазовымпроцессомявляетсяпоследовательность чисел {xi }  x0 , x1 , x3 ,..., x N , которые представляютреализации независимых, равномерно распределенных на интервале (0, 1)случайных величин { i }  1 ,  2 ,  3 ,...,  N . В статистических терминах повторная выборка из равномерно распределенной на интервале (0, 1)генеральной совокупности значений величины .Непрерывная случайная величина  имеет равномерное распределение в интервале (а, Ь), если ее функции плотности (а) и функцияраспределения (б) примет вид (Рис.

1):Рис.1Числовые характеристики случайной величины , принимающейзначения х— это математическое ожидание, дисперсия и среднееквадратическое отклонение соответственно:При моделировании систем на с случайными числами интервала (0,1), где границы интервала соответственно а=0 и б = 1. Частным случаемравномерного распределения является функция плотности и функцияраспределения, соответственно имеющие вид:Такое распределение имеет математическое ожидание М [] = 1/2и дисперсию D[] = 1/12.Это распределение требуется получить на ЭВМ.

Но получить его нацифровой ЭВМ невозможно, так как машина оперирует с п-разряднымичислами. Поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0, 1) используют дискретнуюпоследовательность 2" случайных чисел того же интервала. Закон распределениятакойдискретнойпоследовательностиназываютквазиравномерным распределением.Случайная величина , имеющая квазиравномерное распределение вn1интервале (0, 1), принимает значения xi  i /(2  1) с вероятностями pi  ,2ni  0,2  1 .nМатематическое ожидание и дисперсия квазиравномерной случайнойвеличины соответственно имеют видНа ЭВМ невозможно получить идеальную последовательностьслучайных чисел хотя бы потому, что на ней можно оперировать толькос конечным множеством чисел.

Кроме того, для получения значений хслучайной величины  используются формулы (алгоритмы). Поэтомутакиепоследовательности,являющиесяпосвоейсутидетерминированными, называются псевдослучайными.Требования к генератору случайных чисел.Требованиями, к идеальному генератору случайных чиселформулируются следующим образом. Полученные с помощьюидеального генератора псевдослучайные последовательности чиселдолжны: состоять из квазиравномерно распределенных чисел; содержать статистически независимые числа; быть воспроизводимыми; иметь неповторяющиеся числа; получаться с минимальными затратами машинного времени; занимать минимальный объем машинной памяти.Впрактикемоделированияприменяютсягенерациипоследовательностей псевдослучайных чисел находят алгоритмы вида (1)(1)Данныеалгоритмыпредставляют рекуррентныесоотношения первого порядка, для которых начальное число х0 ипостоянные параметры уже заданы.Метод серединных квадратовПусть имеется 2n-разрядное число, меньшее 1:xi  a1 , a 2 ,...., a 2 n1.Возведем его в квадрат:xi2  0, b1 , b2 ,..., b4 n2.

Отберем средние 2n разрядов xi 1  0, bn 1 , bn  2 ,..., b3n которые будутявляться очередным числом псевдослучайной последовательности.Пример, если начальное число х0=0,2152, то (х0)2=0,04631104,т. е. Xj=0,6311, затем (х1)2=0,39828721, т. е. х2=0,8287, и т. д.Недостаток метода:Наличие корреляции между числами последовательности,некоторых случаях может отсутствовать.вКонгруэнтные процедуры генерации.Конгруэнтные процедуры представляют собой арифметическиеоперации, в основе которых лежит фундаментальное понятиеконгруэнтности.Два целых числа  и  конгруэнтны или сравнимы по модулю m, m —целое число, тогда и только тогда, когда существует такое целое число k, что    km т. е.

разность    делится на m и числа  и  дают одинаковыеостатки от деления на абсолютную величину числа m.Например,1984  4(mod10)1984  4  1984  1019844ост()  ост( )  41010Конгруэнтные процедуры являются чисто детерминированными, таккак описываются в виде рекуррентного соотношения (1), и имеют вид.(2)где X i ,  ,  , M — неотрицательные целые числа.Раскроем рекуррентное соотношение (2):(3)Если заданы начальные числа X 0 ,  ,  , M (3) последовательность целыхчисел {Xi}, составленную из остатков от деления на М членовпоследовательности i X 0   (i  1)}(  1)Таким образом, для любого i>=1 справедливо неравенство Xt<M, получитсяпоследовательность рациональных чисел из единичного интервала (0,1){x i }  {xi / M }Мультипликативный метод.Задается последовательность неотрицательных целых чисел {Xt}, непревосходящих М, рассчитанных по формуле(4)т. е.

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

Преобразование целого числа Xt в рациональную дробь из интервалаxi  (0,1) осуществляется подстановкой слева от Xi двоичной или десятичнойзапятой.Алгоритм построения последовательности для двоичной машины M=pgсводится к выполнению таких операций:1. Выбрать в качестве X0 произвольное нечетное число.2.

Вычислить коэффициент   8t  3 где t — любое целое положительноечисло.3. Найти произведение X 0 , содержащее не более 2g значащихразрядов.4. Взять g младших разрядов в качестве первого члена последовательности X1а остальные отбросить.5. Определить дробь x1 X1из интервала (0, 1).2g6. Присвоить X 0  X 1 .7. Вернуться к п. 3.Смешанный метод.Позволяет вычислить последовательность неотрицательных целых чисел{Xi}, не превосходящих М, по формулеОтличием от мультипликативного метода является   0 .С вычислительной точки зрения смешанный метод генерации сложнеемультипликативного на одну операцию сложения. При этом возможностьвыбора дополнительного параметра позволяет уменьшить возможнуюкорреляцию получаемых чисел.Моделирование случайных воздействийВ моделировании систем методами имитационного моделирования,существенное внимание уделяется учету случайных факторов и воздействий насистему.

Характеристики

Список файлов лекций