40826

Псевдослучайные последовательности и процедуры их машинной генерации

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Способы генерации случайных чисел Примеры статистического использования Пример 4. Структурная схема системы SD Система SD функционирует следующим образом: получается пара независимых случайных чисел интервала 0 1 определяется координата точки xi xi1 показанной на рис. Схема моделирующего алгоритма системы SP В данном моделирующем алгоритме после ввода исходных данных и реализации операторов цикла происходит обращение к генератору случайных чисел т. Отметим что во всех рассмотренных примерах не требуется запоминания всего множества...

Русский

2013-10-22

239.5 KB

18 чел.

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

Примеры статистического использования

Пример 4.2. Необходимо методом статистического моделирования найти оценку площади фигуры (рис. 4.3), ограниченной осями координат, ординатой α = 1 и кривой у = f(α); при этом для определённости предполагается, что 0 ≤ f(α) ≤ 1 для всех α, 0 ≤ α ≤ 1.

Рис. 4.3. Геометрическая интерпретация оценки площади фигуры

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

.

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

Вариант структурной схемы такой системы SD показан на рис.4.4, где элементы выполняют следующие функции:

вычисление В1: hi = f(xi);        

анализ А:   

суммирование С: h =;

вычисление В2: S = h/N. 

Рис. 4.4. Структурная схема системы SD

Система SD функционирует следующим образом: получается пара независимых случайных чисел интервала (0, 1), определяется координата точки (xi, xi+1), показанной на рис.4.3, вычисляется координата xi+1 = f(xi) и проводится сравнение величин xi и xi+1; причём если точка (xi, xi+1) попала в площадь фигуры (в том числе и на кривую f(x)), то исход испытания считается положительным, hi = 1, и в итоге можно получить статистическую оценку площади фигуры  по заданному числу реализаций N.

Логическая схема моделирующего алгоритма вероятностной  системы SD представлена на рис. 4.5. Здесь Y  y = f() – заданная функция (табличная кривая); N – заданное число реализаций; Ii – номер текущей реализации; XIxi, XI1xi+1, HIhi, Ss, SHh = – суммирующая ячейка.

Таким образом, построение некоторой стохастической системы SD позволяет методом статистического моделирования получить оценки для детерминированной задачи.

Пример 4.3. Необходимо методом статистического моделирования решить следующую задачу. Проводится s = 10 независимых выстрелов по мишени, причём вероятность попадания при одном выстреле задана и
равна
p. Требуется оценить вероятность того, что число попадания в мишень будет чётным, т.е. 0, 2, 4, 6, 8, 10.

Данная задача является вероятностной, причём существует её аналитическое решение:

.

Рис. 4.5. Схема моделирующего алгоритма системы SD

В качестве объекта статистического моделирования можно рассмотреть следующую вероятностную систему SP, структура которой представлена на рис. 4.6, где элементы выполняют такие функции:

анализ А1:

суммирование С:

анализ А2:

Рис. 4.6. Структурная схема системы SP

Выходным воздействием в данной системе SP является событие чётного числа попаданий в мишень в серии из десяти выстрелов. В качестве оценки выходной характеристики необходимо при числе испытаний (серий выстрелов), равном N, найти вероятность чётного числа попаданий:

.

Логическая схема алгоритма статистического моделирования для оценки искомой характеристики такой системы P(y) приведена на рис. 4.7. Здесь Pp – заданная вероятность  попадания в мишень при одном выстреле;  заданное число реализаций; XIxi, HJhj=, PYP(y), SY – суммирующая ячейка. 

Рис. 4.7. Схема моделирующего алгоритма системы SP

В данном моделирующем алгоритме после ввода исходных данных и реализации операторов цикла происходит обращение к генератору случайных чисел, т.е. получаются значения  случайной величины, которые равномерно распределены в интервале (0, 1). Вероятность попадания случайной величины в интервал , где , равна длине этого отрезка, т.е. . Поэтому при каждом моделировании выстрела полученное случайное число  сравнивается с заданной вероятностью  и при  регистрируется «попадание в мишень», а в противном случае – «промах». Далее моделируются серии из десяти испытаний каждая, подсчитывается чётное число «попаданий» в каждой серии и находится статистическая оценка искомой характеристики .

Таким образом, подход при использовании статистического моделирования независимого от природы объекта исследования (будет ли он детерминированным или стохастическим) является общим, причём при статистическом моделировании детерминированных систем (система SD в примере 4.2) необходимо предварительно построить стохастическую систему, выходные характеристики которой позволяют оценить искомые.

Отметим, что во всех рассмотренных примерах не требуется запоминания всего множества генерируемых случайных чисел, не используемых при статистическом моделировании системы S. Запоминается только накопленная сумма исходов и общее число реализаций.

4.2. Псевдослучайные последовательности и процедуры их машинной генерации

Способы генерации случайных чисел

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

На практике используется три основных способа генерации случайных чисел: аппаратный (физический), табличный (файловый) и алгоритмический (программный).

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

Структурная схема аппаратного генератора случайных чисел приведена на рис. 4.8, а.

 а     б

Рис. 4.8. Аппаратный способ получения случайных чисел

Здесь ИШ – источник шума; КС – ключевая схема; ФИ – формирователь импульсов; ПС – пересчетная схема. При усилении шумов на выходе ИШ получается напряжение uш(t), которое является случайным процессом, показанным на временной диаграмме (рис. 4.8, б). Причем отрезок шумовой реализации uк(t), сформированный на интервале времени (0, Т) с помощью КС, содержит случайное число выбросов. Сравнение напряжения uк(t) с пороговым Uп позволяет сформировать на выходе ФИ серию импульсов uф(t). Тогда на выходе ПС может быть получена последовательность случайных чисел xi(t). Аппаратный способ получения случайных чисел не позволяет гарантировать качество последовательности непосредственно во время моделирования системы S на ЭВМ, а также повторно получать при моделировании одинаковые последовательности чисел.

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

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

Достоинства и недостатки трех перечисленных способов получения случайных чисел для сравнения представлены в табл. 4.1. Из этой таблицы видно, что алгоритмический способ получения случайных чисел наиболее рационален на практике при моделировании систем на универсальных ЭВМ.

Таблица 4.1

Способ

Достоинства

Недостатки

Аппарат-ный

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

Расходуется мало операций вычислительной машины.

Не занимает место в памяти машины.

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

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

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

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

Таблич-ный

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

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

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

Занимает много места в оперативной памяти или необходимо время на обращение к внешней памяти.

Алгорит-мический

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

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

Занимает мало места в памяти машины.

Не используются внешние устройства.

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

Существенные затраты машинного времени.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. М. : Высш. шк., 2001. 343 с.

2. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. 2-е изд. М.: Высшая школа, 1998. 319 с.

3. Тарасик В.П. Математическое моделирование технических систем: учеб. для вузов / В.П. Тарасик. М.: Наука, 1997. 600 с.

4. Введение в математическое моделирование: учеб. пособие для вузов/ под ред. П.В.Тарасова. М.: Интермет Инжиниринг, 2000. 200 с.

5. Ивченко Г.И. Математическая статистика: учебное пособие для втузов / Г.И. Ивченко, Ю.И. Медведев. М.: Высш. шк., 1984. 248 с.

6. Альянах И.Н. Моделирование вычислительных систем / И.Н. Альянах. Л.: Машиностроение, 1988. 233 с.

7. Шеннон Р. Имитационное моделирование систем – искусство и наука / Р. Шеннон. М.: Мир, 1978. 308 с.

5

хi+1

хi

у=f(α)

  1

hi

0

α

у

хi, хi+1

1

В1

C

В2

А

хi

хi+1

hi'

hi=1

h'

S

Внешняя среда Е

Система SD

yj=1

xi

hi=1

hj

Внешняя среда Е

Система SP

A1

C

A2

yj=0

t

ti ti+l

t

хi(T)

t

иф(t)

ПС

иф(t)

Un

ФИ

0

t

ик(t)

ик(t)

ис(t)

t

ис(t)

КС

иш(t)

ИШ


 

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

61397. Буквы й, Й. Чтение слогов, слов. Слова, которые отвечают на вопросы: какой? какая? какое? какие? 27.5 KB
  Цели: формируем умение анализировать текст; формируем умение классифицировать слова по вопросам; формируем умение различать однозначные и многозначные слова. А что общего вы услышали в словах май пой жуй лей трамвай...
61398. Бумажные фантазии 18.98 KB
  Ознакомить учащихся с техникой выполнения квиллинга. История квиллинга В отличие от оригами родиной которого является Япония искусство бумагокручения возникло в Европе в конце 14 начале 15 века.
61400. ЧЕСТНОЕ ПИОНЕРСКОЕ, ИЛИ УРОКИ ИСТОРИИ (Очерки истории детско-юношеского движения в России) 201.16 KB
  Оборотной стороной богатства процветающего и сверхжадного российского капитала были 12 16-часовой рабочий день не только мужчин но и женщин и детей; штрафы опустошавшие на треть и без того тощий рабочий кошелек; массовый травматизм; тяжелейшие жилищнобытовые условия рабочего люда. Ленин около четырех пятых детей и подростков в России лишено народного образования. Уже в первой Программе партии принятой в 1903 году II съездом РСДРП были изложены основные социально-экономические требования большевиков в области охраны прав детей:...
61402. Деловые игры на уроках экономики 18.12 KB
  Итак каждая группа на рынке самолетов это отдельное предприятие по их производству. Ваша задача: произвести из имеющихся у вас ресурсов как можно больше самолетов. Требования к качеству самолетов...