算法设计与分析

出版时间：2011-6  出版社：清华大学  作者：温敬和 编  

前言

　  前言　  作者1982年2月毕业于上海交通大学，2010年1月退休，在上海第二工业大学工作了近三十年。在此期间，主要从事“编译程序”和“算法”这两门学科的教学和科研。2005年4月清华大学出版社出版了由本人编著的《编译原理实用教程》，该书至今仍用于我校和国内其他普通高等院校“编译原理”课程的教学。相对于“编译原理”课程而言，“算法设计与分析”课程教材的数量不多，辅助教材更少。多年来，我校“算法设计与分析”课程使用的是由电子工业出版社出版的《算法设计技巧与分析》一书，作者是国际著名算法专家M.H.Alsuwaiyel［沙特］。该书涉及范围广、难度大，可称得上是“算法设计与分析”课程的经典教材。使用该教材，在教学中存在一定难度。为了提高“算法设计与分析”课程的教学水平，同时也想抛砖引玉和同行教师交流教学经验，退休后打算根据自己的教学心得写一本该书的辅助教材。在清华大学出版社的大力支持下，我的愿望终于得以实现。　  根据课程教学要求，本书对应《算法设计技巧与分析》中的7章。它们是：第1章 算法分析基本概念，第4章 堆和不相交集数据结构，第5章 归纳法，第6章 分治，第7章 动态规划，第8章 贪心算法和第13章 回溯法。主要内容为：各章的主要算法（包括算法说明、算法伪代码描述、算法分析和算法程序实现）、习题解答和上机题。在书中出现的所有源程序，可以从清华大学出版社指定网站下载。在习题答案中，凡是用伪代码描述的具有一定难度的答案，都有相应的源程序，也可以从清华大学出版社指定的网站下载。另外，由本人编写的“算法设计与分析”课程的电子教案可从“中国高等学校教学资源网”下载。　  本书既可作为“算法设计与分析”课程的主讲教材，也可作为“算法设计与分析”课程的辅助教材。上海第二工业大学教师闫季鸿参与了各章习题答案的编写，原上海第二工业大学学生董淑芳参与了各章上机题的编写。　  由于时间所限，书中存在错误和遗漏之处在所难免，希望广大读者批评指正。　  温敬和 2011年3月

内容概要

　　本书根据课程教学要求编写，内容包括算法分析基本概念、堆和不相交集数据结构、归纳法、分治法、动态规划法、贪心法和回溯法。各章的主要算法（包括算法说明、算法伪代码描述、算法分析和算法实现程序）、习题解答和上机题以及书中出现的所有源程序均可以从清华大学出版社网站(www.tup.com.cn)下载。
　　本书既可作为“算法设计与分析”课程的主讲教材，也可作为其辅助教材，还可以作为软件工程师学习算法设计的参考教材。

书籍目录

第1章 算法分析基本概念
　1.1 主要算法及程序实现
　　1.1.1 二分搜索
　　1.1.2 合并两个已排序的表
　　1.1.3 选择排序法
　　1.1.4 插入排序法
　　1.1.5 自底向上合并排序法
　1.2 习题答案
　1.3 上机实习题
　　1.3.1 选择排序法实现
　　1.3.2 自底向上合并排序法实现
第2章 堆和不相交集数据结构
　2.1 主要算法及程序实现
　　2.1.1 堆上的运算
　　2.1.2 创建堆
　　2.1.3 堆排序法
　　2.1.4 Union-Find算法
　2.2 习题答案
　2.3 上机实习题
　　2.3.1 插入排序法实现
　　2.3.2 堆排序法实现
第3章 归纳法
　3.1 主要算法及程序实现
　　3.1.1 选择排序法
　　3.1.2 插入排序法
　　3.1.3 基数排序法
　3.2 习题答案
　3.3 上机实习题
　　3.3.1 基数排序法实现
　　3.3.2 汉诺塔问题实现
第4章 分治法
　4.1 主要算法及程序实现
　　4.1.1 寻找最大值和最小值
　　4.1.2 二分搜索
　　4.1.3 合并排序法
　　4.1.4 寻找中项和第k小元素
　　4.1.5 划分算法
　　4.1.6 快速排序法
　4.2 习题答案
　4.3 上机实习题
第5章 动态规划法
　5.1 主要算法及程序实现
　　5.1.1 最长公共子序列问题
　　5.1.2 所有点对的最短路径问题
　　5.1.3 背包问题
　5.2 习题答案
　5.3 上机实习题
　　5.3.1 最长公共子序列问题实现
　　5.3.2 所有点对的最短路径问题实现
　　5.3.3 背包问题实现
第6章 贪心法
　6.1 主要算法及程序实现
　　6.1.1 最短路径问题
　　6.1.2 最小耗费生成树（Kruskal算法）
　　6.1.3 最小耗费生成树（Prim算法）
　　6.1.4 文件压缩
　6.2 习题答案
　6.3 上机实习题
　　6.3.1 最短路径问题实现
　　6.3.2 最小耗费生成树（Prim算法）实现
　　6.3.3 Huffman算法实现
第7章 回溯法
　7.1 主要算法及程序实现
　　7.1.1 图的3着色问题
　　7.1.2 4皇后问题
　7.2 习题答案
　7.3 上机实习题
　　7.3.1 图的3着色问题实现
　　7.3.2 4皇后问题实现
参考文献

章节摘录

版权页：插图：

用户评论 (总计5条)

•   自从看了温敬和老师的《编译原理实用教程》一书后，我就十分喜欢温老师写书的风格！这书太尼玛好了！配合着[沙特]《算法设计技巧与分析》一起看，真是再晦涩难懂的东西也变得简单！书中还提供习题答案，让人复习起来倍感亲切温暖！
•   挺好的专业用书
•   有效，实用！！！
•   简单，实用，选修课必备书籍。
•   本书与《算法设计技巧与分析》（电子工业出版社）配套，如果你觉得《算法设计技巧与分析》太难，可考虑先阅读或使用本书。作者
  又及：本人买书的目的是送人