首页 > 图书中心 >图书详情

算法设计与分析(微课视频版)

本书配套资源丰富,配套有教学大纲,教学课件、微课视频等。

作者:张德富,曾华琳,沈思淇
丛书名:21世纪高等学校计算机类课程创新系列教材·微课版
定价:65
印次:1-1
ISBN:9787302632764
出版日期:2024.01.01
印刷日期:2024.01.08

本书主要取材于算法设计与分析领域经典和发展潮流方面的内容,包括非常经典的算法设计技术,例如,递归、分治算法、动态规划、贪心算法、图算法、分支限界、回溯; 也包括一些高级的算法设计,例如,网络流和匹配、线性规划、启发式搜索。在算法分析方面,本书介绍了概率分析、分摊分析和实验分析方法。在算法理论方面,本书介绍了问题的下界、算法的正确性证明,以及NP完全理论等内容。 本书还包括大量的问题实例,给出了相应的设计与分析方法,并精选了一些习题,供读者练习,以巩固所学的算法。在工业应用领域,许多实际问题和疑难问题都需要有效的求解算法,因此,本书提供了设计有效算法的基础,以及大量可供选择的解决途径。 本书可作为计算机科学与技术系、数学系、软件学院等专业和学院的本科生及研究生的教材,也可作为有志参加程序设计竞赛的学生进行学习和训练的参考书。

more >

前言 算法是计算机科学的灵魂,图灵奖(A.M Turing Award)的获得者,算法大师高德纳(Donald E.Knuth)说过: “计算机科学的研究就是算法的研究。”的确,计算机科学的每个领域——不管是软件、硬件,还是具体的应用,如集成电路的设计、操作系统的内存调度、计算机网络中的路由问题等——与算法密不可分。某个领域关键算法的改进直接关系到该领域的突破和进展。迄今为止,在72位图灵奖获得者中,因算法方面的贡献而获奖的就有40多位,可见算法的研究对推动计算机科学的发展起着至关重要的作用。 在厦门大学“算法设计与分析”课程的教学过程中,作者曾选用《算法导论》(Introduction to algorithms)和《算法设计技巧与分析》(Algorithms design techniques and analysis)这两本经典且权威的英文教材作为该课程的教材。在此基础上,作者还吸取了其他算法类教材的优点,最终确定本书的内容和风格。本书将目前计算机科学领域出现的一些经典及新颖的算法设计和分析技术合理地组织起来,并进行全面介绍,旨在帮助读者掌握基本的算法理论知识,提高解决和分析问题的能力,进而使读者对实际问题能够设计出简单有效的算法。 本书的主要内容如下。 第1章从问题入手,介绍了算法的基本概念及性质,计算模型的概念,以及算法时间复杂度的分析方法及算法正确性的证明方法。本章还介绍了问题下界的概念,以及如何衡量算法的效率,以便读者能够明白: 算法能否继续改进,何时才能达到最优。 第2章介绍了算法复杂度分析所需要用到的渐近符号及其含义。 第3章介绍了算法分析方法中常用的概率分析、分摊分析和实验分析方法。 第4章介绍了递归算法的设计及其证明方法,以及递归算法时间复杂度的求解方法。 第5章介绍了分治算法及其在排序、大整数乘法、矩阵乘法、残缺棋盘和快速傅里叶变换问题中的应用。 第6章介绍了动态规划算法的基本过程及性质,动态规划算法在装配线调度问题、矩阵链乘法问题、最长公共子序列问题、0/1背包问题、最优二叉搜索树问题中的应用。其中,最优子结构性质是能够用动态规划算法求解问题的必要条件,重叠子问题是提高动态规划算法效率的关键。 第7章通过活动选择问题引入贪心算法,介绍了贪心算法的过程,以及贪心选择性质的分析方法及证明,贪心算法在背包问题、哈夫曼编码问题、缓存维护问题中的应用。 第8章介绍了图算法的基本知识,重点强调了分摊分析在图算法时间复杂度分析中的应用及图算法正确性的证明方法,它们是网络流和匹配算法的基础。本章还进一步介绍了贪心算法和动态规划算法的应用。 第9章是图算法的扩展,介绍了网络流的最大流问题、最小费用流问题及匹配问题的求解算法。 第10章介绍了计算机、经济及管理领域中经常用到的线性规划问题,并介绍了这些问题的单纯型求解算法。 第11章介绍了NP完全理论,具体介绍了P、NP和NPC的定义及其分类,以及NP完全问题的证明方法。 第12章介绍了求解NP困难问题(NPhard problem)的回溯算法。通过回溯算法在装载问题、0/1背包问题、着色问题、n皇后问题、旅行商问题、流水作业调度问题、零件切割问题中的应用,介绍约束函数、限界函数的设计思路和方法,分析了提高回溯算法效率的关键因素。 第13章介绍了基于宽度优先,同时吸取了回溯算法优点的分支限界算法,特别介绍了两种分支限界算法在不同问题求解中的应用及剪支函数的设计。 第14章介绍了启发式搜索算法的设计,特别详细介绍了A*搜索算法和博弈搜索算法。 本书具有如下特色。 (1) 本书基本上涵盖了常用算法设计的主要内容。 (2) 算法的正确性是软件可靠性的保证,本书为不同类型的算法提供了算法正确性的证明思路。目前,已出版的大多数算法书是没有这部分内容的。 (3) 本书精选了大量的习题,使读者可以有选择性地练习。同时,精选了一些实际的工程项目作为实验题。书中的一些算法实现,读者可以访问算法课程实验网站进行练习。 (4) 本书不仅注重算法的应用设计,而且注重算法时间复杂度的分析。书中大部分算法都提供了具体案例,并进行了详尽分析,使读者加深对算法的理解。 (5) 本书还提供英文课件,便于双语教学。 特别感谢厦门大学现代教育技术与实践训练中心的罗淀老师,她对本书的文字和体例进行了校对,并建议不要写得太复杂,这奠定了本书的风格。没有她的帮助,本书不可能顺利出版。本书还作为中国大学MOOC(慕课)“算法设计与分析”课程的配套教材,我的同事林文水和卢杨两位老师也为慕课课程的建设付出了很多努力。 此外,本书的完成还受到“厦门大学第二批双语教学项目”“算法设计与分析课程”“厦门大学优秀教材出版项目”“福建省一流本科建设项目”“中国大学MOOC项目”的支持。 限于我们的水平和经验,书中难免有不妥之处,还望广大读者指正,在此先表感谢! 谨以此书献给所有关心、鼓励和帮助过我们的人们。 编者 厦门大学计算机科学与技术系 2023年12月10日

more >
扫描二维码
下载APP了解更多

同系列产品more >

数据库原理及应用实验与课程设计指...

刘金岭、龚丹丹、蔡博
定 价:39.80元

查看详情
MySQL数据库技术与应用(第2版·微课...

赵明渊
定 价:59.80元

查看详情
Python编程与项目开发(微课视频版)...

肖衡、周显春、龙草芳、
定 价:49.80元

查看详情
Java Web程序设计基础(微课视频版)...

程细柱、戴经国
定 价:49.90元

查看详情
Vue 3基础入门(项目案例·微课视频...

王宁,李骞,田岳,王峰
定 价:49元

查看详情
图书分类全部图书
more >
  • 本书内容基本上涵盖了目前国内程序设计竞赛所要掌握的主要算法,并在书后精选了部分ACM国际大学生程序设计竞赛的题目,供大家练习。本书将目前计算机科学领域出现的一些经典以及新颖的算法设计和分析技术合理地组织起来,进行了一个全面的介绍。旨在帮助读者掌握基本的算法设计与分析技术,提高解决问题和分析问题的能力,进而对实际问题,设计出简单有效的算法。

more >
  • 目录

    教学大纲

    教学课件

    程序源码

    第1章概念入门

    1.1问题模型

    1.2算法的概念

    1.3算法的正确性

    1.4算法的效率

    1.5问题的下界

    1.6小结

    习题

    实验题

    第2章渐近符号

    2.1Θ符号

    2.2O符号

    2.3Ω符号

    2.4渐近符号的性质

    2.5常用函数的直观含义

    2.6小结

    习题

    第3章算法分析方法

    3.1概率分析

    3.2分摊分析

    3.2.1合计方法

    3.2.2记账方法

    3.2.3势能方法

    3.3实验分析

    3.4小结

    习题

    第4章递归算法

    4.1算法思想

    4.1.1递归算法的应用

    4.1.2递归与迭代

    4.2递归方程的求解

    4.2.1替换法

    4.2.2递归树法

    4.2.3公式法

    4.3多项式求值实验

    4.4小结

    习题

    实验题

    第5章分治算法

    5.1算法思想

    5.2合并排序

    5.3快速排序

    5.4大整数乘法

    5.5矩阵乘法

    5.6残缺棋盘游戏

    5.7快速傅里叶变换

    5.8小结

    习题

    实验题

    第6章动态规划算法

    6.1算法思想

    6.2装配线调度问题

    6.3矩阵链乘法问题

    6.4最长公共子序列问题

    6.50/1背包问题

    6.6最优二叉搜索树问题

    6.7动态规划的基本...

精彩书评more >

标题

评论

版权所有(C)2023 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802042911号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘