【现货速发】信息学进阶

序
全球化和人工智能、大数据、区块链等技术的飞速发展，正在深刻改变着人才需求和教育形态，促使学生掌握在21 世纪生存与成功所需的知识与技能，它们被称为21 世纪的高阶思维技能、更深层次的学习能力以及复杂的思维和沟通技能。创客教育与STEM 教育作为跨学科综合教育的有效形态，在全球范围内，特别是在美国、英国、德国、以色列、芬兰、日本等发达国家，已被提升到国家发展及人才战略的高度。近年来，STEM 教育理念在我国也越来越受到广泛重视并达成共识，其优越性体现在以下方面。
一是用知识解决问题。学生需要应用知识和技能，并且必须能够将知识和技能、学习和能力、惰性学习和主动学习、创造性和适应性的学习转化为有价值的高阶思维的分析、评价与创造。
二是批判性思维。批判性思维被认为是 21 世纪学习的基础，包括对信息的获取、分析和综合，并可以被教授、练习和掌握。批判性思维还利用了其他技能，如交流、信息素养能力，以及检验、分析、解释和评估证据的能力。
三是问题解决能力。21 世纪学生的另一个基本能力是解决问题，研究和解决问题的技能包括识别和搜索、选择、评估、组织和权衡备选方案和解释信息的能力。
四是沟通与协作。良好的沟通能力，包括口头和书面表达令人信服的想法的能力，能提出明确的意见，能接受连贯的指示，并通过言语激励他人，这些能力在工作场所和公共生活中都被高度重视。规范的合作学习需要改变课程、教学、评估实践、学习环境和教师的专业发展，21 世纪的合作将在学校内部、学校之间、学校内外的沟通之间发展。
五是创新与创造力。在全球化竞争和任务自动化的今天，创新能力和创新精神正在迅速成为职业和个人成功的必要条件，勇于“抓住”问题和实践探究“开拓新领域”的能力，激发新的思维方式，提出新的想法和解决方案，提出不熟悉的问题，并得出意想不到的答案，进一步激发创新和创造力。
六是基于项目和问题的探究式学习是21 世纪教与学的核心，是实现21 世纪教育目标的理想教学模式。学生们通过设计和构造现实生活中问题的实际解决方案来学习，在小组合作中，学生将开展跨学科知识融合与研究，对项目的不同部分负责，互相评价对方的工作并创造出专业的高质量产品，这将有助于培养学生在现实世界中解决问题的能力。
国内对STEM 课程的研究还处于起步阶段，存在概念理解偏差、课程设置不完善以及师资力量不足等问题。一些技术驱动的创客内容，脱离了教育本质，未能以核心素养为本推动学生内在发展。
虽然国内也出现了许多课程，如机器人、3D 打印、编程等，但大多呈现出碎片化的状态，没有形成一套完整的课程可供大家参考和借鉴。针对这种情况，“创客教育系列丛书”力求以系统化、可持续、可评价的方式开展STEM 教育和创客教育的理论研究与实践探索，研发了一套STEM 教育和创客教育的系统化课程，完成了从小学、初中到高中的有效衔接，以落实基于21 世纪核心素养人才的培养方案。本丛书编写的指导思想，结合了我国国情，从“立德树人、服务选才、引导教学”角度出发，融项目式学习（PBL）、STEM 理念于一体，基于通识教育，以项目式学习推进STEM 教育。该丛书包括小学三册、初中三册、高中三册，立足于大众创客教育，围绕数字创作、人工智能、创意制作、畅想创作四类课程有效进阶，结合网络学习平台，软硬结合，虚实融合，线上线下整合，培养学生21 世纪核心技能。因此，该丛书的内容设计在选取上注重输入与输出的有效对接，每种课程都有合适的出口，终都呈现出学生作品，与培育精英人才结合，与市、省及的竞赛活动衔接。本丛书解决了跨学科融合与考试升学之间的矛盾；解决了不同地区经费需求不同的问题；解决了创客教育与STEM 教育可持续性问题；解决了创客教育师资不足的问题。丛书出版以符合*公示并通过审核的面向中小学生的全国性竞赛活动为准，作品无论是虚拟创作还是实体制作，都是一个项目、一种工程。该丛书用项目式学习为师生提供明确的教学指引和学习支架，小学、初中、高中各阶段教材均以知识技能为主线，以项目教学或项目式学习为辅线，通过项目范例、项目选题、项目规划、探究活动、项目实施、成果展示、活动评价等环节引领教与学的活动。丛书中项目教学的思路主要通过项目式学习实施路径和项目活动评价表予以落实。
该丛书立足创客教育与STEM 教育战略高度的顶层设计，聚焦教育创新战略，设计教育改革发展蓝图，积极探索新模式，借鉴国际教育发展前沿趋势和国内创新实践，聚焦提升人才培养质量，以为国家建设培养创新人才为核心，整合全社会资源，项目引路，构建由中小学校校内之间、不同学校之间以及校外与科研机构、高新企业、社区和高等学校组成的项目式学习发展共同体，以实施系统完整的创客课程与STEM 课程为主线，打造覆盖区域的课程实施基地，面向全体，让每一个学生接受创客教育与STEM 教育，通过课程的常态化和人才选拔，培养国家发展急需的创新型人才和高技能人才，为国际教育发展和科技创新型人才培养提供中国智慧和中国方案。
该丛书难免存在缺点和不足，殷切希望广大读者批评指正！
中国教育信息化创客教育研究中心
丛书主编 孙晓奎
2020 年7 月

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

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

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