Система компьютерной алгебры

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

Символьные вычисления 

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

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

Некоторые также включают:
 создание и редактирование графики (создание компьютерных изображений, а также обработку сигналов и анализ изображений)
 синтез звука

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

История 
СКА появились в начале 1960-х и поэтапно развивались, в основном, в двух направлениях: теоретическая физика и создание искусственного интеллекта. Одной из ранних программ является, используемая и поныне FORM, из голландского института субатомной физики.

Первым успешным примером была новаторская работа Мартинуса Велтмана (позднее удостоенная Нобелевской премии по физике), который в 1963 создал программу для символьных вычислений (для нужд физики высоких энергий), которая была названа Schoonschip.

Используя LISP, Карл Энгельман в 1964 создал MATHLAB в рамках проекта MITRE (по исследованию искусственного интеллекта). Позже MATHLAB стал доступным в университетах для пользователей мейнфреймов PDP-6 и PDP-10 с такими ОС как TOPS-10 или TENEX. Сейчас он может быть всё ещё запущен на SIMH эмуляциях PDP-10. MATHLAB («mathematical laboratory») не стоит путать с MATLAB («matrix laboratory»), системой для численных расчётов, созданной 15 лет спустя в
университете Нью-Мехико.

Начиная с конца 1960-х первое поколение СКА включало в себя системы:
 MACSYMA (Джоэл Мозес),
 MATLAB (Массачусетский технологический институт),
 SCRATCHPAD (Ричард Дженкс, IBM), 
 REDUCE (Тони Хирн),
 SAC-I, позже SACLIB (Джорж Коллинз),
 MUMATH для микропроцессоров (Дэвид Стоутмайер) и его продолжатель
 DERIVE.
Эти системы были способны выполнять символьные вычисления: интегрирование, дифференцирование, факторизация.

Ко второму поколению, в котором стал применяться более современный графический интерфейс пользователя, относятся Maple (Кейт Геддес и Гастон Гоннет, университет Уотерлу, 1985 год) и Mathematica (Стивен Вольфрам), которые широко используются математиками, учёными и инженерами. Бесплатные альтернативы — Sage, Maxima, Reduce.

В 1987 Hewlett-Packard представила первый карманный аналитический калькулятор (HP-28), и в нём впервые для калькуляторов были реализованы организация алгебраических выражений, дифференциирование, ограниченное аналитическое интегрирование, разложение в ряд Тейлора и поиск решений алгебраических уравнений.

Компания Texas Instruments в 1995 году выпустила калькулятор TI-92 с революционными на тот момент расширениями CAS на основе программного обеспечения Derive. Этот калькулятор и последовавшие за ним, в том числе TI-89 и серии TI-Nspire CAS, выпущенный в 2007 году, продемонстрировали возможность создания сравнительно компактных и недорогих систем компьютерной алгебры.

В третьем поколении стал применяться категориальный подход и операторные вычисления:
 AXIOM, последователь SCRATCHPAD (NAG),
 MAGMA (Джон Кэннон, Сиднейский университет),
 MUPAD (Бенно Фуксштейнер, университет города Падерборн).

На 2012 год исследования в области систем компьютерной алгебры продолжаются в трёх направлениях: возможности по решению всё более широких задач, простота использования и скорость работы.

Разделы математики, используемые в системах компьютерной алгебры 
 Символьное интегрирование — алгоритм Риша
 Гипергеометрическое суммирование — алгоритм Госпера
 Предел (математика) — алгоритм Грюнтза (Gruntz)
 Факторизация полиномов. Для ограниченных областей используются алгоритм Берлекампа или алгоритм Кантора—Цассенхауза.
 Наибольший общий делитель — алгоритм Евклида
 Метод Гаусса
 Базис Грёбнера — алгоритм Бухбергера
 Аппроксимация Паде
 Лемма Шварца-Зиппела и проверка равенства полиномов
 Китайская теорема об остатках
 Диофантово уравнение
 Элиминация кванторов над действительными числами — метод Тарского
 Алгоритм Ландау
 Производные от элементарных и специальных функций (например, смотри неполная гамма-функция)

См. также 
 АНАЛИТИК

Примечания

Литература

Ссылки 
 Definition and workings of a computer algebra system
 Curriculum and Assessment in an Age of Computer Algebra Systems — From the Education Resources Information Center Clearinghouse for Science, Mathematics, and Environmental Education, Columbus, Ohio.
 STACK — система обучения и тестирования на основе компьютерной алгебры
 A collection of computer algebra systems

Математическое программное обеспечение