本站原创Michael Soltys
An Introduction to the
Analysis of Algorithms
2nd Edition
2012,212 p
Hardcover
ISBN9789814401159
Michael Soltys著
2010年图灵奖获得者、当时的微软剑桥研究院首席研究员托尼霍尔爵士（Tony Hoare）在与中国科学院相关研究人员座谈时曾提到：“在我看来,语言设计的目标应该是确保它能够使我们以简便的方法来写出那些正确的程序等评测一种语言,应当根据它最后写出来的程序的正确性来进行评估,这才是评测一个语言质量的科学准则.”霍尔爵士的主要贡献在于对程序正确性证明方面的研究.目前,从基础科学的角度看,计算机科学最为基础的部分在于如何保证算法和程序是正确的,或者简单来说计算过程能够按照我们预想的方向前进.目前无论是软件工程师还是计算机科学家都能举出很多由于计算机程序错误带来巨大损失的例子.例如2003年美国东北部大面积停电事故就是由于能源系统中的计算机程序错误所致.又如1996年美国阿里安五号（Ariane 5）火箭升空仅40秒后就由于内部浮点数错误而爆炸,造成5亿美元损失.虽然目前对于程序进行绝对意义上的正确性验证仍然很难,但是已经有很多理论工具可以帮助我们排除错误.本书就是这一领域的引论性著作,作者希望帮助读者理解程序背后的思想,并且展示如何证明它们的正确性.
全书分为6章,对程序正确性分析和证明进行了系统介绍.1.基础知识；2.贪心算法的相关分析；3.分治算法的分析；4.动态规划算法的分析；5.在线算法的分析；6.随机算法的分析.本书最后还有三个附录,对书中涉及到的数论和群论基础、关系代数,以及数理逻辑进行了回顾,从而方便读者参考.
本书是算法正确性分析和证明领域的一部专著.本书作者是加拿大麦克马斯特大学计算机系教授,其主要研究领域为计算复杂性、算法正确性分析和证明等.本书非常适合科研人员和研究生阅读参考.
张志斌,副研究员
（中国科学院计算技术研究所）
Zhang Zhibin,Associate Professor
（Institute of Computing Technology, CAS）