Groebner基理论与其在一些优化问题上的应用

《Groebner基理论与其在一些优化问题上的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中南大学碛士学位论文AbstractKEYWORDSGroebnerbasis，reducing，propositionallogic，shortestpath，gateassignmentIII学位论文原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。作者签名：奎至墼

2、日期：旦年旦月兰日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。作者签名：监堕聊签恤日期：4年旦月赴日中南大学硕士学位论文第一章绪论1．1数学与计算第一章绪论在人类生活、经济建设和科技发展过程中，“计算’’始终都扮演着非常重要的角色。在对自然界和人类社会各种事物发展规律的研究中，当从定性分析过渡到定量分析时，就必然涉及计

3、算。人类的计算能力与计算工具密切相关，早期的计算主要是靠人的大脑再加上一些简单的计算工具来完成，计算效率低，可靠性也很差。电子计算机的出现大大地提高了人类的计算能力，从而也促进了科学技术的迅猛发展。最初的电子计算机多用一般规模的数值计算，因此计算机的出现也催生了计算数学——研究在计算机实现数值计算的理论与算法的数学分支。顾名思义，计算机是用于计算的机器，有了这样的机器，数学的计算问题就迎刃而解了。当然事情并没有我们那么简单，有许多理论问题和实际问题需要我们去考虑和解决。我们将数学计算分为两种：符号计算与数值之计算。数值计

4、算是指浮点数之间的运算。通常一个数值计算问题的解决需要通过很多步浮点运算来完成，因而会有累积误差。在使用数值计算时还需要考虑算法的稳定性，即输入数据的微小扰动是否会引起输出的大幅波动。在数值逼近时，又需要考虑逼近是否收敛以及收敛的速度。与数值计算不同，符号计算所处理的对象都是具有含义的抽象符号，主要研究如何进行这些符号之间的精确运算，因而没有误差。这些符号可以是整数、数学常数、有理函数、多项式理想，也可以是几何图形、逻辑公式和计算程序。理论和实际计算之间存在着巨大的鸿沟。对实际计算来说，一个好的算法是至关重要的，但实际可

5、行性问题不能容忍粗糙的算法。正是在这个问题下，为了扩充计算机应用领域，要求研究一种新的数学，这种数学的发展使得计算机有着越来越强大的生命力。这种新数学一般称为机械化数学【l】。它对实际可行性比对理论可能性更感兴趣。实际可行性甚至已经成为衡量数学进步的一个重要准则。在这种新数学中，算法的实际可行性往往是以牺牲它的完全性或可靠性为代价的。对于一个问题类，如果找不到实际可行的完全算法，很多时候仅仅给出实际可行的部分算法，即对问题类的某个子类给出实际可行的完全算法也有着重要意义；有时微不足道的出错概率可能大量节省计算所需的资源。

6、这些观念强烈地体现着数学发展动力的现实性的一面，它们在传统的所谓核心数学中却是难以立足的，是经常被忽略了的。数学所面临的这些新的机遇和挑战，促使数学的发展由抽象的、结构主义的道路转向具体的、构造性的、结合实际的、结合计算机发展的道路。中南大学硪士学位论文第一章绪论1．2计算祝代数代数学是数学的一个基本分支，是其他数学分支的基础。它所处理和研究的数学对象是抽象的代数符号与概念，如整数、有理数、多项式、理想等。从数学发展的历史来看，代数与算法有密切的联系。旱在吉希腊时代，在《几何原本》关于数论的论述中，Euchild就给出了

7、求两个正数的最大公因数的方法，这就是著名的Euchild算法。代数学的基本问题是解方程组问题。对于r／元一次方程组，可以用高斯消元法求解，对于一元二次、三次、四次方程可以找到公式解。这些方法都是构造性的方法，哥以用算法来实现。僵是对于一元五次和更高次的方程就找不到公式解了，对于多元多项式方程组更没有一般性的算法。为了解决这些问题，至19世纪以来，一种新的方法引入到了代数学的研究中，这就是“公理化方法"。“公理化方法’’采用抽象的证明，非构造性的论证研究代数问题，获得了巨大的成功。现在“公理纯方法”已经成为代数学的主要方法

8、。不过，数学家依然在寻找髂决某一类问题的算法解。例如Hilbert第十问题就是这类问题。这类问题的提出促进了现代数理逻辑的发展。在20世纪30年代，AlanTuring,AlonzoChurch首先提出了可计算性的概念，从数学上论证了算法的含义。KurtGodel证明了某些数学问题没有算法解。到了∞年代，Alfred