计算机算法设计与分析 (2010 年度畅销榜NO.11358 )

算法设计与分析是计算机科学的主要研究领域之一。本课程是计算机专业和其他相关专业高年级本科生、研究生的一门重要专业基础课程。\r\n\r\n 它的主要目的是讲授在计算机应用中常常遇到的重要的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术。\r\n\r\n 本书共12章，取材先进、内容实用、重点突出、少而精、难易适当，便于自学。全书以非数值算法为主，兼顾数值算法；串行算法和并行算法并重；在附录中介绍并行MULTIPASCAL系统的使用方法，并给出一个并行程序实例。\r\n\r\n 本书可供计算机、管理信息系统、系统工程、应用数学和计算数学等专业本科生、研究生作为教材使用，也可供从事计算机科学研究、汁算机软件开发的工程技术人员参考。\r\n\r\n \r\n
\r\n

第1章 引论 \r\n\r\n 1. 1 算法分析的基本概念和理论 \r\n\r\n 1. 2 搜索有序表算法的分析 \r\n\r\n 练习1 \r\n\r\n 第2章 算法设计技术和分析方法 \r\n\r\n 2. 1 算法设计技术 \r\n\r\n 2. 1. 1 分治方法 \r\n\r\n 2. 1. 2 回溯法 \r\n\r\n 2. 1. 3 贪心法 \r\n\r\n 2. 1. 4动态规划法 \r\n\r\n 2. 1. 5分支限界法 \r\n\r\n 2. 2 递归方程解的展开方法 \r\n\r\n 2. 3 一类特殊递归方程的解 \r\n\r\n 2. 4毋函数方法 \r\n\r\n 练习2 \r\n\r\n 第3章 计算的算术复杂性 \r\n\r\n 3. 1 大整数相乘算法 \r\n\r\n 3. 2 矩阵乘积算法 \r\n\r\n 3. 2. 1 Winograd矩阵乘法 \r\n\r\n 3. 2. 2 Strassen矩阵乘法 \r\n\r\n 3. 3 判定素数的算法 \r\n\r\n 3. 4 RSA数据加解密算法 \r\n\r\n 3. 5 HASH函数和数字签名 \r\n\r\n 3. 6 数据压缩技术 \r\n\r\n 3. 6. 1 ASCII码压缩方法 \r\n\r\n 3. 6. 2 模式置换压缩方法 \r\n\r\n 3. 6. 3 配压缩技术 \r\n\r\n 练习3 \r\n\r\n 第4章 排序算法 \r\n\r\n 4. 1 冒泡排序算法 \r\n\r\n 4. 2 基于比较的排序时间复杂性下界 \r\n\r\n 4. 3 分配排序技术 \r\n\r\n 4. 3. 1 基数排序算法 \r\n\r\n 4. 3. 2 分配分块排序算法 \r\n\r\n 4. 3. 3 分配和归并混合排序算法 \r\n\r\n 4. 3. 4 循环分组散列和循环两路归并排序算法 \r\n\r\n 4. 4 基于映射的汉字字符串排序方法 \r\n\r\n 练习4 \r\n\r\n 第5章 字符串匹配技术 \r\n\r\n 5. 1 简单的字符串匹配算法 \r\n\r\n 5. 2 Knuth-Morris-Pratt串匹配算法 \r\n\r\n 5. 3 改进的Knuth-Morris-Pratt串匹配算法 \r\n\r\n 5. 4 Boyer-Moore串匹配算法 \r\n\r\n 5. 5 改进的Boyer-Moore串匹配算法 \r\n\r\n 5. 6 KARP-RABIN串匹配随机算法 \r\n\r\n 5. 7 字符串近似匹配简介 \r\n\r\n 练习5 \r\n\r\n 第6章 并行计算基础 \r\n\r\n 6. 1 并行处理技术及其应用 \r\n\r\n 6. 2 并行计算机分类 \r\n\r\n 6. 2. 1 Flynn分类法 \r\n\r\n 6. 2. 2 Handler分类法 \r\n\r\n 6. 2. 3 按机器体系结构分类 \r\n\r\n 6. 3 并行计算机的处理器互联方式 \r\n\r\n 6. 3. 1 一维线性阵列结构 \r\n\r\n 6. 3. 2 二维网格结构 \r\n\r\n 6. 3. 3 树结构 \r\n\r\n 6. 3. 4 树网结构 \r\n\r\n 6. 3. 5 超立方连接结构 \r\n\r\n 6. 3. 6 g维网格结构 \r\n\r\n 6. 3. 7 洗牌—交换网络 \r\n\r\n 6. 3. 8 蝶形结构 \r\n\r\n 6. 4 并行计算模型 \r\n\r\n 6. 4. 1 SIMD互联网络模型 \r\n\r\n 6. 4. 2 共享存储的SIMD模型 \r\n\r\n 6. 4. 3 MIMD并行计算模型 \r\n\r\n 6. 5 并行计算的若干理论 \r\n\r\n 6. 5. 1 Grosch定律 \r\n\r\n 6. 5. 2 Minsky猜想 \r\n\r\n 6. 5. 3 Amdahl定律 \r\n\r\n 6. 6 并行算法基础 \r\n\r\n 6. 6. 1 并行算法的基本概念 \r\n\r\n 6. 6. 2 并行算法的复杂性 \r\n\r\n 6. 6. 3 并行算法的形式描述 \r\n\r\n 6. 6. 4 并行算法设计的基本技术 \r\n\r\n 练习6 \r\n\r\n 第7章 程序的基本并行特性 \r\n\r\n 7. 1 多处理机系统的并行程序设计 \r\n\r\n 7. 2 程序并行性的条件 \r\n\r\n 7. 2. 1 数据和计算资源的关系 \r\n\r\n 7. 2. 2 计算机硬件和软件的并行性 \r\n\r\n 7. 3 并行程序的划分和调度 \r\n\r\n 7. 3. 1 计算粒度规模和通信时延 \r\n\r\n 7. 3. 2 粒度的组合和调度 \r\n\r\n 练习7 \r\n\r\n 第8章 并行求和算法 \r\n\r\n 8. 1 SIMD—MC2二维网格机器上的同步并行求和算法 \r\n\r\n 8. 2 SIMD—CC超立方机器上的同步并行求和算法 \r\n\r\n 8. 3 SIMD—SE洗牌交换网络上的同步并行求和算法 \r\n\r\n 8. 4 SIMD—SM机器上的同步并行求和算法 \r\n\r\n 8. 5 MIMD—SM机器上的异步并行求和算法 \r\n\r\n 练习8 \r\n\r\n 第9章并行排序 \r\n\r\n 9. 1 线性阵列上的奇偶转置排序同步并行算法 \r\n\r\n 9. 2 线性阵列上的奇偶归拆排序同步并行算法 \r\n\r\n 9. 3 树机器上的最小抽取排序同步并行算法 \r\n\r\n 9. 4 树机器上的捅分配和归并排序同步并行算法 \r\n\r\n 9. 5 共享存储器并行系统上的Vd5mt归并和排序同步并行算法 \r\n\r\n 9. 5. 1 Valiant归并同步并行算法 \r\n\r\n 9. 5. 2 Valiant排序同步并行算法 \r\n\r\n 9. 6 共享存储MIMD-TC模型上的快速排序异步并行算法 \r\n\r\n 9. 7 MIMD-SM机器上基于散列技术的异步并行排序算法 \r\n\r\n 练习9 \r\n\r\n 第10章 并行查找与并行匹配 \r\n\r\n 10. 1 共享存储器并行系统上范围查找同步并行算法 \r\n\r\n 10. 2 共享存储器并行系统上任意两序列公共元素的同步并行查找算法 \r\n\r\n 10. 3 共享存储器并行系统上KARP-RABIN串匹配并行算法 \r\n\r\n 练习10 \r\n\r\n 第11章 数值并行算法 \r\n\r\n 11. 1 SIMD-SM机器上基于LDU分解的方程组求解同步并行算法 \r\n\r\n 11. 2 MIMD-SM机器上的矩阵相乘异步并行算法 \r\n\r\n 11. 3 SIMD-SM机器上非线性方程求根同步并行算法 \r\n\r\n 练习11 \r\n\r\n 第12章 数据库操作并行算法 \r\n\r\n 12. 1 选择. 投影和集合操作并行算法 \r\n\r\n 12. 1. 1 并行选择算法 \r\n\r\n 12. 1. 2 并行投影算法 \r\n\r\n 12. 1. 3 关系元组集合操作并行算法 \r\n\r\n 12. 2 并行连接算法 \r\n\r\n 12. 2. I 并行嵌套循环连接算法 \r\n\r\n 12. 2. 2 基于排序和合并方法的并行连接算法 \r\n\r\n 12. 2. 3 基于Hash方法的并行连接算法 \r\n\r\n 练习12 \r\n\r\n 附录 并行MULTIPASCAL系统简介及并行程序实例 \r\n\r\n 附录1. 1 并行MULTIPASCAL系统简介 \r\n\r\n 附录1. 1. 1 并行MULTIPASCAL系统的上机操作步骤 \r\n\r\n 附录1. 1. 2 并行MULTIPASCAL从部分语句简介 \r\n\r\n 附录1. 2 基于散列技术的(m,n)选择并行算法及程序实例 \r\n\r\n 附录1. 2. 1 并行散列选择算法的设计 \r\n\r\n 附录1. 2. 2 并行散列选择程序实例 \r\n\r\n 参考文献 \r\n\r\n \r\n
\r\n

算法设计与分析是计算机科学的一个主要研究领域. 本课程是计算机. 管理信息系统. 系统工程. 应用数学和计算数学等专业高年级学生和研究生的二门重要专业课程. 它的主要目的是讲授在计算机应用中常常遇到的实际问题的解法, 讲授设计和分析各种算法的基本原理. 方法和技术, 以培养读者在选择或设计一个算法时, 思考下列问题：这个算法是否有效?这个算法有多好?是否还有更好的算法?用什么方法和技巧去获得更好的算法?从而使得所设计算法的时空复杂性最优, 进而为编写高效的程序. 开发优秀软件奠定基础.

考虑到与离散数学. 程序设计. 计算方法. 数据结构等前驱课程的联系与衔接, 本书兼顾数值和非数值算法, 以非数值算法为主, 并力争做到取材先进. 内容实用. 重点突出. 少而精, 便于自学, 并注意收录一些典型问题的最新研究成果. 期望读者通过本课程的学习, 在教师的指导下能较快地进入某个研究领域, 接受基础研究和应用基础研究的初步训练, 培养独立开展科研工作的能力和创新意识.

目前计算机正朝着微型化. 并行化. 网络化. 智能化和多媒体化方向发展. 并行分布计算技术正发挥着传统的串行计算技术所不能比拟的越来越重要的作用. 因此, 除了介绍串行算法之外, 本书特别用较大的篇幅介绍并行算法设计技术及其分析方法.

从方便读者理解的目的出发, 书中的算法用类PASCAL语言, 或者用类C语言, 也可以用接近自然语言的方式描述. 读者可根据实际情况, 用PASCAL或者C语言适当加以修改即可上机实现, 对于并行算法部分, 可采用支持多线程程序设计的JAVA语言或者采用并行删U叮)ASCAI系统等编程上机实现.

本书由苏德富教授和钟诚副教授编写, 并由钟诚统稿和配置习题. 全书共分12章. 第l章介绍算法分析的基本概念和基本理论, 详细分析了搜索有序表二分查找算法的平均复杂性和最坏情形复杂性, 第2章介绍设计算法的基本技术和分折算法复杂性的基本方法, 第3章讨论若干经典数值计算问题, 包括大整数相乘和矩阵乘积算法, 以及数据加解密算法. 数字签名和数据压缩技术, 第4章主要介绍基于映射(散列)的排序算法和汉字字符串的排序方法, 第5章讲授字符串精确匹配和近似匹配技术, 重点剖析一些典型. 能启迪人们思维的算法设计思想, 第6章介绍并行计算基础知识和并行处理技术的应用, 第7章主要讲授并行程序的特性, 包括并行计算可扩展性. 计算粒度. 程序划分的条件. 并行软件和硬件的匹配等问题, 第8章从数据求和问题人手, 讨论同步和异步并行求和算法的设计与分析方法, 第9章阐述并行排序技术, 其中展示了许多著名串行排序算法如何转换成并行算法, 这对读者开发新的并行算法会有帮助, 第10章介绍若干查找和串匹配问题的并行化算法, 以拓宽读者的视野, 第ll章讨论一些数值问题的并行算法, 第12章重点介绍数据库操作的并行选择算法. 并行投影算法. 并行集合操作算法和并行连接算法. 最后, 在附录中简介并行MULTIPASCAL系统及其使用方法, 同时给出一个基于散列技术的(m, n)选择并行算法和相应的并行程序实例.

编者自20世纪80年代中后期以来, 一直从事算法设计与分析. 并行计算等领域的学习. 教学和研究. 本书在授课讲义基础上, 参考国内外有关论著编写而成. 在编写过程中得到中国科技大学计算机系博士生导师. 国家(合肥)高性能计算中心主任陈国良教授, 武汉大学软件工程国家重点实验室博士生导师康立山教授, 复旦大学计算机系博士生导师朱洪教授和暨南大学计算机系博士生导师苏运霖教授的关心和指导; 国防科技大学计算机学院教授殷建平博士后也提出了宝贵的建议, 在此深表感谢.

本书能在21世纪的新千年里顺利出版, 我们要衷心感谢广西重点教材建设基金和广西大学的资助以及电子工业出版社和责任编辑赵家鹏老师的热情鼓励与大力帮助. 同时, 本书第二作者也要感谢他的家人的充分理解和支持, 感谢他的研究生刘峻. 廖永. 肖立国帮助整理部分文档和绘制部分图表.

全国高校计算机教学指导委员会和中国计算机学会教育专业委员会制订的＜计算机学科教学计划2000＞强调要加强计算机科学与技术专业学生的算法设计与分析能力的培养. 我们希望本书的出版有助于推动我国(计算机算法设计与分析)课程教学的普及和发展.

由于编者学识有限, 加之编写时间较紧, 书中如有不妥之处, 敬请读者批评指正, 以臻完善.

编著者

2000. 6