信息学进阶

图书标准信息

• 作者 宋新波 熊 超 陈智敏 黄细光
• 出版社 清华大学出版社
• 出版时间 2020-08
• 版次 1
• ISBN 9787302559931
• 定价 49.80元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 184页
• 字数 276千字

【内容简介】

《信息学进阶》为创客教育系列丛书的高中第三册，共分为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