算法设计与分析

出版时间：2003-12  出版社：武汉理工大学出版社  作者：刘任任 编  页数：156  
Tag标签：无  

前言

　　早在20世纪70年代，计算机科学巨匠、图灵奖获得者D.E.Knuth曾指出，计算机科学就是研究算法的学问。因此，算法设计与分析是计算机科学的核心问题。计算机科学是一项创造性的思维活动，其教育必须面向设计，而计算机算法设计与分析正是面向设计的、处于核心地位的教育课程。它应当立足于基础课和专业基础课坚实的基础之上，其目的是通过对计算机领域的许多常见问题和有代表性算法的学习、研究、了解，掌握算法设计的一些主要方法，提高分析的基本技能和某些技巧，达到能独立设计算法和对给定算法进行复杂度分析的初级水平。无论从事计算机专业哪一方面的工作，这些知识都是必备的。特别是对计算机系统结构、系统软件和应用软件等专业，更是必不可少的专业知识。　　从应用范围来看，算法可以分为数值算法和非数值算法两大类；从工作方式来看，算法又可以分为串行算法和并行算法两大类。因为数值算法在《数值分析》中介绍得较多，而本书作为《数据结构》的后继课程，主要讲述非数值算法。由于篇幅和时间的限制，本书暂只介绍串行算法。本书中的算法均用自然语言来表述其思路，再以类C语言来描述，力求简洁明了、通俗易懂。考虑到有关排序、图、集合的算法在《数据结构》课程中已有较详细的讲述，本书不再重复。　　本书共分为1l章。第1章介绍了算法的基本概念，并对分析算法的准则、描述算法的语言以及本书用到的基本数据结构作了简要的阐述。第2章至第6章分别介绍了常用的一些非数值算法的设计方法，它们分别是分治法、贪心法、动态规划法、回溯法和分支限界法。这些都是一些通用的算法，可应用于大部分问题之中，所以本书选取了一部分有代表意义的问题来进行讲解。第7章主要介绍了字符串的三种匹配算法，之所以将其单独列为一章，主要是考虑到目前计算机处理的数据类型中，字符串占有相当大的比重，它的处理比一般的数据类型更为复杂。而设计一个理想的匹配算法，需要坚实的理论基础和高超的设计技巧。第8章介绍了NP完全问题和近似算法。NP完全问题是20世纪70年代提出的理论计算机科学中的前沿课题，而近似算法则是目前针对NP完全问题行之有效的方法。第9章概率算法是一类比较特殊的算法，它相对于其他确定型的算法有其独特的优势和应用范围。第10章介绍了目前最常用的几类通用型数据压缩算法，数据压缩应用广泛，极具实用价值。

内容概要

　　算法的基本概念及相关基本知识；常用的一些非数值算法的设计方法（分治法、贪心法、动态规划法、回溯法和分支限界法）；字符串的匹配算法；NP完全问题的近似算法；概念算法；目前常见的通用型数据压缩算法；公钥密码学的基础。　　《算法设计与分析》可作为计算机科学与技术专业的本科生教材；也可供有关计算机工作者阅读。

书籍目录

1 引论1.1 什么是算法1.2 分析算法的准则1.3 描述算法的语言和基本的数据结构思考题与习题2 分治与递归2.1 折半查找2.2 搜索二叉排序树2.2.1 二叉排序树的定义2.2.2 搜索二叉排序树2.2.3 向二叉排序树中插入新结点2.2.4 从二叉排序树中删除一个结点2.2.5 平衡的二叉排序树2.3 快速排序2.4 归并排序2.5 大整数乘法2.6 矩阵乘积的Strassen算法思考题与习题3 贪心算法3.1 最小生成树3.2 单源最短路径3.3 旅行商问题思考题与习题4 动态规划4.1 动态规划在最短路径中的应用4.2 矩阵连乘积问题4.3 求最长公共子序列4.4 凸多边形的最优三角形剖分4.5 旅行商问题思考题与习题5 回溯法5.1 树的深度优先遍历5.2 数的全排列5.3 八皇后问题5.4 0-1背包问题5.5 旅行商问题思考题与习题6 分支限界法6.1 最小耗费搜索6.2 背包问题6.3 旅行商问题思考题与习题7 字符串7.1 串概念及简单串匹配算法7.1.1 字符串的概念7.1.2 串的匹配7.1.3 简单串模式匹配算法7.2 Knuth-Morris-Pratt（KMP）算法7.2.1 KMP算法7.2.2 改进的KMP算法7.3 Boyer.Moore算法7.3.1 Boyer-Moore算法7.4 Karp-Rabin串匹配随机算法思考题与习题8 NP完全问题与近似算法8.1 确定型图灵机8.2 非确定型图灵机8.3 Cook定理和NP完全理论8.3.1 NP完全理论8.3.2 Cook定理8.3.3 若干NP完全问题8.4 。NP完全问题的近似算法8.4.1 0-1背包问题8.4.2 旅行商问题思考题与习题9 概率算法9.1 随机抽样9.2 判定素数的概率算法9.2.1 Fermat素数测试法9.2.2 MiLler-Rabin素数判定概率算法思考题与习题10 数据压缩算法10.1.ASCII码压缩算法10.2 哈夫曼编码10.3 字典法10.4 LZ算法10.4.1 LZ77算法10.4.2 LZ78算法10.4.3 LZW算法思考题与习题11 公钥密码学基础11.1 公钥密码体制的应用与基本思想11.2 背包公钥密码11.3 RSA公钥密码体制10.4 数字签名和Hash算法思考题与习题参考文献