Алгоритмический способ генерации случайных чисел

Алгоритмический способ.

Способ основан на формировании случайных чисел с помощью специальных алгоритмов.

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

Маша ела кашу.

Лабораторная работа №2.

Сравнить эти два способа. Причем сравниваем их по критерию случайности. Т.е. придумать свой критерий случайности (можно конечно и в книжке посмотреть, но лучше самому)..

количественная оценка..

К пятнице:

1. Алгоритм Марселя Зейнмана (?). (целочисленная арифметика) (3-я группа)

2. Функция, увеличивающая период последовательности стандартного генератора rand.

3. Способ Ленмара (?)

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

Сферы применения.

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

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

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

Если n пробегает значения натурального ряда чисел, то поведение y_n выглядит весьма хаотично. Физик Якобит доказал, что при рациональном коэффициенте a множество y конечно, а при иррациональном – бесконечно и всюду плотно в интервале [0, 1]. Для многочленов больших степеней такую задачу решил Герман Вей, т.е. он предложил критерий равномерности распределения любой функции от натурального ряда чисел. Называется это эргодичностью и заключается в том, что среднее по реализациям псевдослучайных чисел равно среднему по всему их множеству с вероятностью 1. Эти результаты далеки от практики, поэтому она используется только для действительных чисел, что затрудняет практическую её реализацию. Попытки замены настоящего иррационального числа его приближением на компьютере привели к тому, что полученные последовательности оканчиваются циклом с коротким периодом.

1. 1946 год, Фон Нейман.

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

1. Лимер
   
   Для подбора коэффициентов k, c, m потрачены десятки лет. Подбор почти иррациональных k ничего не дает. Установили, что при c = 0 и  наибольший период достигается при нечетном начальном числе и при k = 3 + 8i, k = 5 + 8i.
2. Форсайд

В 1977 году показал, что тройки последовательности чисел лежат на 15 параллельных плоскостях.

От отчаяния используют 2 и даже 3 разных генератора, смешивая их значения. Если бы разные генераторы были независимыми, то сумма их последовательностей обладала дисперсией, равной сумме дисперсией. Иначе случайность рядов возрастет при суммировании. Сейчас в системах программирования обычно используют конгруэнтные генераторы по алгоритму, предложенному национальным бюро стандартов США, который имеет длину .

Генерация случайных чисел по алгоритму Зеймана.

{1, 1, 2, 3, 5, 8, 13, 21, …}

mod 10

{1, 1, 2, 3, 5, 8, 3, 1, …}

Переименовываем с помощью какого-либо ГСЧ; пусть всё так и осталось:

{1, 1, 2, 3, 5, 8, 3, 1, …}

С начала CF = 1.

Пример:

randomize(231)

x = rnd();

randomize(231)

y = rnd();

// x  != y

x = rnd(-231)

y = rnd(-231)

// x = y

(Серега рассказывает про то, как можно пытаться смешивать генерацию случайных чисел)

Лабораторная работа №3.

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

Ф-ция распределения, плотность распределения, мат. ожидание, дисперсия, …

Равномерное распределение изучают все.

По списку с периодом 4 изучают

1.

2. экспоненциальное

3. нормальное распределение (Гауссовское)

4. k – распределение Эрланга

Построить графики:

1. Теоретического распределения (функция и плотность распределения)
2. Экспериментального по «своему» закону распределения (ф-ция и плотность)

Программа генерации случайных чисел на Фортране для машин EС (~IBM 360)

SUBROUTINE RANDUM( IX, IY, RN)     // была придумана для 32 разрядной машины

    IY = IX * 1220703125

    IF (IY) 3,4,4       // if (IY < 0) then

3   IY = IY + 2147483647 + 1

4   RN = IY

    RN = RN * 0.4656613E-9

    IX = IY

    RETURN

END

// обращение к данной процедуре

CALL RANDUM(IX, IY, YFL)

IX – число, которое при первом обращении должно содержать нечетное целое число, состоящее менее чем из 9 цифр

IY - полученное случайное число, используемое при последующих обращениях к программе

YFL - полученное равномерно распределенное в интервале [0, 1] случайное число

Для имитации равномерного распределения в интервале от [a, b] используется обратное преобразование функции плотности вероятности:

где R – равномерно распределенное псевдослучайное число на [0, 1].

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

     (1)

Метод основан на утверждении, что случайная величина x, принимающая значения, равные корню уравнения (1) имеет плотность распределения f(x). R - равномерная случайная величина от 0 до 1.

Значение случайной величины распределенной по показательному закону исходя из (1) может быть вычислено следующим образом:

Распределение Пуассона.

Распределение Пуассона относится к числу дискретных, т.е. таких при которых переменная может принимать лишь целочисленные значения, включая норму с мат. ожиданием и дисперсией равной l > 0.

Для генерации Пуассоновских переменных можно использовать метод точек, в основе которого лежит генерируемое случайное значение R_i , равномерно распределенное на [0, 1], до тех пор, пока не станет справедливым

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

Распределение Эрланга.

Распределение Эрланга характеризуется двумя параметрами: l и k. Поэтому при вычислении случайной величины в соответствии с данным законом воспользуемся тем, что поток Эрланга может быть получен прореживанием потока Пуассона k раз. Поэтому достаточно получить k значений случайной величины распределенной по показательному закону и усреднить их.

Нормальное (Гауссово) распределение.

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

Случайная величина X имеющая нормальное распределение с математическим ожиданием M_X и среднеквадратичным отклонением s_X может быть получена по следующей формуле:

Для сокращения вычислений по нормальному закону распределения на практике часто принимают N = 12. Что в дает довольно точные результаты.

Процедура генерирования псевдослучайных чисел (равномерный и нормальный законы распределения):

var n, i:integer;

    x,R:double;

     Const m34: double = 28395423107.0;

         m35: double = 34359738368.0;

         m36: double = 68719476736.0;

         m37: double = 137438953472.0;

function Rand(n:integer):double;

var S, W: double;

    i: integer;

begin

    if n = 0 then

    begin

      x := m34; Rand := 0; exit;

    end;

    S := -2.5;

    for i := 1 to 5 do

    begin

      x := 5.0 * x;

      if x > m37 then x := x - m37;

      if x > m36 then x := x - m36;

      if x > m35 then x := x - m35;

      w := x / m35;

      if n = 1 then

      begin

            Rand := W; exit

      end;

      S := S + W;

    end;

    S := S * 1.54919;

    Rand := ( sqr(S) - 3.0 ) * S * 0.01 + S;

end;

begin

    R := Rand(0);

    for i := 1 to 200 do

      writeln( Rand(2):18:10)

end.

При n = 0 происходит параметрическая настройка или т.н. «установка».

При n = 1 будем получать равномерно распределенную случайную величину.

При n = 2 будет гауссово (нормальное) распределение.

["всем, пожалуйста, поиграться с этим алгоритмом и построить график" (с) by Рудаков]

Методика построения программной модели ВС.

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

Обобщенная структурная схема ВС.

ИИ – источники информации – выдают на вход буферной памяти (БП) независимые друг от друга сообщения. Закон появления сообщений – произвольный, но задан на перед.

В БП (буферной памяти) сообщения записываются «в навал» и выбираются по одному в обслуживающий аппарат (ОА) по принципу FIFO/LIFO. Длительность обработки одного сообщения в ОА в общем случае так же может быть случайной, но закон обработки сообщений должен быть задан. Т.к. быстродействие ОА ограничено то на входе системы в БП возможно сложение данных ожидающих обработки.

А – абоненты.

Программная модель из этой системы создается следующим образом:

Должна быть обязательно программа сбора статистики (ПБССт – программный блок сбора статистики). Причем статистику программа должна собирать по каждому из объектов модели. Так же должна быть программа, которая позволит "оживить" систему – это программа синхронизации (блок синхронизации), которая покажет когда и в какое время будут активизированы те или иные фрагменты модели.

Моделирование работы источника информации (ИИ).

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

где T_i – интервал времени между появлением i-го и (i-1)-го сообщения.

Программа – имитатор выработки таких интервалов:

1) Обратиться к генератору равномерно распределенных случайных величин на [a,b]

2) T_i – по заданному закону

3) К текущему времени + T_i

// процедурка равномерного распределения псевдослучайных чисел на итервале [a,b]

// U - равном. распр. на [0, 1]

// x = a + (b - a)U

double get_time (int i)

{

    double S = 0;

    srand(seek);

    if ( i > 1 ) S += get_time(i - 1);

    S += a + (b - a)get_u();

    return S;

}

или

double get_time (int i)

{

    double S = 0;

    srand(seek);

    for (int i = 0; i < .. ; i++)

      S += a + (b - a)rand();

    return S;

}

Выражения для вычисления времени с разлчным распределением: