首页 > 图书中心 >图书详情
算法设计与分析
作者:李春葆、陈良臣、喻丹丹、曾平
定价:39.50元
印次:1-5
ISBN:9787302381136
出版日期:2015.05.01
印刷日期:2018.06.19
本书系统地介绍了各种常用的算法设计策略,包括穷举法、分治法、贪心法、动态规划法、回溯法、分枝限界法等,并详细讨论了各种图搜索算法和计算几何设计算法。 全书既注重原理又注重实践,配有大量图表、上机实验题和练习题,内容丰富,概念讲解清楚,表达严谨,逻辑性强,语言精练,可读性好。 本书既便于教师课堂讲授,又便于自学者阅读。本书可作为高等院校算法设计与分析课程的教材,也可供ACM和各类程序设计竞赛者参考。
more >算法在计算科学中扮演着重要角色。算法设计是计算机科学与技术专业的专业必修课,其目标是培养学生分析问题和解决问题的能力,使学生掌握算法设计的基本技巧和方法,熟悉算法分析的基本技术,并能熟练运用一些常用算法,解决一些较综合的问题。 在学习本课程之前,学生已经学习了基本的数据结构知识,能熟练运用一门或多门编程语言,并具备了一定的编程经验。如何利用这些已学过的知识,对不同的实际问题设计出有效的算法,正是本课程所要达到的目的。 本课程特点是“问题模型化,求解算法化,设计最优化”,在掌握必要的算法设计技术和编程技巧的基础上,能够在实际工作中根据具体问题设计和优化算法。本书是针对这一特点并结合本课程组的教学经验编写的。 全书由10章构成,各章内容如下: 第1章 概论,介绍算法的概念、算法分析方法和基本的计算复杂性理论。 第2章 递归算法设计技术,介绍递归的概念、递推式的计算、递归算法设计方法和相关示例、递归算法到非递归算法的转化。 第3章 穷举法,介绍穷举法的特点、穷举法的基本应用示例和递归在穷举法中的应用示例。 第4章 分治法,介绍分治法的策略和求解过程,讨论采用分治法求解排序问题、查找问题、最大连续子序列和问题、大整数乘法问题和矩阵乘法问题的典型算法,并简要介绍了并行计算的概念。 第5章 贪心法,介绍贪心法的策略、求解过程和贪心法求解问题应具有的性质,讨论采用贪心法求解区间问题、背包问题、多机调度问题、哈夫曼编码和磁盘排序问题的典型算法。 第6章 动态规划,介绍动态规划的原理和求解步骤,讨论采用动态规划法求解整数拆分问题、最长公共子序列问题、0/1背包问题、最大连续子序列和问题和资源分配问题的典型算法。 第7章 回溯法,介绍解空间概念和回溯法算法框架,讨论采用回溯法求解0/1背包问题、子集和问题、排列和组合问题、迷宫问题、n皇后问题的典型算法。 第8章 分枝限界法,介绍分枝限界法的特点和设计思想,讨论采用队列式分枝限界法和采用优先队列式分枝限界法求解0/1背包问题的典型算法。 第9章 图搜索算法设计,介绍图的存储表示、图的两种基本的搜索算法,利用STL设计算法的基本知识,讨论了构造图最小生成树的两种算法、产生图最短路径的3种算法,并采用5种算法策略求解旅行推销员问题(TSP问题)以及求多段图的关键路径等典型算法; 最后介绍网络流的相关概念以及求最大流和最小费用最大流的算法。 第10章 几何计算,介绍几何计算中常用的矢量运算以及求解凸包问题、最近点对问题和最远点对问题的典型算法。 另有3个附录,附录A给出部分练习题的参考答案,附录B给出所有上机实验题的参考程序,附录C给出书中主要算法实现程序的清单。 本书的特点是内容丰富、由浅入深、循序渐进,在各章中,首先介绍一种算法设计策略的基本思想,然后从解决实际问题入手,由易到难地描述几个经典示例,使读者既能学到一些常用求解问题的算法,又能通过对算法策略的反复应用,掌握其核心思想,以便收到融会贯通之效。同时本书特别注重同一个问题的多种解法以及不同算法的比较,使读者更容易体会到每一种算法策略的设计特点和各自的优缺点。 书中绝大多数算法在VC++6.0中调试通过,本书的教学PPT和所有源程序可以从清华大学出版社网站免费下载。 本书的编写工作得到湖北省教育厅和武汉大学教学研究项目《计算机科学与技术专业课程体系改革》的大力支持,清华大学出版社魏江江主任也全力支持本书的编写工作,作者在此一并表示衷心感谢。 本书是课程组全体教师多年教学经验的总结和体现,尽管作者不遗余力,由于水平所限,仍存在错误和不足之处,敬请教师和同学们批评指正在此表示万分的感谢。 编者2015年3月
more >