I 2 = ХУ =

Ут1 Ушг

4/11 Ун

Угг, Угг,

Утг . Уп

fe,. элементы матрицы z будут равны

2 (%.i-MXK.3-Aj)

/т Г m

2 (*-i)Xl/ 2 (w-:

Трудно заметить, что эти значевия Zi,j совпадают со 1иачениями элементов нормированной- корреляционной матрицы, определяемыми, например, в работе Е. С. Вентцель [42, с. 344, (14.6.7), (14.6.8) и (14.6.9)], если учесть, что индексация (по столбцам) элементов .входной таблицы X [42, С. 343, табл. 14.6.2] .в этих .формулах отличается от принятой Б математике индексации (по .стро-KaiM) элементов матриц.

Алгоритм 396 был транслирован в системе ТА-1М на машине М-220 для т=10, п=5 и следующей входной матрицы х:

-120 -20 2 60 180 -108 -75 -20 20 80 -200 -120 -80 -20 10 -55 -2 40 120 200 • 5 60 100 165 220

-240 -202 -140 -88 -30 10 65 120 160 205 -40 О 65 103 170 -100 -40 -10 55 105 105 135 190 280 330

(пример ИЗ работы Е. С. Вентцеяь [42, с. 345, Табл. 14.6.3]). Была получена следующая матрица г:

1.0000000 0.9773284В 0.99268070 0.98592846 0.95107158 0.97732846 1.0000000 0.98959900 0.98668350 0.97305512 0.99268070 0.98959900 0.99999999 0.98771220 0.96036111 0.98592846 0.98668350 0.98771220 0.99999999 0,97352692 0.95107158 0.97305512 0.96036111 0.97352692 1.0000000 t

Элементы этой матрицы z с точностью до единицы последней цифры в значениях, приведенных в работе Е. С. Веитцель [42, с. 346], совпадают со значениями элементов матрицы (см. [42, с. 346]):

1.00 0.97 0.99 0.98 0.98 1.00 0.99 0.99 0.97 1.00 0.98 0.96 1.00 0.97 1.00

Несовпадение последних элементов первой строки объясняется, по-види1мому, опечаткой в работе Е. С. Вентцель (0.98 вместо 0.95).

Следует заметить, что вычисляемые процедурой norm еще и значения квадратичных отклонений s, отличаются от принятых Б советской литературе тем, что знаменатель под корнем равен т вместо т-1 (см., например, [42, с. 344, (14.6.7)]). Однако это несовпадение легко устранить, если заменить первый оператор в теле процедуры norm на

r: = sqrt(m-1);

Свидетельство к алгоритму 39а

Алгоритм ЗОа получен в результате сокращения и ординарной переработки алгоритма 39 (Sassouni Р. «САСМ», 1961, № 3).

АЛГОРИТМ 406

Планирование критического пути (анализ сети ПЕРТ) [Н]

Для процедуры criticalpath (т. е. критический путь) задаются параметры:

п - общее число работ (операций) по проекту; i\ti\, ][k\-вектор-пара, представляющая -ю рабо-

т-у, которая понимается как стрелка, связывающая событие с событием j[k] {i[k]<j[k], й= 1, 2, ..., n); dij[k] -продолжительность k-й операции. Процедура определяет (для k-и операции):

slyk] -самый ранний срок начала; s2 k - самый поздний срок начала; шШ fl k - самый ранний срок заверщеиия; Ш f2[k -самый поздний срок .заверщения; щ, tf[k] - полный резерв времени;

-свободный резерв времени. Должны иметь место соотнощения: г[1]=:1 и i[k]<i[k+l]. Например, если первые три работы обозначены как (1, 2); (1, 3) и (2,4)), то векторами i и / являются (1, 1, 2) и (2, 3, 4) соответственно. Критический путь задается стрелками, соединяющими события, для которых полный резерв времени равен нулю.

Для .выходов из процедуры используются следующие нелокализованные метки:

out2 - если i[k] вне последовательности; outs - если i[k] пропущено.

Автор алгоритма 40 ссылается на работы Дж. Келли [14i] и М. Фрищберга [15i].

procedure criticalpath(n,i,j,dij)result:(sl,s2,fl,f2,tf,ff); value n; integer n; integer array i,j,dij,sl,s2,fl,f2,tf,ff; begin integer k,index,rnax,rnin; integer array ti,tell:n]; index: = l;

for k:= 1 step 1 until n do begin

if i[k]j[k] then go to outl; if i[k]<index then go to out2; if ik >index+l then go to out3; if i[k =index+l then index: = ilk]; tii[k]:=0;.te{k]:=9999 end;

for k:= 1 step 1 until n do • •

begin rnax: = ti[ilk]] + diji[k];

if ti[ji[k]]<max then ti[jlk]]: = max end ti; te[jln]]: = ti[In]]; for k:= n step -1 until 1 do begin min :=te[j[k]]-dij(k];

if tep[k]]>min then te[ii[k]]:==min