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)

ИШ


 

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

82595. Система дошкольного образования 139.5 KB
  Система дошкольного образования Республики Беларусь обеспечивает реализацию конституционного права родителей на образование ребенка при первом же обращении их в органы образования. Каждой семье, каждому ребенку предоставляются возможности в получении качественного дошкольного образования...
82596. Основные течения философии ХIХ в. (позитивизм, марксизм, философия жизни, феноменология) 40.49 KB
  Философия XIX века включает различные философские течения и школы в том числе: романтизм и идеализм на подъеме немецкой философии противоположное движение позитивизм во Франции и Англии материализм Маркса и Фейербаха философия отдельных великих мыслителей Шопенгауэр Ницше Кьеркегор неокантианство...
82597. Щелочные полевые шпаты. Плагиоклазы. Бариевые полевые шпаты 99.5 KB
  Можно с уверенностью сказать что полевые шпаты являются наиболее изученными минералами и все важнейшие этапы развития минералогии и петрографии связаны с их исследованием. Полевые шпаты широко используются в керамической промышленности как наполнители лёгкие абразивы например в производстве...
82598. АНАЛІЗ БАЛАНСУ АПТЕКИ ТА ЙОГО СТРУКТУРИ 64.8 KB
  Самофінансування здійснюється за рахунок прибутку й амортизації. У процесi нагромадження обсяг прибутку піддається зменшенню за рахунок податків і різних платежів із прибутку. В остаточному підсумку залишається нерерозподілений прибуток.
82599. «Великая депрессия»: характер и причины возникновения. Новый курс Рузвельта 43.29 KB
  Важнейшей разделительной вехой в истории США XX в., как и в американской истории в целом, стал 1933 г. Краткое различие между двумя эпохами американской истории, разделенными этой датой, можно охарактеризовать следующим образом.
82600. КОРПОРАТИВНАЯ ЭТИКА. ЮРИДИЧЕСКАЯ И СОЦИАЛЬНАЯ ОТВЕТСТВЕННОСТЬ ФИРМЫ 46.54 KB
  Деловой этикет порядок поведения работников компании включающий систему регламентированных правил поведения в различных деловых ситуациях в том числе при деловой переписке деловом общении приеме на работу обращении к руководству и т.д.
82601. Основы управления персоналом 83.5 KB
  На основе внутренней мотивации люди действуют спокойнее быстрее добросовестнее тратят меньше сил лучше усваивают задания и знания. Добиться желаемого поведения можно двумя путями: подобрать человека с заданным уровнем внутренней мотивации или воспользоваться внешней.
82602. Роль кардинала Ришельє в історії Франції 144.5 KB
  Бажаючи досягти абсолютної влади, Ришельє вступає на шлях придушення будь-якого опору, обмеження привілеїв окремих міст і провінцій і, врешті-решт, знищення противників. Ришельє проводить цю політику від імені Людовика XIII. При цьому сходження Ришельє на політичний олімп було важким і болісним.
82603. Педагогічні умови розвитку ораторських здібностей 108.5 KB
  Основні аспекти розвитку ораторських здібностей молодших школярів. Педагогічні умови розвитку ораторських здібностей. Засоби практичного розвитку ораторських здібностей. Психологопедагогічна робота з розвитку ораторських здібностей...