前言

教学建议

第1章  绪论

  1.1 算法在计算机科学体系中的地位

    1.1.1 计算机理论模型和计算问题的分类

    1.1.2 利用计算机求解问题

    1.1.3 计算机科学的知识体系

    1.1.4 算法是计算机科学的重要主题

    1.1.5 算法设计与分析的意义

  1.2 算法的概念

  1.3 算法分析

    1.3.1 算法正确性分析

    1.3.2 算法复杂度分析

  1.4 算法设计方法

  习题

第2章  数学基础

  2.1 复杂度函数的阶

    2.1.1 函数阶的定义

    2.1.2 函数阶的性质

  2.2 标准符号和通用函数

    2.2.1 flour函数和ceiling函数

    2.2.2 求和

  2.3 递归方程

    2.3.1 常系数线性递归方程

    2.3.2 非常系数线性递归方程

    2.3.3 生成函数

    2.3.4 分治算法递归方程

  习题

第3章  分治算法

  3.1 分治算法原理

  3.2 大整数乘法

  3.3 Strassen矩阵乘法

  3.4 快速傅里叶变换

  3.5 最邻近点问题

  3.6 平面点集的凸包

    3.6.1 求解凸包问题的蛮力算法

    3.6.2 GrahamScan算法

    3.6.3 凸包问题的分治算法

  3.7 基于剪枝搜索方法的分治算法

    3.7.1 剪枝搜索方法

    3.7.2 线性时间选择算法

    3.7.3 二元线性规划的线性时间算法

    3.7.4 1-圆心问题的线性时间算法

  习题

第4章  动态规划算法

  4.1 动态规划原理

  4.2 最长公共子序列

  4.3 矩阵链乘法

  4.4 0-1背包问题

  4.5 最优二叉搜索树

  4.6 评注

  习题

第5章  贪心算法

  5.1 贪心算法的基本原理

  5.2 活动选择问题

  5.3 哈夫曼编码问题

  5.4 最小生成树问题

    5.4.1 Kruskal算法

    5.4.2 Prim算法

  5.5 贪心算法的理论基础

    5.5.1 拟阵

    5.5.2 加权拟阵上的贪心算法

  5.6 单位时间任务调度问题

  习题

第6章  平摊分析

  6.1 平摊分析方法

    6.1.1 聚集方法

    6.1.2 会计方法

    6.1.3 势能方法

  6.2 动态表性能的平摊分析

    6.2.1 动态表及其操作

    6.2.2 动态表的扩张

    6.2.3 动态表扩张和收缩

  6.3 斐波那契堆及其操作代价的平摊分析

    6.3.1 斐波那契堆

    6.3.2 斐波那契堆操作算法及其平摊代价

    6.3.3 斐波那契堆最大度的上界

  6.4 并查集及其操作代价的平摊分析

    6.4.1 并査集及其基本性质

    6.4.2 阿克曼函数及其逆函数

    6.4.3 并查集上操作序列代价的平摊分析

  习题

第7章  最大值最小值方法

  7.1 网络流

    7.1.1 最大流问题和最小割问题

    7.1.2 Ford-Fulkerson算法

    7.1.3 Edmonds-Karp算法

    7.1.4 推送复标算法

    7.1.5 复标前置算法

  7.2 匹配算法

    7.2.1 匹配与覆盖

    7.2.2 最大二分匹配

    7.2.3 一般图上的最大匹配

    7.2.4 最大权值二分匹配

    7.2.5 稳定二分匹配

  习题

第8章  树的搜索策略

  8.1 问题解空间的树表示

  8.2 典型搜索策略

    8.2.1 广度优先搜索

    8.2.2 深度优先搜索

    8.2.3 爬山法

    8.2.4 最佳优先搜索

    8.2.5 分支限界法

  8.3 分支限界法的应用

    8.3.1 用分支限界法求解人员分配问题

    8.3.2 用分支限界法求解旅行商问题

    8.3.3 用分支限界法求解0-1 背包问题

  8.4 A*算法及其应用

  8.5 博弈树和α-β剪枝

    8.5.1 博弈树及其评估

    8.5.2 α-β剪枝

    习题

第9章  随机算法

    9.1 随机算法概述

    9.2 数值随机算法

    9.2.1 随机投点法

    9.2.2 平均值方法

  9.3 随机选择和拉斯维加斯算法

    9.3.1 随机选择算法

    9.3.2 拉斯维加斯算法

  9.4 快速排序和舍伍德算法

    9.4.1 快速排序算法描述

    9.4.2 快速排序算法的性能分析

    9.4.3 随机快速排序算法

    9.4.4 舍伍德算法

  9.5 素数测试和蒙特卡罗算法

    9.5.1 素数测试随机算法

    9.5.2 蒙特卡罗算法

  9.6 最小割随机算法

  习题

第10章  近似算法

  10.1 近似算法的性能分析

  10.2 基于组合优化的近似算法

    10.2.1 顶点覆盖问题的近似算法

    10.2.2 装箱问题的近似算法

    10.2.3 最短并行调度问题的近似算法

    10.2.4 旅行商问题的近似算法

    10.2.5 子集和问题的完全多项式近似模式

  10.3 基于贪心思想的近似算法

    10.3.1 集合覆盖问题的近似算法

    10.3.2 不相交路径问题的近似算法

  10.4 基于局部搜索的近似算法

    10.4.1 最大割问题的近似算法

    10.4.2 设施定位问题的近似算法

  10.5 基于动态规划的近似算法

    10.5.10-1 背包问题的完全多项式近似模式

    10.5.2 装箱问题的多项式近似模式

  10.6 基于线性规划的近似算法

    10.6.1 线性规划及对偶定理

    10.6.2 加权集合覆盖问题的线性规划表示

    10.6.3 舍入法及随机舍入法

    10.6.4 对偶拟合方法

    10.6.5 原偶模式

  10.7 不可近似性

    10.7.1 鸿沟归约与不可近似性

    10.7.2 PCP定理

    10.7.3 MAX-3 SAT问题的不可近似性

    10.7.4 α,β-鸿沟归约与不可近似性

  习题

第11章  在线算法

  11.1 在线算法与竞争度分析

  11.2 欧几里得最小生成树问题的在线算法

    11.2.1 在线贪心算法

    11.2.2 在线随机算法

  11.3 凸包在线算法

  11.4 线性链表在线更新算法

  11.5 最短并行调度在线算法

  习题

参考文献