算法设计与分析:C++语言描述

本书特色

[

本书为普通高等教育“十一五”*规划教材。 本书内容分为3部分：算法和算法分析、算法设计策略、求解困难问题。第1部分介绍问题求解方法、算法复杂度和分析、递归算法和递推关系；第2部分讨论常用的算法设计策略：基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法；第3部分介绍NP完全问题、*算法、近似算法、遗传算法和密码算法，其中遗传算法是本次修订新增的内容。书中还介绍了两种新的数据结构：跳表和伸展树，以及它们特定的算法分析方法，并对现代密码学做了简要论述。

]

内容简介

[

本书为普通高等教育“十一五”*规划教材。 新增遗传算法。

]

作者简介

[

教授，南京邮电大学计算机学院，主持了多项信息产业部基金项目的研究工作，并负责了多项企业办公自动化和信息管理网络系统的研制开发。出版多本教材。曾获江苏省普通高校教学成果三等奖，其主持的《数据结构》课程获江苏省高校一类优秀课程。

]

目录

目 录第1部分 算法和算法分析 第1章 算法问题求解基础 11.1 算法概述 11.1.1 什么是算法 11.1.2 为什么学习算法 31.2 问题求解方法 31.2.1 问题和问题求解 41.2.2 问题求解过程 41.2.3 系统生命周期 51.3 算法设计与分析 51.3.1 算法问题求解过程 51.3.2 如何设计算法 61.3.3 如何表示算法 61.3.4 如何确认算法 61.3.5 如何分析算法 71.4 递归和归纳 71.4.1 递归 71.4.2 递归算法示例 91.4.3 归纳证明 11本章小结 12习题1 13第2章 算法分析基础 142.1 算法复杂度 142.1.1 什么是好的算法 142.1.2 影响程序运行时间的因素 152.1.3 算法的时间复杂度 162.1.4 使用程序步分析算法 172.1.5 算法的空间复杂度 182.2 渐近表示法 192.2.1 大O记号 192.2.2 ?记号 202.2.3 ?记号 212.2.4 小o记号 212.2.5 算法按时间复杂度分类 212.3 递推关系 222.3.1 递推方程 222.3.2 替换方法 232.3.3 迭代方法 232.3.4 主方法 242.4 分摊分析 252.4.1 聚集方法 262.4.2 会计方法 262.4.3 势能方法 27本章小结 28习题2 28第3章 伸展树与跳表 303.1 伸展树 303.1.1 二叉搜索树 303.1.2 自调节树和伸展树 303.1.3 伸展操作 313.1.4 伸展树类 323.1.5 旋转的实现 343.1.6 插入运算的实现 343.1.7 分摊分析 363.2 跳表 383.2.1 什么是跳表 383.2.2 跳表类 393.2.3 级数分配 413.2.4 插入运算的实现 423.2.5 性能分析 43本章小结 44习题3 44第2部分 算法设计策略第4章 基本搜索和遍历方法 454.1 基本概念 454.2 图的搜索和遍历 464.2.1 搜索方法 464.2.2 邻接表类 474.2.3 广度优先搜索 484.2.4 深度优先搜索 504.3 双连通分量 534.3.1 基本概念 534.3.2 发现关节点 544.3.3 构造双连通图 574.4 与或图 584.4.1 问题分解 584.4.2 判断与或树是否可解 594.4.3 构建解树 61本章小结 62习题4 62第5章 分治法 645.1 一般方法 645.1.1 分治法的基本思想 645.1.2 算法分析 655.1.3 数据结构 665.2 求*大*小元 675.2.1 分治法求解 675.2.2 时间分析 685.3 二分搜索 695.3.1 分治法求解 695.3.2 对半搜索 705.3.3 二叉判定树 715.3.4 搜索算法的时间下界 735.4 排序问题 745.4.1 合并排序 745.4.2 快速排序 765.4.3 排序算法的时间下界 805.5 选择问题 825.5.1 分治法求解 825.5.2 随机选择主元 825.5.3 线性时间选择算法 845.5.4 时间分析 865.5.5 允许重复元素的选择算法 865.6 斯特拉森矩阵乘法 875.6.1 分治法求解 875.6.2 斯特拉森分治法 88本章小结 88习题5 88第6章 贪心法 916.1 一般方法 916.2 背包问题 926.2.1 问题描述 926.2.2 贪心法求解 926.2.3 算法正确性 946.3 带时限的作业排序 956.3.1 问题描述 956.3.2 贪心法求解 956.3.3 算法正确性 976.3.4 可行性判定 976.3.5 作业排序贪心算法 986.3.6 一种改进算法 996.4 *佳合并模式 1026.4.1 问题描述 1026.4.2 贪心法求解 1036.4.3 算法正确性 1046.5 *小代价生成树 1056.5.1 问题描述 1056.5.2 贪心法求解 1056.5.3 普里姆算法 1066.5.4 克鲁斯卡尔算法 1096.5.5 算法正确性 1116.6 单源*短路径 1116.6.1 问题描述 1126.6.2 贪心法求解 1126.6.3 迪杰斯特拉算法 1126.6.4 算法正确性 1156.7 磁带*优存储 1166.7.1 单带*优存储 1166.7.2 多带*优存储 1176.8 贪心法的基本要素 1196.8.1 *优量度标准 1196.8.2 *优子结构 119本章小结 120习题6 120第7章 动态规划法 1227.1 一般方法和基本要素 1227.1.1 一般方法 1227.1.2 基本要素 1237.1.3 多段图问题 1237.1.4 资源分配问题 1267.1.5 关键路径问题 1277.2 每对结点间的*短路径 1297.2.1 问题描述 1297.2.2 动态规划法求解 1307.2.3 弗洛伊德算法 1317.2.4 算法正确性 1327.3 矩阵连乘 1327.3.1 问题描述 1327.3.2 动态规划法求解 1337.3.3 矩阵连乘算法 1347.3.4 备忘录方法 1367.4 *长公共子序列 1377.4.1 问题描述 1377.4.2 动态规划法求解 1377.4.3 *长公共子序列算法 1387.4.4 算法的改进 1407.5 *优二叉搜索树 1407.5.1 问题描述 1407.5.2 动态规划法求解 1417.5.3 *优二叉搜索树算法 1437.6 0/1背包 1447.6.1 问题描述 1447.6.2 动态规划法求解 1457.6.3 0/1背包算法框架 1477.6.4 0/1背包算法 1507.6.5 性能分析 1527.6.6 使用启发式方法 1537.7 流水作业调度 1547.7.1 问题描述 1547.7.2 动态规划法求解 1557.7.3 Johnson算法 157本章小结 158习题7 158第8章 回溯法 1608.1 一般方法 1608.1.1 基本概念 1608.1.2 剪枝函数和回溯法 1618.1.3 回溯法的效率分析 1638.2 n-皇后 1638.2.1 问题描述 1638.2.2 回溯法求解 1648.2.3 n-皇后算法 1658.2.4 时间分析 1668.3 子集和数 1678.3.1 问题描述 1678.3.2 回溯法求解 1678.3.3 子集和数算法 1688.4 图的着色 1708.4.1 问题描述 1708.4.2 回溯法求解 1708.4.3 图着色算法 1718.4.4 时间分析 1728.5 哈密顿环 1728.5.1 问题描述 1728.5.2 哈密顿环算法 1738.6 0/1背包 1748.6.1 问题描述 1748.6.2 回溯法求解 1748.6.3 限界函数 1758.6.4 0/1背包算法 1768.7 批处理作业调度 1788.7.1 问题描述 1788.7.2 回溯法求解 1788.7.3 批处理作业调度算法 178本章小结 180习题8 180第9章 分枝限界法 1829.1 一般方法 1829.1.1 分枝限界法概述 1829.1.2 LC分枝限界法 1849.1.3 15谜问题 1859.2 求*优解的分枝限界法 1879.2.1 上下界函数 1879.2.2 FIFO分枝限界法 1889.2.3 LC分枝限界法 1899.3 带时限的作业排序 1909.3.1 问题描述 1909.3.2 分枝限界法求解 1909.3.3 带时限作业排序算法 1919.4 0/1背包 1939.4.1 问题描述 1939.4.2 分枝限界法求解 1949.4.3 0/1背包算法 1959.5 旅行商问题 1979.5.1 问题描述 1979.5.2 分枝限界法求解 1989.6 批处理作业调度 2019.6.1 问题描述 2019.6.2 分枝限界法求解 2019.6.3 批处理作业调度算法 202本章小结 205习题9 205 第3部分 求解困难问题 第10章 NP完全问题 20710.1 基本概念 20710.1.1 不确定算法和不确定机 20810.1.2 可满足性问题 21010.1.3 P类和NP类问题 21110.1.4 NP难度和NP完全问题 21110.2 Cook定理和证明 21210.2.1 Cook定理 21210.2.2 简化的不确定机模型 21210.2.3 证明Cook定理 21410.3 一些典型的NP完全问题 21710.3.1 *大集团 21710.3.2 顶点覆盖 21810.3.3 三元CNF可满足性 21910.3.4 图的着色数 22010.3.5 有向哈密顿环 22110.3.6 恰切覆盖 22310.3.7 子集和数 22510.3.8 分划问题 225本章小结 226习题10 226第11章 随机算法 22811.1 基本概念 22811.1.1 随机算法概述 22811.1.2 随机数发生器 22811.1.3 随机算法分类 22811.2 拉斯维加斯算法 22911.2.1 标识重复元素算法 22911.2.2 性能分析 23011.3 蒙特卡罗算法 23111.3.1 素数测试问题 23111.3.2 伪素数测试 23111.3.3 米勒-拉宾算法 23211.3.4 性能分析 23311.4 舍伍德算法 23411.4.1 随机快速排序算法 23411.4.2 舍伍德算法的其他应用 234本章小结 234习题11 235第12章 近似算法 23612.1 近似算法的性能 23612.1.1 基本概念 23612.1.2 绝对性能保证 23612.1.3 相对性能保证 23712.1.4 近似方案 23812.2 绝对近似算法 23812.2.1 *多程序存储问题 23812.2.2 NP难度绝对近似算法 23912.3 ?-近似算法 24012.3.1 顶点覆盖近似算法 24012.3.2 旅行商问题 24112.3.3 NP难度?-近似旅行商问题 24212.3.4 具有三角不等式性质的旅行商问题 24312.3.5 任务调度近似算法 24412.4 ?(n)-近似算法 24712.4.1 集合覆盖问题 24712.4.2 集合覆盖近似算法 24712.4.3 ln(n)-近似算法 24812.5 多项式时间近似方案 24912.5.1 任务调度近似方案 24912.5.2 多项式时间近似方案 25112.6 子集和数的完全多项式时间近似方案 25112.6.1 子集和数的指数时间算法 25112.6.2 完全多项式时间近似方案 252本章小结 254习题12 254第13章 遗传算法 25613.1 进化计算 25613.2 遗传算法的生物学基础 25713.3 遗传算法的基本思想 25813.4 基本遗传算法 25913.4.1 基本遗传算法构成要素 25913.4.2 基本遗传算法流程图 26213.5 遗传算法的特点和应用 26213.5.1 遗传算法的特点 2

封面

书名:算法设计与分析:C++语言描述

作者:陈慧南编著

页数:11,304页

定价:¥49.0

出版社:电子工业出版社

出版日期:2018-01-01

ISBN:9787121330544

PDF电子书大小:96MB 高清扫描完整版