信息学进阶

"“创客教育系列丛书”的特色如下： （1）知名作者，经验丰富，见解独到 作者对我国的创客教育有着深入的研究和分析，并具有丰富的在基础教育阶段开展创客教育活动的教育教学经验，因此，更能知道目标受众需要什么，并根据目标受众的需求，将干货内容进行针对性的呈现。 （2）打通热点，专攻痛点，单点很好 重点解决父母及社会关心的孩子创新思维能力培养以及孩子未来发展的痛点，为目标受众提供一套能够多方面提高孩子创新能力的教材，让丛书内容能够更好地满足目标受众的核心需求。 （3）案例丰富，方法众多，突破困境 重在思维方法和动手实践的培养，让孩子们不仅能通过丰富的案例和方法举一反三，而且能够通过项目学习，与同学合作、探究学习，突破困境，培养创新素养，提高动手能力和解决真实问题的能力。 "

《信息学进阶》为创客教育系列丛书的高中第三册，共分为7章，涵盖了高中信息学竞赛的所有知识点。内容描述力求化繁为简，深入浅出，针对每个重要的知识点配以经典实例进行精心剖析，结合清晰的代码及生动的文字、画龙点睛的注解，力求通俗易懂。《信息学进阶》由全国有名信息学国际金牌教练、NOI钻石教师宋新波老师主笔，NOI金牌教师熊超等老师参与编写，与创客教育教材初中第三册《信息学初步》一脉相承，是初中版基础上的深化与拓展，属于发展性课程及研究性课程范畴，因而本书不再重复信息学基本知识，主要侧重于算法、数据结构专题，假如你是一名初学者，强烈建议先阅读《信息学初步》。《信息学进阶》为创客教育系列丛书高中第三册，适合高中三年级学生阅读使用。

"主编介绍 孙晓奎，中国教育信息化创客教育研究中心秘书长，《中国教育信息化》《基础教育参考》编辑。 胡永跃，粤教版高中信息技术教材分册主编，出版《中学创客教育丛书》《Arduino科技课堂宝典》等书籍。 陈明宏，广东省特级教师，中山市小学、初中信息技术教材主编，粤教版高中信息技术教材分册主编。 "

第1章 深度优先搜索的优化
1．1 剪枝优化
【知识讲解】
【实践巩固】
1．2 迭代加深优化
【知识讲解】
【实践巩固】
第2章 广度搜索的优化
2．1 双向广度优先搜索
2．2 优先队列广度优先搜索
2．3 Hash判重
第3章 动态规划进阶
3．1 区间类动态规划
3．2 树形动态规划
3．3 数位DP
3．3．1 数位DP的基本思想
3．3．2 数位DP的应用
3．4 状态压缩DP
3．4．1 状态压缩DP的基本思想
3．4．2 状态压缩DP的应用
3．5 单调队列优化
3．6 斜率优化动态规划
3．6．1 知识讲解
3．6．2 实践巩固
第4章 图论
4．1 图的基本概念
4．1．1 图的一些定义和概念
4．1．2 图的存储结构
4．2 图的遍历
4．2．1 深度优先遍历和广度优先遍历
4．2．2 一笔画问题
4．3 最短路径算法
4．3．1 Bellman-Ford算法的实现及运用
4．3．2 SPFA算法的实现及运用
4．3．3 Dijkstra算法的实现及运用
4．3．4 Floyd算法的实现及运用
4．4 图的连通性
4．4．1 无向图的割点与桥
4．4．2 无向图的双连通分量
4．4．3 有向图的强连通分量
4．5 最小生成树
4．5．1 Prim算法
4．5．2 Kruskal算法
4．6 拓扑排序与关键路径
4．6．1 AOV网
4．6．2 拓扑排序算法的基本思想与应用
4．6．3 关键路径
第5章 字符串算法
5．1 哈希和哈希表
5．2 KMP算法
5．3 Trie字典树
5．3．1 Trie字典树的思想
5．3．2 Trie字典树的应用
第6章 高级数据结构
6．1 并查集
6．2 树状数组
6．3 RMQ
6．4 快速幂与矩阵乘法
6．4．1 快速幂
6．4．2 矩阵乘法
6．4．3 LCA
6．5 线段树
6．5．1 线段树的基本思想
6．5．2 线段树的单点修改
6．5．3 线段树的区间查询
6．5．4 区间修改和标记
6．6 平衡树
6．6．1 二叉查找树的基本思想与应用
6．6．2 Treap的基本思想与应用
第7章 数学基础
7．1 GCD与拓展GCD
7．1．1 优选公约数GCD的求法
7．1．2 扩展欧几里得算法的基本思想与应用
7．2 同余定理
7．2．1 同余定理概述
7．2．2 线性同余方程的求解
7．3 逆元问题
7．3．1 逆元问题的求解
7．3．2 逆元的应用
7．4 容斥原理