计算机算法设计与分析

内容简介

　　算法设计与分析是计算机科学的主要研究领域之一。本课程是计算机专业和其他相关专业高年级本科生、研究生的一门重要专业基础课程。它的主要目的是讲授在计算机应用中常常遇到的重要的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术。本书共12章，取材先进、内容实用、重点突出、少而精、难易适当，便于自学。全书以非数值算法为主，兼顾数值算法；串行算法和并行算法并重；在附录中介绍并行MULTIPASCAL系统的使用方法，并给出一个并行程序实例。本书可供计算机、管理信息系统、系统工程、应用数学和计算数学等专业本科生、研究生作为教材使用，也可供从事计算机科学研究、计算机软件开发的工程技术人员参考。适合计算机科学技术飞速发展，面向新世纪高校教学改革和人才培养的需求。匹配“计算机学科教学计划2000”的要求，是必修课程之五。以非数值计算的计算机算法为主，兼顾数值计算的计算机算法。顺序（串行）算法和并行算法并重，反映时代特色。算法描述和分析详尽，许多算法稍加修改即可上机实现。“计算机算法设计与分析”是程序设计、开发优秀软件的基础。

作者简介

暂缺《计算机算法设计与分析》作者简介

图书目录

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