еющук» нуль в каждой отроке н в каждом столбце, не включается во Беременной интервал.

В каждом эксперименте была использована ©дна и я же последовательность 14 значений порядка матрицы 1- 2, 3, 4, 5, 6, 8, 10, 12, 15, 19, 23, 29, 36, 46. Каждое значение составляет нримерно 1.25 от предыдущего. Для надежности каждое получаемое значение подвигалось проверке.

Временная статистика была получена из 50 проб для каждого п, каждый элемент каждой испытуемой матрицы бул псевдослучайным целым числом из интервала от О до 2-1. Эмпирическое среднее время решения в зависимости от и изображено на рис. 1. Штриховые линии представляют время решения одного (эмпирического) стандартного отклонения от среднего. Вычисление наилучшего линейного приближения к log{t) по log(n) дает «116 мкс.

Наихудший результат был получен при использовании матрицы (djj) =,((i-1) X (/-1)) (рис. 2). Наилучшая логарифмо-линейная аппроксимация здесь дает j«94.7 r4 мкс.

Дополнительные зсперименты были проведены для определения воздействия ограниченной последовательности значений элементов на производительность. Для каждого k=2, 6, 10, 23 и каждого п было проведено 20 опытов с матричными элементами, выбранными по псевдослучайному закону в интервале между О и 2-1. На рис. 3 изображены результаты, показывающие, как «вырожденность» коэффициентов ускоряет процесс решения.

Представляется, что если значение п превосходит число возможных значений элементов матрицы, то время решения отклоняется от своей обычной зависимости по п и начинает расти более медленно.

Подтверждение к алгоритму 27 Р. Уитти (Witty R. D. «САСМ», 1963, № 12)

Алгоритм 27 был успешно проверен на машине Burroughs В5000 с использованием расширенного языка АЛГОЛ-60 и с исходной матрицей

60 10 о 40

60 16 27 О 40

28 4

О 76 О О 18 10 60 24

X) 40

б5 VI

,2 4

18 3

62 16 11 53

10 84 О 16

Был получен результат х= (6, 4, 3, 1, б, 2).

Перед трансляцией алгоритма в него были внесены следующие изменения *. Оператор

min:=d[r[q, cb[q]; был заменен на оператор

min:=d[r[l], cb[\]];

Оператор

if x[i]=0 then

begin x[i]:=j; go to start end; был заменен на оператор if xli]=0 then begin xli):=j;

for i:= 1 step 1 until n do if x{i]=0 then go to start; go to fin . end;

Последняя строка

end assign; была заменена на строку

fin: end assign;

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

Алгоритм 286 не публикуется здесь потому, что соответствующий алгоритм 28 был позднее заменен в журнале «САСМ» более соверщенным алгоритмом 296.

АЛГОРИТМ 296

Преобразование полинома при замене аргумента к на at+b[Ci]

Процедура potyx вычисляет коэффициенты do, 4и , dn преобразованного полинома p{t) через данные коэф-,

* Первая « третья из этих поправок были уже ранее замечены авторами (выпусков и внесены в алгоритм 27а при его составлении. Здесь используются обозначения, принятые в алгоритме 27а, в частности, вместо 44]. cb[i]] пишется 444. сЩ].

дициенты Со, Си...,Сп полинома р(х), где x=at+b. nrocedure polyx (a,b,c,n) result: (d); P value a,b,n; real a,b; integer n; array c,d; heeirt integer i,j,k; array z,wIO:n]:-d[0]:=oIO]; z[Ol:wIO]: = l; for i: == 1 step 1 until n do begin w[i]: = l; zO];"bXzl[i-1];

dIO]:-=dIO]+c[i]XzO] end i;

for j:= 1 step 1 until n do begin w[0]: = a X wIC]; d[j]:=c[j] X w[0]; for i:= j + 1 step 1 until n do begin k: = i-j;

w[k]: = a X w[k]+w[k-1 ]; d[i]: = d[j]+cIi]Xw[k]Xz{k] end! end j end polyx;

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

IP Алгоритм 296 получен в результате внесения попра-вок в алгоритм 29а, указанных в «Замечаний и лод-тверждении к алгоритму 29а» И. Р. Гитмана (см. ниже).

Алгоритм 296 был транслирован на машине БЭСМ-б в системе БЭСМ-АЛГОЛ и успешно использован для отладки алгоритма 296.

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

Алгоритм 29а получен в результате сокращений и ординарной переработки алгоритма 29 (М а с к i п п е у J, G. «САСМ», I960, №11). С .помощью транслятвра был трансформирован полином 2х+Зх+1 с xl+t. Пслучегн правильный результат:. 2P+7t+6.

Замечание и подтверждение к алгоритму 29а

И. Р. Гитман, Ленинград, 1967

Алгоритм 29а содержит ошибку, из-за которой не дает правильного результата при аф1. Для исправления нужно строки 8, 9 и 10 описания процедуры, начиная с оператора w[0]:-aXw[0]-„ заменить на end;

for j:= 1 step 1 untiln do