ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 150
Скачиваний: 0
программы управления, хранимые в ОЗУ ESS № 2. Эти программы состоят из 75 000 команд по 22 бита.
Язык SMILE используется: 1) для статистического моделирова ния схем, предлагаемых инженерами, и выбора оптимальных; тем самым ускоряется процесс конструирования АТС; 2) для состав ления и отладки программы управления ESS № 2.
Для облегчения связи инженеров с машиной разработан спе циальный символический язык записи инженерных решений, со ставлена программа SWAP (Switching Assembler Program) для перевода инженерной символической записи в двоичную запись ма шины с последующим моделированием предлагаемых схем посред ством языка SMILE.
Использование ЭВМ может многократно уменьшить время кон струирования АТС, время создания математического обеспечения программно управляемых АТС, время наладки вводимых в строй станций. Отражением этого запроса практики является создание проблемно-ориентированного языка TPL-1 [179, 190].
7.2.СЛУЧАЙНЫЕ ЧИСЛА. КРИТЕРИИ СЛУЧАЙНОСТИ
1.Равномерно распределенные случайные числа
Для моделирования случайных процессов необходимо иметь последовательности чисел, подчиняющихся различным распределе ниям, например, экспоненциальному, Эрланга, нормальному и дру гим. Обычно для этого используют равномерно распределенные случайные числа, которые можно получить:
1)программным путем (такие числа называются псевдослучай ными) ;
2)при помощи датчика случайных чисел;
3)из заранее составленной таблицы случайных чисел. Подробнее рассмотрим программный метод. Наибольшее рас
пространение получил способ перемешивания. Например, одна из возможных программ получения случайных чисел, равномерно распределенных на интервале (0, 1), состоит из четырех команд. Пусть исходное случайное число находится на ячейке а; рабочие ячейки — а+1 и а + 2. Команды следующие:
1) |
сдвиг содержимого исходной ячейки |
а на семь разрядов |
вправо, запись результата в ячейку а+ 1; |
|
|
2) |
сдвиг содержимого исходной ячейки а на семь разрядов |
|
влево и запись результатов в ячейку а + 2; |
|
|
3) |
сложение (команд) а + 1 и а + 2 с записью в а + 2;. |
|
4) |
взятие модуля с нормализацией числа, |
находящегося в ячей |
ке а + 2, и запись его в ячейку а. Это и есть следующее равномер но распределенное случайное число.
Полученная серия равномерно распределенных случайных чисел характеризуется некоторым отрезком апериодичности и длиной пе
137
риода, зависящими от исходного числа. Для приведенной програм
мы длина |
отрезка |
апериодичности достигает |
50 000 |
с длиной пе |
||||
|
|
|
|
риода около 5000. Для удлинения отрез |
||||
|
|
|
|
ка апериодичности |
в |
исходную серию |
||
|
|
|
|
случайных чисел вносят возмущения, оп |
||||
|
|
|
|
ределяемые другой программой образо |
||||
|
|
|
|
вания случайных чисел. |
|
|
||
|
|
|
|
Для получения случайных чисел, рав |
||||
|
|
|
|
номерно распределенных |
на интервале |
|||
|
|
|
|
[а, b], берем числа, равномерно раопреде- |
||||
|
|
|
|
^ ленные .на [0, 1], и |
делаем преобразова |
|||
|
|
|
|
ние подобия и сдвиг, а именно, если леев- |
||||
Рис. 7.1. Схема получе- |
доелучайное число |
а |
распределено |
рав- |
||||
ния |
случанных |
чисел, |
номерно на интервале [0, |
1], то число |
|3 = |
|||
ных |
на |
произвольном |
<т)схЧ-о распределено на интервале |
|||||
интервале [а, 6] |
|
[а, 6] (рис. 7.1.). |
|
|
|
|
||
2. Критерии случайности
Разработана система тестов для проверки серии равномерно распределенных случайных чисел. Укажем наиболее применяемые тесты.
Проверка частот. Отрезок i[0, 1] разбивается на т (обычно 10—20) равных интервалов. Полученные эмпирические частоты
— l |
, i = l , ..., т, 2n,'=uV, сравниваются с теоретическими |
N |
£ |
вероятностями l /т. Согласие проверяется по критерию х2>так как величина
т Е("•-£)■ |
(1) |
£=i |
|
подчиняется распределению х2 с т— 1 степенями свободы. Проверка пар. Рассматриваются последовательные пары при
делении интервала (0, 1] на т частей. Каждая пара случайно попа
дает в одно из т 2 делений квадратной таблицы т Хт . |
Согласие |
с теоретическим распределением опять проверяем но х2 |
При этом |
в зависимости от метода образования пар меняется число степеней свободы.
Пусть дана серия чисел Х\, |
хъ х3, .. ., xN. Если пары образовы |
||
вать венде (хи х2), (х3, |
Xi) |
. ■., то пары взаимно-независимы, эмпи |
|
рические частоты |(их число т2) |
сравниваются с теоретическими ве |
||
роятностями равномерного |
распределения 1 /т 2. Величина |
||
т |
|
|
|
“ I, /=1 Е ( » |
« |
- £ |
Г |
распределена по закону %2 с т2—т степенями свободы, где — число попаданий в i, j — клетку таблицы.
138
Ситуация более сложная, если пары образовывать в виде ( ад, х г ) , { х г , Х з ) , . . . Этот метод образования пар более выгодный, так как он более полно использует выборку чисел, но из-за зависимости пар
распределение |
статистики (2) уже другое. Башарин [13] показал, |
|
что вместо (2) следует брать статистику |
||
|
/га |
/га |
i, |
}=1 |
£=1 |
которая, |
как и |
(2), распределена по х2 с т (т — 1) степенями сво |
боды. Там же указано, что следуя работе Кендалла и Смита [238], иногда ошибочно предполагают, что только первое слагаемое в (3) имеет распределение %2 с т (т — 1) степенями свободы.
Проверка серий. Делим интервал [0, 1] на две части, например, пополам. Пусть первое число £<1/2. Тогда вычисляем количество подряд следующих чисел, которые меньше 1/2. Потом следует се рия чисел, больших 1/2, и т. д. Известны формулы для вычисления
согласия в этом случае [22]. |
Например, |
известно, что только в |
52 случаях в серии из 10 000 |
равномерно |
распределенных случай |
ных чисел можно встретить хотя бы одну серию длины 15 и бо лее.
3.О проверке случайности по текущим результатам моделирования
Рассмотренные выше критерии случайности предполагали 'спе циальные исследования выбранной серии псевдослучайных чисел. Сейчас рассмотрим один критерий, который основан на обработке текущих результатов моделирования. Этот критерий особенно це нен при использовании датчика случайных чисел, так как .в дан ном случае важно контролировать качество случайных чисел не прерывно.
Пусть дана коммутационная система произвольной структуры с потерями (возможны и другие дисциплины обслуживания). Пред положим только, что поступает пуассоновский поток вызовов ин тенсивности X, обслуживание — экспоненциальное с единичной ин тенсивностью. Через т+1, т+2 .. . обозначим моменты, непосредст венно следующие, за моментами поступления вызовов. Если в ка кой-то 'момент т+л занято i линий (т. е. ]х)(т+л) |= £), то в момент т~и+1 может быть занято любое случайное число / линий, /<П. Со ответствующие вероятности, перехода
р _. _ |
*' |
* ~~ 1 |
J + I |
л |
_ |
|
% i А, |
—1 |
А, + / + 1 А / |
|
|
j = 0, |
1, • • •, |
i; i = l, 2, |
• • •, шах |х |= |
и. |
|
|
|
|
xes |
|
|
П X
/! П (* + *) k—i
(4)
139
Следовательно, реализация процесса дает матрицу чисел
« м |
« 1 1 |
0 |
0 |
« 2 0 |
« 2 1 |
« 2 2 |
0 |
п з о |
« 3 1 |
« 3 2 |
« 3 3 |
где tiij — число моментов ть таких, что \х(х+h) \= i, |х;(т—л+i) |==/. Вероятности перехода х(х~к)-*-х(х^11) зависят от структуры схе
мы. При данных = |
каждая строчка матрицы Цп^Н опреде- |
/=о
ляется полиномиальным распределением согласно (4). Поэтому для проверки качества случайных чисел можно проверять согласие по лученной матрицы Ц/Zijll с вероятностями (4) на основе критерия X2. Получаем
ЕЕ |
(riiPij - |
пцУ |
|
(5) |
|
|
n iPti |
|
|
||
i=l /=о |
|
|
|
|
|
Число степеней свободы выражения |
(5) равно 2 + 3 + |
. . . + fu + |
|||
+ 1)—v = |
|
V |
(сумма числа ненулевых элементов |
матрицы |
|
llreijll минус v |
связей типа Пх=Ъпц). |
Оно может быть уменьшено |
|||
еще на единицу, если в (4) подставить оценку максимального прав доподобия параметра X. Рассмотрим соответствующее уравнение. При данных tii вероятность получения реализации, имеющей мат рицу Hftij-L равна
MX) = n |
n |
/ f |
1=1 |
/=0 \ |
П а + £) |
|
\ |
*=/ |
V |
А |
Оценку максимального правдоподобия \Х для параметра К по-
лучаем из уравнения — logL (?o)= 0. Ввиду громоздкости этого
дХ
уравнения подробную его запись опустим. Заметим только, что для
его решения можно использовать итерационный алгоритм [233]. В
л
нашем случае оценкой X может быть также оценка среднего чис ла поступивших вызовов за единицу времени, которая близка к оценке максимального правдоподобия.
4.Произвольно распределенные случайные числа
Наиболее известный способ получения случайных чисел т), подчиненных функции распределения F (x ), основан на применении уравнения
I = А (П). |
(6) |
140