目 录

第一章绪论

§1 引言

§2 什么是算法

§3 算法的效率

§4 若干符号和它们的意义

习题

第二章搜索技术

§1 引言

§2 DFS搜索法

§3 图的算法

§4 BFS搜索法

§5 α-β剪枝术

§6分支定界法

§7 同顺序加工任务安排问题

*§8 搜索技术在整数规划中的应用

*§9 分支定界法在解整数规划问题中的应用

§10字符串匹配

§11网络流问题——Ford-Fulker-son算法

§12 Edmonds-Karp修正算法及其它

习题

第三章动态规划

§1 最短路径问题

§2 最佳原理

§3 旅行商问题的动态规划解法

§4 矩阵链乘积问题

§5 最长公共子序列

§6 图的两点间最短路径

§7 其它举例

习题

第四章优先策略和分治策略

§1 优先策略举例——最短树的Kruskal算法

§2 求最短树的Prim算法

§3 求距离的Dijkstra算法

§4 Huffman树

§5 安排问题

§6 分治策略的基本思想

§7 Strassen矩阵乘法

§8 三个前苏联人的算法及Wino-grad算法

§9 FFT运算

§10卷积

*§11数论变换

*§12线性规划的分解原理

习题

第五章分类与查找

§1 分类和它的下界估计

§2 二分树的性质

§3 递选分类法

§4 下溢分类法

§5 归并分类法

§6 快速分类法

§7堆集分类法

§8 Shell分类法

§9 Ford-Johnson分类法

§10基数分类法

§11外存分类法

§12置换选取段的构造

§13三条带的外存归并法

§14阶式归并法

§15分类网络

§16 0-1原理

§17归并网络

§18 Batcher奇偶归并网络

§19求第k个元素

习 题

第六章均衡树等若干数据结构

§1 最佳二分树

§2 AVL树之一：关于高度均衡的二分树

§3 2-3树和2-3-4树

§4 BR树

§5 B－树

§6 混列

§7双重混列

习题

它

§1 概率算法举例

第七章概率算法、并行算法及其

§2 素数生成的概率算法

§3 并行计算机和并行算法若干基本概念

§4 求第k个元素的并行算法

§5 递推关系的并行计算

§6 “脉动”阵列和网状计算装置

§7 图的并行算法

§8 求连通块的并行算法

§9 分布计算简介

§10计算几何之一——关于线段问题

§11 计算几何之二——凸包问题

习题

§1 引言

第八章 复杂性理论及若干课题的

新进展

§2 图灵机、P和NP

§3 多项式归约

§4 可满足性问题及Cook定理

§5 若干NP完全问题及其证明

§6 复杂度类

§7 近似算法

§8 近代密码学简介

*§9 Klee和Minty的举例

*§10哈奇扬（хачиян）算法

*§11卡玛卡（Karmarkar）算法

习题