算法设计与分析(第3版在线教学版21世纪大学本科计算机专业系列教材)

作者简介

王捍贫，博士，北京大学信息科学技术学院教授，博士生导师，软件研究所副所长，中国人工智能学会离散智能计算专委会主任。长期从事离散数学、形式化方法及算法设计与分析的教学和研究工作。主持完成多项国家研究课题，撰写和翻译多部离散数学和计算理论教材，曾获得北京市教学成果奖一等奖，系国家精品课“离散数学”课程主讲教师，国家级精品资源共享课“离散数学”课程主持人，“算法设计与分析”课程主讲教师。

内容简介

本书由北京大学优秀教学团队编写，凝聚了教学团队多年教学经验和科研成果。 计算机科学技术发展迅猛，各种新的技术和算法层出不穷。然而万变不离其宗，各种新的算法依然是建立在各种经典算法技术的基础上，最新的算法技术往往是对各种已有算法技术的组合和改进。在掌握了本书所介绍的各种经典算法技术之后，再学习理解新的算法技术时，或者再学习掌握各领域内的专门算法时，往往可以事半功倍。 本书以算法设计技术为主线组织素材，以伪码描述算法，深入分析了各种设计技术的使用范围、设计步骤、算法正确性证明与时间复杂度估计方法，以及改进算法的途径、局限性等，为实际问题的建模与算法设计在理论上提供清晰的思路。从对具体算法的设计与分析，自然过渡到对问题难度的分析和界定，系统地介绍了一些关于问题复杂度的分析方法。力求用清晰易懂的语言介绍NP完全性理论的核心内容和难解问题的处理策略，希望为求解实际中的复杂问题提供帮助。除了传统的算法外，本书还介绍了随机算法、模拟退火算法、基于统计物理的消息传递算法、量子算法等，给有兴趣的读者提供进一步学习和研究的入门知识。本书的主要素材来自多年的教学积淀，也有一些研究的心得。既注意理论上严谨性，又精选了大量实例，并配有难度适当的练习，适合教学使用。