思考的演算:跟著電腦學思考,你也可以成為計算思考大師
文/白榮銓
臺中市居仁國中退休教師
十二年國民基本教育課程綱要草案,新增「科技領域」,學習內涵包含「生活科技」與「資訊科技」。資訊科技課程是以
「運算思維」(computational thinking, CT)為主軸,學習重點強調「透過電腦科學相關知能的學習,以培養學生的運算思維能力;並藉由資訊科技之設計與實作,增進學生運算思維的應用能力與解決問題的能力」;教學實施則強調「以問題解決或專題製作之方式進行,鼓勵學生進行自主性、探索式的學習,以實踐運算思維的課程理念」。到底何謂運算思維(本書譯為「計算思考」)?包含那些技能?如何應用來解決問題?
本書作者科松(Paul Curzon)與馬克歐文(Peter McOwan),都是倫敦瑪麗皇后大學(Queen Mary University of London)的電腦科學教授,共同創辦了「電腦科學好好玩」(Computer Science for Fun)網站,致力於提供教師專業發展課程。他們在青少年時代,熱愛閱讀美國數學科普大師加德納(Martin Gardner, 1914-2010)撰寫的娛樂性數學(recreational mathematics)讀物,深受加德納的啟發和影響。本書內容來自作者重新改寫他們在「電腦科學好好玩」網站、雜誌、以及在用來協助程式寫作與資訊融入教學的網站「Teaching London Computing」上所發表的文章,以讀者容易理解的方式,搭配遊戲(game)、謎題(puzzle)、魔術以及電腦科學家在研究的真實難題,解釋何謂計算思考,以及這種問題解決方法中的各種技巧,包括:演算法思考(algorithm thinking)、評估(evaluation)、模式比對(pattern matching)、通化(generalization)、抽象化(abstraction)以及拆解(decomposition)等,幫助讀者了解與學習電腦科學家的思考方式。
(封面圖片來源)
計算思考
1980年,美國數學家暨教育家派普特(Seymour Papert, 1928-2016)出書《心智衝擊:兒童、電腦與充滿活力的創意》(Mindstorms: Children, Computers, and Powerful Ideas),首次提出「計算思考」(computational thinking)一詞。計算思考是「人類解決複雜問題的多元技能之集合」,適用於電腦科學、人文科學、數學與所有科學領域,計算思考有助於學生了解學科與學科、以及課堂與生活之間的關係。
2007年,改編自真人實事的法國電影《潛水鐘與蝴蝶》(The Diving Bell and the Butterfly, 圖1)上映,劇情描述法國時尚雜誌《ELLE》總編輯鮑比(Jean-Dominique Bauby, 1952-1997),於1995年12月突然中風,陷入昏迷,雖然三星期後甦醒,卻被診斷患有閉鎖症候群(locked-in syndrome),全身癱瘓,完全喪失發音能力,全身僅剩左眼可以自由活動,在接下來的兩年時間內,神奇地完成他生命中唯一的一本書《潛水鐘與蝴蝶》。鮑比在書中記錄自己中風後的日常生活點滴。假設你是他的語言治療師杜蘭(Henriette Durand),請問要如何為他設計出一套與外界溝通,而且能完成寫作的方法。
圖1. 《潛水鐘與蝴蝶》電影海報(圖片來源)
此時,你需要和他達成共識,找出一套能將「眨眼動作轉為字母」的方法,你的第一想法可能是告訴他:「眨一次眼代表字母A,眨兩次眼代表字母B」,以此類推;接著,手上拿著紙筆的杜蘭,只要數他眨了幾次眼,記錄下相對應的字母,就像網路世界中,不同電腦之間用於資料編碼與解碼的「通訊協定」(protocol)。當我們設計出一系列可以遵循及解決問題的步驟,能正確地溝通病患所想的字母,我們就已在進行像電腦科學家一樣的思考,這就是計算思考的核心,稱為「演算法思考」。透過演算法思考,人們不只能想出單一答案,更能想出一套可以依照一定步驟,甚至更有效解決問題的方案。
鮑比在書中的確有更好的方法,他描述:杜蘭依序大聲地朗讀出字母A、B、C……,當他腦中所想的那個字母被朗讀出來時,他就眨一次眼,接著,杜蘭就會寫出那個字母,然後再重新開始朗讀一個又一個的字母。問題是需要用來溝通的元件,不只是字母,還需要空格、數字、逗號及句號等;另一個問題是:萬一不小心眨了眼怎麼辦。像這樣,檢查一個演算法在理論及實際上,是否都行得通,是計算思考的重要部分之一,稱為「評估」。
為了與鮑比加速溝通流程,最好是拼一個字的一部分字母,就能正確地猜出這個字,例如杜蘭已經寫下a-n-t-e-l,就能猜出鮑比腦中想的是antelope(羚羊)。因此可以改變規則,讓杜蘭以這種方式猜猜看,這種演算法類似於手機與電腦在「聯想字詞」時所使用的運作方式。當人們在搜尋引擎輸入一個想要搜尋的關鍵詞時,它所做的事情和上面情況類似,這是計算思考的另一個重要部分,稱為「模式比對」。
能夠運用「聯想字詞」這種解決方法,是因為杜蘭和電腦所面臨的問題是類似的,即杜蘭必須一個字母接著一個字母,認出閉鎖症患者想要表達的單字;而電腦必須一個字母接一個字母,拼出使用者想輸入的單字」。更理想的情況是,我們已有一個適用於許多類似問題的解決方法,並從一開始就為該運算法創造一個描述(description),這樣只要類似情況一出現,就能使用這種演算法,這是計算思考的重要技巧之一,稱為「通化」。
身為法國女性雜誌《ELLE》的總編輯,鮑比對於語言有很深的造詣,他知道這種ABC演算法,還可以用不同方式來加以改善,有些字母比起其他字母出現的頻率更高,例如E是最常出現的字母(在英語和法語中皆然),因為鮑比使用的是法語,所以在電影中,他請杜蘭以法文常出現的頻率順序「E-S-A-R-……」(圖2)來朗讀字母,就可以使杜蘭加速念到單字內所含的字母。像這樣,使用頻率分析(frequency analysis)的方法,就是運用了計算思考中的「模式比對、通化」等技巧。
圖2. 劇中的法文字母出現頻率順序卡(圖片來源)
運用計算思考的技巧,能得到比最初「針對每一個字母,分別眨眼不同次數」更好的溝通方法,對於「寫完整本書要多久的時間、是否為最佳方式」,進行評估之後,我們是否能設計出更理想的演算法,幫助鮑比完成這本書。我們可以利用「分析式思考」(analytical thinking),用簡單的數學來計算,只要將字母的數量,乘上念一個字母所需的時間,如此不但能知道想要完成的工作量,更能知道這是否為最佳方式。像這樣,過濾或忽略不必要的特徵,集中在重要的特徵上(例如字母的數量、念一個字母的時間),是計算思考的重要技巧之一,稱為「抽象化」。
使用頻率分析能得到更佳的溝通方式,但最糟糕的情況依然要念完26個字母;於是我們還要思考:如何再減少杜蘭念的字母數量。19世紀時,美國各地風行「20個問題」(Twenty Questions)遊戲,遊戲規則:選擇一名玩家作為「回答者」(answerer),這個人選擇一個「主題」(subject);其他的玩家都是「提問者」(questioner),每個人輪流問一個問題,回答者只能用簡單的「是、否」做答。遊戲中,回答者不允許說謊,提問者須在20個問題內,正確猜中「主題」,猜中者將成為下一輪遊戲的回答者,例如「想像我是一位名人,猜猜我是誰?」提問者與回答者的對答如下:「是女的嗎?不是」、「還活著嗎?不是」、「是電影明星嗎?不是」、「來自英國嗎?是的」、「是作家嗎?是的」、「20世紀的人物嗎?不是」、「19世紀的人物嗎?不是」、「是莎士比亞嗎?是的」。
玩「20個問題」的秘訣:無論答案是什麼,每次提問都要是「能排除一半人選」的問題,即每次都能提出「二分法」的問題。像這樣,將一個複雜的問題,分解成很多的小問題,使問題能更容易解決,是計算思考的重要技巧之一,稱為「拆解」。依照「模式比對與通化」的技巧,猜鮑比腦中的字母,與猜「回答者」腦中的主題,應屬於類似的問題。杜蘭一開始可以提問「這是一個A到M之間的字母嗎?」(圖3)如果答案為「是」,則可以再問「這是一個A到F之間的字母嗎?」如果答案為「否」,則改為問「這是一個N到S之間的字母嗎?」以此類推,這樣一定能在5個問題內,得到鮑比要的字母,我們還可以藉助運算法的聯想字詞,這樣將更能提升解決問題的效率
圖3. 決策樹上用來得出每一個字母的密碼
猜字母的決策樹(decision tree),能夠衍生出一個截然不同的解決方案。如果我們將圖3的「yes(是)、no(否)」以及「眨眼、不眨眼」,定義成「1、0」,這棵決策樹就能夠定義出字母的「二進位序列」(binary sequence,表1)。進行溝通時,只要使用此序列,就能找出對應的字母,例如密碼1100(眨眼、眨眼、不眨眼、不眨眼),代表F字母,亦即利用演算思考,我們最終能得到溝通的編碼(code)。
由上述可知,「演算法思考」是計算思考的核心,能幫助我們開發出解決問題的不同方法及規則;「評估」則能讓我們知道各種演算法是否可行,甚至發展出更佳的解決方法。「模式」讓問題簡化,「模式比對」則能找出類似問題的共同特徵;「通化」能讓我們使用相同的解決方法,去解決類似的問題。「抽象化」讓我們忽略不必要的特徵,將問題具體化。「拆解」幫助我們將一個複雜的問題,分解成許多小問題,使問題更容易被理解及解決。
導遊謎題與騎士之旅
底下以導遊謎題及騎士之旅,做為運用「計算思考」解決問題的實例。假設你是某旅館的導遊,住在該旅館的遊客,希望參加一個包含該城市所有景點的一日遊行程,你有一張標示市內所有景點,及不同景點之間的地鐵路線圖(圖4)。因為旅客只在這城市待一天,為了節省時間,他們不想經過同一景點兩次,所以你必須設計一條路線,帶著城市旅遊團,從飯店出發,在一天內,乘坐地鐵,遊遍地圖內的所有觀光景點,每一個景點只能經過一次,當天最後必須回到飯店,你能畫出符合旅客需求的導覽路線圖嗎?
圖4. 導遊手上的城市導覽地圖(圖片來源)
為了探究導遊謎題的解決方法,每名學生各發一份:棋盤(圖5)、騎士(knight)棋子的移動規則(圖6)、解決方案空白紙。騎士棋子的移動規則:朝一個方向移動2格,然後轉90度,再走1格;或者朝一個方向移動1格,然後轉90度,再走2格,即走L形路線。因此,騎士自方格1出發,可以分別走至方格6、7、9。對學生提出問題:依照騎士的移動規則,在騎士之旅的解決方案空白紙上,填寫從方格1開始的移動順序,讓騎士經過各個方格一次,最後回到方格1。
圖5.騎士之旅的棋盤(圖片來源)
圖6. 騎士棋子的移動規則(圖片來源)
騎士之旅和導遊謎題非常類似,兩個問題在本質上有些相似點:(1)旅程都從一個指定地點開始,(2)旅程必須造訪每一地點,(3)旅程不可經過之前已造訪過的地點,(4)旅程必須要回到一開始的起點。我們以圖解對「騎士之旅」做進一步的分析,以圓點表示每一個方格,就像地鐵圖上以圓圈表示觀光景點一樣。當騎士依照移動規則,從任何一個圓點,走到另一個圓點時,我們就在兩個圓點之間畫上一條線,這些線就是圖解的邊。從方格1分別能夠移到方格6、9、7,我們就分別在兩者之間畫上一條線(圖7);接著同樣依照移動規則,畫出所有從方格6延伸出去的所有線、從方格9延伸出去的所有線,以及從方格7延伸出去的所有線。以此類推,這種方法稱為圖解的「廣度優先搜尋」(breadth-first search, BFS)演算法,這種演算法,會先將同一層的所有節點,全都拜訪(visit)之後,再拜訪下一層的節點。
圖7. 「騎士之旅」在棋盤上的移動可能性
另一種選擇是探索從源頭,直到終點的一條路線,例如沿著1-9-3-11-5-7……,分別在兩者之間畫上一條線,直到終點1,如果失敗,則回頭嘗試不同路線,這種方法則稱為圖解的「深度優先搜尋」(depth-first search, DFS)演算法,這種演算法總是先拜訪最深的節點(deepest node)。廣度優先搜尋演算法和深度優先搜尋演算法,是兩種不同的「圖解遍歷演算法」(graph traversal algorithms)。
以圖解法繪製騎士的路線圖,圖上有許多交叉的線條,看起來有點混亂(圖8)。為了不讓任兩條線交叉,重新整理成比較整齊的圖形,繪製出相同對應關係,並以箭頭標示「騎士之旅」的正確路線圖(圖9),請注意正確路線不只一種。仔細觀察這個版本的圖形,發現它與導遊手上的城市旅遊地圖相同,不同的只是標記在圓圈上的標籤是數字,而不是景點名稱,只要你破解了其中一個問題,另一題也就解出來了(圖10)。
圖8. 騎士之旅的圖解 圖9. 比較整齊的騎士之旅圖解(圖片來源)
圖10.導遊謎題的解答(圖片來源)
著名的「柯尼斯堡七橋」(Seven Bridges of Königsberg,圖11)問題,是另一個可供思考的謎題。問題如下:「18世紀時,柯尼斯堡市區橫跨歐洲的普瑞格爾河(Pregel River)兩岸,河中心有座小島,島上有7座古橋,分別連接河流的兩岸,以及河流中的兩座小島,當時城鎮的居民開始思考:如何在只通過各座橋一次的前提下,走遍7座古橋?」,充滿趣味性的生活化題目,吸引無數市民踴躍嘗試,卻始終無法挑戰成功。
圖11.柯尼斯堡七橋問題(圖片來源)
1735年,瑞士數學家暨物理學家尤拉(Leonhard Euler, 1707-1783),對於「柯尼斯堡七橋」深感興趣,展開研究。尤拉利用圖解,將問題簡化為平面上的圓圈與線條之組合(圖12A),每一座橋以一條曲線或直線表示,7座橋所連接的地區,包含北岸(north bank)、南岸(south bank)、東島(east island)、西島(west island),各以圓圈表示,視為一個節點(node)。如果一個節點有偶數條線聚集,則這個節點能夠讓人從一邊進,另一邊出,符合「只經過各座橋一次」的規則;如果一個節點有奇數條線聚集,則不符合「只經過各座橋一次」的規則(圖12B)。因此,奇數條線聚集的節點必須是0或2個,若是2個,則其中一個節點作為起點,另一個作為終點。因為柯尼斯堡圖解上的4個節點,全都是奇數條線聚集,所以「柯尼斯堡七橋」無法讓人在只經過各座橋一次的前提下,走遍7座古橋。
圖12.(A)柯尼斯堡七橋問題的圖解說明(圖片來源)
圖12.(B)柯尼斯堡七橋問題的圖解說明(圖片來源)
由上述可知,導遊手上的城市導覽地圖,將所有景點以及地鐵路線無關的細節,其餘不相關的資訊全都隱藏起來,這就是整座城市的「抽象化」表現。導遊謎題與騎士之旅,都是由指定的起點前往指定的終點,途中經過其他的節點,而且只經過一次,透過「模式比對與通化」,我們能判定它們是同一類的問題,其實,電腦科學家將這種路線的圖解,稱為「漢密頓循環」(Hamiltonian cycle)。
綜合上述,計算思考不是電腦思考的方式,而是人類讓電腦完成任務時,所必須做的各種思考方法。計算思考是由許多不同的技巧所構成,電腦科學家常將這些豐富有用的技巧,以相互連結的方式,靈活地組合起來解決問題;最終,電腦科學家能以這些技巧為基礎,創造出以機器為基礎的解決方案。當演算法變為程式時,我們的生活、工作和遊戲方式都會發生改變,尤其是在發展「人工智慧」時,電腦科學家已逐漸能寫出讓機器進行計算思考的程式。至於如何運用計算思考,讓數學魔術萬無一失?人類的觀看能力來自於我們能在影像中找到邊界,那麼電腦要如何「觀看」到邊界呢?如何藉助演算法及電子設備,將科學以及數學,轉變為拯救生命的醫療科技?這些都有待您進一步的閱讀與思考!
悠遊卡
王嘉陵 圖一 揭開悠遊卡的神秘面紗~悠遊卡內含一個小晶片,感應天線
圍繞在卡片四周,圖左為一般市售悠遊卡,圖右為悠遊卡的透明圖。 圖二 悠遊卡發行量已超過500萬張,
發行速度為全球第二 圖三 台北縣市聯營公車都可使用悠遊卡,
圖為公車上裝設的悠遊卡驗票機 什麼是智慧卡 悠遊卡是一種智慧卡, 智慧卡 (Smart Card)也稱為IC 卡(Integrated Circuit Card),是將專用的晶片鑲嵌於 塑膠卡片中,以進行資料儲存或運算處 理。隨著科技的發展,智慧卡技術也更 臻成熟,並在交通旅遊、身份辨識、出 勤管理、金融消費、醫療衛生等各方面 獲得廣泛的應用。
悠遊卡的誕生 台北市過去的交通票證是各自獨 立的,搭公車用公車儲值卡,搭捷運則 要用捷運儲值卡,停車時又用另外一種 繳費紙卡,彼此並不能互相通用,對民 眾非常不方便。台北市政府為了整合大 台北地區的交通票證,徵求民間機構共 同推動交通IC 票卡,民國91 年9 月30日,全國第一張大型交通IC 智慧卡, 於是在台北誕生。 截至今天為止,悠遊卡在短短的 時間內,發卡量已突破500萬張,發行 速度僅次鄰近的新加坡,是全球第二 名;而若以發行數量來看,悠遊卡在全 球各發行交通IC 票卡的城市中,位居 第六名,僅次於漢城、上海、香港、東 京、新加坡。
解構悠遊卡 悠遊卡屬於非接觸式IC 智慧卡, 內含一個電子晶片,大約只有一隻蒼蠅 的大小,這個晶片就如同是悠遊卡的心 臟,所有資料的管理與運算,都在這裡 進行與完成;感應線圈則圍繞在卡片四 周。持卡人以「非接觸」的感應方式, 於0.4 秒內完成資料的傳輸運算與交 易,因此無需將卡片從皮夾或口袋中拿 出,不分正反面,都能迅速完成感應, 通行無阻。 悠遊卡的外觀看起來與一般塑膠卡 片無異,但其中大有學問,悠遊卡厚度 雖然只有0.76 公釐,但可細分為五層, 其中中間層含微晶片與感應天線,其外 兩層為印刷層,最外還有兩層護膜。 悠遊卡不但在使用上便捷外,還可不斷重覆加值使用,使用次數高達 100,000次以上。與用完就必須丟棄的 磁卡相比,更具有環保的價值,並具有 多領域整合及防偽的功能。
驚天動地的0.4 秒 別小看悠遊卡感應所需的「0 . 4 秒」,在這短短0.4 秒間,可發生不少 事情。首先當卡片接近讀卡設備的有效 距離(大約10 公分)時,讀卡設備的 天線會充滿了磁場,這種磁場是一種交 流磁場,卡片的天線感應到讀卡設備的 磁場後立刻充滿能量,此一能量足以應 付接下來卡片與讀卡機間進行的驗證與 資料傳遞。 在雙方資料互相傳遞前,必須先 經過一場科技的「對話」,來驗證彼此 的身份。首先卡片先向讀卡設備發出一 訊息,設備接獲訊息後,予以回覆並再 丟一個訊息給卡片,要卡片「回答」, 像這樣經過三次反覆來回的對話後,設 備與卡片才完成驗證。完成驗證後,讀 卡設備裡的程式則會將這趟交易所花費 的金額等資料,紀錄在卡片中,進行資 料交換與扣款。
小晶片,大智慧 悠遊卡內的晶片雖然只有蒼蠅般大小,記憶體卻有1KB 。目前悠遊卡 在台北的應用範圍僅止於交通領域中的 捷運、公車與停車場,但其實卡片中的 記憶區塊仍有相當大的空間,可以作多 方面的應用。在國外,非接觸式智慧卡 除了各種交通領域外,更使用於校園、 大樓保全、公共電話、門票、便利商 店、速食店、自動販賣機、訂票系統, 甚至與信用卡結合等等,超過100種的 使用範圍,將智慧卡的潛力作最大的發 揮,更帶給使用者無限的便利。 悠遊卡近年來也努力擴展使用範 圍,在交通方面,即將試辦計程車以悠 遊卡付費、路邊停車也可使用悠遊卡 等;此外,與企業員工證結合,使員工 證變「聰明」了,集合交通、差勤紀 錄、門禁管理功能於一身;甚至與信用 卡結合,發行悠遊卡聯名卡,使用範圍 甚至可擴大到小額消費,到便利商店、 速食店、加油站等,都可以用。 悠遊卡也計畫走入校園,最近正 在進行一項學生證結合悠遊卡的試辦計 畫,參與的學校包括私立復興中小學、 東門國小、育成高中、大同高中,就是 將學生證和悠遊卡結合在一起。卡面的 正面有各校的校徽、學生的照片,背面 則是悠遊卡。這張二合一的卡片功能相 當廣泛,學生從出家門搭車,用悠遊卡 付費,到了學校,在校門口的刷卡機感 應,就可紀錄出缺勤;若要到圖書館借書,這張卡片就是借書證;肚子餓了到福利社買麵包,也可用這張卡片內的電子錢包付費。一顆小小的晶片,可發揮極大的智慧。
悠遊卡的未來 悠遊卡的晶片除了放入現在所通 用的塑膠卡片中,更可放入其他與大家 生活息息相關的物品內。手錶、鑰匙 圈、手機等等,都將會是悠遊卡未來的 新面貌,大家可以將悠遊卡更方便地攜 帶在身上,輕鬆地到各個地方悠遊消 費。發行悠遊卡的台北智慧卡公司目前 正計畫發行一款手錶,即是將悠遊卡所 使用的晶片放置入手錶中,搭車時只要 以手錶在讀卡機前感應一下,即可扣款 付費。 此外,日本發行交通IC卡的Suica 交通卡(又稱為「西瓜卡」)已計畫在 今年下半年試辦以手機搭車付費, Sony 與DoCoMo 電話公司合資成立 FeliCa Network公司,計劃二年內發行 千萬支可小額消費手機。未來晶片卡是 不是還以卡片的型式呈現在民眾的面 前,恐怕要打上一個大大的問號,只要 你想的到的,手錶、手機、耳環、項 鍊、MP3等,都可能是「新一代」悠遊 卡所展現的不同面貌。 國外的專家預估未來五年,將是 世界各地開始蓬勃發展IC 智慧卡的時 期,我們的悠遊卡也在此時,準備向更 高更遠的天際遨翔。請您握緊手上的悠 遊卡,因為它將帶您上山下海,邁向更 快速便捷的生活。 圖四 以悠遊卡通過捷運閘門,不必分正反面,也不須插入票孔
,甚至不必拿出卡片,在10 公分的感應距離內,0.4 秒即可完成扣款
圖五 停車時以悠遊卡付費,可省去排隊繳停車費的麻煩