Лекция № 3.

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

Введем алфавит Z = {Z₁, Z_2, Z_3, … Z_m}

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

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

P(Z_i) = 1/m – числа, удовлетворяющие равномерному распределению.

Примеры:

1. Для всякого iÎ N определим x_i равенство.

x_i = [p*10ⁱ]-10[p*10^i-1]

P(x_i) = 1/9

2. x_i = [1/7*10ⁱ]-10[1/7*10^i-1]

x_i+1 = j(x_i) – рекуррентное выражение первого порядка.

x_i+1 = j(x_i, c, l)

x_i+1 = A*X_i A = (a_ij)_n*n

X_i = < …> a_ij Î {0, 1}

1. Большой период

2. Простота реализации

3. Качество: хорошие статистические свойства

(*)

0 0 0 0

aⁿ = 0 0 0 1

...

1 1 1 1

n

Пример.

Пусть 000 – запрещенная комбинация.

1 0 1

0 1 0

0 0 1

1 0 0 7 = 2³-1

1 1 0

1 1 1

0 1 1

1 0 0

P¢ (1) = (2^n-1)/(2ⁿ-1)

P¢ (0) = (2^n-1-1)/(2ⁿ-1)

P (11) = (2^n-2)/(2ⁿ-1)

P (01) = (2^n-2-1)/(2ⁿ-1)

X_i+1 = Aⁱ*X_i i = 2ⁿ-1 – происходит повторение периода