新書推薦:
《
母亲的选择:看不见的移民保姆与女性工作
》
售價:NT$
340.0
《
城邦政治与灵魂政治——柏拉图《理想国》中的政治哲学研究
》
售價:NT$
590.0
《
3分钟漫画墨菲定律:十万个为什么科普百科思维方式心理学 胜天半子人定胜天做事与成事的权衡博弈之道
》
售價:NT$
249.0
《
1911:危亡警告与救亡呼吁
》
售價:NT$
349.0
《
旷野人生:吉姆·罗杰斯的全球投资探险
》
售價:NT$
345.0
《
笼中王国 : 18世纪法国的珍禽异兽与社会文化
》
售價:NT$
340.0
《
思考的框架3:风靡华尔街的思维训练法
》
售價:NT$
295.0
《
被记忆的西周史(中山大学中珠学术译丛)
》
售價:NT$
690.0
|
編輯推薦: |
对算法的解读通常通过作者称为“思路”的方式展开,并通过设置问题和解答问题的方式,让读者不仅对算法知其然,也知其所以然。
在每章的最后一节都会讨论该算法的一个重要应用,一方面体现算法的应用价值,另一方面激发读者对算法进一步学习的兴趣。
配套提供电子课件、教学大纲、微课视频、MOOC(B站)、试卷及答案。
|
內容簡介: |
本书主要讨论和分析基础算法,包括排序、递归、分治、动态规划、贪心、图算法、回溯和分支限界,以及匹配与指派。为了让读者不仅掌握算法,也能够理解算法的设计思想,本书对算法的解读通常通过作者称为“思路”的方式展开,并通过设置问题和解答问题的方式,让读者不仅对算法知其然,也知其所以然。尽管这些算法是基础算法,但它们在实际中有着广泛的应用。本书的另一大特点是对算法应用的讨论,这些讨论一方面体现算法的应用价值,另一方面激发读者对算法进一步学习的兴趣。
本书可作为高等院校计算机类专业本科生的算法课程的教材,也可作为各行业从事算法设计和开发的人员的技术参考书。
|
關於作者: |
林海,现任武汉大学-国家网络安全学院副教授,先后毕业于法国巴黎第六大学(硕士)和法国国立高等通信学校(博士),并取得了计算机网络博士学位,是武汉大学作为人才引进的优秀青年学术骨干。在加入武汉大学之前,曾经先后在法国电信 Orange 研究院从事博士后研究和在中兴通讯欧洲研究所(巴黎)从事系统工程师工作。本书作者一直从事算法方面的教学和研究,有着多年本科生《算法设计与分析》和研究生《高级算法》教学经验。
|
目錄:
|
前言
第1章算法概念和基础
11基本概念
111搜索
112排序
12算法复杂度
121时间复杂度
122算法的时间复杂度
123空间复杂度
13数据结构
131堆
132不相交集
14本章小结
15习题
第2章排序
21比较排序
211冒泡排序
212堆排序
213插入排序
214归并排序
22线性排序
221桶排序
222计数排序
223基数排序
23本章小结
24习题
第3章递归
31基本概念
32递归例子
321生成排列
322整数划分
33复杂度的递归方法求解
331展开法
332代入法
333递归树方法
334主方法
335几种递归形式的复杂度分析
34本章小结
35习题
第4章分治
41基本概念
42快速排序
43最大子数组问题
44最近点对问题
45棋盘覆盖问题
46寻找第k小元素
47分治在傅里叶变换中的应用*
48本章小结
49习题
第5章动态规划
51基本概念和步骤
52最大子数组问题
530-1背包问题
54旅行商问题
55最长公共子序列
56斯坦纳最小树*
57状态压缩动态规划
571集合状态压缩
572空间状态压缩
58动态规划和贝尔曼方程*
59本章小结
510习题
第6章贪心
61基本概念
62小数背包和0-1背包
621小数背包贪心算法的正确性证明
6220-1背包贪心算法
63最小生成树
631Kruskal算法
632Prim算法
64霍夫曼编码
65贪心算法在稳定匹配中的应用*
66本章小结
67习题
第7章图算法
71深度优先搜索
711无向图的深度优先搜索
712有向图的深度优先搜索
713应用:寻找图的关节点
72广度优先搜索
721无向图的广度优先搜索
722有向图的广度优先搜索
723应用:最短路径(跳数)
73单源最短路径
731Dijkstra算法
732Bellman-Ford算法
733SPFA算法
734差分约束系统
74多源最短路径
741Floyd算法(弗洛伊德算法)
742Johnson算法
75最短路径在网络路由中的应用*
76本章小结
77习题
第8章回溯和分支限界
81回溯的基本方法
811回溯法的基本步骤
812回溯法的通用框架
82骑士巡游问题
830-1背包问题
84最大团问题
841最大团的回溯算法
842Bron-Kerbosch算法
85分支限界法
851基本方法
852旅行商问题
853任务指派问题
86分支限界在流水线作业调度中的应用*
87本章小结
88习题
第9章匹配与指派
91基本概念
92基于图的匈牙利算法
921匹配问题
922指派问题
93基于矩阵的匈牙利算法
931算法流程
932最大化指派
94匹配算法在多目标跟踪中的应用*
95本章小结
96习题
参考文献
|
內容試閱:
|
要不要写一本算法教材,这个问题从作者从事算法教学开始就形成困扰,一则毕竟珠玉在前,市面上已有一些非常优秀的算法教材,再写出一本有特色的教材并不是一件容易的事;二则担心一旦开始,能否顺利将之完成,因需查阅大量文献,教材的编写不是容易的事。后来,在教学的过程中,对算法有了更深的认识,也有了自己的一些思路和想法,特别是教学得到了学生的认可,终于下定决心开始编写本书和《高级算法》。历时三年多终于完成本书,希望此书不仅能对本科层次算法课程教学有帮助,也希望更多的读者能够通过自身的阅读、学习,对算法有更深入的认识。本书作为教材,但是不是应该完 全按照教材的风格来写?大多数教材的撰写略显刻板,作者在教学的过程中也发现,对于一些知识点的学习,学生通常并不是通过教材,而是通过博客、知乎等网络渠道来学习,因为后者对读者更加友好,比如描述更亲切(或者说更口语化)、更详尽,逻辑上也是从有利于读者理解的角度出发,而不是像教材从知识点本身的构成进行描述。所以,本书在保持知识结构严谨的基础上,尽量采用对读者更加友好的方式进行描述,以期达到既可作为教材,也可作为自学书籍的目的。
本书主要是讨论和分析基础算法,包括排序、递归、分治、动态规划、贪心、图算法、回溯和分支限界,以及匹配与指派。学习算法不仅要掌握设计和应用,也要分析算法,所以本书在概念和基础章节着重讨论算法复杂度的分析;同时讨论两个重要的数据结构——堆和不相交集,这两个数据结构会在讲授的算法中广泛使用。同样,排序也是很多算法的基础,所以本书第2章对目前主流的排序算法进行讨论分析。接着,本书对递归进行了详尽的讲解,递归是分治、回溯等算法的具体实现方法;第3章也讨论了递归复杂度的计算。之后,本书讨论分治、动态规划和贪心算法,其中,动态规划可以解决很多经典算法问题,更是算法竞赛考查的重点;而贪心算法因其简单性,是人们在实际中比较喜欢采用的算法,但实际上,设计一个好的贪心算法并不容易,对贪心算法进行分析,也是一个难点。本书的第7章讨论图的基础算法,它是图高级算法的基础,作者对图问题特别关注,是因为图模型在新的社交模式下以及人工智能时代起着越来越重要的作用。之后,本书在第8章讨论了回溯和分支限界两种算法,特别是分支限界法,因其采用了类似神经网络对解搜索的思想,对一些复杂问题的求解有着很高的效率。最后,针对匹配算法在搜索、目标跟踪、推荐等领域的广泛使用,本书专门讨论了匈牙利算法,也就是匹配问题的求解方法。
本书讲解的算法在大多数的算法教材中都会涉及,但很多教材存在描述晦涩、缺乏系统性、缺乏算法思想讨论的问题,这使得算法的学习变得枯燥和困难,或者是即使学了算法,也难以理解其设计思想。所以写一本对读者友好,且读者能够理解算法设计思想的教材是作者的初衷,也是本书的一个特色。为此,本书对算法的解读在很多地方会通过作者称之为“思路”的方式展开,并通过设置问题和解答问题的方式,让读者不仅对算法知其然,也知其所以然。尽管本书讨论的是基础算法,但是这些算法在实际中也有着广泛的应用,所以作者在每章的最后一节都会讨论该算法的一个重要应用,一方面体现算法的应用价值,另一方面激发读者对算法进一步学习的兴趣,这是本书的另一特色。本书选取的应用尽量体现当前的一些重要技术,如在信号处理中的重要技术傅里叶变换,强化学习的基础方程贝尔曼方程,还有经济学中的稳定匹配,无人驾驶和虚拟现实中的多目标跟踪等。作者希望通过这些应用,让读者明白基础算法不仅仅用于考试和解题,在实际中也有着极重要的应用价值。
为了让读者能够更好地学习书中的知识,作者对课堂教学进行了实录,目前录课已经发布在B 站,账号为foretmer,有兴趣的读者可以结合视频来学习本书。同时,和本书相关的课件、课后习题也会在B 站上发布。此外,作者也在知乎上开辟了一个专栏,讨论和本书相关的一些知识,读者也可以在专栏中和作者展开讨论与交流。
本书的编写得到了武汉大学本科生院和武汉大学网络安全学院的支持,在此一并谢过。同时还要特别感谢作者教过的历届学生,在日常教学中,他们提供了很多灵感并帮助作者修改了一些错误,如伪代码错误、公式错误等。另外,感谢编辑人员对全文进行了认真的校对。
尽管作者已经尽了努力去避免错误,但由于时间和能力的原因,书中难免存在不妥之处,如读者发现错误,还请指出,不胜感激。
|
|