2021 Bebras知识大纲

版权声明
引言
第一部分内容大纲
第二部分内容大纲详解
第三部分真题
第四部分推荐书目

版权声明

本手册内容（包括但不限于文字、图片、设计、编排等）均归 ITCCC - Inspiring Teenagers to Create, Collaborate and Contribute 所有。本手册仅用于个人学习、交流或研究，以及其它非商业性或非盈利性用途。使用者应遵守著作权法及其它相关法律的规定，不得侵犯本书及相关权利人的合法权利。除此以外，将本指南任何内容或服务用于其它用途时，须征得 ITCCC 与相关权利人的书面许可。

联系电话：010-66537227
电子邮箱：bebras@itccc.org.cn
网站：http://bebras.itccc.org.cn

引言

Bebras国际信息学与计算思维等级测评活动是由立陶宛大学的瓦伦蒂娜·达吉安教授创立于2004年，面向全球的青少年学生开展的信息学和计算思维领域的教育活动。它旨在帮助青少年锻炼计算思维能力，从数字化社会的原住民和消费者成长为数字化社会的创新人才。截至2020年，Bebras拥有全世界70多个正成员国/地区或观察员国/地区，每年帮助近300万青少年在计算思维领域实现提升，是信息学教育领域拥有最大用户群体的计算思维主题活动。

第一部分内容大纲

计算思维的核心是计算机如何解决真实世界的问题，即如何充分利用计算机快速、精确、规模化的能力，把这些能力用算法表示出来，并帮助计算机完成问题解决。目前业界公认的计算思维包含4个方面：分解问题（如何把复杂问题分解为可重复的简单问题并逐个攻破）、模式识别（识别重复的模式）、抽象（把信息抽象表达成计算机可理解的信息）、算法（一些常用的解决问题方法）。我们在此基础上单独将数据结构模块提出，因为数据的表示是利用算法有效地解决问题的基础，它和算法的实现相辅相成，也是计算思维的重要组成部分。考虑到青少年的认知和理解能力，Bebras主要涉及的信息学和计算思维概念是计算机科学的一个子集，主要概念如下面的思维导图所示。
2021 Bebras知识大纲 - 图1

第二部分内容大纲详解

1. 分解问题

分解问题就是分治法拆解复杂问题，直到复杂问题成为可重复的简单问题。用计算思维解决问题，首先就要拆解。分解问题是把原问题分解成子问题，解子问题，再把子问题的解合成原问题的解。无论多么强大的计算机应用，背后都是把原问题分解成可以解的子问题，只是规模不同。本节重点：

1.1 串行

一次执行一个任务，且按照顺序执行。对于串行的多个任务，只能按照给定的先后顺序来执行。
相关样题：2017-SK-10 栅栏上色

1.2 并行

并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个计算机来协同求解同一问题，即将被求解的问题分解成若干个可以全部或部分同时执行的部分，各部分均由一个独立的计算机同时进行计算。通过并行计算完成数据的处理，再将处理的结果返回给用户。
相关样题：2016-HU-08 烹饪顺序

1.3 流程图

流程图是表示算法、工作流程的图表。流程图将步骤显示为各种类型的方框，并用箭头连接方框来说明命令执行的顺序。一个设计良好的流程图对来自任何决策点的分支具有明确的区分，能为任何场景定义流程。
相关样题：2019-DE-05 陷阱岛

2. 模式识别

模式就是可重复的规律。手写汉字识别、语音识别，以及许多AI领域的应用都基于模式识别的方法。计算思维的关键不是解决一个问题，而是解决一类问题，也就是符合模式的所有问题。这也是计算机如此强大的原因所在：一个问题一旦被解决一次，就可以被反复地、可预测地解决。本节重点：

2.1 发现模式

模式识别就是找到可以重复的规律，把它描述和表现成计算机可以理解的任务，它也是计算思维的核心思想之一。通过识别出问题的共性，用同一个方法来解，这样我们就可以把这些问题交给计算机算法来解决。
相关样题：模式识别 2018-AU-03 鹦鹉的颜色

2.2 条件判断

条件判断是用于判断是否满足给定的条件，然后再根据判定的结果（真或假）决定执行哪种操作。这也被称作逐步逻辑（step-wise logic）：告诉计算机在每一种情况下应该怎样做。
相关样题：2016-US-03 真假货币

2.3 循环

循环是计算机科学里常用的概念，指的是反复地做一件事情，直到某一个条件被满足为止。循环结构是指在程序中反复执行某个功能的—种程序结构，由循环体中的条件来判断是继续执行某个功能还是退出循环。
相关样题：2012-JP-02 小海狸的控制

2.4 嵌套

在一个循环体内，完整包含了另一个循环，称为循环的嵌套。循环的嵌套可以是多层，但每一层循环在逻辑上必须是完整的。
相关样题：2016-US-07 足球比赛

3. 抽象

把真实物理世界和计算机数字世界对应的过程就是抽象。一旦问题被抽象成计算机可以理解的形式，那么这个问题就有约定俗成的解法。抽象是从物理世界到数字世界的过程，是我们和计算机对话的方法，也是抽出要素而忽略不相关细节的过程。本节重点：

3.1 二进制

在计算机里，不仅仅各种数字用二进制表示，一切都是用二进制来表示的，比如字母、图画、照片、视频、地图、音乐、程序等。我们看到的计算机展示的任何画面，在计算机里面都是用0和1这两个数字来存储的，只是在最后展示的时候，比如在手机上或者电脑上给人展示的时候，计算机选择了人们可以理解的、喜欢的方式。
相关样题：2017-CZ-02 纸牌秘密

3.2 编码/解码

文字、图像、视频，各种复杂的信息在计算机世界都有约定俗成的表示方法。编码是把真实世界的文字、图像等信息转化成一串计算机可以计算和存储的数字的过程。编码的方法不是唯一的，编码的好坏会影响信息存储和使用的效率。解码是编码的相反过程，不同的编码对应不同的解码方法。
相关样题：2012-CA-05 复杂的代码

3.3 状态图

状态图也是一幅图，它有结点和边，每个结点里是一个状态，每条边上有一个动作。从一个状态，经过一个动作，可以到达另一个状态。它是一种重要的将真实世界的行为转化为计算机可理解的问题的抽象方式。
相关样题：2019-SI-03 太空之旅

3.4 加密和解密

在计算机互相传递信息的时候，信息常常要加以保护，这样其他人或者其他计算机如果看到这条信息也不能理解这是什么。但是，真正需要收到信息的人拿到这条信息可以通过解密真正知道这条信息是什么意思。这种保护我们叫加密。加密是把信息变得不容易直接理解的过程，解密是把加密过的信息还原的过程。这个传递的过程可以是在公开的网络上进行的，比如通过邮件或者微信。接收者拿到加密信息后，经过解密（可能利用秘钥），就能看到真正的信息。
相关样题：2012-JP-05 海狸的加密算法

4. 数据结构

算法离不开数据，数据结构是数据存储的各种方法。算法的有效性依赖于数据结构。用对了数据结构，算法就会更快、更好，尤其在数据量大的时候。大数据、云计算是未来数据和算法的方向，AI的基础就是计算机利用大数据进行的训练和学习。本节重点：

4.1 队列

队列是一种“先进先出”的数据结构，也就是先被放到队列里的数据必须先被处理。
相关样题：2019-PK-01 糖果店

4.2 堆栈

堆栈是一种“后进先出”的数据结构，后被放进去的数据，会先被取出处理。
相关样题：2020-PT-02 砖块塔

4.3 树

树是由结点和边组成的数据结构，从根结点出发每个结点都可能通过边连接到一些子结点。二叉树是一种每个结点最多有2个分支的树。通过遍历二叉树可以访问树上的每一个结点。
相关样题：2015-BE-08 徒步旅行

4.4 图

图也是由结点和边组成的数据结构。但是和树不同的是，图中的任何结点之间都可能存在连接（可以有封闭的环形的存在）。
相关样题：2013-LT-01 小镇

5. 算法

算法是计算机可理解、可执行的有清晰流程的解决问题的方法。计算机的算法就是一系列的指令，而指令是计算机能理解的语言。算法是流程化的、可调用的、逻辑清晰的。一个算法可以解不同的问题，一个问题也可以由不同的算法来解。本节重点：

5.1 排序算法

排序是计算机内经常进行的一种操作，其目的是将一组”无序”的记录序列调整为”有序”的记录序列。计算机可以采用多种不同的算法对序列排序，但是不同的排序算法在所需时间、空间上可能差别很大。
相关样题：2012-EE-01 整理书架

5.2 分类算法

将数据或信息按照某种原则分成类别是计算机常常要面对的问题。世界上很多问题都是分类问题，比如人脸识别问题。
相关样题：2015-CH-03 最爱的音乐

5.3 搜索算法

计算机依靠搜索算法在大量的信息中快速找到所需的信息。搜索的效率和如何组织信息有很大关系。所以，搜索不是独立的，和排序、分类、新信息的插入、整理息息相关。面对现代的海量信息，搜索的速度和效率非常重要，迅速缩小搜索空间和把结果按相关性进行排序至关重要。其中，二分搜索法是最常用的搜索方法。二分搜索法在已经排好顺序的物品中，每次去比较中间的那个值，以此决定下一次的搜索范围。二分搜索法很直观，它每一步都直接帮你把剩下的工作去掉一半。这种方法在搜索物品的数目较大时非常有用。
相关样题：2014-FR-03 抓住怪兽

5.4 递归算法

递归是根据本身的简单版本去定义问题或解决问题的过程，递归算法把一个大的问题拆解成同构的小问题。每一个递归算法都必须有一个终止条件，这样这个算法才能停下来。形象地说，递归算法是不能在原地不动的，每次使用，结果一定要越来越小，直到遇到终止条件。递归算法的好处除了简洁优美，还有不要求预先固定问题的大小层级和结构，非常灵活。
相关样题：2017-PL-05 计算机组合

5.5 优化算法

优化往往是时间和空间的权衡，或者说，速度和大小的权衡。在处理大量数据的时候，算法有多快非常重要。比较典型的优化算法有旅行商问题、背包问题、贪心算法等。

旅行商问题是计算机领域非常有名的优化问题。这个问题可以这样描述：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短？旅行商问题在少量结点（城市）时很容易解决，但是随着问题的规模变大解决起来会越来越困难。人们发明了很多种算法来解决大规模的旅行商问题。它们在地图导航、交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用。。

装箱问题又叫背包问题（knapsack problem）。背包问题是组合优化中的这样一个问题：给定一组物品，每个物品都有重量和价值，需要找到一些物品，它们的总重量小于或等于给定极限，而总价值尽可能大。它的名称源于人们装自己的背包，受到固定大小的背包的约束，人们必须用最有价值的物品装满它。背包问题已经被研究了一个多世纪，最早可以追溯到1897年。很多人终身研究和处理这个问题，因为这个问题通常出现在资源分配中：决策者必须在固定预算下或时间限制内分别从一组不可分割的项目或任务中进行选择。背包问题在现实世界许多领域的关键决策过程中都很有用，例如制造业寻找原材料浪费最少的方法，选择投资和投资组合等。

贪婪算法又称贪心算法，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解，虽然它并不能保证做到整体最优。具体来说，我们面临一个问题时需要做一系列的选择，我们受到一定的时间、空间或者其他限制。为每个选择，我们可能得到一个“回报”。贪婪算法比较简单实用，就是从当前回报最大的那个选择开始选择，直到不能再做更多选择。

相关样题：