不插电的计算机科学教材（中文版）.pdf

不插电的计算机科学不插电的计算机科学不插电的计算机科学（Computer Science Unplugged,简称Unplugged项目）是Tim Bell,Mike Fellows and Ian Witten领导的一个非赢利性项目,在很多国家 都有捐助者（包括新西兰、美国、瑞典、澳大利亚、中国、韩国、台湾和加拿大）。团队包括的成员或关键组织的成员有ACM K-12委员会、ACM课程委员会、CSTA（CS教师协会）,也包括那些将此项目作为他们研究的校长、教师、大学 outreach coordinators,研究生等。它链接到Google赞助的CS4ALL项目（UW、CMU和UCLS）,并将为一些项目提供资源和支持，如NCWIT（National Center for Women&Information Technology,妇女与信息技术国家中心）和 TECS（Teacher Enrichment in Computer Science,计算机科学教师强化）。现在正在 建立一个国际顾问团队为该项目提供指导，包括K-12教育的代表（小学和中学），专业团队（如ACM、CSTA）,国际捐助者（如Google、Microsoft）。Unplugged项目在全世界已经实施超过16年了，可以在教室、科学中心，家里，甚至是公园的游园活动中进行。其主要目标是将计算机科学（以及通常的 计算）作为一种有趣的、迷人的、智力上刺激的学科，从而向年轻人推广。该项 目希望激发人们的想象力，并希望表达那些不依赖于特定软件或系统的基本原理 以及那些到2020年仍不会过时的概念。Unplugged项目适合所有年龄段的人，从小学到大学，可以跨越国界和文化背景。通过该项目可以实施踏平高科技教育 解决方案难以实施的障碍，跨越资讯富有和资讯贫乏之间、发达国家和发展中国 家之间的鸿沟。1目 录活动1进位的计算二进制数.1活动2数字表示色彩一图像表示.6活动3文本压缩.11活动4卡片魔术一检错与纠错.14活动5 20次猜测信息理论.18活动6战舰一搜索算法.23活动7排序算法.39活动8敲钟排序网.45活动9泥泞的城市一最小生成树.50活动10橙子游戏一网络中的路由和死锁.54活动11寻宝有限状态机.57活动12排序编程语言.65活动13贫穷的制图师图形着色.68活动14旅行城镇支配集.77活动15冰冻之路一Steiner树.82活动16分享秘密信息隐藏协议.91活动17秘鲁人掷硬币问题密码协议.94活动18公钥加密.102活动19巧克力工厂人性化界面设计.106活动20计算机对话一图灵测试.1152活动1进位的计算二进制数适用年级：小学生以上预设能力：可以计算15或31,并能进行配对与排序所需时间：10到40分钟适用人数：从个人到整个班都可以重要概念使用2为基数来表示数字2进位的表示模式和相互关系摘要现代数字化计算机上所有的数据，几乎都是采用。和1的方式来储存和传送，这个活动 就是要展示如何只以两个数字0和I来表示所有的文字和数字。专有名词二进制表示法、二进制与十进制的转换、位与字节、当字符集f 1（二4=十r-图1.1二进制卡片的最初布局多A瓜图1.2翻开卡片显示五点所需教材1矍每个小孩都需要有：从图1.5剪下来的一组五张数字卡，图1.6的活动单和一支钢笔或铅笔。1活动流程1.我们坐在孩子们可以看到你地方，并给每个孩子一套卡片。2.儿童可以像图1.1那样预订卡片，留下点数为16的卡片。有些儿童会试图将卡片以反 方向排序放置，因此，你应该检查他们的数从左至右是以降序放置的。对于幼小的儿童，不 用使用16点的卡片。BINARY NUMBERSTry to work out these binary numbersffffj尸？V uo o o o o QOf7夕=Z7 O O O。=公W 4 /=bC-.，】12 13 r s t18 19包25 26展-Hilf OOIOt OHIO OfIN 00000 00W0 Otfll 01110 00101 well d。c&图1.3图1.6工作表的解决方案3.我们让孩子们计算出翻转的卡片，以致五个点数都能确切显示出来。做这唯一（正确）的方式是4点的卡片和1点的卡片相对，而其余的卡片都正面朝下（如图1.2）。每张卡片要 么朝上显示所有的点数，要么朝下什么也不显示。我们准备一些新颖的方式获得五点一在八 张卡片里面通过使用其余的五张来覆盖三张的点数，对于小孩来说，按照规定的次数完成是 不正常的！4.现在我们让孩子们展示其它号码的点，以致于他们可以探索表示的号码。问他们一些 号码，如3（需要卡片2和1）、12（需要卡片8和4）、19（需要卡片16,2和1）等。对 那些很快找到号码组合的人，我们问他们是否可以找到另一种方式获得该号码（他们最终很 可能会发现显示每一个号码的出路只有一条）。让他们讨论什么号码需要的卡片最多（答案 是31为5张卡片，15为4张卡片）。那最小的呢？（通常数字1将第一被给出，但是这里 的正确答案是零。）是否有任何数字在最小和最大的数字之间不能被表示？（没有一所有号 码可以代表，每个都具有独特的代表性。）5.对于那些年龄较大的孩子，我们问问他们在序列中如何显示数字1,2,3,4,.2看看他们是否可以计算出一个递增数字的程序以一次在卡片上显示（如果您从右到左倒装所 有卡片，那么卡片数字的点将逐一增加，直到你将它翻转过来）。6.这个部分的活动是要使用。和1来表示纸牌是翻起或覆盖的状态，告诉学生我们使用 0来代表纸牌是隐藏的、1则代表纸牌是显示的，例如：图1.2的样版是00101,你也可以给 其它的范例来试试看，例如：ioioi代表21、inn代表31,另外给学生一些练习，让他们 两者之间可以互转，你可以让一部份学生轮流说出自己的生日，并使用o和1来表示这个 日期，而另一部份学生则将这些以o和1表示的数字转换成原来的日期，这就是二进制的 转换，也就是以2为基底的数字表示法。7.请使用图1.6扩充练习上的工作表（完整的工作表请见图1.3）,这个工作表使用灯泡 的亮或暗来表示纸牌的隐藏与显示，灯泡亮表示纸牌显示，灯泡暗表示纸牌隐藏。前面的几 个题型应该非常容易完成，例如第一题是代表8和1的纸牌显示，所以代表9。对于低于五 个灯泡的题型，学生应该使用前几个纸牌即可，例如在第二个题型中，只有使用三个灯泡，从左到右对应的值分别是4、2和1,让学生试试看是否可以自己完成所有的练习。六个灯泡的问题刚好可以配合六张纸牌的问题，每一张纸牌上的点数刚好是前一张的两 倍，点数分别是：1,2,4,8,16,32,64.,所以32点的纸牌刚好可以用来解决六张纸牌的 问题。在工作表下面有一个使用26的数字来表示英文字母的对照表（0可以用来代表空白），学生必须先学会每一个数字所代表的英文字，并且能找到对照表中的字母，这个表格代表我 们可以将文字的讯息转换成一系列的。与1,而学生们可以透过这种方法来传递编码过的机 密信息。变换与拓展在以下的练习中，我们使用棒子的长度来取代纸牌的点数（我们可以使用长度分别为1,2,4,8和16单位的棒子来产生代表0-31单位的长度），或是使用重量来取代纸牌的点数（我 们可以使用重量分别为1,2,4,8和16单位的东西来产生代表0-31单位的重量）。我们现在可以尝试使用高低音来取代如01101的顺序，高音频代表1、低音频代表0,这 个活动将会在教室中造成非常吵杂的结果，但是学生们将印象深刻。其实调制解调器和传真 机就是使用类似的音频技术来传递数据的，但是持续的高音音频将会造成类似撕裂的声音，假如学生不熟悉这样的声音，可以让他们尝试以电话拨打传真机,他就可以听到这样的声音。任一个有两种状态的对象都可以用来表示数字，图1.4显示我们可以使用各种不同的方法来 来表示数字9（01001）,有一个比较特别的方法是使用手指头，手指头向上代表1、手指头 向下代表0,我们使用5根手指头可以代表最大的值为31,10根手指头则可以表示最大到 1023,这样的表示法需要一点点的小技巧，因为它将会产生一些奇怪的姿势，其实真正的挑 战是使用脚趾头，这将可以让你表示超过一百万的数字（真正是多少呢？两只手可以表示0 到1023,手指和脚趾在一起可以表示1024*1024=1048576）。中高年级的学生可能对于扩充1,2,4,8,16,32的顺序会有极大的兴趣，这样的顺序存 在着一个非常有趣的关系：假如你将右边的数字累加到左边，总和将会永远比下一个数字少 lo二进制有另一个非常有趣的性质那就是：你只要插入一个数字0在该数字的最右边，就 会产生2倍的效果，例如：1001（9）的倍数是10010（18）,中高年级的学生应该可以自己解释 这样的现象代表什么（因为所有原来是1的位数值，现在都是原先的2倍了，所以总和变成 原来的2倍，相同的效果也会发生在10进位上，如果插入一个0在该数字的最右边，就会 产生10倍的效果）。3口国国M 5 X X 3图14表示数字9的一些其他方法二进制数的概念可以被运用在猜数字的游戏之上，我们可以透过如：“该数字大于或等于 X吗？”的问句达成，例如我们知道该数字小于32,我们可以继续问“该数字小于16吗？”来逐步达成猜数字的游戏。活动5将有更详细的描述。使用5个数字可以表示所有的英文字母，但是如果要加上大小写那就不够使用了，你可 以让学生算算看计算机到底需要多少不同的字符来表示才足够（包括小数点、逗点和一些特 别的记号如$等），并且结论是要多少字符才能够储存所有的字符（两组英文字母、10个数 字和一些标点符号，全部已经超过了 64个，所以需要7个数字才足够使用，但是7个数字 可以表达128个字符，已经非常足够了），目前大多数的计算机内部使用ASCII来储存数据,每一个字符使用7个位来表示。相关知识现在的数字计算机几乎全部都使用上述的方式来表示信息，这样的表示方式称为二进制 制，因为只有采用了两个不同的数字来表示，这也可以称为以2为基底的表示方法（这和一 般人所熟知的以10为基底完全不同）。每一个。或是1称为位（bit,它是binary digit二进 制数的缩写），“位”通常被用来表示计算机主存储器的地址，它是透过晶体管的开或关以及 电容器的充电或放电来表示不同的相位。在软式或硬式磁盘中，位则是透过磁盘片表面上磁 场的方向来表示，不是南一北就是北一南。CDROM则是透过光学的反射来表示，它运用 光的反射与否来表示。与1。而当数据要透过电话线或无线电来传递时，必须先将数据以高 音频和低音频来表示。或1。一个位可能无法表示太多数据，所以我们必须将这些字节合起来使用，我们常以8个位 来表示数据，8个位可以表示0255的数字，8个位我称之为字节。位不但可以表示数字，我们也可以拿它来表示文书处理文件中的字符，一个位通常被用 来表示一个单一的文字字符，所以数字0255就可以拿来表示所有的大小写英文字、数字、标点符号和一些特殊符号。为了要表示更大的数字，我们会将更多字节合起来使用，两个字节（16位）就可以被用 来表示65536个不同的值，四个字节（32位）可以表示超过40亿个不同的值。计算机的运 算速度会受到它一次可以处理位数多少的影响，例如32位计算机一次可以进行32位的运算,而16位的计算机因为每次只能进行16位的运算，所以它必须将比较大的数打散成16位的 量，所以这样会造成速度变慢。一般来说，我们无法直接看到计算机上的位和字节，因为它们在显示时已经自动转换成 字符和数字。但是，位和字节的观念，在计算机上用来储存数字、文字和其它讯息时，仍然 是非常重要的一种观念。4补充读物大部分的计算机简介书籍都会讨论到二进制的数字系统，在Gareth Powell所写的“My friend Arnold book of Personal Computers”一书第二章中，有完整的二进制数的介绍。图1.5说明：复制此页的卡片，并按着框图剪下图案，使两套这样的5张卡片。BINARY NUMBERSTry to work out these binary i f ft/夕/=wm O O O Q O=I o=f图1.6说明：计算出本页顶端电灯代表的数字。在表中查找相关信息并计算出数字。r/tm、，。，?。=/=%h II jk1 m n I 1 8 9 10 11 12 13 14|V w X yri|22|23 24 25 26b secret codes止匕外，在本页底端有一个二进制代码的消息;5活动2数字表示色彩一图像表示适用年级：小学生以上（至少7岁）预设能力：可以计算初级数学 所需时间：10到40分钟适用人数：从个人到整个班都可以关注焦点表示方法 着色图摘要图画、照片及其他的图片都可以存储在计算机中，本课程讲述计算机如何有效地使用数 字来表示图片。专有名词：光栅图像，像素，图像压缩，行程编码（run-length coding）,传真机所需教材每个学生要发一张填空图（详见图2.1,形式如下图），铅笔、橡皮图2.1填空图6教师需要准备如图2.2的幻灯片，也可以将其画在黑板上。d 图2.2左为计算机屏幕上显示的字母“a”，右图为其放大情形，可以清楚地看出组成的像素活动流程1.跟学生一起讨论传真机是如何进行传真的（在本次课程前最好安排学生先使用传真 机进行收发），计算机在什么情况下需要存储图片（例如：画图程序，游戏或多媒体等）。接下来，向学生说明计算机智能存储数字（学过活动1-二进制数的学生对这一点会有 所了解），建议学生让计算机只使用数字来表示图片，看看他们如何做到。2.我们如下解释计算机屏幕式如何显示图片：计算机屏幕被划分为许多小点，称之为 像素。“像素”是“图像元素”的简称，在黑白屏幕上，每一个像素不是黑就是白。图2.2显示 了屏幕上字母“屋放大时的情况，可以看见组成的点。计算机在存储图片时，只需要存储哪 些点是黑色，哪些点是白色就可以了。3.我们以图2.2为例，说明图片怎样用数字表示，说明过程如下：写下第一行开始时连 续的白色像素数目（图2.1开始时只有一个白色的像素）；然后是连续的黑色像素数目（3）；以次类推，知道整行被编码。如此，第一行可以表示为1,3,lo用这种方法将其余行都编好数字，例如第二行表示 为4,1,即开始是4个白色的像素，接着是1个黑色像素。图2.3为图2.2的全部编码。注 意开始数字为0的行表示该行开头没有白色像素，第一个像素为黑色。使用黑板进行说明可能比较困难，因为在黑板上难以分辨黑色像素131 4114 01.5,114图2.3使用数字编码的图形2.24.让学生将图2.6进行解码。解码后图片如2.3,2.4为缩小后的样子。右边的“test”比较容易，而左边的“being”最为复杂，在方格内完成图像，由于十分容 易出错，所以最好使用铅笔。由于在填涂过程中表示黑色像素的数字十分容易出错，为了更 容易解码，我们可以将方格中的行和列编号，并将表示黑色像素的数字圈起来。7图2.4放大图图2.5压缩图变换与拓展将描图纸覆在网格上进行解码，最后完成图像时就没有网格，这样会使图像更为清晰。学生还可以使用方形彩色贴纸或其它替代物来取代铅笔填涂网格。十字绣的图案也可以使用 这种方式编码。学生可以在网格中自己设计图案（或照着计算机屏幕显示出的画），然后将其编码，再 让其他学生还原。由于二进制数表示的长度有限，通常实际应用中，像素最大长度是有限的。我们可以向 学生提问，让他们回答如何用7个格子来表示12个黑色像素（一种方法是将7个格子涂黑,再下一行紧接着5格黑色），如果将颜色使用数字表示（例如：。表示黑色，1为红色，2为 绿色，等等）就可使用这种方法表示彩色图像。增加两个数字来表示一行像素，第一个水给 出像素的长度，第2个数字代表颜色。相关知识计算机中最简单表示黑白图像的方法是用。来表示白色，1来表示黑色。通常图像中经 常会有大块的白色（特别是页边）和连续的黑色（如水平线）。传真机中，每英寸有100个 像素，因此7英寸宽的页的一行开头的白色需要占用700bit存储量。我们在课程中使用的“行程编码”方式更为有效,只需用lObit就可以表示上例中需要700 个二进制表示的图像。这个例子有一些极端，但也表明该方法可以显著节约空间。使用这种 节约空间的技术称为“压缩”，这也是计算机进行图像操作的关键。例如，一般来说，传真机 8可以将图片压缩至原来的!。如果没有压缩技术，传真机需要花费7倍的时间进行传送，7这样会限制了传真机的使用。存储在计算机中的图像经常被压缩至,甚至，有了压缩 10 100技术，计算机能够存储更多的图片。存储动画时这项技术更为重要，因为动画中每秒包含了 25张或更多图片。本课程所讲的压缩技术类似于大多数通用传真机使用技术。还有许多其 它压缩技术，一种是有损压缩，这种技术会轻微的改变图像以达到更好的压缩效果。压缩技 术会不会起反效果，反而将图像扩大了呢？也存在这种情况。假如有像国际象棋棋盘这样的 黑白间隔图像，直接使用像素表示黑白比使用数字编码更能节约空间，尽管这是一个假设，但是一些真正的图像（如半调图像、向报纸上的插图等），由许多微小的点构成的图像，不能 很好地压缩甚至还会放大，因此，我们对这类图像表示方法的研究就显得十分必要。补充读物Netravali 和 Haskell 的 Digitalpictures:representation and compression 深入探讨了计算机 图像表示。Hunter 和 Robinson 于 1978 年发表的“Intemational digital facsimile coding standards”,文 章叙述了传真机编码标准方法。最新关于 图像编码标准 的书是Pennebaker和 Mitchell.的JPEG:Still Image Data Compression Standard。9l,030000 出宓Namegl&xPlanet7 5.78 0.17图2.6说明：用数字在正方形内着色。图中的每一行都对应一行数字。例如，4,9,2,1这行代 表着方格4为空，方格9着色，方格2为空，方格1着色。10活动3文本压缩适用年级：小学生以上（至少9岁）预设能力：可以抄写文本 所需时间：大约10分钟 适用人数：从个人到整个班都可以关注焦点写抄在写过的文本中反复写摘要尽管现代计算机大规模存储技术有了很大进步，设备的存储效率仍然非常重要。在 数据存储时对数据编码，读取数据时对数据解码，这两处虽然耗费了一些时间，但是可 以很大程度上提高计算机的存储能力。本课程讲述了如何将文本进行编码以节约空间。专有名词文本压缩，Ziv-Lempel编码所需教材给每个学生发一张填空图，如图3.1所示。教师需要准备一些诗歌或文章来给学生练习编码。图3.1说明：根据箭头指向，在每个空白框填写所指的字母11活动流程1.给每一位学生发一张填空图，并让他们来解码，即：将箭头所指向的字母填入空 格中，完成诗歌内容。例如，第一个空格应该填入字母e,第二行的第一个空格应填入 第一行的短语Peoseporridge。填好后如下图。图3.2已完成的工作表2.我们让学生自己找一些文本，并使用箭头和空格表示，使最后留下来的文字越少 越好。若空格的填充顺序是从上到下，从左到右，箭头应一直指向前面的部分，这样才 能保证能够解密。学生可以自己写一些文本，将其编码，也可以使用教师提供的文本。因为许多儿歌和诗歌有许多重复的单词、短语或句子，所以它们都可进行有效的编码，如Dr.Seusss的书Green eggs and ham就是一个很好的素材。变换与拓展箭头与空格编码必须要使箭头总是指向前面的文本，例如，图3.3显示了单词“Banana”的编码情况，尽管空格的箭头指向该单词本身，仍然可以按照从左到右的顺 序成功解码，对于有较长循环的字符或模式，采用这种自表达的方式编码很有用。图3.3自我参考复制的代码12在计算机中，箭头和空格都可使用数字表示，例如：图3.3可以表示为“Ban（2,3）2表示第2个字符为第一个要抄的字符，3表示需要照抄3个连续的字符。解码过程如下：Ban-.Bana.Banan,Banana图3.4在计算机中，显然两个数字要表示两个以上的字符，如只用来表示一个字符，则没 有编码的必要。学生可以尝试采用数字表示法来进行编码和解码。为了让学生更好的认识这种编码，可以发给学生一张印有文本的纸做练习，让学生 找出可以用数字来取代的部分，这些部分必须包含有两个或以上字母，因为若用两个数 字对一个字母进行编码不能节约空间，练习的目的是尽可能的将字母用数字表示。相关知识计算机的存储能力正在以不可置信的速度增长，过去25年中，计算机存储量实现了 百万倍的增长，但是相对于存储需求，这种增长仍不够。计算机能够储存一本书的能力 提供了存储整个图书馆藏书的可能，可以显示高质量的图片意味着可以播放电影，具有 较高可靠性的CD-ROM取代了软盘存储分散数据和程序。任何拥有计算机的人都会见证 Parkinson定律，即总有存不完的数据。为了满足存储需要，除了购买更多的存储空间外，还可以压缩现有的数据。本课程 描述了压缩过程：改变数据的表达形式来节约空间。计算机会自动执行压缩和解压缩，用户几乎不会意识到这个过程，他们只是注意到磁盘存储数据越多，从磁盘中读取文件 所需时间有了增加。计算机在存储和读取时也要耗费一些时间，有时系统使用压缩的文 件会更快，这是因为解压缩的时间要小于读压缩文件所节约的时间。人们提出了许多压缩方法，其中普遍被采用的技术就是指向先出现重复的大块文 本，通常称这种技术为“Ziv-Lempel编码”或LZ编码，是以色列的两个教授于20世纪70 年代到80年代所提出的。这种编码对许多数据都有效，它还可适用于西班牙语、英语，甚至是日语这种使用完全不同的字母表组成的文字，这种编码应用于文本，因为文本中 有很多单词会重复出现，可以使用指针取代。典型的LZ编码压缩可以将数据减少一半，通用的档案存储程序如Z力和ARC以及磁盘备份时都使用了LZ编码进行，高速modem也 使用了LZ编码，当计算机通过普通电话线进行交互，压缩技术可以减少电话线传输数据 来量，从而显著提高传输速度。还有一种压缩方法是采用较短码长表示高频字（如Morse编码）。此外还有更好的 方法（所需时间更多），基于这种思想，我们可以凭借现有的几个字母时测出下一个字 母，这将在活动5中有所介绍。补充读物Bell,Cleary,Witten写的TkU compressionby 以及Witten,Moffat,Bell写的 Gigabytes:Compressing and indexing 全面介绍了压缩算法，这是面向大学计算机科学的学生的。如果你对计算机编程感兴趣的话，还可以阅读Mark Nelson的“zed口 compression book,这是一本以应用为指南的书，Dewdney的77/rz力g 0n力加在文本压缩这 一章还讨论 了“Huffman coding”。13活动4卡片魔术一检错与纠错适用年级：小学三年级以上预设能力：能够识别和数出小的奇数和偶数所需时间：大约30分钟适用人数：从一个人到全班都适用关注焦点奇数和偶数模式 小魔术摘要我们通常假定数据从一台计算机传送到另一台时总是正确的。然而，事实却不是这样，会有一些意外发生，使数据发生改变，这次课程使用一个小魔术来展示如何检查出这些错误 并进行纠正。专有名词检错码，纠错码，奇偶校验所需教材每两个学生需要一套约25张的相同的卡片，卡片具体要求在后面描述为了向全班进行演示，教师需要一套约40张的带磁卡片和一块金属板活动流程这次课程通过魔术来教导学生，在第一次演示时能够很容易的引起学生的兴趣，然后再 告诉学生怎么变这个魔术。为了增强魔术的效果，可加入一些戏剧因素。学生的位置安排必 须使他们可以清楚的看到教师的动作。表演这个魔术需要一叠同样的两面不同的卡片，比如,一面是红色，一面是白色，可以用一张大的单面有颜色的卡纸裁开制成；或是使用扑克牌。为了便于演示，卡片应带有磁性，可以买一些磁条粘在卡片上。制作大约40张这样的卡片，一半为正面，一半为反面。将卡片放在一块竖着的金属板上，以便演示给全体学生看，而当 学生表演时，可以让他们把卡片平放在面前的地上或桌子上。1.让一个或两个学生随意选择卡片排列成一个矩形，任何大小都可以，例如5X5（矩 形摆得越大，效果越好），卡片的排列方式任意，图4.1为一个示例：图4.1 一张初始任意的5X5卡片排列142.教师随意的增加一行和一列，使卡片排列看上去更为复杂（如图4.2）。这一步是魔 术的关键，其方法是必须保证每一行和每一列中有颜色的卡片为偶数张。图4.2增加一行一列的卡片排列3.找一个学生来翻动一张卡片，改变它的颜色。当学生翻卡片时，教师可以蒙住眼睛,背对卡片，不去看学生是如何做的。例如图4.3,第4行第3章卡片被翻动了。然后，解放眼 睛，仔细研究卡片，并断定哪一张卡片被动过了。将其恢复后，可再找一些学生来做演示,使学生信服。这个魔术可以用任意多张的卡片做，卡片数量越多，效果越好。口口”一口口口口 口”口:您 Q 口”口图4.3翻动一张卡片的排列4.让学生来猜这个魔术是怎样做的。5.此时教师可以提出将秘密告诉学生。将学生分成两人一组，让每一组学生将他们的卡片排列成4X4的方形，卡片的排列方式 任意，检查学生是否能记住奇数和偶数的概念，并说明0是一个偶数。然后让他们再增加一 行或一列，确保有偶数张有颜色卡片（如果有色卡片的颜色已经是偶数，就增加一张白色的 卡片），此时教师可以将这张卡片称为奇偶校验卡片，以教学生奇偶校验这个术语。指出当 一张卡片被翻过后会变成怎样：翻过了的卡片所处的行和列中有色卡片的数量成为了奇数。当学生会4X4后，可以让他们排更大的矩形。变换与拓展教师可以用任意具有两种状态的物体来代替卡片。例如硬币（正面/反面）、棍棒（水 平放置和垂直放置）、杯子（口向上和底向上）等等。如果将此活动替代活动1,可以标志 卡片的一面为0,另一面为I。将卡片用二进制表示，奇偶校验位用来保护信息。通过卡片练习学生还可以发现更多。让他们考虑两张卡片被翻动时的情况，在这种情况 下，将无法确定的判断出被翻的两张卡片，尽管可以看出有卡片被翻过了。当3张卡片被翻 动后，会出现类似的情况，能够看出卡片被翻过了，不能准确的看出是哪几张被翻过了。当 4张卡片被翻动时，有可能校验位变成正确地，此时也不能发现有错了。另一有趣的练习是关于最后一张卡片（最右边最下面）的设置。如果它在列上是正确的,15那么在一行中是不是也是正确的呢？（答案是肯定的，可以让学生来寻找反例以证明这一 点）。上面所用到的校验码是偶校验，即使有色卡片数量为偶数，也可以使用奇校验，即使每 一行和每一列中的有色卡片数量为奇数，此时最后放置的卡片（最右边最下面）时只有行数 和列数同为奇数或同为偶数时才可成立，例如当矩形为5X9或12X4时可以，而3X4时不行。可以让学生自己来做奇校验并试着让他们发现这个规律。生活中用到检错的有用于图书出版的国际标准图书号（ISBN）。它是一个有10位数字 的号码，一般印在书的封底，用来唯一的标识一本图书。最后（第10个）的一位数字并不是 图书标识，而是一个校验码，就像我们之前说的奇偶校验码，用来检验整个号码是否有错误。如果，我们使用ISBN订购图书，若有一位数字出错，则通过校验和可以检查出，使我们不 会买到错误的书。校验和可以通过一些简单的算法计算，可以将第一位数乘以10,第二位数乘9,第三位 乘8,依次类推，直到第九位数乘2,将所有的积相加所得到的和用s表示。例如：有这样一 个ISBN号码，0-13-911991-4,贝iJs=0X10+1X9+3X8+9X7+1X6+1X5+9X4+9X3+1X2=172。然 后取s除以n所得的余数，在上例中为7。如果余数为o,那么校验和为o,否则，取该数与n 的差作为校验和，位ISBN中的最后一位，即得n-7=4。此时如有算得ISBN中的最后一位不 为4,就可知道有错误发生。使用此方法计算出的校验和最大值为10,在ISBN中使用字母X来表示，校验和为10的情 况是十分少见的。让学生试着检验一些真正的ISBN的校验和。让他们知道他们可以检测出下列常见错误：1.一位数字的值被改变了 2.两位相邻数字的值互换 3.增加了一位 4.减少了一位让学生思考哪些错误是不能被检测出来的，例如，一位数字变大了二另一数字变小导致 和不变。另一种相似的校验码（使用了另一种算法）为条形码。例如日用货品上的（图4.4）。如 果条形码读错了，则会出现最后一位与计算结果不同，此时，扫描器报警通知并重新扫描。9 4 ioj udjuiv图4.4 一张来自食品的条形码（UPC）相关知识假设我们要在银行中存入10元，银行工作人员输入这张存单并将其传送给中央电脑，使 你的帐户增加10元，若在传送过程中由于噪声干扰，在数量上出现错误，会使增加10元变为 增加1000元。面对这种情况，毫无疑问，银行很有必要保证传送信息的正确性。这只是数据传送中必须检错的一个例子，事实上，无论那种场合，计算机间进行数据传 送，接受方能够检验接收的数据是否受到线路噪声的干扰使非常重要的。这种传送可能是金 16融数据、文件传真或是电子邮件。不仅是文件传送，还有一种情况下进行检错也是非常重要 的，即当我们从光盘或磁盘上读数据时。由于这些存储介质会受到磁性、电辐射、热量以及 物理损害的影响，因此我们不仅想要直到存储数据是否受到损坏，还想要重构哪些被损坏的 数据，与数据传送时不同，我们无法要求重传有问题的数据。还有一种情形也不能重传数据，即数据是从遥远的空间探测头上传来的，因为移动探测头上收集的数据会随时间而变化，若 有错误发生，进行重传的等待时间十分漫长，而且空间探测头的容量十分有限，无法存储足 够的资料。能够发现数据中的错误称为检错，能够重新构造原来的数据称为纠错。一种实现检错和 纠错的简单的方法是同一数据传送3次，如果有错误发生，那么该数据就会与其他两份数据 不同，我们可以知道并将错误的数据丢弃。然而，这种方法存在不少问题，例如如果有两份 数据正好都犯了同样的错误，就会判断出错。另外，使用该方法会使系统效率十分低，因为 必须存储或转发3倍的数据。尽管所有的错误控制体都须要增加额外的数据，我们仍然可以 采用更好的方法。所有计算机数据存储和传送时都是采用0和1序列，称为位，所以问题的关键就是确保发 送的01序列是正确的。卡片魔术用了两面不同的卡片分别表示。和1,并增加了奇偶校验来发 现错误，同样的技术可以用于计算机中，在一行序列中增加一个校验位可以发现一位错误，将这些序列排列成矩形(同游戏)，并在每一行和列都增加一个偶校验位，我们就可以做到 检错和纠错了。事实上，计算机使用更为复杂的错误控制体系来发现和纠正多级错误，不过，这种体系 类似于奇偶校验方法，即使是最好的错误控制体系，也会有检测不出错误的可能，不过这种 可能性十分微小，小到与一只猴子能够随意敲击出莎士比亚的作品一样。补充读物奇偶校验的方法探测错误是比较原始的，还有许多种更好的方法，其中比较重要的方 法有Hamming distances,CRC(cyclic redundancy check),BCH(Bose-Chaudhuri-Hocquenghem)codes,Reed-Solomon Codes,和回旋码(convolutional codes),这些方法的具体内容可参照 Richard Hamming的Coding and Information Theory,and Benjamin Arazi,s A commonsense approach to the theory of error correcting code。Hamming的书的ISBN号码为0-13-139139-9,这 本关于编码的书有一个十分有意思的书号。比较简单，易懂的关于纠错的书有The Turing Omnibus,作者是Dewdney,以及in Computer Science:An Overview作者是Brookshear。17活动5 20次猜测信息理论适用年级：小学三年级以上预设能力：比较两数大小和数的归类所需时间：20到30分钟适用人数：从2个人到全班都适用关注焦点演绎数的归类提问题摘要计算机科学非常关注信息，信息对于计算机非常重要，计算机系统要进行信息存储、读 取、分析、总结并与其他计算机交互，因此信息的量化十分关键。信息理论提供了衡量信息 的方法，包括如何有效地存储或传输的规则。本课程研究了衡量信息内容的方法。专有名词信息理论香农定理编码数据压缩检错和纠错嫡所需教材板书，如黑板和粉笔 如表5.1的卡片消息类型消息样例说明1到100之间的数字67对年龄较大的学生，可以使用1到10万之间1到1000N间的数字387的数字任意数字145对年龄较大的学生，可以取更大的数字回答问题的学生年龄10不介意的话，可以使用教师的年龄告诉学生有6个有规律的数字，让学生猜从数字序列(2,4,6,8,10,12)第一个到最后一个的数字这些数字是先加2,再减1,再加2,再减句子1,324,3,5,4,6,5,71,句子需要按从左到右的顺序，一次猜测一The switch is on个字母表5.1建议问题（见说明）18活动流程1.与学生讨论信息。问问他们信息的定义，我们如何衡量一本书含有多少信息，他们可 能会回答用页数或使用单词来进行衡量。但是，一本枯燥无味的书与一本引人入胜的书所包 含的信息是否一样多呢？一本书没有什么内容，只是重复的短语“blah blah blah那么400 页这样的书所包含的信息量能否等于与400页的电话簿的信息量？显然我们可以凭感觉知道信息的内容，但很难将其量化。计算科学用信息（书）是否能 令人吃惊来衡量信息。告诉一件你早已知道的事，例如，你一位总是走路上学的朋友告诉你：“我今天是走路上学的不会给你带来什么信息，因为它不能使你感到吃惊。而如果他说：“我今天坐直升飞机来学校”，一定会使你感到惊讶，同时这句话也包含了信息。信息中的惊人因素怎么衡量？一种方法是看能够猜到信息的难度，如果你的朋友是走来 学校的，问你：“猜猜我今天是怎么到学校的?”，你一定可以很容易的一下猜到，而如果 他是坐直升飞机来的，你可能要猜好几次，而如果他是坐宇宙飞船来的，恐怕要猜更多次。下面的课程的目的就是基于猜中一个消息的难度，感知其中包含信息的多少。这很像哲 学家的20个问题的游戏，当然，学生可以不只问20个问题。2.找一个学生站到前面来提问，问题如教师准备的卡片（表5.1）。提问的学生要告诉大 家这是一个关于什么方面的问题，是数字、数字序列或句子。如果是数字，那么它的范围是 多少。其余的学生可以向提问者发问，但只能回答“是”或“不是”。例如猜一个在1和100 之间的数字，可以问：“是不是大于50”或“在20和60之间吗？，若是后者，必须在回答 前声明是否包含20和60。教师要检查学生给出的答案是否正确，因为错误的问答会误导其他 学生。将问题和答案用粉笔记录在黑板上，使所有人能参考以前的问题，也可以让拿有卡片的 同学挑选提问者。当数字被猜中后，记录下问题的数量，并指出这是衡量该数字所含信息量的方法。3.继续猜表5.1中的项目，记录下猜出每项所需问题数量。要猜完表5.1的那么多项目也许会令学生感到枯燥，这取决于他们的年龄，也可以只猜表 5.1所列的部分项避免这点。当学生们猜中数字后，讨论一下他们所使用的策略。最好的策略（学生也许已经知道）是每次提问将数字的范围减半，通过这种方法，猜1到100之间的数字需要7次，而随意的猜 测所需次数不定。当数字的范围扩大到1000,我们并不需要增加10倍的问题，只需要多问3个问题，而在1 到10万之间猜一个数只需要20个问题，每次数字范围加倍，只需增加一个问题，问题的增加 与范围的对数成正比。当数字很大时，学生们可能会采用其他策略，例如逐位猜数字，这也是合理的，它的基 本思想是把一个大的消息分解，使之成为较小的部分。然而范围减半法仍然还是猜数字的最 有效的方法。假如要猜得数字没有