不插電的計(jì)算機(jī)科學(xué)-教材（中文版） - 網(wǎng)絡(luò)課程

力膜嗯糜可咳啰

不插電的計(jì)算機(jī)科學(xué)

董榮勝主持編譯

計(jì)算思維及應(yīng)用研究室

桂林電子科技大學(xué)

2008年10月

桂電“計(jì)算機(jī)科學(xué)導(dǎo)論”參考教材

（內(nèi)部資料，僅供參考）

不插電的計(jì)算機(jī)科學(xué)

不插電的計(jì)算機(jī)科學(xué)（ComputerScienceUnplugged,簡(jiǎn)稱Unplugged項(xiàng)目）

是TimBell,MikeFellowsandIanWitten領(lǐng)導(dǎo)的?個(gè)非贏利性項(xiàng)目，在很多國(guó)家

都有捐助者（包括新西蘭、美國(guó)、瑞典、澳大利亞、中國(guó)、韓國(guó)、臺(tái)灣和加拿大）。

團(tuán)隊(duì)包括的成員或關(guān)鍵組織的成員有ACMK-12委員會(huì)、ACM課程委員會(huì)、

CSTA（CS教師協(xié)會(huì)）,也包括那些將此項(xiàng)目作為他們研究的校長(zhǎng)、教師、大學(xué)

outreachcoordinators,研究生等。它鏈接到Google贊助的CS4ALL項(xiàng)目（UW、

CMU和UCLS）,并將為一些項(xiàng)目提供資源和支持，如NCWIT（NationalCenter

forWomen&InformationTechnology,婦女與信息技術(shù)國(guó)家中心）和

TECS（TeacherEnrichmentinComputerScience,計(jì)算機(jī)科學(xué)教師強(qiáng)化）?，F(xiàn)在正在

建立一個(gè)國(guó)際顧問(wèn)團(tuán)隊(duì)為該項(xiàng)目提供指導(dǎo)，包括K-12教育的代表（小學(xué)和中學(xué)），

專業(yè)團(tuán)隊(duì)（如ACM、CSTA）,國(guó)際捐助者（如Google、Microsoft）□

Unplugged項(xiàng)目在全世界已經(jīng)實(shí)施超過(guò)16年了，可以在教室、科學(xué)中心，

家里，甚至是公園的游園活動(dòng)中進(jìn)行。其主要目標(biāo)是將計(jì)算機(jī)科學(xué)（以及通常的

計(jì)算）作為一種有趣的、迷人的、智力上刺激的學(xué)科，從而向年輕人推廣。該項(xiàng)

目希望激發(fā)人們的想象力，并希望表達(dá)那些不依賴于特定軟件或系統(tǒng)的基本原理

以及那些到2020年仍不會(huì)過(guò)時(shí)的概念。Unplugged項(xiàng)目適合所有年齡段的人，

從小學(xué)到大學(xué)，可以跨越國(guó)界和文化背景。通過(guò)該項(xiàng)目可以實(shí)施踏平高科技教育

解決方案難以實(shí)施的障礙，跨越資訊富有和資訊貧乏之間、發(fā)達(dá)國(guó)家和發(fā)展中國(guó)

家之間的鴻溝。

1

目錄

活動(dòng)1進(jìn)位的計(jì)算—二進(jìn)制數(shù)................................1

活動(dòng)2數(shù)字表示色彩一圖像表示............................6

活動(dòng)3文本壓縮...........................................11

活動(dòng)4卡片魔術(shù)一檢錯(cuò)與糾錯(cuò)...............................14

活動(dòng)520次猜測(cè)——信息理論...............................18

活動(dòng)6戰(zhàn)艦一搜索算法....................................23

活動(dòng)7排序算法..........................................39

活動(dòng)8敲鐘——排序網(wǎng)....................................45

活動(dòng)9泥濘的城市一最小生成樹............................50

活動(dòng)10橙子游戲一網(wǎng)絡(luò)中的路由和死鎖.....................54

活動(dòng)11尋寶——有限狀態(tài)機(jī)...............................57

活動(dòng)12排序——編程語(yǔ)言.................................65

活動(dòng)13貧窮的制圖師——圖形著色.........................68

活動(dòng)14旅行城鎮(zhèn)——支配集...............................77

活動(dòng)15冰凍之路一Steiner樹...............................82

活動(dòng)16分享秘密——信息隱藏協(xié)議.........................91

活動(dòng)17秘魯人擲硬幣問(wèn)題——密碼協(xié)議...................94

活動(dòng)18公鑰加密.......................................102

活動(dòng)19巧克力工廠一人性化界面設(shè)計(jì)......................106

活動(dòng)20計(jì)算機(jī)對(duì)話一圖靈測(cè)試...........................115

2

活動(dòng)1進(jìn)位的計(jì)算--二進(jìn)制數(shù)

適用年級(jí)：小學(xué)生以上

預(yù)設(shè)能力：可以計(jì)算15或31,并能進(jìn)行配對(duì)與排序

所需時(shí)間：10到40分鐘

適用人數(shù)：從個(gè)人到整個(gè)班都可以

重要概念

使用2為基數(shù)來(lái)表示數(shù)字

2進(jìn)位的表示模式和相互關(guān)系

摘要

現(xiàn)代數(shù)字化計(jì)算機(jī)上所有的數(shù)據(jù)，幾乎都是采用0和1的方式來(lái)儲(chǔ)存和傳送，這個(gè)活動(dòng)

就是要展示如何只以兩個(gè)數(shù)字〈0和D來(lái)表示所有的文字和數(shù)字。

專有名詞

二進(jìn)制表示法、二進(jìn)制可十進(jìn)制的轉(zhuǎn)換、位與字節(jié)、字符集

圖1.1二進(jìn)制卡片的最初布局

圖1.2翻開卡片顯示五點(diǎn)

所需教材

每個(gè)小孩都需要有：

從圖1.5剪下來(lái)的一組〈五張〉數(shù)字卡，圖1.6的活動(dòng)單和一支鋼筆或鉛筆。

1

活動(dòng)流程

1.我們坐在孩子們可以看到你地方，并給卷個(gè)孩子一套卡片。

2.兒童可以像圖1.1那樣預(yù)訂卡片，留下點(diǎn)數(shù)為16的卡片。有些兒童會(huì)試圖將卡片以反

方向排序放置，因此，你應(yīng)該檢查他們的數(shù)從左至右是以降序放置的。對(duì)于幼小的兒童，不

用使用16點(diǎn)的卡片。

BINARYNUMBERS

Trytoworkoutthesebinarynumbers

10

=13

mooowCo=。g

:fW4

oo=4}

63

Mthesesecretcodes

-Will00101OltOOmittNONNINMillOHIOOOIOI

welldoc&

gv，玲3

圖1.3圖1.6工作表的解決方案

3.我們讓孩子們計(jì)算出翻轉(zhuǎn)的卡片，以致五個(gè)點(diǎn)數(shù)都能確切顯示出來(lái)。做這唯一（正確）

的方式是4點(diǎn)的卡片和1點(diǎn)的卡片相對(duì)，而其余的卡片都正面朝下（如圖1.2）。每張卡片要

么朝上顯示所有的點(diǎn)數(shù)，要么朝下什么也不顯示。我們準(zhǔn)備一些新穎的方式獲得五點(diǎn)一在八

張卡片里面通過(guò)使用其余的五張來(lái)覆蓋三張的點(diǎn)數(shù)，對(duì)于小孩來(lái)說(shuō)，按照規(guī)定的次數(shù)完成是

不正常的！

4.現(xiàn)在我們讓孩子們展示其它號(hào)碼的點(diǎn)，以致于他們可以探索表示的號(hào)碼。問(wèn)他們一些

號(hào)碼，如3（需要卡片2和1）、12（需要卡片8和4）、19（需要卡片16,2和1）等。對(duì)

那些很快找到號(hào)碼組合的人，我們問(wèn)他們是否可以找到另?種方式獲得該號(hào)碼（他們最終很

可能會(huì)發(fā)現(xiàn)顯示每一個(gè)號(hào)碼的出路只有一條）。讓他們討論什么號(hào)碼需要的卡片最多（答案

是31為5張卡片，15為4張卡片）。那最小的呢？（通常數(shù)字1將第一?被給出，但是這里

的正確答案是零。）是否有任何數(shù)字在最小和最大的數(shù)字之間不能被表示？（沒(méi)有一所有號(hào)

碼可以代表，每個(gè)都具有獨(dú)特的代表性。）

5.對(duì)于那些年齡較大的孩子，我們問(wèn)問(wèn)他們?cè)谛蛄兄腥绾物@示數(shù)字1,2,3,4,..

2

看看他們是否可以計(jì)算出一個(gè)遞增數(shù)字的程序以一次在卡片上顯示（如果您從右到左倒裝所

有卡片，那么卡片數(shù)字的點(diǎn)將逐一增加，直到你將它翻轉(zhuǎn)過(guò)來(lái)）。

6.這個(gè)部分的活動(dòng)是要使用。和1來(lái)表示紙牌是翻起或覆蓋的狀態(tài)，告訴學(xué)生我們使用

0來(lái)代表紙牌是隱藏的、1則代表紙牌是顯示的，例如：圖1.2的樣版是00101,你也可以給

其它的范例來(lái)試試看，例如：10101代表21、11111代表31,另外給學(xué)生一些練習(xí)，讓他們

兩者之間可以互轉(zhuǎn)，你可以讓一部份學(xué)生輪流說(shuō)出自己的生日，并使用0和1來(lái)表示這個(gè)

日期，而另一部份學(xué)生則將這些以0和1表示的數(shù)字轉(zhuǎn)換成原來(lái)的日期，這就是二進(jìn)制的

轉(zhuǎn)換，也就是以2為基底的數(shù)字表示法。

7.請(qǐng)使用圖1.6擴(kuò)充練習(xí)上的工作表（完整的工作表請(qǐng)見圖1.3）,這個(gè)工作表使用燈泡

的亮或暗來(lái)表示紙牌的隱藏與顯示，燈泡亮表示紙牌顯示，燈泡暗表示紙牌隱藏。前面的幾

個(gè)題型應(yīng)該非常容易完成，例如第?題是代表8和1的紙牌顯示，所以代表9。對(duì)于低于五

個(gè)燈泡的題型，學(xué)生應(yīng)該使用前幾個(gè)紙牌即可，例如在第二個(gè)題型中，只有使用三個(gè)燈泡，

從左到右對(duì)應(yīng)的值分別是4、2和1,讓學(xué)生試試看是否可以自己完成所有的練習(xí)。

六個(gè)燈泡的問(wèn)題剛好可以配合六張紙牌的問(wèn)題，每一張紙牌上的點(diǎn)數(shù)剛好是前張的兩

倍,點(diǎn)數(shù)分別是：1,2,4,8,16,32,64所以32點(diǎn)的紙牌剛好可以用來(lái)解決六張紙牌的

問(wèn)題。

在工作表下面有個(gè)使用卜26的數(shù)字來(lái)表示英文字母的對(duì)照表（0可以用來(lái)代表空白）,

學(xué)生必須先學(xué)會(huì)每一個(gè)數(shù)字所代表的英文字，并且能找到對(duì)照表中的字母，這個(gè)表格代表我

們可以將文字的訊息轉(zhuǎn)換成?系列的0與1,而學(xué)生們可以透過(guò)這種方法來(lái)傳遞編碼過(guò)的機(jī)

密信息。

變換與拓展

在以下的練習(xí)中，我們使用棒子的長(zhǎng)度來(lái)取代紙牌的點(diǎn)數(shù)（我們可以使用長(zhǎng)度分別為1,2,

4,8和16單位的棒子來(lái)產(chǎn)生代表0-31單位的長(zhǎng)度），或是使用重量來(lái)取代紙牌的點(diǎn)數(shù)（我

們可以使用重量分別為1,2,4,8和16單位的東西來(lái)產(chǎn)生代表0-31單位的重量）。

我們現(xiàn)在可以嘗試使用高低音來(lái)取代如01101的順序，高音頻代表1、低音頻代表0,這

個(gè)活動(dòng)將會(huì)在教室中造成非常吵雜的結(jié)果，但是學(xué)生們將印象深刻。其實(shí)調(diào)制解調(diào)器和傳真

機(jī)就是使用類似的音頻技術(shù)來(lái)傳遞數(shù)據(jù)的，但是持續(xù)的高音音頻將會(huì)造成類似撕裂的聲音，

假如學(xué)生不熟悉這樣的聲音，可以讓他們嘗試以電話撥打傳真機(jī),他就可以聽到這樣的聲音。

任一個(gè)有兩種狀態(tài)的對(duì)象都可以用來(lái)表示數(shù)字，圖14顯示我們可以使用各種不同的方法來(lái)

來(lái)表示數(shù)字9（01001）,有?個(gè)比較特別的方法是使用手指頭，手指頭向上代表1、手指頭

向下代表0,我們使用5根手指頭可以代表最大的值為31,10根手指頭則可以表示最大到

1023,這樣的表示法需要?點(diǎn)點(diǎn)的小技巧，因?yàn)樗鼘?huì)產(chǎn)生一些奇怪的姿勢(shì)，其實(shí)真正的挑

戰(zhàn)是使用腳趾頭，這將可以讓你表示超過(guò)一百萬(wàn)的數(shù)字（真正是多少呢？?jī)芍皇挚梢员硎?

到1023,手指和腳趾在?起可以表示1024*1024=1048576）,

中高年級(jí)的學(xué)生可能對(duì)于擴(kuò)充1,2,4,8,16,32…的順序會(huì)有極大的興趣，這樣的順序存

在著一個(gè)非常有趣的關(guān)系：假如你將右邊的數(shù)字累加到左邊，總和將會(huì)永遠(yuǎn)比下一個(gè)數(shù)字少

lo

二進(jìn)制有另一個(gè)非常有趣的性質(zhì)那就是：你只要插入一個(gè)數(shù)字0在該數(shù)字的最右邊，就

會(huì)產(chǎn)生2倍的效果，例如：1001⑼的倍數(shù)是10010（18）,中高年級(jí)的學(xué)生應(yīng)該可以自己解釋

這樣的現(xiàn)象代表什么（因?yàn)樗性瓉?lái)是1的位數(shù)值，現(xiàn)在都是原先的2倍了，所以總和變成

原來(lái)的2倍，相同的效果也會(huì)發(fā)生在10進(jìn)位上，如果插入一個(gè)0在該數(shù)字的最右邊，就會(huì)

產(chǎn)生10倍的效果）。

3

口圖□□國(guó)

X5XX5

圖1.4:表示數(shù)字9的一些其他方法

二進(jìn)制數(shù)的概念可以被運(yùn)用在猜數(shù)字的游戲之上，我們可以透過(guò)如：''該數(shù)字大于或等于

X嗎？”的問(wèn)句達(dá)成，例如我們知道該數(shù)字小于32,我們可以繼續(xù)問(wèn)“該數(shù)字小于16嗎？”

來(lái)逐步達(dá)成猜數(shù)字的游戲?；顒?dòng)5將有更詳細(xì)的描述。

使用5個(gè)數(shù)字可以表示所有的英文字母，但是如果要加上大小寫那就不夠使用了，你可

以讓學(xué)生算算看計(jì)算機(jī)到底需要多少不同的字符來(lái)表示才足夠（包括小數(shù)點(diǎn)、逗點(diǎn)和一些特

別的記號(hào)如$等），并且結(jié)論是要多少字符才能夠儲(chǔ)存所有的字符（兩組英文字母、10個(gè)數(shù)

字和一些標(biāo)點(diǎn)符號(hào)，全部已經(jīng)超過(guò)了64個(gè)，所以需要7個(gè)數(shù)字才足夠使用，但是7個(gè)數(shù)字

可以表達(dá)128個(gè)字符，已經(jīng)非常足夠了），目前大多數(shù)的計(jì)算機(jī)內(nèi)部使用ASCII來(lái)儲(chǔ)存數(shù)據(jù)，

每一個(gè)字符使用7個(gè)位來(lái)表示。

相關(guān)知識(shí)

現(xiàn)在的數(shù)字計(jì)算機(jī)幾乎全部都使用上述的方式來(lái)表示信息，這樣的表示方式稱為二進(jìn)制

制，因?yàn)橹挥胁捎昧藘蓚€(gè)不同的數(shù)字來(lái)表示，這也可以稱為以2為基底的表示方法（這和一

般人所熟知的以10為基底完全不同）。每一個(gè)0或是1稱為位（bit,它是binarydigit二進(jìn)

制數(shù)的縮寫），“位”通常被用來(lái)表示計(jì)算機(jī)主存儲(chǔ)器的地址，它是透過(guò)晶體管的開或關(guān)以及

電容器的充電或放電來(lái)表示不同的相位。在軟式或硬式磁盤中，位則是透過(guò)磁盤片表面上磁

場(chǎng)的方向來(lái)表示，不是南一北就是北一南?CD—ROM則是透過(guò)光學(xué)的反射來(lái)表示，它運(yùn)用

光的反射與否來(lái)表示0與.1。而當(dāng)數(shù)據(jù)要透過(guò)電話線或無(wú)線電來(lái)傳遞時(shí)，必須先將數(shù)據(jù)以高

音頻和低音頻來(lái)表示0或1。

一個(gè)位可能無(wú)法表示太多數(shù)據(jù)，所以我們必須將這些字節(jié)合起來(lái)使用，我們常以8個(gè)位

來(lái)表示數(shù)據(jù)，8個(gè)位可以表示0—255的數(shù)字，8個(gè)位我稱之為字節(jié)。

位不但可以表示數(shù)字，我們也可以拿它來(lái)表示文書處理文件中的字符，一個(gè)位通常被用

來(lái)表示個(gè)單一的文字字符，所以數(shù)字0—255就可以拿來(lái)表示所有的大小寫英文字、數(shù)字、

標(biāo)點(diǎn)符號(hào)和一些特殊符號(hào)。

為了要表示更大的數(shù)字，我們會(huì)將更多字節(jié)合起來(lái)使用，兩個(gè)字節(jié)（16位）就可以被用

來(lái)表示65536個(gè)不同的值，四個(gè)字節(jié)（32位）可以表示超過(guò)40億個(gè)不同的值。計(jì)算機(jī)的運(yùn)

算速度會(huì)受到它一次可以處理位數(shù)多少的影響，例如32位計(jì)算機(jī)?次可以進(jìn)行32位的運(yùn)算,

而16位的計(jì)算機(jī)因?yàn)槊看沃荒苓M(jìn)行16位的運(yùn)算，所以它必須將比較大的數(shù)打散成16位的

量，所以這樣會(huì)造成速度變慢。

一般來(lái)說(shuō)，我們無(wú)法直接看到計(jì)算機(jī)上的位和字節(jié)，因?yàn)樗鼈冊(cè)陲@示時(shí)已經(jīng)自動(dòng)轉(zhuǎn)換成

字符和數(shù)字。但是，位和字節(jié)的觀念，在計(jì)算機(jī)上用來(lái)儲(chǔ)存數(shù)字、文字和其它訊息時(shí)，仍然

是非常重要的一種觀念。

4

補(bǔ)充讀物

大部分的計(jì)算機(jī)簡(jiǎn)介書籍都會(huì)討論到二進(jìn)制的數(shù)字系統(tǒng)，在GarethPowell所寫的“My

friendArnold^bookofPersonalComputers一書第二章中，有完整的二進(jìn)制數(shù)的介紹。

■.

????

????

????

????????

????????

????????

??????????

圖1.5說(shuō)明：復(fù)制此頁(yè)的卡片，并按著框圖剪下圖案，使兩套這樣的5張卡片。

BINARYNUMBERS展

Trytoworkoutthosebinarynumbers

f*cwt

vtm:

OOOsOO=w1OOwOO1Y

/夕=fOfIOOI

圖1.6說(shuō)明：計(jì)算出本頁(yè)頂端電燈代表的數(shù)字。此外，在本頁(yè)底端有?個(gè)二進(jìn)制代碼的消息;

在表中查找相關(guān)信息并計(jì)算出數(shù)字。

5

活動(dòng)2數(shù)字表示色彩一圖像表示

適用年級(jí)：小學(xué)生以上（至少7歲）

預(yù)設(shè)能力：可以計(jì)算初級(jí)數(shù)學(xué)

所需時(shí)間：10到40分鐘

適用人數(shù)：從個(gè)人到整個(gè)班都可以

關(guān)注焦點(diǎn)

表示方法

著色

圖

摘要

圖畫、照片及其他的圖片都可以存儲(chǔ)在計(jì)算機(jī)中，本課程講述計(jì)算機(jī)如何有效地使用數(shù)

字來(lái)表示圖片。

專有名詞：

光柵圖像,像素，圖像壓縮,行程編碼（run-lengthcoding）,傳真機(jī)

所需教材

每個(gè)學(xué)生要發(fā)一張?zhí)羁請(qǐng)D（詳見圖2.1,形式如下圖），鉛筆、橡皮

圖2.1填空?qǐng)D

6

教師需要準(zhǔn)備如圖2.2的幻燈片，也可以將其畫在黑板上。

a■■■■

圖2.2左為計(jì)算機(jī)屏幕上顯示的字母“a”，

右圖為其放大情形，可以清楚地看出組成的像素

活動(dòng)流程

1.跟學(xué)生一起討論傳真機(jī)是如何進(jìn)行傳真的（在本次課程前最好安排學(xué)生先使用傳真

機(jī)進(jìn)行收發(fā)），計(jì)算機(jī)在什么情況下需要存儲(chǔ)圖片（例如：畫圖程序，游戲或多媒體等）。

接下來(lái)，向?qū)W生說(shuō)明計(jì)算機(jī)智能存儲(chǔ)數(shù)字（學(xué)過(guò)活動(dòng)1-二進(jìn)制數(shù)的學(xué)生對(duì)這一點(diǎn)會(huì)有

所了解），建議學(xué)生讓計(jì)算機(jī)只使用數(shù)字來(lái)表示圖片，看看他們?nèi)绾巫龅健?/p>

2.我們?nèi)缦陆忉層?jì)算機(jī)屏幕式如何顯示圖片：計(jì)算機(jī)屏幕被劃分為許多小點(diǎn)，稱之為

像素?！跋袼亍笔恰皥D像元素”的簡(jiǎn)稱，在黑白屏幕上，每一個(gè)像素不是黑就是白。圖2.2顯示

了屏幕上字母“a”放大時(shí)的情況，可以看見組成的點(diǎn)。計(jì)算機(jī)在存儲(chǔ)圖片時(shí)，只需要存儲(chǔ)哪

些點(diǎn)是黑色，哪些點(diǎn)是白色就可以了。

3.我們以圖2.2為例，說(shuō)明圖片怎樣用數(shù)字表示，說(shuō)明過(guò)程如下：寫下第一行開始時(shí)連

續(xù)的白色像素?cái)?shù)目（圖2.1開始時(shí)只有一個(gè)白色的像素）；然后是連續(xù)的黑色像素?cái)?shù)目（3）；

以次類推，知道整行被編碼。

如此，第一行可以表示為1,3,lo用這種方法將其余行都編好數(shù)字，例如第二行表示

為4,1,即開始是4個(gè)白色的像素，接著是1個(gè)黑色像素。圖2.3為圖2.2的全部編碼。注

意開始數(shù)字為0的行表示該行開頭沒(méi)有白色像素，第一個(gè)像素為黑色。

使用黑板進(jìn)行說(shuō)明可能比較困難，因?yàn)樵诤诎迳想y以分辨黑色像素

圖2.3使用數(shù)字編碼的圖形2.2

4.讓學(xué)生將圖2.6進(jìn)行解碼。

解碼后圖片如2.3,2.4為縮小后的樣子。

右邊的“test”比較容易，而左邊的“being”最為復(fù)雜，在方格內(nèi)完成圖像，由于十分容

易出錯(cuò)，所以最好使用鉛筆。由于在填涂過(guò)程中表示黑色像素的數(shù)字十分容易出錯(cuò)，為了更

容易解碼，我們可以將方格中的行和列編號(hào)，并將表示黑色像素的數(shù)字圈起來(lái)。

7

圖2.5壓縮圖

變換與拓展

將描圖紙覆在網(wǎng)格上進(jìn)行解碼，最后完成圖像時(shí)就沒(méi)有網(wǎng)格，這樣會(huì)使圖像更為清晰。

學(xué)生還可以使用方形彩色貼紙或其它替代物來(lái)取代鉛筆填涂網(wǎng)格。十字繡的圖案也可以使用

這種方式編碼。

學(xué)生可以在網(wǎng)格中自己設(shè)計(jì)圖案（或照著計(jì)算機(jī)屏幕顯示出的畫），然后將其編碼，再

讓其他學(xué)生還原。

由于二進(jìn)制數(shù)表示的長(zhǎng)度有限，通常實(shí)際應(yīng)用中，像素最大長(zhǎng)度是有限的。我們可以向

學(xué)生提問(wèn)，讓他們回答如何用7個(gè)格子來(lái)表示12個(gè)黑色像素（?種方法是將7個(gè)格子涂黑，

再下一行緊接著5格黑色），如果將顏色使用數(shù)字表示（例如：0表示黑色，1為紅色，2為

綠色，等等）就可使用這種方法表示彩色圖像。增加兩個(gè)數(shù)字來(lái)表示一行像素，第一個(gè)水給

出像素的長(zhǎng)度，第2個(gè)數(shù)字代表顏色。

相關(guān)知識(shí)

計(jì)算機(jī)中最簡(jiǎn)單表示黑白圖像的方法是用0米表示白色，1來(lái)表示黑色。通常圖像中經(jīng)

常會(huì)有大塊的白色（特別是頁(yè)邊）和連續(xù)的黑色（如水平線）。傳真機(jī)中，每英寸有100個(gè)

像素，因此7英寸寬的頁(yè)的一行開頭的白色需要占用700bit存儲(chǔ)量。

我們?cè)谡n程中使用的“行程編碼”方式更為有效,只需用lObit就可以表示上例中需要700

個(gè)二進(jìn)制表示的圖像。這個(gè)例子有一些極端，但也表明該方法可以顯著節(jié)約空間。使用這種

節(jié)約空間的技術(shù)稱為“壓縮”，這也是計(jì)算機(jī)進(jìn)行圖像操作的關(guān)鍵。例如，一般來(lái)說(shuō)，傳真機(jī)

8

可以將圖片壓縮至原來(lái)的,。如果沒(méi)有壓縮技術(shù)，傳真機(jī)需要花費(fèi)7倍的時(shí)間進(jìn)行傳送，

7

這樣會(huì)限制了傳真機(jī)的使用。存儲(chǔ)在計(jì)算機(jī)中的圖像經(jīng)常被壓縮至’-甚至「一，有了壓縮

10100

技術(shù)，計(jì)算機(jī)能夠存儲(chǔ)更多的圖片。存儲(chǔ)動(dòng)畫時(shí)這項(xiàng)技術(shù)更為重要，因?yàn)閯?dòng)畫中每秒包含了

25張或更多圖片。本課程所講的壓縮技術(shù)類似于大多數(shù)通用傳真機(jī)使用技術(shù)。還有許多其

它壓縮技術(shù)，一種是有損壓縮，這種技術(shù)會(huì)輕微的改變圖像以達(dá)到更好的壓縮效果.壓縮技

術(shù)會(huì)不會(huì)起反效果，反而將圖像擴(kuò)大了呢？也存在這種情況。假如有像國(guó)際象棋棋盤這樣的

黑白間隔圖像，直接使用像素表示黑白比使用數(shù)字編碼更能節(jié)約空間，盡管這是一個(gè)假設(shè)，

但是?些真正的圖像（如半調(diào)圖像、向報(bào)紙上的插圖等），由許多微小的點(diǎn)構(gòu)成的圖像，不能

很好地壓縮甚至還會(huì)放大，因此，我們對(duì)這類圖像表示方法的研究就顯得十分必要。

補(bǔ)充讀物

Netravali和Haskell的Digitalpictures:representationandcompression深入探討了計(jì)算機(jī)

圖像表示。

Hunter和Robinson于1978年發(fā)表的“Internationaldigitalfacsimilecodingstandards",文

章敘述了傳真機(jī)編碼標(biāo)準(zhǔn)方法。

最新關(guān)于圖像編碼標(biāo)準(zhǔn)的書是Pennebaker和Mitchell.的JPEG:StillImageData

CompressionStandard。

9

KjdFa*

i—.......J

QQ

>>)

Planet

Row1652.3

25.2,3,1

Being

3

Powf622.2

9.1.1,1

252.2.2,1

511.1

66

2

91.1

3

828Testpicture

62

Rowf11

92

723,1.4,1,3.1

9.2.1

4.2,3.1

1.Z12.29.2,1

112.2.5.1

11

1235,2

6.1.2.1.6.149

2.5

7,2.7.149

57

5.2,5.1

fS10.1

166.2

圖2.6

說(shuō)明：用數(shù)字在正方形內(nèi)著色。圖中的每一行都對(duì)應(yīng)一行數(shù)字。例如，4,9,2,1這行代

表著方格4為空，方格9著色，方格2為空，方格1著色。

10

活動(dòng)3文本壓縮

適用年級(jí)：小學(xué)生以上（至少9歲）

預(yù)設(shè)能力：可以抄寫文本

所需時(shí)間：大約10分鐘

適用人數(shù)：從個(gè)人到整個(gè)班都可以

關(guān)注焦點(diǎn)

寫

抄

在寫過(guò)的文本中反復(fù)寫

摘要

盡管現(xiàn)代計(jì)算機(jī)大規(guī)模存儲(chǔ)技術(shù)有了很大進(jìn)步，設(shè)備的存儲(chǔ)效率仍然非常重要。在

數(shù)據(jù)存儲(chǔ)時(shí)對(duì)數(shù)據(jù)編碼，讀取數(shù)據(jù)時(shí)對(duì)數(shù)據(jù)解碼，這兩處雖然耗費(fèi)了一些時(shí)間，但是可

以很大程度上提高計(jì)算機(jī)的存儲(chǔ)能力。本課程講述了如何將文本進(jìn)行編碼以節(jié)約空間。

專有名詞

文本壓縮，Ziv-Lempel編碼

所需教材

給每個(gè)學(xué)生發(fā)一張?zhí)羁請(qǐng)D，如圖3.1所示。

教師需要準(zhǔn)備一些詩(shī)歌或文章來(lái)給學(xué)生練習(xí)編碼。

圖3.1說(shuō)明：根據(jù)箭頭指向，在每個(gè)空白框填寫所指的字母

11

活動(dòng)流程

1.給每一位學(xué)生發(fā)一張?zhí)羁請(qǐng)D，并讓他們來(lái)解碼，即：將箭頭所指向的字母填入空

格中，完成詩(shī)歌內(nèi)容。例如，第一個(gè)空格應(yīng)該填入字母e,第二行的第一個(gè)空格應(yīng)填入

第一行的短語(yǔ)Peaseporridge。填好后如下圖。

圖3.2已完成的工作表

2.我們讓學(xué)生自己找一些文本，并使用箭頭和空格表示，使最后留下來(lái)的文字越少

越好。若空格的填充順序是從上到下，從左到右，箭頭應(yīng)一直指向前面的部分，這樣才

能保證能夠解密。學(xué)生可以自己寫一些文本，將其編碼，也可以使用教師提供的文本。

因?yàn)樵S多兒歌和詩(shī)歌有許多重復(fù)的單詞、短語(yǔ)或句子，所以它們都可進(jìn)行有效的編碼，

如Dr.Seuss's的書"Greeneggsandham"就是一個(gè)很好的素材。

變換與拓展

箭頭與空格編碼必須要使箭頭總是指向前面的文本，例如，圖3.3顯示了單詞

“Banana”的編碼情況，盡管空格的箭頭指向該單詞本身，仍然可以按照從左到右的順

序成功解碼，對(duì)于有較長(zhǎng)循環(huán)的字符或模式，采用這種自表達(dá)的方式編碼很有用。

圖3.3自我參考復(fù)制的代碼

12

在計(jì)算機(jī)中，箭頭和空格都可使用數(shù)字表示，例如：圖3.3可以表示為“Ban（2,3）”，

2表示第2個(gè)字符為第一個(gè)要抄的字符，3表示需要照抄3個(gè)連續(xù)的字符。解碼過(guò)程如下：

Ban___

Bana..

Banan.

Banana

圖3.4

在計(jì)算機(jī)中，顯然兩個(gè)數(shù)字要表示兩個(gè)以上的字符，如只用來(lái)表示一個(gè)字符，則沒(méi)

有編碼的必要。學(xué)生可以嘗試采用數(shù)字表示法來(lái)進(jìn)行編碼和解碼。

為了讓學(xué)生更好的認(rèn)識(shí)這種編碼，可以發(fā)給學(xué)生一張印有文本的紙做練習(xí)，讓學(xué)生

找出可以用數(shù)字來(lái)取代的部分，這些部分必須包含有兩個(gè)或以上字母，因?yàn)槿粲脙蓚€(gè)數(shù)

字對(duì)一個(gè)字母進(jìn)行編碼不能節(jié)約空間，練習(xí)的目的是盡可能的將字母用數(shù)字表示。

相關(guān)知識(shí)

計(jì)算機(jī)的存儲(chǔ)能力正在以不可置信的速度增長(zhǎng)，過(guò)去25年中，計(jì)算機(jī)存儲(chǔ)量實(shí)現(xiàn)了

百萬(wàn)倍的增長(zhǎng)，但是相對(duì)于存儲(chǔ)需求，這種增長(zhǎng)仍不夠。計(jì)算機(jī)能夠儲(chǔ)存一本書的能力

提供了存儲(chǔ)整個(gè)圖書館藏書的可能，可以顯示高質(zhì)量的圖片意味著可以播放電影，具有

較高可靠性的CD-ROM取代了軟盤存儲(chǔ)分散數(shù)據(jù)和程序。任何擁有計(jì)算機(jī)的人都會(huì)見證

Parkinson定律，即總有存不完的數(shù)據(jù)。

為了滿足存儲(chǔ)需要，除了購(gòu)買更多的存儲(chǔ)空間外，還可以壓縮現(xiàn)有的數(shù)據(jù)。本課程

描述了壓縮過(guò)程：改變數(shù)據(jù)的表達(dá)形式來(lái)節(jié)約空間。計(jì)算機(jī)會(huì)自動(dòng)執(zhí)行壓縮和解壓縮，

用戶幾乎不會(huì)意識(shí)到這個(gè)過(guò)程，他們只是注意到磁盤存儲(chǔ)數(shù)據(jù)越多，從磁盤中讀取文件

所需時(shí)間有了增加。計(jì)算機(jī)在存儲(chǔ)和讀取時(shí)也要耗費(fèi)一些時(shí)間，有時(shí)系統(tǒng)使用壓縮的文

件會(huì)更快，這是因?yàn)榻鈮嚎s的時(shí)間要小于讀壓縮文件所節(jié)約的時(shí)間。

人們提出了許多壓縮方法，其中普遍被采用的技術(shù)就是指向先出現(xiàn)重復(fù)的大塊文

本，通常稱這種技術(shù)為“Ziv-Lempel編碼”或LZ編碼，是以色列的兩個(gè)教授于20世紀(jì)70

年代到80年代所提出的。這種編碼對(duì)許多數(shù)據(jù)都有效，它還可適用于西班牙語(yǔ)、英語(yǔ)，

甚至是日語(yǔ)這種使用完全不同的字母表組成的文字，這種編碼應(yīng)用于文本，因?yàn)槲谋局?/p>

有很多單詞會(huì)重復(fù)出現(xiàn)，可以使用指針取代。典型的LZ編碼壓縮可以將數(shù)據(jù)減少一半，

通用的檔案存儲(chǔ)程序如Zip和ARC以及磁盤備份時(shí)都使用了LZ編碼進(jìn)行，高速modem也

使用了LZ編碼，當(dāng)計(jì)算機(jī)通過(guò)普通電話線進(jìn)行交互，壓縮技術(shù)可以減少電話線傳輸數(shù)據(jù)

來(lái)量，從而顯著提高傳輸速度。

還有一種壓縮方法是采用較短碼長(zhǎng)表示高頻字（如Morse編碼）。此外還有更好的

方法（所需時(shí)間更多），基于這種思想，我們可以憑借現(xiàn)有的幾個(gè)字母時(shí)測(cè)出下一個(gè)字

母，這將在活動(dòng)5中有所介紹。

補(bǔ)充讀物

Bell,Cleary,Witten寫的Texfcompressionby以及Witten,Moffat,Bell寫的

Gigabytes:Compressingandindexing全面介紹了壓縮算法，這是面向大學(xué)計(jì)算

機(jī)科學(xué)的學(xué)生的。如果你對(duì)計(jì)算機(jī)編程感興趣的話，還可以閱讀MarkNelson的T成血柩

compressionbook,這是一本以應(yīng)用為指南的書，Dewdney的O"皿沏/在文本壓縮這

一章還討論了“Huffmancoding”。

13

活動(dòng)4卡片魔術(shù)一檢錯(cuò)與糾錯(cuò)

適用年級(jí)：小學(xué)三年級(jí)以上

預(yù)設(shè)能力：能夠識(shí)別和數(shù)出小的奇數(shù)和偶數(shù)

所需時(shí)間：大約30分鐘

適用人數(shù)：從一個(gè)人到全班都適用

關(guān)注焦點(diǎn)

奇數(shù)和偶數(shù)

模式

小魔術(shù)

摘要

我們通常假定數(shù)據(jù)從一臺(tái)計(jì)算機(jī)傳送到另一臺(tái)時(shí)總是正確的。然而，事實(shí)卻不是這樣，

會(huì)有一些意外發(fā)生，使數(shù)據(jù)發(fā)生改變，這次課程使用一個(gè)小魔術(shù)來(lái)展示如何檢查出這些錯(cuò)誤

并進(jìn)行糾正。

專有名詞

檢錯(cuò)碼，糾錯(cuò)碼，奇偶校驗(yàn)

所需教材

每?jī)蓚€(gè)學(xué)生需要一套約25張的相同的卡片，卡片具體要求在后面描述

為了向全班進(jìn)行演示，教師需要一套約40張的帶磁卡片和?塊金屬板

活動(dòng)流程

這次課程通過(guò)魔術(shù)來(lái)教導(dǎo)學(xué)生，在第一次演示時(shí)能夠很容易的引起學(xué)生的興趣，然后再

告訴學(xué)生怎么變這個(gè)魔術(shù)。為了增強(qiáng)魔術(shù)的效果，可加入?些戲劇因素。學(xué)生的位置安排必

須使他們可以清楚的看到教師的動(dòng)作。表演這個(gè)魔術(shù)需要一疊同樣的兩面不同的卡片，比如,

?面是紅色，一面是白色，可以用?張大的單面有顏色的卡紙裁開制成；或是使用撲克牌。

為了便于演示，卡片應(yīng)帶有磁性，可以買一些磁條粘在卡片上。制作大約40張這樣的卡片，

?半為正面，-半為反面。將卡片放在一塊豎著的金屬板上，以便演示給全體學(xué)生看，而當(dāng)

學(xué)生表演時(shí)，可以讓他們把卡片平放在面前的地上或桌子上。

1.讓一個(gè)或兩個(gè)學(xué)生隨意選擇卡片排列成一個(gè)矩形，任何大小都可以，例如5X5（矩

形擺得越大，效果越好），卡片的排列方式任意，圖4.1為一個(gè)示例：

圖4.1一張初始任意的5X5卡片排列

14

2.教師隨意的增加一行和一列，使卡片排列看上去更為復(fù)雜（如圖4.2）。這一步是魔

術(shù)的關(guān)鍵，其方法是必須保證每一行和每一列中有顏色的卡片為偶數(shù)張。

圖4.2增加一行一列的卡片排列

3.找一個(gè)學(xué)生來(lái)翻動(dòng)一張卡片，改變它的顏色。當(dāng)學(xué)生翻卡片時(shí)，教師可以蒙住眼睛,

背對(duì)卡片，不去看學(xué)生是如何做的。例如圖4.3,第4行第3章卡片被翻動(dòng)了。然后，解放眼

睛，仔細(xì)研究卡片，并斷定哪一張卡片被動(dòng)過(guò)了。將其恢復(fù)后，可再找一些學(xué)生來(lái)做演示,

使學(xué)生信服。這個(gè)魔術(shù)可以用任意多張的卡片做，卡片數(shù)量越多，效果越好。

口■口”

口口口口

口

flfDDCD

圖4.3翻動(dòng)一張卡片的排列

4.讓學(xué)生來(lái)猜這個(gè)魔術(shù)是怎樣做的。

5.此時(shí)教師可以提出將秘密告訴學(xué)生。

將學(xué)生分成兩人一組，讓每一組學(xué)生將他們的卡片排列成4X4的方形，卡片的排列方式

任意，檢查學(xué)生是否能記住奇數(shù)和偶數(shù)的概念，并說(shuō)明0是一個(gè)偶數(shù)。然后讓他們?cè)僭黾右?/p>

行或冽，確保有偶數(shù)張有顏色卡片（如果有色卡片的顏色已經(jīng)是偶數(shù)，就增加?張白色的

卡片），此時(shí)教師可以將這張卡片稱為奇偶校驗(yàn)卡片，以教學(xué)生奇偶校驗(yàn)這個(gè)術(shù)語(yǔ)。指出當(dāng)

?張卡片被翻過(guò)后會(huì)變成怎樣：翻過(guò)了的卡片所處的行和列中有色卡片的數(shù)量成為了奇數(shù)。

當(dāng)學(xué)生會(huì)4X4后，可以讓他們排更大的矩形。

變換與拓展

教師可以用任意具有兩種狀態(tài)的物體來(lái)代替卡片。例如硬幣（正面/反面）、棍棒（水

平放置和垂直放置）、杯子（口向上和底向上）等等。如果將此活動(dòng)替代活動(dòng)1,可以標(biāo)志

卡片的一面為0,另一面為1。將卡片用二進(jìn)制表示，奇偶校驗(yàn)位用來(lái)保護(hù)信息。

通過(guò)卡片練習(xí)學(xué)生還可以發(fā)現(xiàn)更多。讓他們考慮兩張卡片被翻動(dòng)時(shí)的情況，在這種情況

下，將無(wú)法確定的判斷出被翻的兩張卡片，盡管可以看出有卡片被翻過(guò)了。當(dāng)3張卡片被翻

動(dòng)后，會(huì)出現(xiàn)類似的情況，能夠看出卡片被翻過(guò)了，不能準(zhǔn)確的看出是哪幾張被翻過(guò)了。當(dāng)

4張卡片被翻動(dòng)時(shí)，有可能校驗(yàn)位變成正確地，此時(shí)也不能發(fā)現(xiàn)有錯(cuò)了。

另一有趣的練習(xí)是關(guān)于最后一張卡片（最右邊最下面）的設(shè)置。如果它在列上是正確的,

15

那么在一行中是不是也是正確的呢？（答案是肯定的，可以讓學(xué)生來(lái)尋找反例以證明這一

點(diǎn)）。

上面所用到的校驗(yàn)碼是偶校驗(yàn)，即使有色卡片數(shù)量為偶數(shù)，也可以使用奇校驗(yàn)，即使每

一行和每一列中的有色卡片數(shù)量為奇數(shù)，此時(shí)最后放置的卡片（最右邊最下面）時(shí)只有行數(shù)

和列數(shù)同為奇數(shù)或同為偶數(shù)時(shí)才可成立，例如當(dāng)矩形為5X9或12X4時(shí)可以，而3X4時(shí)不行。

可以讓學(xué)生自己來(lái)做奇校驗(yàn)并試著讓他們發(fā)現(xiàn)這個(gè)規(guī)律。

生活中用到檢錯(cuò)的有用于圖書出版的國(guó)際標(biāo)準(zhǔn)圖書號(hào)（ISBN）。它是一個(gè)有10位數(shù)字

的號(hào)碼，一般印在書的封底，用來(lái)唯?的標(biāo)識(shí)一本圖書。最后（第10個(gè)）的一位數(shù)字并不是

圖書標(biāo)識(shí)，而是一個(gè)校驗(yàn)碼，就像我們之前說(shuō)的奇偶校驗(yàn)碼，用來(lái)檢驗(yàn)整個(gè)號(hào)碼是否有錯(cuò)誤。

如果，我們使用ISBN訂購(gòu)圖書，若有一位數(shù)字出錯(cuò)，則通過(guò)校驗(yàn)和可以檢查出，使我們不

會(huì)買到錯(cuò)誤的書。

校驗(yàn)和可以通過(guò)一些簡(jiǎn)單的算法計(jì)算，可以將第一位數(shù)乘以10,第二位數(shù)乘9,第三位

乘8,依次類推，直到第九位數(shù)乘2,將所有的積相加所得到的和用s表示。例如：有這樣一

個(gè)ISBN號(hào)碼，0-13-911991-4,則s=0X10+1X9+3X8+9X7+1X6+1X5+9X4+9X3+1X2=172。然

后取s除以11所得的余數(shù)，在上例中為7。如果余數(shù)為0,那么校驗(yàn)和為0,否則，取該數(shù)與11

的差作為校驗(yàn)和，位ISBN中的最后一位，即得11-7=4。此時(shí)如有算得ISBN中的最后一位不

為4,就可知道有錯(cuò)誤發(fā)生。

使用此方法計(jì)算出的校驗(yàn)和最大值為10,在ISBN中使用字母X來(lái)表示，校驗(yàn)和為10的情

況是十分少見的。

讓學(xué)生試著檢驗(yàn)一些真正的ISBN的校驗(yàn)和。讓他們知道他們可以檢測(cè)出下列常見錯(cuò)誤：

1.一位數(shù)字的值被改變了

2.兩位相鄰數(shù)字的值互換

3.增加了一位

4.減少了一位

讓學(xué)生思考哪些錯(cuò)誤是不能被檢測(cè)出來(lái)的，例如，一位數(shù)字變大了二另一數(shù)字變小導(dǎo)致

和不變。

另一種相似的校驗(yàn)碼（使用了另一種算法）為條形碼。例如日用貨品上的（圖4.4）。如

果條形碼讀錯(cuò)了，則會(huì)出現(xiàn)最后一位與計(jì)算結(jié)果不同，此時(shí)，掃描器報(bào)警通知并重新掃描。

圖4.4一張來(lái)自食品的條形碼（UPC）

相關(guān)知識(shí)

假設(shè)我們要在銀行中存入10元，銀行工作人員輸入這張存單并將其傳送給中央電腦，使

你的帳戶增加10元，若在傳送過(guò)程中由于噪聲干擾，在數(shù)量上出現(xiàn)錯(cuò)誤，會(huì)使增加10元變?yōu)?/p>

增加1000元。面對(duì)這種情況，毫無(wú)疑問(wèn)，銀行很有必要保證傳送信息的正確性。

這只是數(shù)據(jù)傳送中必須檢錯(cuò)的?個(gè)例子，事實(shí)上，無(wú)論那種場(chǎng)合，計(jì)算機(jī)間進(jìn)行數(shù)據(jù)傳

送，接受方能夠檢驗(yàn)接收的數(shù)據(jù)是否受到線路噪聲的干擾使非常重要的。這種傳送可能是金

16

融數(shù)據(jù)、文件傳真或是電子郵件。不僅是文件傳送，還有一種情況下進(jìn)行檢錯(cuò)也是非常重要

的，即當(dāng)我們從光盤或磁盤上讀數(shù)據(jù)時(shí)。由于這些存儲(chǔ)介質(zhì)會(huì)受到磁性、電輻射、熱量以及

物理?yè)p害的影響，因此我們不僅想要直到存儲(chǔ)數(shù)據(jù)是否受到損壞，還想要重構(gòu)哪些被損壞的

數(shù)據(jù)，與數(shù)據(jù)傳送時(shí)不同，我們無(wú)法要求重傳有問(wèn)題的數(shù)據(jù)。還有一種情形也不能重傳數(shù)據(jù),

即數(shù)據(jù)是從遙遠(yuǎn)的空間探測(cè)頭上傳來(lái)的，因?yàn)橐苿?dòng)探測(cè)頭上收集的數(shù)據(jù)會(huì)隨時(shí)間而變化，若

有錯(cuò)誤發(fā)生，進(jìn)行重傳的等待時(shí)間十分漫長(zhǎng)，而且空間探測(cè)頭的容量十分有限，無(wú)法存儲(chǔ)足

夠的資料。

能夠發(fā)現(xiàn)數(shù)據(jù)中的錯(cuò)誤稱為檢錯(cuò)，能夠重新構(gòu)造原來(lái)的數(shù)據(jù)稱為糾錯(cuò)。一種實(shí)現(xiàn)檢錯(cuò)和

糾錯(cuò)的簡(jiǎn)單的方法是同一數(shù)據(jù)傳送3次，如果有錯(cuò)誤發(fā)生，那么該數(shù)據(jù)就會(huì)與其他兩份數(shù)據(jù)

不同，我們可以知道并將錯(cuò)誤的數(shù)據(jù)丟棄。然而，這種方法存在不少問(wèn)題，例如如果有兩份

數(shù)據(jù)正好都犯了同樣的錯(cuò)誤，就會(huì)判斷出錯(cuò)。另外，使用該方法會(huì)使系統(tǒng)效率十分低，因?yàn)?/p>

必須存儲(chǔ)或轉(zhuǎn)發(fā)3倍的數(shù)據(jù)。盡管所有的錯(cuò)誤控制體都須要增加額外的數(shù)據(jù)，我們?nèi)匀豢梢?/p>

采用更好的方法。

所有計(jì)算機(jī)數(shù)據(jù)存儲(chǔ)和傳送時(shí)都是采用0和1序列，稱為位，所以問(wèn)題的關(guān)鍵就是確保發(fā)

送的01序列是正確的。卡片魔術(shù)用了兩面不同的卡片分別表示。和1,并增加了奇偶校驗(yàn)來(lái)發(fā)

現(xiàn)錯(cuò)誤，同樣的技術(shù)可以用于計(jì)算機(jī)中，在一行序列中增加一個(gè)校驗(yàn)位可以發(fā)現(xiàn)一位錯(cuò)誤，

將這些序列排列成矩形(同游戲)，并在每?行和列都增加?個(gè)偶校驗(yàn)位，我們就可以做到

檢錯(cuò)和糾錯(cuò)了。

事實(shí)上，計(jì)算機(jī)使用更為復(fù)雜的錯(cuò)誤控制體系來(lái)發(fā)現(xiàn)和糾正多級(jí)錯(cuò)誤，不過(guò)，這種體系

類似于奇偶校驗(yàn)方法，即使是最好的錯(cuò)誤控制體系，也會(huì)有檢測(cè)不出錯(cuò)誤的可能，不過(guò)這種

可能性十分微小，小到與一只猴子能夠隨意敲擊出莎士比亞的作品一樣。

補(bǔ)充讀物

奇偶校驗(yàn)的方法探測(cè)錯(cuò)誤是比較原始的，還有許多種更好的方法，其中比較重要的方

法有Hammingdistances,CRC(cyclicredundancycheck),BCH(Bose-Chaudhuri-Hocquenghem)

codes,Reed-SolomonCodes,和回旋碼(convolutionalcodes),這些方法的具體內(nèi)容可參照

RichardHamming的CodingandInformationTheory,andBenjaminArazi'sAcommonsense

approachtothetheoryoferrorcorrectingcode。Hamming的書的ISBN號(hào)碼為0-13-139139-9,這

本關(guān)于編碼的書有一個(gè)十分有意思的書號(hào)。比較簡(jiǎn)單，易懂的關(guān)于糾錯(cuò)的書有TheTuring

Omnibus,作者是Dewdney,以及inComputerScience:AnOverview作者是Brookshear。

17

活動(dòng)520次猜測(cè)——信息理論

適用年級(jí)：小學(xué)三年級(jí)以上

預(yù)設(shè)能力：比較兩數(shù)大小和數(shù)的歸類

所需時(shí)間：20到30分鐘

適用人數(shù)：從2個(gè)人到全班都適用

關(guān)注焦點(diǎn)

演繹

數(shù)的歸類

提問(wèn)題

摘要

計(jì)算機(jī)科學(xué)非常關(guān)注信息，信息對(duì)于計(jì)算機(jī)非常重要，計(jì)算機(jī)系統(tǒng)要進(jìn)行信息存儲(chǔ)、讀

取、分析、總結(jié)并與其他計(jì)算機(jī)交互，因此信息的量化十分關(guān)鍵。信息理論提供了衡量信息

的方法，包括如何有效地存儲(chǔ)或傳輸?shù)囊?guī)則。本課程研究了衡量信息內(nèi)容的方法。

專有名詞

信息理論香農(nóng)定理編碼數(shù)據(jù)壓縮檢錯(cuò)和糾錯(cuò)嫡

所需教材

板書，如黑板和粉筆

如表5.1的卡片

消息類型消息樣例說(shuō)明

1到100之間的數(shù)字67

對(duì)年齡較大的學(xué)生，可以使用1到10萬(wàn)之間

1到1000之間的數(shù)字387

的數(shù)字

任意數(shù)字145對(duì)年齡較大的學(xué)生，可以取更大的數(shù)字

回答問(wèn)題的學(xué)生年齡10不介意的話，可以使用教師的年齡

告訴學(xué)生有6個(gè)有規(guī)律的數(shù)字，讓學(xué)生猜從

{2,4,6,8,10,12}

第一個(gè)到最后一個(gè)的數(shù)字

數(shù)字序列

這此數(shù)字是先加2,再減1,再加2,再減

{1,3,243,5,4,6,5,7}

1,.......

句子需要按從左到右的順序，一次猜測(cè)一