Компьютерная алгебра
-
Определение и терминология
- Компьютерная алгебра (символьные вычисления) — научная область, изучающая алгоритмы и программное обеспечение для манипулирования математическими выражениями.
- Символьные вычисления отличаются от научных вычислений, так как используют точные вычисления с переменными, а не числа с плавающей запятой.
- Термины «компьютерная алгебра» и «символьные вычисления» могут использоваться как синонимы, но иногда различаются.
-
Программное обеспечение и научное сообщество
- Системы компьютерной алгебры включают методы представления данных, пользовательский язык программирования, менеджер памяти и интерфейс.
- SIGSAM (Special Interest Group) занимается символическими и алгебраическими манипуляциями.
- Проводятся конференции, такие как ISSAC, и публикуются журналы, такие как Journal of Symbolic Computation.
-
Представление данных и числа
- В компьютерной алгебре используются точные вычисления с точно представленными данными, что может приводить к расширению выражений.
- Основные числа — целые числа математиков, представленные неограниченной последовательностью цифр.
- Для арифметических операций используется библиотека GMP.
-
Выражения и упрощение
- Выражения представляются как символы операторов и последовательности операндов.
- Упрощение выражений достигается с помощью правил перезаписи, таких как E − E → 0 и sin(0) → 0.
- Ассоциативные операции, такие как сложение и умножение, упрощаются с помощью правил перезаписи.
-
Математические аспекты
- Рассматриваются многомерные рациональные дроби, но иррациональные функции упрощаются как новые неопределенные.
- Существует два понятия равенства: математическое и логическое.
-
Синтаксическое и семантическое равенство
- Синтаксическое равенство — это равенство выражений в компьютере.
- Семантическое равенство — это когда два выражения представляют один и тот же математический объект.
- Теорема Ричардсона утверждает, что не существует алгоритма для проверки семантического равенства выражений с экспонентами и логарифмами.
-
Каноническая и нормальная формы
- Каноническая форма: выражения в канонической форме семантически равны тогда и только тогда, когда они синтаксически равны.
- Нормальная форма: выражение в нормальной форме семантически равно нулю только в том случае, если оно синтаксически равно нулю.
- Нормальные формы предпочтительнее в компьютерной алгебре из-за их меньшей вычислительной сложности и независимости от произвольных вариантов.
-
История компьютерной алгебры
- Ранние системы компьютерной алгебры, такие как ENIAC, управлялись людьми.
- Джон Маккарти исследовал символьные выражения с помощью языка Lisp, что способствовало развитию Project MAC и Стэнфордской лаборатории искусственного интеллекта.
- Первые попытки в символьных вычислениях столкнулись с проблемами неэффективности алгоритмов.
-
Проблемы и решения
- Исследователи пересмотрели классическую алгебру для повышения эффективности алгоритмов.
- Алгоритмы, такие как алгоритм Бухбергера и алгоритм Кантора–Зассенхауса, используются для различных задач.
-
Современные алгоритмы
- Алгоритм Бухбергера: находит базис Гребнера.
- Алгоритм Кантора–Зассенхауса: факторные многочлены над конечными полями.
- Алгоритм Faugère F4: находит базис Гребнера.
- Алгоритм Госпера: находит суммы гипергеометрических слагаемых.
- Алгоритм завершения Кнута–Бендикса: для переписывания систем правил.
- Алгоритм многомерного деления: для многочленов с несколькими неопределенностями.
- Алгоритм кенгуру Полларда: алгоритм для решения задачи дискретного логарифмирования.
- Многочленное деление в длину: алгоритм деления многочлена на другой многочлен.
- Алгоритм Риша: алгоритм для математической операции неопределенного интегрирования.
-
Связанные области
- Автоматизированное средство доказательства теорем.
- Компьютерное доказательство.
- Вычислительная алгебраическая геометрия.
- Система компьютерной алгебры.
- Дифференциальный анализатор.
- Средство проверки подлинности.
- Средство проверки моделей.
- Символьно-числовые вычисления.
- Символьное моделирование.
- Символический искусственный интеллект.