书籍详情
信息学进阶
作者：宋新波 熊 超 陈智敏 黄细光
出版社：清华大学出版社
出版时间：2020-08-01
ISBN：9787302559931
定价：¥49.80
购买这本书可以去
内容简介
《信息学进阶》为创客教育系列丛书的高中第三册，共分为7 章，涵盖了高中信息学竞赛的所有知识点。内容描述力求化繁为简，深入浅出，针对每个重要的知识点配以经典实例进行精心剖析，结合清晰的代码及生动的文字、画龙点睛的注解，力求通俗易懂。 《信息学进阶》由全国著名信息学国际金牌教练、NOI 钻石教师宋新波老师主笔，NOI 金牌教师熊超等老师参与编写，与创客教育教材初中第三册《信息学初步》一脉相承，是初中版基础上的深化与拓展，属于发展性课程及研究性课程范畴，因而本书不再重复信息学基本知识，主要侧重于算法、数据结构专题，假如你是一名初学者，强烈建议先阅读《信息学初步》。 《信息学进阶》为创客教育系列丛书高中第三册，适合高中三年级学生阅读使用。
作者简介
主编介绍孙晓奎，中国教育信息化创客教育研究中心秘书长，《中国教育信息化》《基础教育参考》编辑。胡永跃，粤教版高中信息技术教材分册主编，出版《中学创客教育丛书》《Arduino科技课堂宝典》等书籍。陈明宏，广东省特级教师，中山市小学、初中信息技术教材主编，粤教版高中信息技术教材分册主编。
目录
第１章 深度优先搜索的优化 1
1.1 剪枝优化 2
【知识讲解】 2
【实践巩固】 5
1.2 迭代加深优化 5
【知识讲解】 5
【实践巩固】 9
第2 章 广度搜索的优化 11
2.1 双向广度优先搜索 12
2.2 优先队列广度优先搜索 13
2.3 Hash 判重 15
第3 章 动态规划进阶 19
3.1 区间类动态规划 20
3.2 树形动态规划 23
3.3 数位DP 27
3.3.1 数位DP 的基本思想 27
3.3.2 数位DP 的应用 29
3.4 状态压缩DP 34
3.4.1 状态压缩DP 的基本思想 34
3.4.2 状态压缩DP 的应用 36
3.5 单调队列优化 42
3.6 斜率优化动态规划 46
3.6.1 知识讲解 46
3.6.2 实践巩固 50
第4 章 图论 51
4.1 图的基本概念 52
4.1.1 图的一些定义和概念 52
4.1.2 图的存储结构 54
4.2 图的遍历 58
4.2.1 深度优先遍历和广度优先遍历 58
4.2.2 一笔画问题 60
4.3 短路径算法 67
4.3.1 Bellman-Ford 算法的实现及运用 67
4.3.2 SPFA 算法的实现及运用 70
4.3.3 Dijkstra 算法的实现及运用 73
4.3.4 Floyd 算法的实现及运用 75
4.4 图的连通性 77
4.4.1 无向图的割点与桥 77
4.4.2 无向图的双连通分量 80
4.4.3 有向图的强连通分量 81
4.5 小生成树 83
4.5.1 Prim 算法 83
4.5.2 Kruskal 算法 84
4.6 拓扑排序与关键路径 86
4.6.1 AOV 网 86
4.6.2 拓扑排序算法的基本思想
与应用 87
4.6.3 关键路径 89
第5 章 字符串算法 93
5.1 哈希和哈希表 94
5.2 KMP 算法 97
5.3 Trie 字典树 104
5.3.1 Trie 字典树的思想 104
5.3.2 Trie 字典树的应用 106
第6 章 高级数据结构 111
6.1 并查集 112
6.2 树状数组 115
6.3 RMQ 118
6.4 快速幂与矩阵乘法 122
6.4.1 快速幂 122
6.4.2 矩阵乘法 124
6.4.3 LCA 126
6.5 线段树 131
6.5.1 线段树的基本思想 131
6.5.2 线段树的单点修改 133
6.5.3 线段树的区间查询 134
6.5.4 区间修改和标记 139
6.6 平衡树 144
6.6.1 二叉查找树的基本思想与应用 144
6.6.2 Treap 的基本思想与应用 148
第7 章 数学基础 153
7.1 GCD 与拓展GCD 154
7.1.1 公约数GCD 的求法 154
7.1.2 扩展欧几里得算法的基本思想与应用 158
7.2 同余定理 164
7.2.1 同余定理概述 164
7.2.2 线性同余方程的求解 167
7.3 逆元问题 168
7.3.1 逆元问题的求解 168
7.3.2 逆元的应用 171
7.4 容斥原理 174
1.1 剪枝优化 2
【知识讲解】 2
【实践巩固】 5
1.2 迭代加深优化 5
【知识讲解】 5
【实践巩固】 9
第2 章 广度搜索的优化 11
2.1 双向广度优先搜索 12
2.2 优先队列广度优先搜索 13
2.3 Hash 判重 15
第3 章 动态规划进阶 19
3.1 区间类动态规划 20
3.2 树形动态规划 23
3.3 数位DP 27
3.3.1 数位DP 的基本思想 27
3.3.2 数位DP 的应用 29
3.4 状态压缩DP 34
3.4.1 状态压缩DP 的基本思想 34
3.4.2 状态压缩DP 的应用 36
3.5 单调队列优化 42
3.6 斜率优化动态规划 46
3.6.1 知识讲解 46
3.6.2 实践巩固 50
第4 章 图论 51
4.1 图的基本概念 52
4.1.1 图的一些定义和概念 52
4.1.2 图的存储结构 54
4.2 图的遍历 58
4.2.1 深度优先遍历和广度优先遍历 58
4.2.2 一笔画问题 60
4.3 短路径算法 67
4.3.1 Bellman-Ford 算法的实现及运用 67
4.3.2 SPFA 算法的实现及运用 70
4.3.3 Dijkstra 算法的实现及运用 73
4.3.4 Floyd 算法的实现及运用 75
4.4 图的连通性 77
4.4.1 无向图的割点与桥 77
4.4.2 无向图的双连通分量 80
4.4.3 有向图的强连通分量 81
4.5 小生成树 83
4.5.1 Prim 算法 83
4.5.2 Kruskal 算法 84
4.6 拓扑排序与关键路径 86
4.6.1 AOV 网 86
4.6.2 拓扑排序算法的基本思想
与应用 87
4.6.3 关键路径 89
第5 章 字符串算法 93
5.1 哈希和哈希表 94
5.2 KMP 算法 97
5.3 Trie 字典树 104
5.3.1 Trie 字典树的思想 104
5.3.2 Trie 字典树的应用 106
第6 章 高级数据结构 111
6.1 并查集 112
6.2 树状数组 115
6.3 RMQ 118
6.4 快速幂与矩阵乘法 122
6.4.1 快速幂 122
6.4.2 矩阵乘法 124
6.4.3 LCA 126
6.5 线段树 131
6.5.1 线段树的基本思想 131
6.5.2 线段树的单点修改 133
6.5.3 线段树的区间查询 134
6.5.4 区间修改和标记 139
6.6 平衡树 144
6.6.1 二叉查找树的基本思想与应用 144
6.6.2 Treap 的基本思想与应用 148
第7 章 数学基础 153
7.1 GCD 与拓展GCD 154
7.1.1 公约数GCD 的求法 154
7.1.2 扩展欧几里得算法的基本思想与应用 158
7.2 同余定理 164
7.2.1 同余定理概述 164
7.2.2 线性同余方程的求解 167
7.3 逆元问题 168
7.3.1 逆元问题的求解 168
7.3.2 逆元的应用 171
7.4 容斥原理 174
猜您喜欢
