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