Из истории отечественной компьютерной алгебры

УДК 519.682+531.6

Г.Б. ЕФИМОВ, М.В. ГРОШЕВА

ИЗ ИСТОРИИ ОТЕЧЕСТВЕННОЙ КОМПЬЮТЕРНОЙ АЛГЕБРЫ

Abstract: In the paper we briefly discuss some stages of development and application of Computer Algebra (CA) and CA systems. The list of known Russian CA systems is presented. We also give the list of Conferences, Seminars and Books with papers in this branch of informatics.

Key words: computer algebra, mechanic, history of science.

Анотація: У роботі коротко викладені деякі етапи, проблеми розвитку і використання комп’ютерної алгебри (КА) і систем комп’ютерної алгебри (СКА). Наведений список відомих вітчизняних систем комп’ютерної алгебри, конференцій, семінарів, збірників праць у цій галузі інформатики.

Ключові слова: комп’ютерна алгебра, історія науки, механіка.

Аннотация: В работе кратко излагаются некоторые этапы, проблемы развития и использования компьютерной алгебры (КА) и систем компьютерной алгебры (СКА). Приводится список известных отечественных систем компьютерной алгебры, конференций, семинаров, сборников трудов в этой области информатики.

Ключевые слова: компьютерная алгебра, история науки, механика.

1. Введение

Истории развития символьных, аналитических преобразований или вычислений на ЭВМ и систем для аналитических вычислений или, более современно, компьютерной алгебре и системам для нее (СКА) в нашей стране, а также обзорам по различным приложениям КА и программным системам СКА посвящено уже немало работ. Но стоит остановиться на некоторых моментах этой истории -на роли конференций, семинаров в развитии отечественных исследований по КА и ее приложений, а также напомнить об отечественных системах КА, в том числе разработанных для задач механики.

2. Этапы истории отечественных исследований по компьютерной алгебре

В истории развития и применения КА в Советском Союзе можно отметить несколько этапов. После первых, весьма интересных, но немногочисленных экспериментов по преобразованию символьных (формульных) выражений на компьютере, выяснилось, что для дальнейшего их развития требуются большие ресурсы и затраты труда. Исследования продолжались небольшими коллективами в крупных научных центрах в Ленинграде, Киеве, Новосибирске, Москве, Харькове и др. Существенным прорывом явилось создание СКА АНАЛИТИК в Институте кибернетики Академии наук Украины в Киеве. АНАЛИТИК был аппаратно реализован на машине МИР-2, небольшой и поэтому достаточно доступной, с языком пользователя по тому времени весьма высокого уровня. На АНАЛИТИКе было выполнено немало прикладных работ, организована ассоциация пользователей машин МИР, которая активно работала.

В следующий период, после появления БЭСМ-6, машин ряда ЕС и языков достаточно высокого уровня, было создано большое число СКА, очень различных по объему и возможностям, разнородных по областям применения. Они отличались по степени универсальности, набору и совершенству реализованных в них алгоритмов КА, как общих математических, так и проблемноориентированных. Многочисленность СКА определялась рядом обстоятельств. Ограниченность ресурсов компьютеров затрудняла использование и развитие языков высокого уровня, удобного сервиса и средств взаимодействия различных систем, в частности, СКА, численных пакетов и комплексов программ. Из-за этого затруднялись использование уже существующих СКА для задач

© Ефимов Г.Б., Грошева М.В., 2009

ISSN 1028-9763. Математичні машини і системи, 2009, № 2

другого типа и стыковка их с существующими комплексами численных вычислений. Отсутствовали и объединяющие проекты по развитию КА и СКА. В программировании на повестке дня стояли другие задачи. Поэтому создавались все новые СКА, каждая для своей группы задач.

Можно отметить еще одно обстоятельство общего характера. Серьезные ресурсы компьютеров и исследователей были сосредоточены на больших ВЦ, специализированных на решении важных прикладных задач. Вузы имели, как правило, весьма ограниченные ресурсы современных компьютеров. Мировой опыт показал, что широкое распространение получили те СКА, которые были широко доступны. Так, система Reduce, первоначально специализированная, активно развивалась и стала универсальной благодаря тому, что была доступна в университетах. Открытость обеспечила ей быстроту развития, рост числа и совершенствование качества новых алгоритмов КА. Специфика ситуации у нас не создала такой возможности.

Объединяющим центром по работам в КА в этот период явился Объединенный институт ядерных исследований в Дубне. В нем смогли получить и адаптировать Reduce, активно способствовали его распространению. Кроме собственных больших работ на этой системе, сотрудничали и с исследователями других организаций, проводилась стажировка в ОИЯИ, что способствовало освоению Reduce во многих центрах. Большую роль в объединении научных сил играли Совещания по КА, регулярно проводившиеся в Дубне, с публикацией их трудов. Были налажены контакты с ведущими специалистами за рубежом. Дополнением к организующей работе в Дубне служил Семинар по КА под руководством Д.В. Ширкова на физическом факультете МГУ. С появлением у нас персональных компьютеров появились и широкие возможности для международных контактов. Ситуация в исследованиях по КА существенно изменилась. Но хотелось бы остановиться, в основном, на описании предыдущих этапов нашей истории.

Многочисленность отечественных СКА заставляла собирать информацию об имевшихся в то время системах о том, что предпринималось авторами в ряде обзоров. Несомненно, ряд систем остались за их рамками, но собранный материал дает большую информацию о разработанных СКА. Часть ее мы представляем ниже. Более полная - в монографии авторов [1].

3. Отечественные системы компьютерной алгебры

Приводим список наиболее известных СКА. В конце списка даны СКА для задач механики системы тел, по некоторым СКА данные не полны. В описание входят: название, город, фамилии авторов, язык реализации и ЭВМ.

АВТО-АНАЛИТИК. Томск: Е.А. Арайс, Б.Ш. Гельфман, В.М. Зюзьков, А.В. Шутенков; БЭСМ-6, язык Автоаналитик; ЕС, ПК.

АНАЛИЗ. Москва: Ю.А. Герасимов, А.А. Красилов; БЭСМ-6, Алгол-60.

АНАЛИТИК-74, -79. Киев: В.М. Глушков, С.Б. Погребинский, В.П. Клименко, Ю.С. Фишман и др.; язык АНАЛИТИК-74, МИР-2, СМ-1410.

АНАЛИТИК-89, -91. Киев: В.П. Клименко, С.Б.Погребинский, Ю.С. Фишман и др.; программная реализация, язык АНАЛИТИК-89, -91.

АНАЛИТИК-93, -2000. Киев: В.П. Клименко, А.А. Морозов, Ю.С. Фишман, А.Л. Ляхов и др.; программная реализация с новыми языковыми возможностями.

АЛГЕБРА-0.5. Горький: М.А. Чубаров, Г.А. Долгов и др.; ЕС, Фортран.

АЛЬКОР. Москва: Л.В. Проворов; ЕС, БЭСМ-6, СМ-4, ПК, Рефал.

АРАП. Новосибирск: А.Л. Семенов; БЭСМ-6, ЯРМО; "Эльбрус", Автокод-Эльбрус.

АУМ. Новосибирск: Н.А. Калинина, И.В. Поттосин, А.Л. Семенов; БЭСМ-6, ЯРМО; "Эльбрус", Автокод-Эльбрус.

БОРА. Томск: Ю.Б. Шмидт; БЭСМ-6, машинные коды.

ВИБРАН. Вильнюс: Р.В. Кульветене, Г.П. Кульветис; ЕС, СМ, ПК, Фортран.

ВФЛ-1. Иркутск: В.М. Матросов, С.Н. Васильев, В.Г. Каратуев, Е.А. Суменков; БЭСМ-6, "Эльбрус", Паскаль.

ДИНАМИКА. Иркутск: В.Д. Иртегов, Л.А. Бурлаков, М.В. Почтаренко; БЭСМ-6, Алгол-ГДР.

ДИРАК. Новосибирск: А.Г. Грозин; "Одра", ЕС, "Электроника 100-25", Паскаль.

КЕНТАВР. Минск: В.Л. Катков, М.Д. Попов; БЭСМ-6, ЯРМО.

КИДИМ. Харьков: Л.И. Штейнвольф, В.Н. Митин; ЕС, Алгол-68.

МАРС. Томск: Е.А. Арайс, В.М. Дмитриев, В.Ф. Шадрин, А.В. Шутенков и др.; БЭСМ-6, ЕС,

Автоаналитик, Фортран.

МЕХАНИК. Иркутск: А.В. Банщиков, Л.А. Бурлакова, Г.Н. Иванова, С.С. Смирнов; ЕС, PH.

МЬР Иркутск: М.В. Почтаренко; БЭСМ-6, Алгол-ГДР.

ММАЫв. Гродно: О.М. Городецкий; ЕС, Рефал.

МОДЕЛЬ. Ташкент: В. Бузурханов, М. Музафаров; БЭСМ-6, Паскаль.

НОРМАЛИЗАЦИЯ. Иркутск: В.Д. Иртегов, М.А. Новиков; БЭСМ-6, Алгол-ГДР.

ПАС. Москва: Г.Б. Ефимов, БЭСМ-6, Фортран.

ПЛ-ОСИАЛ. Ташкент: Т.Т. Имамов, Б. Курманбаев; ЕС, ПЛ/1.

ПЛЭНЕР-АНАЛИТИК. Москва: В.А. Эльтеков; БЭСМ-6, язык Плэнер.

ПОЛИНАЛ. Москва: А.Б. Константинов; БЭСМ-6, Алгол-ГДР.

САВАГ. Ленинград: Ю.К. Демьянович; БЭСМ-6, Алгол-ГДР.

САНТ. Дмитровград: Ю.В. Марков; БЭСМ-6, Макро-ассемблер БЭМШ.

САНТРА. Москва: И.Б. Щенков, ЕС, Рефал.

СИРИУС-СПУТНИК. Харьков: И.Р. Аксельрод, Л.Ф. Белоус; ЕС, М-222, Спутник.

СИРИУС-2.1. Харьков: И.Р. Аксельрод, Л.Ф. Белоус; ЕС, Спутник, Рефал.

СПРИНТ. Ленинград: Н.Н. Васильев; БЭСМ-6, Фортран.

СТР. Ленинград: Н.Н. Васильев; БЭСМ-6, "Эльбрус", Фортран.

СРМ. Москва: В.Л. Топунов, И.Г. Резников, В.И. Стеллецкий; БЭСМ-6, ЕС, Рефал.

УПП. Ленинград: В.А. Брумберг, С.В. Тарасевич, Т.В. Иванова, Н.Н. Васильев, В.И. Скрипниченко, И.О. Бабаев; БЭСМ-6, ЕС, "Эльбрус", Фортран.

САТА. Вильнюс: В.В. Тумасонис; БЭСМ-6, ЕС, Лисп.

вРАТОЗ. Ленинград: С.В. Тарасевич; БЭСМ-6, ЕС, "Эльбрус", Фортран.

ЗАЗМ. Ленинград: А.В. Кузьмин; БЭСМ-6, Фортран, Автокод Мадлен.

БАТЫРЫ. Москва: Д.В. Куликов; ЕС, Рефал.

Чебоксары: Б.В. Алексеев; БЭСМ-6, Фортран, машинные коды.

Ленинград: П.И. Бегун, Г.А. Водень и др.; БЭСМ-6, Алгол-60, ЕС, Фортран.

Новосибирск: В.Г. Ганжа, С.И. Мазурик, В.П. Шапеев; БЭСМ-6, ЕС, Рефал.

Москва: Е.В. Панкратьев, Р.Е. Серов, С.Г. Хлебутин; СМ-4, Рефал.

Ташкент: Т. Фархадов, Т. Юлдашев; БЭСМ-6, Алгол-60.

Устойчивость-1. Горький: Г.А. Долгов, Д.Н. Макарычева, М.А. Чубаров; ЕС, Фортран.

СотрНЕР. Э.Э. Боос, М.Н. Дубинин, В.Ф. Еднерал и др., ИЯФ МГУ, Редьюс.

АЛМАК. Тула: Ю.Б. Подчуфаров, А.П. Матвеев, АНАЛИТИК, СМ-1410.

СПИН. Ленинград: Р.И. Сольницев, И.В. Ковтун, Фортран, ЕС.

АЫТРА-УЕКТРА. Ленинград: А.Б. Кикин, З.Е. Пейсах, Фортран, ЕС.

ММТ-1/У2. Киев: С.Я. Свиситунов и др., РЬ-1, ЕС.

БУМА. Москва: А.В. Яценко, РЬ-1, ЕС.

Пермь: А.Б. Бячков, В.А. Иванов и др., М.Ю. Дроздов, В.В. Маланин, Лисп-РеЬиое, ЕС, ПК.

Полимех-символ. Москва: Д.М. Климов и В.М.Руденко, Редьюс, ЕС, ПК.

Универсальный процессор. Брянск: Д.Ю. Погорелов, Фортран, ПК.

КАПСУЛА. Москва: М.Г. Зотов, М.М. Востостряков, П.В. Киргизбаев.

АММУСТ. Ленинград: В.А. Коноплев, численная система с СКА САВАГ В.П.Червонных.

4. Системы компьютерной алгебры для задач механики

Авторы принимали участие в рабочей группе по СКА для исследования динамики системы тел, к которым относятся СКА: АВТО-АНАЛИТИК, АЛГЕБРА-0,5, (также УСТОЙЧИВОСТЬ, АНФОР той же группы), ВИБРАН, КИДИМ, иркутские ДИНАМИКА, М1_Р и МЕХАНИК, АЫТРА-УЕКТРА, ММАЫв, ММТ-1/У2, АЛМАК, СПИН, БУМА, КАПСУЛА, Плимех-символ, Универсальный процессор, СКА Пермского университета, ПАС и ряд других. (По этим СКА см. Горький-84, Информатор-83, Ленинград-88,89, Вильнюс-84,90, Севастополь-91 и по фамилиям авторов в [1]).

Обсуждение СКА для исследования динамики системы тел (см. Ленинград-88, Ленинград-89-11, Вильнюс-90) показало дифференциацию внутри этой группы СКА: по сходным задачам и режимам работы. Назовем три группы с достаточно выраженной спецификой. Первая группа (задачи типа "проектирования") имеет дело с большим числом вариантов-моделей, среди которых производятся выбор, оптимизация параметров. Важна формализация модели для общения пользователя с системой (этапы 1, 2, 3 цикла А.А. Самарского), далее работа ведется численно. Во второй группе (моделирование в громоздких и сложных случаях) СКА выполняет этапы 1-4 цикла, в центре внимания оказывается эффективность счета - вид уравнений движения, представление данных и их преобразований, организация счета, контроль точности и т.п. Третья подгруппа -качественные исследования свойств уравнений и решений: нормализация, линеаризация, устойчивость, поиск стационарных решений и т.п. СКА используется на многих этапах. Главное -богатство и совершенство алгоритмов, в том числе специальных, их развитие. Каждая группа имеет ярких представителей, есть и промежуточные случаи.

К первой группе относим КИДИМ, КАПСУЛА (в задачах управления), СотрНЕР. Последняя СКА, для моделирования и оптимизации физического эксперимента, ярко демонстрирует роль СКА при формализации задачи. Поэтому мы ее рассматриваем вместе с механическими СКА. Ко второй группе относятся АММУСТ (с СКА САВАГ), ММАЫв, АНФОР. К третьей группе - иркутские

МЕХАНИК и ДИНАМИКА, Полимех-символ Института проблем механики АН, на которой отрабатывались механические алгоритмы. Систему Универсальный процессор первоначально можно было отнести к первой группе, но ее более поздний вариант соответствовал группе второй.

5. Конференции по компьютерной алгебре и публикации их трудов

Большую роль в развитии КА и систем КА играли конференции, семинары разного масштаба и уровня. При том, что большая часть публикаций по КА и ее применениям находилась в малодоступных сборниках трудов вузов, редко попадала в крупные журналы, роль обмена информацией на научных собраниях трудно переоценить. Отечественные разработки по КА опубликованы весьма неравномерно. Многие из них труднодоступны и нередко отражены лишь в материалах конференций, семинаров и совещаний. Приводим список значительной части научных конференций и сборников их материалов, в том числе, специально с механическим уклоном. Сюда же отнесены некоторые публикации, специально посвященные КА и СКА. Перед каждым из них приводим его сокращенное обозначение - для удобства ориентации в их множестве. Естественно, не все конференции, где актуальной была тема о КА, попали в наш список: на многих из них, особенно в ранние годы, КА занимала скромное место, хотя для развития КА они могли играть заметную роль. В качестве примеров можно назвать конференции «Методы трансляции» (Новосибирск, 1981 г.), «Диалог Человек-ЭВМ» (Протвино, 1983 г.) или 3-ю Четаевскую конференцию по устойчивости движения и механике (Иркутск, 1975 г.). Многие работы по применению КА докладывались на конференциях и семинарах по математике, механике или физике, где КА была представлена слабо, и терялись в общей массе работ.

Харьков-72. Вычислительная математика и вычислительная техника // Всесоюзный семинар. -Харьков, 1979. - Харьков: ФТИНТ АН УССР, 1972. - № 3. - 152 с.

Дубна-80. Аналитические вычисления на ЭВМ и их применение в теоретической физике // Материалы международного совещания. - Дубна, 1979. - Дубна: ОИЯИ, 1980. - 187 с.

Дубна-83. Аналитические вычисления на ЭВМ и их применение в теоретической физике. Материалы международного совещания. - Дубна, 1983. - Дубна: ОИЯИ, 1983. - 260 с. Информатор-83. Системы аналитических вычислений на ЭВМ (Аналитические пакеты прикладных программ) / М.В. Грошева, Г.Б. Ефимов, В.А. Брумберг, И.О. Бабаев, Н.Н. Васильев, Т.В. Иванова,

В.И. Скрипниченко, С.В. Тарасевич, И.Р. Аксельрод, Л.Ф. Белоус, Г.А. Долгов, А.В. Кузьмин, Р.В.

Кульветене, Г.П. Кульветис, М.В. Почтаренко, М.А. Чубаров. // Материалы семинара Института механики МГУ, 1981. - Информатор. ИПМ АН СССР, 1983. - № 1. - 65 с.

Вильнюс-84. Теория и практика автоматизированных систем аналитических преобразований. Тезисы республиканского совещания. - Вильнюс, 1984. - Вильнюс: ИПК СНХ Лит. ССР, 1984. -93 с.

Горький-84. Системы для аналитических преобразований в механике // Тезисы докладов Всесоюзной конференции. - Горький, 1984. - Горький: ГГУ, 1984. - 147 с.

Дубна-85. Аналитические вычисления на ЭВМ и их применение в теоретической физике // Материалы международного совещания. - Дубна, 1985. - Дубна: ОИЯИ, 1985. - 420 с. Аналитические ППП-88. Пакеты прикладных программ. Аналитические преобразования. - М.:

Наука, 1988. - 156 с.

Ленинград-88. Методы компьютерного конструирования моделей механики систем твердых тел // Материалы Всесоюзного рабочего совещания. - Л., 1988. - Препр. Ленингр. фил. Ин-та машиновед. АН СССР. - 1989. - № 16. - 32 с.

Киев-88. Системы аналитических вычислений (методы компьютерной алгебры) в механике деформируемого твердого тела // Доклады Всесоюзного совещания. - Киев, 1988. - КГУ. - Киев, 1990, (168 с.). Деп. УкрНИИНТИ 17.04.90. - № 732. - Ук90.

Ленинград-89. I,II - Методы компьютерного конструирования моделей классической и небесной механики-89. Секция I: Небесная механика // Тезисы докладов Всесоюзного совещания. - Л., 1989.

- Ин-т теор. астрон. АН СССР, 1989. - 67 с. Секция II: Теория и практика компьютерного конструирования моделей механики многозвенных технических систем // Материалы Всесоюзного совещания. - Л., 1989. - Препр. Ленингр. фил. Ин-та машиновед. АН СССР, 1989. - № 32. - 83 с. Вильнюс-90. Аналитические преобразования на ЭВМ в автоматизации научно-исследовательских работ // Всесоюзная конференция. - Вильнюс, 1990. - Вильнюс: ИПК СНХ ЛитССР, 1990. - 94 с. Ленинград-90. Алгоритмы и программы небесной механики // Всесоюзное совещание. - Л., 1990. -Л., Ин-т теор. астрон. АН СССР, 1990. - 80 с.

Дубна-90 - Computer Algebra in Physical Research // Conf. Computer Algebra Phys. Res. - Dubna, USSR, 1990. Memorial Volume for N.N. Govorun. - Singapore; New Jersey; London; Hong Kong: - World Scientific, 1991. - 453 p. // Сб. аннотаций. - Дубна, ОИЯИ, 1990. - 96 с.

Севастополь-91. Применение ЭВМ для решения задач механики // Тезисы научно-технической конференции. - Севастополь, 1991. - Киев: "Знание" Украины, 1991. - 55 с.

С.-Петербург-91,-92,-95. Компьютерные методы небесной механики // Тезисы докладов Всесоюзного совещания с международным участием. - СПб.,1991. - Институт теоретической астрономии АН СССР, 1991. - 101 с.; ИТА РАН, 1992. - 95 с.; 1995. - 208 с.

Киев-93. International Symposium on Symbolic and Algebraic Computation (ISSAC'93). July 6-8, 1993, Kiev, Ukraine. Abstracts, 1993, 321 p. + International Workshop "Computer Algebra Application". July 9, 1993, Kiev, Ukraine. Extended Abstracts. S-Petersburg, 1993. - 55 p.

St.-Pеtеrsburg-93, -94. International Congress on Computer Systems and Applied Mathematics (CSAM'93). 19-23 July 1993. Abstract. 1993. - 278 p. Section: "Computer Algebra Applications". International Conference on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL'94). 7-10 March, 1994. Abstracts. 1994. - 266 p.

Переславль Залесский -94, -95. International Workshop "New Computer Technologies in Control Systems", Pereslavl-Zalessky. 11-15 July, 1994; Abstracts. 1994. - 99 p.; 13-19 August, 1995; Abstracts.

- 81 p.

Bucharest-95. International Conference "Symbolic Calculations and Their Application in Fundamental Researches", Bucharest, 5-11 September 1995. Abstracts. ITA RAS, St.-Petersburg, 1995. - 48 p. Инфосфера-95. Международная конференция "Эволюция инфосферы" ("Информатика-95"). -Москва, 21-23 ноября 1995.

Москва, Институт механики МГУ - 1978, 1981, 1986-1990 гг. - Всесоюзные совещания по использованию САВ в задачах механики. (По материалам первого из них подготовлен

Информатор-83).

Минск-97. Компьютерная алгебра в фундаментальных и прикладных исследованиях // Международная конференция. - 1997. - Тезисы. Белорусский ГУ. - Минск, 1997.

Pragua-98 // 4-th Intern. IMACS conference on Applications of Computer Algebra - IMACS ACA'98, Prague, Aug. 9-11, 1998. - The History of Computer Algebra Applications. Session. Theses. Moscow, 1998. - 36 p.

Минск-99. Компьютерная алгебра в фундаментальных и прикладных исследованиях и образовании // Тезисы Второй Международной конференции. - Минск, 1999. - 108 с.

St-Petersburg-2000 // 6 Intern. IMACS confer. on Applications of Computer Algebra - IMACS ACA' 2000, St-Petersburg, July 2000. - Theses. St-Petersburg, 2000.

Dubna-2001. Computer Algebra and it's Application to Physics. - CAAP-2001. - Dubna, JINR, 2001.

б. Заключение

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

Работа поддержана грантами РФФИ 04-01-0385 и НШ.248.2006.1.

СПИСОК ЛИТЕРАТУРЫ

1. Ефимов Г.Б. и др. История использования аналитических вычислений в задачах механики / Г.Б. Ефимов, М.В. Г рошева, В.А. Самсонов. - М.: Издание ИПМ им. М.В. Келдыша РАН, 2005. - 87 с.

Стаття надійшла до редакції 07.11.2008