Главная Промышленная автоматика.

Преобразование ленточной матрицы

Данный выпуск является продолжением серии, начатой выпуском «Библиотека алгоритмов 16-506» [23], и результатом дальнейшего совершенствования выпуска «Алгоритмы (101-150)» [25]. Последний содержал алгоритмы 101а-150а, являющиеся, в свою очередь, результатом переработки соответствующих алгоритмов журнала «Communi-cations of the АСМ» [13]. К каждому из алгоритмов данного выпуска прилагаются соответствующие «Подтверждения» и «Замечания» как из вышеуказанного журнала, так и от советских пользователей алгоритмами, а также «Свидетельства», составленные авторами выпзока. Алгоритмы публикуются здесь на эталонном языке АЛГОЛ-60 [14], описываемом во многих учебниках [16-19, 52, 53]. Там, где это возможно без заметного зхудшения алгоритмов, они предварительно переводились авторами выпуска на сокращенный АЛГОЛ-60 [15] * с некоторым его расширением в сторону полного языка АЛГОЛ [дспускались: 1) различение идентификаторов по всем содержащимся в них символам, 2) возведение целых чисел в любую целую степень, 3) операция и 4) условное именующее выражение]. В частности, все алгоритмы здесь записаны с использованием строчных бзкв латинского алфавита **. Прописные буквы используются только в приложении 1 {подтверждение к алгоритму 50CJ) для идентификаторов, являющихся русскими словами.

В свидетельствах к алгоритмам указывается оригинал переработанного алгоритма, перечисляются виды работ, произведенных над алгоритмом, внесенные в него изменения и приводятся результаты контрольного решения по данному алгоритму. Работы, которые проводились «ад всеми алгоритмами, для краткости называются здесь «ординарной переработкой». К ней относятся перевод на русский язык комментариев, подтверждений и замечаний, придание алгоритму наглядной, удобочитаемой формы (путем применения однотипной стзпенчатой записи-по правилам, опубликованным в статье [56], и использования идентификаторов интернационального характера), а также перевод алгоритмов на сокращенный АЛГОЛ. Все другие модификации алгоритмов (например, внесение в них исправлений, сокращение их записи, оптимизация и т. д.), а также отличия используемых языковых средств от сокращенного АЛГОЛа [15] и те слзчаи, когда алгоритмы составлялись заново, оговариваются в свидетельствах особо.

В приложении 3 к данному выпуску приводится тематический указатель алгоритмов, появившихся в советской и зарубежной печати

* Этот вариант языка АЛГОЛ-60 почти не отличается от получившего распространение в Советском Союзе языка АЛГАМС [54, 87, 88].

** Из типографских соображений эти латинские буквы набраны в тексте курсивом, а в описаниях процедур - прямым шрифтом. Например, в алгоритме 1606 powc и роАс означают одлк и тот же идентификатор. (Прилг. ред.)



к моменту составления выпуска. Алгоритмы в этом указателе группируются в соответствии с классификацией, принятой в журналах «Communications of the АСМ». Названия алгоритмов в выпусках сопровождаются индексами, соответствующими этой классификации. Например, в заголовке «Алгоритм 1156. Генератор перестановок [G6]» индекс [G6] укавывает, что алгоритм 1156 относится к классу G& («Суммирование рядов. Ускорение сходимости»). Расшифровка таких индексов имеется в указателе.

В выпусках серии «Библиотека алгоритмов» номера алгоритмов снабжаются буквой «б» для отличия их как от исходных, так и от алгоритмов предыдущей серии [11, 12, 25-27]. В ссылках на источники аббревиатура «САСМ» означает журнал «Communications of the АСМ» [13]. В переводах «Подтверждений» и «Замечаний» перечень поправок к алгоритмам обычно опускается, поскольку эти поправки, как правило, уже внесены в переработанный алгоритм. В соответствующих местах ставятся многоточия и делаются сноски. Контрольные решения по алгоритмам проводились с использованием транслятора * ТА-1М [20, 61, 83] на машинах М-220 [57] и транслятора БЭСМ-АЛГОЛ [51, 61, 83] на машине БЭСМ-6 [84] (быстродействие - миллион операций в секунду, память - около 32000 ячеек, длина мантиссы чисел - 10 цифр).

В серии «Библиотека алгоритмов» публикуются только отлаженные алгоритмы. Однако, учитывая известный каждому программисту факт, что никакая отладка и даже многолетнее использование не гарантируют абсолютную безошибочность программ, а также то, что пределов совершенствования алгоритмов практически не существует, авторы выпуска обращаются ко всем читателям и пользователям с просьбой присылать свои замечания и подтверждения в адрес издательства (для Агеева М. И.). Публикация таких замечаний будет продолжаться, так же как это делалось в предыдущих выпусках**.

Работа по подготовке к изданию алгоритмов предыдущей серии [11, 12, 25-27] была начата в соответствии с объявлением, регулярно (начиная с мая 1964 г.) публиковавшимся в разделе «Алгоритмы» журнала «САСМ»: «Репродукция алгоритмов данного раздела разрешается совершенно безвозмездно. Если репродукция делалась с целью публикации, то необходима ссылка на автора алгоритма и на выпуск журнала «САСМ», в котором опубликован алгоритм». Первый выпуск «Алгоритмы (1-50)» сразу после публикации был послан на отзыв редактору раздела «Алгоритмы» журнала «САСМ» президенту АСМ проф. Г. Форсайту и получил его полное одобрение.

Появление в печати предыдущей серии [11, 12, 25-27] было встречено горячим одобрением не только подавляющего большинства читателей и пользователей, но и самих авторов и издателей исходных алгоритмов (см., например, «Замечания» Г. Форсайта, Дж. Вараха

* В дальнейшем здесь наряду со словом «транслятор» будут употребляться слова «транслируюшая система» или просто «система». (Прим. ред.)

** В недавно опубликованном в русском переводе «Справочнике алгоритмов на АЛГОЛе» Уилкинсона н Райнша [79, с. 12] эта же мысль выражена следующими словами: «Публикация материала подобного содержания связана с теми особенностями, что выбранные рабочие алгоритмы должны быть полезными в течение длительного времени. Авторы убеждены, что создание работоспособных алгоритмов - процесс непрерывный, и они будут благодарны всем, кто укажет на ошибки и трудности, встретившиеся при практической работе с предложенными алгоритмами».



и г, Цилке в приложении 1 к выпуску «Библиотека алгоритмов 16-506»). Тем не менее, так же как и в предыдущих выпусках, здесь подчеркивается, что коллектив сотрудников, выполнявших одновременно работу составителей, переводчиков, переработчиков « отладчиков алгоритмов и собирательно именуемых здесь авторами выпуска, на авторство на отдельные алгоритмы отнюдь не претендует, за исключением только тех специально оговоренных в «Свидетельствах» случаев, когда алгоритмы составлялись заново. Сделанные в процессе переработки изменения, как правило, лишь улучшали их машинную реализацию (исправления, сокращения, оптимизации и т.д.) и повышали удобства ими пользования, но не затрагивали существа алгоритмов, их численных методов.

Таким образом, алгоритмы, номера которых снабжены буквами «б» или «а», являются лишь вариантами исходных алгоритмов, публикуемыми на правах обычных их подтверждений. Поэтому читателям и пользователям в ссылках на источники нужно указывать авторов исходных алгоритмов и номера журнала «САСМ», из которых взяты эти алгоритмы, независимо от того, будут ли при этом читатели упоминать и авторов гоответствующего выпуска данной серии или нет *.

Контрольные решения по алгоритмам проводил Ю. И. Марков, а подготовку рукописи к изданию - В. П. Алик. В проверке рукописи принимал участие Э. М. Каплинский и В. М. Агеев, в переводе текстового материала принимали участие Л. С. Кривонос и Л. В. Малюк. Основная переработка алгоритмов, написание текста свидетельств, компоновка выпуска и его общая редакция выполнялись М. И. Агеевым.

Авторы выпуска выражают свою глубокую благодарность всем тем читателям, которые прислали свои замечания и подтверждения к ранее опубликованным алгоритмам, тем, кто дал в своих замечаниях высокую оценку проделанной авторами выпуска работы, и тем, кто ссылками в своих опубликованных работах (см., например, работы [46, 53, 55, 61, 79, 89, 90]) подтвердил значение «Библиотеки алгоритмов», как нового справочного пособия.

* Вопрос об авторстве на алгоритмы широкого назначения, публикуемые в справочных пособиях, подобных данному, наиболее точно освешен в вышеупомянутом справочнике Уилкиисона и Райнша [79, с. 12], где сказано следуюшее: «Само содержание книги указывает на то, что это плод совместных усилий большого числа исследователей. Во многих случаях исходная основа алгоритма претерпевала изменения в течение длительного периода времени, и многие математики принимали участие в улучшении перовначального варианта. Мы благодарны всем, кто принимал непосредственное участие в этом издании».





[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

0.0019