Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ММПП лекции

.pdf
Скачиваний:
51
Добавлен:
28.03.2015
Размер:
8.95 Mб
Скачать

Системы Массового Обслуживания (СМО)

Системы Массового Обслуживания (СМО)

Системы Массового Обслуживания (СМО)

Системы Массового Обслуживания (СМО)

Системы Массового Обслуживания (СМО)

Системы Массового Обслуживания (СМО)

 

Генераторы случайных чисел

 

Моделирование случайных чисел.

 

Генераторы случайных чисел.

 

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom

number generator, PRNG) — алгоритм, генерирующий

последовательность чисел, элементы которой почти независимы

друг от друга и подчиняются заданному распределению (обычно

равномерному).

 

Генераторы широко используются в самых разных приложениях — от

метода Монте-Карло и имитационного моделирования до криптографии.

При этом от качества используемых ГПСЧ напрямую зависит качество

получаемых результатов.

 

Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью

из ORNL (англ.): «генерация случайных чисел слишком важна, чтобы

оставлять её на волю случая».

 

Генераторы случайных чисел по способу получения чисел делятся на:

Физические (аппаратные);

табличные;

алгоритмические.

Генераторы случайных чисел

Аппаратный генератор случайных чисел — устройство, которое

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

параметров протекающего физического процесса. Работа таких устройств

часто основана на процессах уровня элементарных частиц, таких как

тепловой шум, фотоэлектрический эффект, другие квантовые явления. Эти

процессы, в теории, абсолютно непредсказуемы.

Среди аппаратных ГСЧ наиболее известны LFSR-генераторы (в

переводе: Регистр сдвига с линейной обратной связью), широко

применявшихся в качестве аппаратных ГПСЧ в XX веке.

В настоящее время очень мало известно о современных аппаратных

ГПСЧ, так как большинство из них разработано для военных целей и

держатся в секрете. Почти все существующие коммерческие аппаратные

ГПСЧ запатентованы и также держатся в секрете.

Наиболее простым примером физических ГСЧ могут служить: монета

(«орел» — 1, «решка» — 0); игральные кости; поделенный на секторы с

цифрами барабан со стрелкой; аппаратурный генератор шума (ГШ), в

качестве которого используют шумящее тепловое устройство, например,

транзистор.

 

 

 

 

 

 

Генераторы случайных чисел

 

Табличные ГСЧ

 

 

 

 

 

Табличные ГСЧ в качестве источника случайных чисел используют

специальным образом составленные таблицы, содержащие проверенные

некоррелированные, то есть никак не зависящие друг от друга, цифры.

Ниже приведен небольшой фрагмент такой таблицы. Обходя таблицу слева

направо сверху вниз, можно получать равномерно распределенные от 0 до

1 случайные числа с нужным числом знаков после запятой (в нашем

примере мы используем для каждого числа по три знака). Так как цифры в

таблице не зависят друг от друга, то таблицу можно обходить разными

способами, например, сверху вниз, или справа налево, или, скажем, можно

выбирать цифры, находящиеся на четных позициях.

 

 

 

Случайные цифры

 

 

 

Равномернораспределенные от0 до1 случайные числа

9

2

9

2

0

4

2

6

0.929

9

5

7

3

4

9

0

3

0.204

5

9

1

6

6

5

7

6

0.269

Достоинство данного метода в том, что он дает действительно случайные

числа, так как таблица содержит проверенные некоррелированные цифры.

Генераторы случайных чисел