本书主要论述计算机科学的基本概念、思想、方法和结果。全书内容由5个部分组成。“预备知识”部分包括算法学中的基本概念、算法结构、算法所操纵的数据以及描述算法所用的程序设计语言。“方法和分析”部分包括算法设计的方法、算法的正确性和效率、评价算法的方法。“局限性和健壮性”部分包括可执行算法的固有局限性以及实现这些算法的计算机的固有局限性、不可计算性和不可判定性、算法学的通用性及其健壮性。此外,还讨论了并发模型、并行模型以及密码学中的一些根本性的问题,并且介绍了反应式系统和分布式系统以及计算机与人工智能(human intelligence)之间的关系。
这是唯一一本从全新的视角来系统地阐述计算机科学中根本问题的书籍。通过形象的比喻来描述算法和计算理论中的一些富有挑战性的问题。本书力图用最精炼的数学语言阐述算法和数据结构、图灵机、有限自动机、不可判定性、不可计算性、复杂度、NP 完全性、并行算法、概率算法等概念,同时又不失论述的严谨性,使一般读者易于理解和掌握。
本书适合作为高等学校计算机专业本科高年级和研究生“算法学”课程的教材,也可作为从事软件开发、系统分析、系统设计等专业人员的参考书。此外,也可供算法和计算理论的爱好者和参加各种编程大赛的选手参考使用。
- 前言
- 致谢
- 第一部分 预备知识
- 第1章 导引和历史回顾
- 第2章 算法和数据
- 第3章 程序设计语言和范型
- 第二部分 方法和分析
- 第4章 算法学方法
- 第5章 算法的正确性
- 第6章 算法的效率
- 第三部分 局限性和健壮性
- 第7章 无效性和难解性
- 第8章 不可计算性和不可判定性
- 第9章 算法学的通用性及其健壮性
- 第四部分 松弛规则
- 第10章 并行、并发及其他模型
- 第11章 概率算法
- 第12章 密码学和可靠交互
- 第五部分 更宏伟蓝图
- 第13章 软件工程
- 第14章 反应式系统
- 第15章 算法学与智能
- 后记
- 习题选解
- 参考书目注释
- 英汉对照表