算法设计与分析高级教程

第1章 预备知识

1.1 数学基础

1.2 问题的复杂性

1.3 规划问题

第2章 随机算法

2.1 基本概念

2.2 数值随机算法

2.3 Sherwood算法

2.4 Las Vegas算法

2.5 Monte Carlo算法

2.6 随机复杂性

2.7 总结

第3章 近似算法

3.1 基本概念

3.2 调度问题

3.3 旅行商问题

3.4 覆盖问题

3.5 Bin packing问题

3.6 背包问题

3.7 随机近似算法

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

3.9 近似的难度

3.10 在线算法

3.11 总结

第4章 启发式算法

4.1 概述

4.2 作业车间调度问题

4.3 packing问题

4.4 SAT问题

4.5 总结

参考文献

本书主要取材于反映当今计算机科学与技术学科中算法设计及分析发展潮流方面的内容。内容除包括国外一些比较成熟的算法技术，例如基本的随机算法以及近似算法，还包括一些最新的研究成果，例如基于近似和随机思想的混合算法：随机近似算法、在线算法、现代启发式算法等。本书包括大量的问题实例并给出了相应的求解方法。而工业应用领域的许多实际问题和疑难问题，都需要有效的求解算法，本书提供了大量的可供选择的解决途径。
本书可作为计算机科学系、数学系、管理科学等高年级本科以及研究生课程的教材，也适合科研人员学习使用。