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)

ИШ


 

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

41860. Окислительно-восстановительное титрование. Иодометрическое определение пероксида водорода. Иодометрическое определение растворённого в воде кислорода 65.63 KB
  Сформировать умения по стандартизации раствора тиосульфата натрия; выполнению иодометрического определения пероксида водорода; иодометрического определения растворенного в воде кислорода. При этом к определяемому веществу добавляют взятое в заведомом избытке точное количество стандартного раствора иода. Какую среду сильнокислую слабокислую должен иметь раствор после добавления серной кислоты Почему при добавлении крахмала амилозы к раствору иода появляется синее окрашивание Какие ещё вещества могут взаимодействовать с иодом...
41861. Определение удельной теплоты плавления олова 286.55 KB
  Температура при которой вещество плавится называется температурой плавления вещества. Температура плавления для данного вещества при одинаковых условиях одинакова. Однако это не значит что в процессе плавления к телу не надо подводить энергию.
41862. Диаграмма Парето 48.04 KB
  Например если на складе находится большое число деталей проводить контроль всех деталей без всякого различия неэффективно. Но если разделить детали на группы по их стоимости то на долю группы наиболее дорогих деталей группа А составляющих 2030 от общего числа деталей придётся 7080 от общей стоимости всех деталей. На долю группы самых дешёвых деталей группа С составляющей 4050 от всего количества деталей придётся всего 510 от общей стоимости. Контроль деталей на складе будет эффективным если контроль деталей группы А будет...
41863. Редактирование рабочей книги. Построение диаграмм 976.65 KB
  Изучение способов работы с данными в ячейке. Изучение возможностей автозаполнения. Построение диаграмм. Создание и сохранение таблицы (рабочей книги). Форматирование содержимого ячеек, выбор диапазона ячеек и работа с ними, редактирование содержимого ячеек.
41864. Функционально-стоимостной анализ в конструкторской подготовке производства 296 KB
  Функционально-стоимостной анализ — метод, позволяющий отбирать наилучшие технические решения при создании и освоении новой техники (технологии), увязывать в единый комплекс вопросы обеспечения функциональной полезности и качества новой техники (технологии)
41865. Гистограмма. Характерные типы гистограмм 82 KB
  Результаты измерений вводим в электронную таблицу. В ячейку А1 вводим заголовок работы. Начиная с ячейки А3 вводим в столбец порядковые номера измерений с 1 по 100 например при помощи команды ПравкаЗаполнитьПрогрессия . В ячейки В3:В102 вводим значения коэффициента деформации из табл.
41866. Графики. Построение и виды графиков. 53.14 KB
  На третьем шаге вводим заголовки диаграммы и осей основные линии сетки по осям удаляем легенду. Характер изменения выручки а также прогноз даёт линия тренда построить которую можно открыв контекстное меню на ломаной линии и выбрав команду Добавить линию тренда. В открывшемся диалоговом окне на вкладке Тип показаны возможные типы линии тренда. Чтобы выбрать тип линии наилучшим образом аппроксимирующий данные можно поступить следующим образом: поместить на диаграмме линии тренда всех приемлемых типов т.
41867. Построение фигур и линий в CorelDRAW. Рабочая среда и интерфейс пользователя 549.49 KB
  Модель кривой В основе принятой в CorelDRW модели линий лежат два понятия: узел и сегмент. По характеру предшествующих сегментов выделяют три типа узлов: начальный узел незамкнутой кривой прямолинейный и криволинейный. В средней части строки состояния для кривой выводится обозначение класса объекта Кривая на слое 1 а также количество узлов этой кривой. Вместо этого задается расположение узлов будущей кривой и появляется возможность уже в процессе построения воздействовать на положение направляющих точек в каждом из них.
41868. Табличный процессор Excel. Ознакомление. Форматирование таблиц в Excel 202.96 KB
  Название ошибки Значение ошибки ДЕЛ 0 Деление на нуль Н Д Неопределенные данные ИМЯ Программа не может распознать имя использованное в формуле ПУСТО Задано пересечение областей не имеющих общих ячеек ЧИСЛО Возникли проблемы с числом ССЫЛКА Формула неправильно ссылается на ячейку например если ячейки были удалены ЗНАЧ Аргумент или операнд имеет недопустимый тип ВЫПОЛНЕНИЕ РАБОТЫ: Задание Создать таблицу в соответствии с предложенным вариантом по образцу. Создайте таблицу в соответствии с вашим вариантом по образцу Для...