ММПП лекции
.pdfСистемы Массового Обслуживания (СМО) |
|
Системы Массового Обслуживания (СМО) |
|
Системы Массового Обслуживания (СМО) |
|
Системы Массового Обслуживания (СМО) |
|
Системы Массового Обслуживания (СМО) |
|
Системы Массового Обслуживания (СМО) |
|
|
Генераторы случайных чисел |
|
Моделирование случайных чисел. |
|
Генераторы случайных чисел. |
|
Генератор псевдослучайных чисел (ГПСЧ, англ. 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 |
Достоинство данного метода в том, что он дает действительно случайные |
||||||||
числа, так как таблица содержит проверенные некоррелированные цифры. |
Генераторы случайных чисел |
|