- 算法设计与分析(第2版高等学校计算机专业系列教材)
- - 作者：编者:黄宇|责编:张梦玲
  - 出版社：机械工业
  - ISBN：9787111657231
  - 出版日期：2020/07/01
  - 页数：225
- 售价：23.6

内容大纲
本书是在作者多年从事“算法设计与分析”课程教学和研究的基础上编写而成的，系统地介绍了算法设计与分析的理论、方法和技术。算法分析与设计的内容很丰富，可以从不同视角进行组织和阐述。本书内容围绕两条主线来组织。一条主线是介绍经典的算法问题，如排序、选择、图遍历等；另一条主线是介绍经典的算法设计与分析策略，如分治、贪心、动态规划等。
本书主要面向计算机专业本科生，以及其他需要学习计算机科学基本知识与了解计算机程序设计背后原理的读者。
作者介绍
黄宇，南京大学计算机科学与技术系教授，博士生导师，主要研究方向为分布式算法、分布式系统、系统软件。曾主持三项国家自然科学基金，并作为主要成员参与了国家973计划、国家自然科学基金创新群体项目等多项国家重大科研项目。2014年获得南京大学登峰人才支持计划资助，联合指导的博士论文分别获得2016年、2017年中国计算机学会优秀博士学位论文奖。已在ACM PODC、IEEE SRDS、IEEE Trans.on Computers、IEEE Trans.on Parallel and Distributed Systems等重要国际会议、期刊上发表多篇论文。在教学方面的成就：曾入选201 8年度国家“高校计算机专业优秀教师奖励计划”，获得2018年度南京大学“刘厚俊奖教金”；所教授的算法课程入选2019年度“南京大学百层次优质课程”，并被评为2019年度计算机系毕业生“我心目中的好课程”。
目录
前言
教学建议
第一部分  计算模型
  第1章  抽象的算法设计与分析
    1.1  RAM模型的引入
      1.1.1  计算的基本概念
      1.1.2  计算模型的基本概念
      1.1.3  RAM模型
      1.1.4  计算模型的选择：易用性与精确性
    1.2  抽象算法设计
      1.2.1  算法问题规约
      1.2.2  算法正确性证明：数学归纳法
    1.3  抽象算法分析
      1.3.1  抽象算法的性能指标
      1.3.2  最坏情况时间复杂度分析
      1.3.3  平均情况时间复杂度分析
    1.4  习题
  第2章  从算法的视角重新审视数学的概念
    2.1  数学运算背后的算法操作
      2.1.1  取整□和□
      2.1.2  对数log n
      2.1.3  阶乘n!
      2.1.4  常用级数求和□f(i)
      2.1.5  期望E[X]
    2.2  函数的渐近增长率
    2.3  “分治递归”求解
      2.3.1  替换法
      2.3.2  分治递归与递归树
      2.3.3  Master定理
    2.4  习题
第二部分  从蛮力到分治
  第3章  蛮力算法设计
    3.1  蛮力选择与查找
    3.2  蛮力排序
      3.2.1  选择排序
      3.2.2  插入排序
    3.3  习题
  第4章  分治排序
    4.1  快速排序
      4.1.1  插入排序的不足
      4.1.2  快速排序的改进
      4.1.3  最坏情况时间复杂度分析
      4.1.4  基于递归方程的平均情况时间复杂度分析
      4.1.5  基于指标随机变量的平均情况时间复杂度分析
    4.2  合并排序
    4.3  基于比较的排序的下界
      4.3.1  决策树的引入
      4.3.2  比较排序的最坏情况时间复杂度的下界
      4.3.3  比较排序的平均情况时间复杂度的下界
    4.4  习题

  第5章  线性时间选择
    5.1  期望线性时间选择
      5.1.1  选择算法设计
      5.1.2  选择算法分析
    5.2  最坏情况线性时间选择
      5.2.1  选择算法设计
      5.2.2  选择算法分析
    5.3  习题
  第6章  对数时间查找
    6.1  折半查找
      6.1.1  经典折半查找
      6.1.2  查找峰值
      6.1.3  计算□
    6.2  平衡二叉搜索树
      6.2.1  二叉搜索树及其平衡性
      6.2.2  红黑树的定义
      6.2.3  红黑树的平衡性
    6.3  习题
  第7章  分治算法设计要素
    7.1  分治算法的关键特征
    7.2  计算逆序对的个数
      7.2.1  依托于合并排序的逆序对计数
      7.2.2  原地的逆序对计数
    7.3  整数乘法
      7.3.1  简单分治
      7.3.2  更精细的分治
    7.4  芯片检测
    7.5  习题
第三部分  从图遍历到图优化
  第8章  图的深度优先遍历
    8.1  图和图遍历
    8.2  有向图上的深度优先遍历
      8.2.1  遍历框架
      8.2.2  深度优先遍历树
      8.2.3  活动区间
    8.3  有向图上深度优先遍历的应用
      8.3.1  拓扑排序
      8.3.2  关键路径
      8.3.3  有向图中的强连通片
    8.4  无向图上的深度优先遍历
      8.4.1  无向图的深度优先遍历树
      8.4.2  无向图的深度优先遍历框架
    8.5  无向图上深度优先遍历的应用
      8.5.1  容错连通
      8.5.2  寻找割点
      8.5.3  寻找桥
    8.6  习题
  第9章  图的广度优先遍历
    9.1  广度优先遍历
      9.1.1  广度优先遍历框架

      9.1.2  有向图的广度优先遍历树
      9.1.3  无向图的广度优先遍历树
    9.2  广度优先遍历的应用
      9.2.1  判断二分图
      9.2.2  寻找k度子图
    9.3  习题
  第10章  图优化问题的贪心求解
    10.1  最小生成树问题与给定源点最短路径问题
    10.2  Prim算法
      10.2.1  Prim算法的正确性
      10.2.2  Prim算法的实现
      10.2.3  Prim算法的分析
    10.3  Kruskal算法
      10.3.1  Kruskal算法的正确性
      10.3.2  Kruskal算法的实现与分析
    10.4  最小生成树贪心构建框架MCE
      10.4.1  从MCE框架的角度分析Prim算法
      10.4.2  从MCE框架的角度分析Kruskal算法
    10.5  Dijkstra算法
      10.5.1  Dijkstra算法的设计
      10.5.2  Dijkstra算法的正确性证明与性能分析
    10.6  贪心遍历框架BestFS
    10.7  习题
  第11章  贪心算法设计要素
    11.1  贪心算法的基本结构
    11.2  相容任务调度问题
      11.2.1  直觉的尝试
      11.2.2  基于任务结束时间的贪心算法
    11.3  Huffman编码
      11.3.1  可变长度编码
      11.3.2  编码方案的性质
      11.3.3  贪心的Huffman编码
    11.4  习题
  第12章  图优化问题的动态规划求解
    12.1  有向无环图上的给定源点最短路径问题
    12.2  所有点对最短路径问题
      12.2.1  传递闭包问题和Shortcut算法
      12.2.2  所有点对最短路径：基于路径长度的递归
      12.2.3  Floyd-Warshall算法：基于中继节点范围的递归
    12.3  习题
  第13章  动态规划算法设计要素
    13.1  动态规划的动机
    13.2  动态规划的引入
      13.2.1  基于朴素遍历的递归
      13.2.2  未做规划的递归
      13.2.3  采用动态规划的递归
    13.3  动态规划的关键特征
    13.4  动态规划应用举例
      13.4.1  编辑距离问题
      13.4.2  硬币兑换问题

      13.4.3  和连续子序列问题
      13.4.4  相容任务调度问题
    13.5  习题
第四部分  围绕数据结构的算法设计
  第14章  堆与偏序关系
    14.1  堆的定义
    14.2  堆的抽象维护
      14.2.1  堆的修复
      14.2.2  堆的构建
    14.3  堆的具体实现
    14.4  堆的应用
      14.4.1  堆排序
      14.4.2  基于堆实现优先队列
    14.5  习题
  第15章  并查集与动态等价关系
    15.1  动态等价关系
    15.2  基于根树的基础实现：普通“并”+普通“查”
    15.3  保证合并的平衡性：加权“并”+普通“查”
    15.4  降低查找的代价：加权“并”+路径压缩“查”
    15.5  习题
  第16章  哈希表与查找
    16.1  直接寻址表：查找表的蛮力实现
    16.2  哈希表的基本原理
    16.3  封闭寻址冲突消解
    16.4  开放寻址冲突消解
    16.5  习题
  第17章  有限自动机与串匹配
    17.1  蛮力串匹配
    17.2  基于有限自动机的串匹配
    17.3  从有限自动机的角度理解KMP算法
      17.3.1  对传统匹配自动机的改进
      17.3.2  自动机构建的原理
      17.3.3  KMP算法的实现
    17.4  习题
第五部分  算法分析进阶
  第18章  平摊分析
    18.1  平摊分析的动机
    18.2  平摊分析的基本过程
    18.3  MultiPop栈
    18.4  数组扩充
    18.5  二进制计数器
    18.6  基于栈实现队列
    18.7  习题
  第19章  对手论证
    19.1  对手论证的基本形式
    19.2  选择或最小元素
    19.3  同时选择和最小元素
    19.4  选择次大元素
    19.5  选择中位数
    19.6  习题

第六部分  计算复杂性初步
  第20章  问题与归约
    20.1  NP问题
      20.1.1  优化问题和判定问题
      20.1.2  P问题的定义
      20.1.3  NP问题的定义
    20.2  问题间的归约
      20.2.1  归约的定义
      20.2.2  归约的代价与问题难度的比较
    20.3  习题
  第21章  NP完全性理论初步
    21.1  NP完全问题的定义
    21.2  NP完全性证明的初步知识
      21.2.1  一般问题和特例问题
      21.2.2  等价问题
    21.3  习题
  附录A  数学归纳法
  附录B  二叉树
  参考文献

内容大纲

作者介绍

目录

同类热销排行榜

推荐书目