正版书籍 计算机科学与技术学科研究生教材:计算机算法基础沈孝钧机械工业出版社 下载 pdf 百度网盘 epub 免费 2025 电子版 mobi 在线

　　《计算机科学与技术学科研究生教材：计算机算法基础》是作者20多年在国内外教学与科研实践的结晶，深入浅出地介绍计算机算法中涉及的基本理论和方法。主要内容包括算法复杂度的概念和表达、分治法、贪心法、动态规划、图的遍历技术、平扫线技术、回溯法、分支限界法、剪枝等。在讲述这些理论和方法的同时，介绍一系列重要问题的算法，包括排序问题、选择问题、最小支撑树问题、最短路径问题、网络流问题、二分图的匹配问题、字符串的匹配问题以及若干几何算法问题，并将这些问题的解法及所用技术紧密相连，有机地编排在一起。此外，本书还介绍了问题本身固有的计算复杂性的概念和NP完全问题的理论以及近似算法。

《计算机科学与技术学科研究生教材：计算机算法基础》讲解细腻、分析透彻，以探索解决问题的方式深入分析了大量案例，使读者能清晰触摸到作者的思维方法，并建立起自己独立思考的学习习惯。本书可以作为计算机科学等相关专业本科生、研究生的教材，也可供从事计算机算法设计与分析工作的教师与研究人员参考。

前言

教学建议

第1章 概述

1.1 算法与数据结构及程序的关系

1.1.1 什么是算法

1.1.2 算法与数据结构的关系

1.1.3 算法与程序的关系

1.1.4 选择排序的例子

1.1.5 算法的伪码表示

1.2 算法复杂度分析

1.2.1 算法复杂度的度量

1.2.2 算法复杂度与输入数据规模的关系

1.2.3 输入数据规模的度量模型

1.2.4 算法复杂度分析中的两个简化假设

1.2.5 最好情况、最坏情况和平均情况的复杂度分析

1.3 函数增长渐近性态的比较

1.3.1 三种比较关系及O、Ω、Θ记号

1.3.2 表示算法复杂度的常用函数

1.4 算法复杂度与问题复杂度的关系

1.4.1 问题复杂度是算法复杂度的下界

1.4.2 问题复杂度与算法

1.4.3 易处理问题和难处理问题

习题

第2章 分治法

2.1 分治法原理

2.1.1 二元搜索的例子

2.1.2 表示复杂度的递推关系

2.2 递推关系求解

2.2.1 替换法

2.2.2 序列求和法和递归树法

2.2.3 常用序列和公式

2.2.4 主方法求解

习题

第3章 基于比较的排序算法

3.1 插入排序

3.1.1 插入排序的算法

3.1.2 插入排序算法的复杂度分析

3.1.3 插入排序的优缺点

3.2 合并排序

3.2.1 合并算法及其复杂度

3.2.2 合并排序的算法及其复杂度

3.2.3 合并排序的优缺点

3.3 堆排序

3.3.1 堆的数据结构

3.3.2 堆的修复算法及其复杂度

3.3.3 为输入数据建堆

3.3.4 堆排序算法

3.3.5 堆排序算法的复杂度

3.3.6 堆排序算法的优缺点

3.3.7 堆用作优先队列

3.4 快排序

3.4.1 快排序算法

3.4.2 快排序算法最坏情况复杂度

3.4.3 快排序算法平均情况复杂度

3.4.4 快排序算法最好情况复杂度

3.4.5 快排序算法优缺点

习题

第4章 不基于比较的排序算法

4.1 比较排序的下界

4.1.1 决策树模型及最坏情况下界

4.1.2 二叉树的外路径总长与平均情况下界

4.1.3 二叉树的全路径总长及堆排序最好情况下界

4.2 不基于比较的线性时间排序算法

4.2.1 计数排序

4.2.2 基数排序

4.2.3 桶排序

习题

第5章 中位数和任一顺序数的选择

5.1 问题定义

5.2 数和最小数的选择

5.2.1 和最小顺序数的选择算法及其复杂度

5.2.2 同时找出数和最小数的算法

5.3 线性时间找出任一顺序数的算法

5.3.1 最坏情况复杂度为O（n）的算法

5.3.2 平均情况复杂度为O（n）的算法

5.4 找出k个顺序数的算法

5.4.1 一个理论联系实际的问题

5.4.2 利用堆来找k个的顺序数的算法

5.4.3 利用锦标赛树来找k个顺序数的算法

习题

第6章 动态规划

6.1 动态规划的基本原理

6.2 矩阵连乘问题

6.3 最长公共子序列问题

6.4 二元搜索树

6.5 多级图及其应用

6.6 最长递增子序列问题

习题

第7章 贪心算法

7.1 邮局设置问题

7.2 活动安排问题

7.3 哈夫曼编码问题

7.3.1 前缀码

7.3.2 前缀码——哈夫曼编码

7.4 加油计划问题

习题

第8章 图的周游算法

8.1 图的表示

8.1.1 邻接表

8.1.2 邻接矩阵

8.2 广度优先搜索及应用

8.2.1 广度优先搜索策略

8.2.2 广度优先搜索算法及距离树

8.2.3 无向图的二着色问题

8.3 深度优先搜索及应用

8.3.1 深度优先搜索策略

8.3.2 深度优先搜索算法和深度优先树

8.3.3 深度优先搜索算法举例和图中边的分类

8.3.4 拓扑排序

8.3.5 无回路有向图中最长路径问题及应用

8.3.6 有向图的强连通分支的分解

8.3.7 无向图的双连通分支的分解

习题

第9章 图的最小支撑树

9.1 计算最小支撑树的一个通用的贪心算法策略

9.2 Kruskal算法

9.3 Prim算法

习题

第10章 单源最短路径

10.1 Dijkstra算法

10.2 Bellman-Ford算法

习题

第11章 网络流

11.1 网络模型和网络流问题

11.2 网络中流与割的关系

11.2.1 网络中的割及其容量

11.2.2 剩余网络和增广路径

11.2.3 流最小割定理

11.3 Ford-Fulkerson方法

11.3.1 Ford-Fulkerson的通用方法

11.3.2 Edmonds-Karp算法

11.3.3 Dinic算法

11.3.4 0-1网络的流问题

11.4 二部图的匹配问题

11.4.1 用网络流求二部图的匹配算法

11.4.2 Philip-Hall婚配定理

11.4.3 Birkhoff-vonNeuman定理

11.5 推进-重标号算法简介

11.5.1 预流和高度函数

11.5.2 在剩余图中对顶点的两个操作

11.5.3 推进-重标号算法的初始化

11.5.4 推进-重标号的通用算法

习题

第12章 计算几何基础

12.1 平面线段及相互关系

12.1.1 向量的点积和叉积

12.1.2 平面线段的相互关系

12.2 平扫线技术和线段相交的确定

12.2.1 平扫线的状态

12.2.2 用平扫线确定线段相交的算法

12.3 平面点集的凸包

12.3.1 Graham扫描法

12.3.2 Jarvis行进法

12.4 最近点对问题

习题

第13章 字符串匹配

13.1 一个朴素的字符串匹配算法

13.2 Rabin-Karp算法

13.3 基于有限状态自动机的匹配算法

13.3.1 有限状态自动机简介

13.3.2 字符串匹配自动机

13.3.3 基于有限状态自动机的串匹配算法

13.4 Knuth-Morris-Pratt（KMP）算法

13.4.1 模式的前缀函数

13.4.2 KMP算法的伪码

习题

第14章 NP完全问题

14.1 预备知识

14.1.1 图灵机

14.1.2 符号集和编码对计算复杂度的影响

14.1.3 判断型问题和优化型问题及其关系

14.1.4 判断型问题的形式语言表示

14.1.5 多项式关联和多项式归约

14.2 P和NP语言类

14.2.1 非确定图灵机和NP语言类

14.2.2 多项式检验算法和NP类语言

14.3 NP完全语言类和NP完全问题

14.3.1 第一个NPC问题

14.3.2 若干著名NPC问题的证明

习题

第15章 近似算法

15.1 近似算法的性能评价

15.2 顶点覆盖问题

15.3 货郎担问题

15.3.1 满足三角不等式关系的货郎担问题

15.3.2 无三角不等式关系的一般货郎担问题

15.4 集合覆盖问题

15.5 MAX-3-SAT问题

15.6 加权的顶点覆盖问题

15.7 子集和问题

15.7.1 一个保证解的指数型算法

15.7.2 子集和问题的一个完全多项式近似机制

15.8 鸿沟定理和不可近似性

15.8.1 鸿沟定理

15.8.2 任务均匀分配问题

习题

第16章 穷举搜索

16.1 搜索问题及方法的描述

16.2 回溯法

16.2.1 回溯法的通用算法

16.2.2 n皇后问题

16.2.3 子集和问题

16.2.4 回溯法的效率估计

16.3 分支限界法

16.3.1 分支限界法解n皇后问题

16.3.2 0/1背包问题

16.4 博弈树和α-β剪枝

16.4.1 博弈树及其评估的方法

16.4.2 α-β剪枝法

习题

附录红黑树

参考文献

暂时没有内容

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：正版书籍 计算机科学与技术学科研究生教材:计算机算法基础沈孝钧机械工业出版社在线阅读

在线听书地址：正版书籍 计算机科学与技术学科研究生教材:计算机算法基础沈孝钧机械工业出版社在线收听

在线购买地址：正版书籍 计算机科学与技术学科研究生教材:计算机算法基础沈孝钧机械工业出版社在线购买

暂无原文赏析，正在全力查找中！

编辑推荐

暂时没有内容

书摘插图

暂时没有内容

书籍介绍

计算机算法是计算机科学的一个重要分支，也是一个难点。本书作者根据自己20多年在国内、国外的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分最主要的算法技术，包括：分治法、贪心法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、最小生成树问题、最短路径问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等，还介绍了问题本身的计算复杂性的概念和NP完全问题的理论，并介绍近似算法的设计和分析。

主要特点如下

精心设计了大量案例，并深入浅出地进行分析，使读者能够逐步领悟到算法的精妙之处。

推理严谨、丝丝入扣，对比了各种算法的方案，使学生能养成自觉地运用所学方法去追求最好结果的良好习惯。

以探索解决问题的方式进行讲解，使读者能清晰触摸到作者的思维方法，并建立起自己独立思考的学习习惯。

为了方便教学，每章配有难易适度的习题，并为教师免费提供电子课件。