Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [ 104 ] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

Таким образом,

Заметим, что для выбора М различных чисел из N при использовании алгоритма SELECT должно генерироваться только фиксированное

ITEM

ITEM

ITEM

ITEM

ITEM

СГЕНЕРИРОВАННОЕ.

СЛУЧАЙНОЕ

ЧИСЛО

6 7 6 4 3

МЕЖДУ

1-10 1-9 1« 1-7 16

ВЫБРАННОЕ ЧИСЛО

ITEM(6J = e ТЕМ.(71 = 7 1ТЕМ(61 = 10 1ТЕМ(41=4 ТЕМ(Э1=3 Рис. 6.3.1. Пример работы алгоритма SELECT (выбор).

количество М случайных чисел. В действительности объем необходимой работы равен 0{N+M), т. е. алгоритм SELECT выполняет: операторов присваивания на шаге 1;

4М операторов присваивания на шаге 2;

М обращений к генератору случайных чисел на шаге 3. Сравните это с алгоритмом SS, выполняющим:

2 оператора присваивания на шаге 0;

0{N) обращений к генератору случайных чисел на шаге 2;

0{N) проверок на шаге 3;

ЗМ операторов присваивания на шаге 3;



0{N) сложений на шаге 4.

Заметим также, что в качестве побочного продукта алгоритм SELECT дает случайную перестановку чисел 1, .... Л, что еще увеличивает его полезность.

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

В разд. 2.4 мы определили дискретные случайные переменные, т. е. случайные переменные, множества значений ) которых конечны или являются бесконечными счетными множествами. Случайные переменные, множества значений которых - бесконечные несчетные множества, называются непрерывными. Хотя большинство элементарных приложений теории вероятности и статистики в вычислительной математике используют только дискретные случайные переменные, существует два важных непрерывных распределения, возникающих столь часто, что они заслуживают специального рассмотрения.

Случайная переменная X является непрерывной, если существует неотрицательная функция f{x), определенная на всей вещественной прямой и обладающая тем свойством, что если S - произвольное множество вещественных чисел, то

P{XeS)=lfix)dx.

Функция fix) называется плотностыо распределения вероятности X.

В частности, если S - вся вещественная прямая, то, поскольку X обязательно принимает некое значение,

1 = Р(Х€(-оо, оо))= ] f{x)dx.

~ со

Аналогично, если S - некоторый интервал [а, Ь] на вещественной прямой, то

P{aXb) = lf(x)dx.

Непрерывньш аналогом дискретной переменной с равновероятным распределением является равномерно распределенная переменная. Если X - случайная переменная, принимающая с одинаковой вероятностью любое значение в интервале [О, 1], ее плотность вероятности равна

/1, 0<х<1;

остальных случаях.

) Напоминаем, случайная переменная является функцией.



Тогда, например,

Е[Х]=] xf{x)dx; var[X]= I {x-E[X]ff{x)dx.

Для равномерно распределенной переменной U в [0,1] получим

о~ 2

[t/]= J xf{x)dx = xdx = var[t/]= J {x-E[X]mx)dx=[x-ydx = .

-oo 0

Еще одно важное непрерывное распределение - это нормальное распределение. Плотность вероятности для случайной переменной X, обладающей нормальным распределением с параметрами [л и о.

) Иногда для обозначения этого распределения мы будем пользоваться символом и (О, 1).

P(l/4<X<3/4)= 5 Ыл;=3/4-1/4=1/2;

Р(Х=1/2)= J Ыл;= 1/2-1/2 = 0.

Последний результат особенно важен. Вероятность того, что непрерывная случайная переменная окажется равной некоторому частному значению из своего интервала, всегда равна О, а не /(X). Невозможно поставить в соответствие конечную вероятность каждому из бесконечного множества значений, так как «сумма» всех этих вероятностей окажется бесконечной (а не единицей). Не забывайте об этом. Равномерное распределение на интервале [0,1]i)-или (0,1); имеет ли это какое-нибудь значение? - по существу является именно тем распределением, которое моделируют программные генераторы случайных чисел. То есть случайное число, генерируемое компьютером, по существу представляет собой выборку из равномерно распределенной переменной.

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [ 104 ] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.001