正版
随机算法导论
- 书名
- 随机算法导论
- 作者
- 张鹏 著 著
- 出版社
- 山东大学出版社
- 出版时间
- 2025-10-01
- ISBN
- 9787560785721
- 货号
- 1204024041
- 品相
- 全新
- 分类
- 当代·科技
- 书名
- 随机算法导论
- 作者
- 张鹏 著 著
- 出版社
- 山东大学出版社
- 出版时间
- 2025-10-01
- ISBN
- 9787560785721
- 货号
- 1204024041
- 品相
- 全新
- 分类
- 当代·科技
目录▼
第一章 计算模型
1.1 对计算建模
1.2 图灵机和运行时间
1.3 不同类型的图灵机
1.4 通用图灵机
1.5 停机问题和不可计算性
第二章 P与NP
2.1 问题和语言
2.2 P类
2.3 NP类
2.4 非确定图灵机和NP的另一个定义
2.5 第一个NP完全问题
2.6 经典的NP完全问题
2.7 困难问题举例
第三章 随机算法简介
3.1 概率空间和随机事件
3.2 找中位数
3.3 最小割算法
3.4 随机算法的分类
第四章 随机算法举例
4.1 验证矩阵相乘
4.2 快速排序
4.3 判断多项式恒等
4.4 二分图上的完美匹配
第五章 尾不等式
5.1 马尔可夫不等式和切比雪夫不等式
5.2 奖券收集问题
5.3 切尔诺夫界
5.4 对3-可着色的稠密图着色
第六章 球和箱子模型
6.1 箱子中至少有两个球
6.2 箱子中恰好有k个球
6.3 最满的箱子中有多少个球
第七章 概率方法
7.1 使用条件期望的去随机化技术
7.2 概率大于零的存在性证明技术
7.3 洛瓦兹局部引理
第八章 马尔可夫链和随机游走
8.1 马尔可夫链的定义和表示
8.2 2-SAT问题的随机算法
8.3 状态分类
8.4 平稳分布
8.5 无向图上的随机游走
第九章 随机舍入
9.1 集合覆盖问题
9.2 最大可满足性问题
9.3 设施选址问题
9.4 最大满意边问题
第十章 图论问题
10.1 随机图上的哈密尔顿圈问题
10.2 在线匹配问题
第十一章 网络优化问题
11.1 最大割问题的随机超平面舍入算法
11.2 租或买网络设计问题
11.3 标签s-t割问题的整性间隙
第十二章 数论问题
12.1 素性检测
12.2 原根
12.3 勒让德符号的性质
12.4 勒让德符号的计算
12.5 判定素数的概率
参考文献
文摘▼
本书着重介绍了随机算法的基本概念、技术基础、设计方法和分析方法,同时也介绍了计算复杂性理论中P类和NP类的基本概念。本书内容概括如下:首先,讲述计算模型和计算复杂性的基本概念;其次,讲述随机算法的基本概念和技术基础;最后,讲述面向各专题的随机算法设计和分析方法。本书是计算机相关专业本科算法课程的延伸与深化,着重培养学生运用数学知识进行理论证明与分析的能力。本书可作为计算机相关专业研究生课程的参考教材,也可供科研人员阅读借鉴。





