算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课，越来越受到重视，CC2001和CCC2002都将“算法和复杂性”列为主领域，将算法设计策略、基本可计算性理论、P和NP问题类等算法设计技术和复杂性分析方法列为核心知识单元。

无论是计算科学还是计算实践，算法都在其中扮演着重要角色，算法被公认为是计算机科学的基石。翻开重要的计算机学术刊物，算法都占有一席之地，没有算法，计算机程序将不复存在。对于计算机专业的学生，学会读懂算法、设计算法，应该是一项最基本的要求，而发明算法则是计算机学者的最高境界。

提高学生的问题求解能力是高等教育的一个主要目标，在计算机科学的课程体系中，安排一门关于算法设计与分析的课程是非常必要的，因为这门课程能够引导学生的思维过程，告诉学生如何应用一些特定的算法设计策略来解决问题。学习算法还能够提高学生分析问题的能力。算法可以看作是解决问题的一类特殊方法——它不是问题的答案，而是经过精确定义的、用来获得答案的求解过程。因此，无论是否涉及计算机，特定的算法设计技术都可以看作是问题求解的有效策略。

本书将计算机经典问题和算法设计技术很好地结合起来，系统地介绍了算法设计技术及其在经典问题中的应用。通过同一算法设计技术在不同问题中的应用进行比较，牢固掌握算法设计技术的基本策略；通过不同的算法设计技术在同一问题中的应用进行比较，更容易体会到算法设计技术的思想方法，收到融会贯通的效果。所以，本书采用了模块化的设计思想，读者除了按本书组织的章节学习外，还可以将每种算法设计技术的问题提取出来，比较解决相同问题的不同解决方法。随着本书内容的不断展开，读者也将感受到综合应用多种算法设计技术有时可以更有效地解决问题。

全书共12章，第1章介绍了算法的基本概念和算法分析方法，第2章从算法的观点非形式化地介绍了NP完全理论，第3章~第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术，第12章基于图灵机计算模型介绍了计算复杂性理论。

书中所有问题均给出了若干应用实例，每章还设有一个实验项目，通过设计提高学生创造性思维的培养。每章均附有一篇阅读材料，以通俗易懂的笔触介绍了算法领域的一些最新研究成果，保证知识的先进性。书中所有算法均给出了伪代码，大部分算法还给出了C++描述。在算法介绍上，注重对问题求解过程的理解，注重算法设计思路和分析过程的讲解，体现了“授之以渔”的教学理念。

王涛老师收集和整理了本书的阅读材料，参加本书编写的还有胡明、许建潮、孙卫佳、逄焕利、刘钢、陈志雨等老师，研究生张倩、魏卓调试了本书的全部算法。算法设计与分析

由于作者的知识和写作水平有限，书稿虽几经修改，仍难免有缺点和错误。热忱欢迎同行专家和读者批评指正，使本书在使用中不断改进、日臻完善。

作者2006年2月