Loading AI tools
来自维基百科，自由的百科全书
数学和计算机科学中，[1]计算机代数或符号计算或代数计算，是研究、开发用于操作表达式等数学对象的算法与软件的科学领域。这通常被视为是运算科学的一个子领域，但运算科学一般基于近似浮点数的数值计算，而符号计算则使用含变量的表达式进行精确计算，其中变量没有赋值。 执行符号计算的软件系统称为计算机代数系统，“系统”暗示了软件的复杂性，其中至少包括一种在计算机中表示数学数据的方法、一种编程语言（通常异于用于实现的语言）、一种专门的内存管理器、一套供输入输出表达式的用户界面、一大套用于通常运算的子程序，如表达式简化、能实现链式法则、多项式因式分解、不定积分等等的求导算法。
计算机代数被广泛用于数学实验、设计数值程序所用的公式。纯数值方法失效时，计算机代数也可用于完整的科学计算，这见于公开密钥加密和一些非线性问题。
有些学者区分“计算机代数”（computer algebra）与“符号计算”（symbolic computation），后者指数学公式计算之外的符号计算。有人则用“符号计算”表示计算机科学方面的内容，而用“计算机代数”表示数学方面的内容。[2]
目前还没有计算机代数领域的专门学会，这一职能由计算机协会的特别兴趣小组（special interest group）SIGSAM承担。[3]
计算机代数领域有多个年会，最重要的是由SIGSAM定期主办的ISSAC（符号与代数计算国际研讨会）。[4]
有几种专门研究计算机代数的期刊，其中最重要的一种是由Bruno Buchberger于1985年创办的《符号计算》（Journal of Symbolic Computation）。[5]其他一些期刊也定期发表计算机代数方面的文章。[6]
由于数值软件在进行数值计算时的效率很高，因此在计算机代数中，通常用精确数据进行精确计算。这意味着即使输出规模很小，计算过程的中间数据也可能不可预测地增长，这种行为称为表达式膨胀（expression swell）。为解决这问题，数据表示和处理算法中有各种各样的方法。
数值计算最常用的数字系统是浮点数和大小固定的整数。由于表达式膨胀，这些系统都不便于计算机代数。[7]
因此，计算机代数使用的基数是数学整数，通常用某个底数（一般是机器字允许的最大底数）的无界有符序列表示。从整数可以定义有理数。
为高效算术运算编程是一项艰巨的任务，因此大多数免费的计算机代数系统和商业系统，如Mathematica和Maple都使用GMP库，它也因此成为事实上的标准。
除数字和变量外，每个表达式都可看做是跟着操作数序列的算符。在计算机代数软件中，表达式通常都这样表示，许多看似不是表达式的东西都可以这样表示和操作，非常灵活。例如，方程是以“=”为算符的表达式，矩阵可表为以“矩阵”为算符、行为操作数的表达式。
连程序也可以看做是以“过程”为算符、含至少两个操作数（参数列表与内容）的表达式，内容也是以“正文”为算符、以指令为操作数的表达式。反过来，表达式也可以看成程序：a + b可看做加法运算程序，参数是a、b。执行这个程序即对给定值的a、b表达式求值；若无给定值，则求值结果就是输入。
这种“延迟求值”在计算机代数中是最基本的。例如，等式中的“=”也是等式检验程序的名称：通常，等式求值结果仍是等式，但进行检验时，无论是用户通过“求布尔值”命令提出明确要求，还是系统在程序内部启动的自动检验，都会执行求值为布尔值的结果。
由于表达式操作数的规模无法预测，而且在过程中可能变化，因此操作数序列通常用指针序列（如Macsyma）或哈希表元素序列（如Maple）。
在表达式上直接应用关于x的求导基本规则，可得
一般来说，我们需要比这更简单的表达式，需要简化。
这一般通过重写逻辑完成。[9]有几类重写逻辑值得考虑，最简单的是总要缩减表达式，例如E − E → 0或sin(0) → 0。它们被系统地用于计算机代数系统。
加法、乘法这种有结合律的运算的混合会带来困难。处理结合运算的标准方法是，考虑其操作数是任意的，即将a + b + c表示为"+"(a, b, c)。因此a + (b + c)、(a + b) + c 都能简化为"+"(a, b, c)，展示为a + b + c。对于a − b + c这样的表达式，最简单的办法是系统地将−E、E − F、E/F分别改写为(−1)⋅E、E + (−1)⋅FE⋅F−1。换句话说，表达式的内部表示中，数字的表示没有减法、除法或一元负号。
加法和乘法的交换律也是一个难点。问题在于如何快速识别同类项。对很长的和或积来说，测试每对项的成本都很高。Macsyma排序了和与积的操作数，将同类项放在连续位置上，这样就可以轻松检测出来。Maple则使用了散列函数，输入同类项时会产生碰撞，由此可以立即合并。这样，计算中多次出现的子式就能被立即识别，并只储存一次，这样就避免了重复操作，从而节省内存并加快计算速度。
部分重写规则有时会增加表达式的大小，有些会减小，例如分配律和三角恒等式。具体来说，分配律允许、。这类重写规则没有很好的决策方式，一般交给用户决定。实现分配的计算机函数通常叫做“展开”，反向则是“因式分解”，需要一种非平凡算法，因此是计算机代数系统的一个关键功能。
在计算机中处理表达式时会出现一些基本数学问题。我们主要考虑多元有理函数，这不是严格的限制，因为表达式中出现的无理函数一旦被简化，通常都会被视为新的不定项，例如
视为和组成的多项式。
对表达式而言，有两种等价关系。语法相等指在计算机中的表示相等，这在程序中很容易测试；语义相等指两个表达式表示相同的数学对象，如
由理查森定理可知，若表达式中允许指数或对数，便可能不存在算法可判断代表数字的的两式是否语义相等。因此，只能对多项式和有理函数等部分表达式进行（语义）等价测试。
要测试两式是否登记爱，通常都不用特别设计算法，而是将表达式置于某个规范形中，或将差置于标准形中，再测试结果的语义等价。
在计算机代数中，“规范形”与“标准形”不是同义词。[10]“规范形”（canonical form）是指只有语法相等时才语义相等；“标准形”（normal form）是指只有语法上为0时，才在语义上为0.换句话说，0在标准形表达式中有唯一形式。
标准形是计算机代数的首选，有以下几个原因。首先，规范形的计算成本可能更高。例如，求多项式规范形必须要展开每个积，而标准形不需要（下详）。其次，与含根式的表达式类似，规范形（如果存在）取决于一些任意的选择，对于独立计算的两式可能是不同的。这就使得规范形的使用变得不切实际。
计算机代数起源于约1970年，当人们首次将闻名已久的算法应用于计算机时发现其效率非常低。[11]因此，研究者的主要工作是重新应用经典代数，以使其生效，并构造实现它们的高效算法。一个典型例子是计算多项式最大公约数，是简化分式必须的。令人惊讶的是，经典的辗转相除法对无穷域上的多项式效率很低，因此需要开发新的算法。线性代数的经典算法也如此。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
