Курсовая работа: Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса

;

.

Отсюда получаем выражение для среднеквадратичного значения в виде

. (8)

Напомним, что для равномерно распределённой в интервале [0,1] величины x имеем

Из формулы (8) следует, что при среднеквадратичное отклонение σ квазиравномерной совокупности стремится к . Ниже приведены значения отношения среднеквадратичных значений двух величин ξ и η в зависимости от числа разрядов, причём величина η имеет равномерное распределение в интервале [0,1] (табл. 1).

Таблица 1

k	2	3	5	10	15
σξ /ση	1,29	1,14	1,030	1,001	1,00

Из табл. 1 видно, что при k>10 различие в дисперсиях несущественно.

На основании вышеизложенного задача получения совокупности квазиравномерных чисел сводится к получению последовательности независимых случайных величин z_i (i=1,2,…, k), каждая из которых принимает значение 0 или 1 с вероятностью 1/2. Различают два способа получения совокупности этих величин: физический способ генерирования и алгоритмическое получение так называемых псевдослучайных чисел. В первом случае требуется специальная электронная приставка к цифровой вычислительной машине, во втором случае загружаются блоки машины.

При физическом генерировании чаще всего используются радиоактивные источники или шумящие электронные устройства. В первом случае радиоактивные частицы, излучаемые источником, поступают на счётчик частиц. Если показание счётчика чётное, то z_i =1, если нечётное, то z_i =0. Определим вероятность того, что z_i =1. Число частиц k, которое испускается за время Δt, подчиняются закону Пуассона:

.

Вероятность чётного числа частиц

.

Таким образом, при больших λΔt вероятность P{Z_i =1} близка к 1/2.

Второй способ получения случайных чисел z_i более удобен и связан с собственными шумами электронных ламп. При усилении этих шумов получается напряжение u(t), которое является случайным процессом. Если брать его значения, достаточно отстоящие друг от друга, так чтобы они были некоррелированы, то величины u(t_i ) образуют последовательность независимых случайных величин. Обычно выбирают уровень отсечки a и полагают

причём уровень a следует выбрать так, чтобы

.

Также применяется более сложная логика образования чисел z_i . В первом варианте используют два соседних значения u(t_i ) и u(t_{i +1} ), и величина Z_i строится по такому правилу:

Если пара u(t_i ) – a и u(t_{i +1} ) – a одного знака, то берётся следующая пара. Требуется определить вероятность при заданной логике. Будем считать, что P {u(t_i )>a}=W и постоянная для всех t_i . Тогда вероятность события равна по формуле событий A₁ H_v . Здесь H_v – это вероятность того, что v раз появилась пара одинакового знака

u(t_i ) – a; u(t_{i +1} ) – a. (9)

Поэтому вероятность события A₁ H_v

P{A₁ H_v }=W (1-W) [W² +(1-W)² ]^v .

Это – вероятность того, что после v пар вида (9) появилось событие A₁ . Оно может появиться сразу с вероятностью W (1-W), оно может появиться и после одной пары вида (9) с вероятностью

W (1-W) [W² +(1+W)² ]

и т.д. В результате