Algorithms in real algebraic geometry
Algorithms in real algebraic geometry
复制标题
DOI：
10.1007/3-540-33099-2
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
D. S. Arnon;B. Buchberger
中科院分区：
文献类型：
--
作者：
D. S. Arnon;B. Buchberger
由于一个真实的单变量多项式并不总是有真实的根，一个非常自然的算法问题是设计一种方法来计算给定多项式的真实的根的数量（从而决定它是否有任何根）。“真实的根计数问题”在本书所研究的几乎所有“真实的代数几何中的算法”中起着关键作用。许多数学是算法的，因为许多定理的证明提供了一个有限的过程来回答一些问题或计算一些东西。一个经典的例子是证明任何一对真实的一元多项式（P，Q）有一个最大公约数，通过给出一个有限的程序来构造（P，Q）的最大公约数，即欧几里得余项序列。然而，不同的程序来解决一个给定的问题，在多少计算所需要的每一个解决这个问题。为了理解“需要多少计算”的含义，人们需要更全面地理解算法是什么以及它的“复杂性”意味着什么。这将在本书第二部分的第8章开始时讨论。本书的第一部分（第1章至第7章）主要包括第二部分所需的数学背景。这方面的大部分背景已经为人所知，并出现在各种文本中。由于这些结果来自许多领域的数学，如几何，代数，拓扑和逻辑，我们认为它方便提供一个独立的，连贯的阐述这些主题。
Since a real univariate polynomial does not always have real roots, a very natural algorithmic problem, is to design a method to count the number of real roots of a given polynomial (and thus decide whether it has any). The “real root counting problem” plays a key role in nearly all the “algorithms in real algebraic geometry” studied in this book. Much of mathematics is algorithmic, since the proofs of many theorems provide a finite procedure to answer some question or to calculate something. A classic example of this is the proof that any pair of real univariate polynomials (P, Q) have a greatest common divisor by giving a finite procedure for constructing the greatest common divisor of (P, Q), namely the euclidean remainder sequence. However, different procedures to solve a given problem differ in how much calculation is required by each to solve that problem. To understand what is meant by “how much calculation is required”, one needs a fuller understanding of what an algorithm is and what is meant by its “complexity”. This will be discussed at the beginning of the second part of the book, in Chapter 8.The first part of the book (Chapters 1 through 7) consists primarily of the mathematical background needed for the second part. Much of this background is already known and has appeared in various texts. Since these results come from many areas of mathematics such as geometry, algebra, topology and logic we thought it convenient to provide a self-contained, coherent exposition of these topics.