03. 有限狀態自動機

https://teachinglondoncomputing.org/resources/inspiring-unplugged-classroom-activities/hexahexaflexagon-automata-activity/

Computer Science activities with a sense of fun: Computational Thinking: HexaHexaFlexagon Automata V1.0, 21 April 2015

Created by Paul Curzon, Queen Mary, University of London for Teaching London Computing: http://teachinglondoncomputing.org

本教材以創用CC 3.0 姓名標示-非商業性-相同方式分享釋出(creative commons 3.0 BY-NC-SA) https://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh_TW

"六角變形體 - HexaHexaFlexagon"自動機探索活動

遵循一個設計好的演算法，將一條彩色的紙帶折疊、黏貼，製造出一個六角變形體。

隨著你重覆折疊、展開它的過程中，你會驚喜地發現這個變形體一直在變換它的顏色。

而為了探索它運作的原理，會需要一張「地圖(map)」來協助你的推理。

一個圖形就類似一張水管圖，上面有圓圈（節點）代表了不同的地點，用線條（邊）連接這些圓圈，它代表了你在折疊、展開六角變形體(Flexagon)的時候，圓圈隨之移動的方式。

這種圖形就像我們之前學習過的「有限狀態自動機」概念圖，圖形中的節點代表Flexagon的狀態（顏色）、邊則是顯示了可以在狀態切換時採取了什麼樣的動作。有限狀態自動機的概念，是運算思維中很重要的一個工具，它也是描述電腦系統的一個關鍵的方式。

在這個單元可以學習到:

• 圖形
• 有限狀態自動機
• 規格specification
• 運算思維
• 抽象化
• 資料表示
• 一般化
• 模式匹配
• 評價與邏輯思維

如何製作HexaHexaFlexagon:

1. 將以下PDF檔的內容印給學生，一人一張。（彩色、黑白皆可）

2. 在背面（沒有顏色那面）塗上膠水，沿著正中間的直線對折、緊密粘合。(或是從正中間切開，再合併粘粘)

3. 將標示FLAP1的三角形如圖放罝，下方的黃色三角形保持不動，開始沿著黑線「折、並捲動」這個紙條，讓藍色相鄰、紅色相鄰…依此類推，最後會留下紅色單獨一個三角形。

4. 逆時針旋轉，讓FLAP1的方向如圖所示。接著繼續沿著黑線折紙，讓黃色的三角形逐步相鄰。

5.一直折到剩下藍、藍、紅三個三角形

6.沿兩個藍色三角形中間的那條線對折，此時會看到FLAP2的三角形，把它塞到六邊形的下方去。

7.反折FLAP1，讓寫有FLAP1跟FLAP2的兩個三角形重疊，接著拿出膠水塗在FLAP2字樣上，將兩個重疊的三角形黏在一起。到此則大功告成，你會看到這樣的六邊形。

HexaHexaFlexagon要怎麼玩:

1. 一個Flexagon有六種不同顏色的面，透過壓與捏的動作，可以輕易地將它翻面，為了更方便地辨認顏色，我們用圍繞Flexagon中心點的六個數字來作為每一個面的編號，這樣會比較容易記憶與推導。以上面這個Flexagon來說，起始面的編號為「3」。

2. 玩Flexagon的手指動作有兩個，一個叫「壓平（Flatten）」、一個叫「捏（Pinch）」。「捏」的動作必須用在一條線的上、下都有同一個英文字母的時候，用右手的食指和大拇指往下作捏的動作（在折紙的術語中稱為山形）。捏下去之後，Flexagon的正中間會出現一個Ｙ形狀的空隙，用左手的大拇指頂住Ｙ的交會點、往左邊扳動，這個Flexagon就會順勢被打開，接著繼續往後翻，直到它整個被攤平為止。

3. 以剛剛完成的Flexagon為例，它有兩種翻面的選擇：捏a或捏b。如果捏的是a，將會翻到正中間的編號為「2」的那一面；如果捏的是b，則會翻到正中間編號為「4」的那一面。

4. 正中間的編號總共從「0」到「8」，總共9個面。學生的任務有二：

(1) 想辦法先翻出所有的面。

(2) 依照老師的指令，翻到指令的編號面。

運算思維提示:

如果學生是隨機地嘗試翻面，不去注意規則的話，他們會發現有些編號非常容易找到（也許會一直在編號1、2、3之間不斷循環），編號7、8、0這三面卻一直翻不出來。

一個偉大的探險家不只是在新發現的大陸上四處閒逛，看河看山看瀑布，他們會在離去前繪製好那裡的地圖，讓以後到達的人也能遵循地圖的指示到達指定的地點。想要翻出所有編號的面，我們也同樣需要一張地圖。地圖是整個世界被我們抽象化之後的結果，上面只標示出我們感興趣的地理特徵，像是河流、瀑布、山脈、城市、導路…等。隨著需求的不同，有時候我們會在不同種類的地圖上刪去不重要的其他細節，像是鐵路圖上也許就會忽略掉河流的部份。

想要完整地探索一個Flexagon，最好的地圖表示法被電腦科學家稱為圖形（graph）。跟數學家所說的圖形不同，這裡的圖形只有包括圓圈（節點）與連接線（邊）。節點代表了要造訪的地方，而邊則代表了要用什麼方式才能到達那裡。像是捷運路線圖、公車路線圖就是一種圖形的例子。這些圖形將站與站之間的距離省略掉不表示，讓我們能夠把焦點放在如何走才能到達目標地。

用graph來表示Flexagon，節點內的編號就代表圍繞正中心的那六個數字，「捏」了那個一英文字母可以到達下一個編號，我們用一個箭頭、上方標記英文字母的方式來表示。舉例來說，下圖代表「捏」了a之後，就可以將編號3的面翻到編號2。捷運路線圖的邊是沒有箭頭的，代表它的路線是雙向通行，像下圖這種單向通行的圖形，我們稱為「有向圖（directed graph）」。

試圖用有向圖的方式，找到一個編號的面，也就是我們透過捏什麼英文字母，就能夠到達那一個編號的面。透過一邊翻面一邊加上節點與邊的方式，就能逐一地把所有的面都找出來。為什麼要選擇使用編號的方式來標記這些面，而不是直接用顏色就好了呢？那是因為有些顏色的面會出現不只一次，若沒有編號來協助辨認，使用者很快地就會被搞混了。

畫出來的圖，有沒有可能走到死巷而找不到往下走的路？如果發生這種事，就沿著箭頭退回上一步，再找別的路前進吧。Flexagon因為是經過設計的，所以不會有走到死巷又無法回頭的問題，而且總是有機會再回到起點 （編號3的那一面）。

每個人畫出來的圖不見得一樣，當你畫完圖形之後，編排那些節點與邊的位置，試圖讓它更美觀一些。

用圖形來描述一個機器的運作，表示它的「地點」與「移動方式」，我們可以稱為「有限狀態機器（finite state machines）」或是「有限狀態自動機（finite state automata）」。有限狀態機器的節點就是它的「狀態」，而邊則是它的「轉換方式」。我們用英文字母表示一個狀態轉換到另一個狀態的可能方式，像是在上面的圖，Flexagon從編號3到編號2的狀態，使用的轉換是捏了a這條線，所以我們就把a標示在箭頭的上方。

一個有限狀態機器，必須有一個操作的起始點，我們稱為「初始狀態」，用一個雙圈來表示。所以依照範例中的Flexagon，編號3是一開始的第一個面，我們可以把圖改成這個樣子：

有限狀態機器就像一支電腦程式。它描述了可能的操作方式，以及對應的操作結果。從初始狀態開始，隨著操作的步驟，用箭頭與字母來表示轉換的流程，然後變成下一個狀態。對於運算思維的發展來說，有限狀態機器是一個很重要的工具。設計師在設計一個工具或是一支程式的時候時常會被用到，用來提供一個操作動作的規格（specification），使用者只能按照設計出來的介面、使用設計出來的功能來進行操作，不可能開放整個系統讓人家隨便玩。

畫出Flexagon的有限狀態機器圖形後，就能夠協助我們找到平時很難翻到的編號7、8、0這三個面，可以說我們為這個Flexagon建立了一個良好的運算模型，只要遵循圖形上箭頭的方向就能到達想要的地方。現在很多的物品被賦予更多的功能，像是電子錶，以前也許只提供了顯示時間、日期的功能，現在可能還要加上鬧鈴、碼錶甚至世界時鐘這些東西。一個使用者如果不詳讀說明書，光是要找到如何設定新的日期與時間，就要在錶上的好幾個按鈕之間尋找、重覆操作。一個東西提供了一堆功能，卻讓使用者在尋找功能時有如陷入迷宮一般，那這就不是一個良好的設計。

最後我們可能會想要知道，如何製作一個自己的Flexagon？我可以不要只是在不同的面顯示顏色，而是用圖案來代替嗎？設計的方式同樣牽涉到了演算法的思維（algorithmic thinking），只要我們理解了Flexagon的演算法之後，照著步驟一步步執行下去，就能設計出一個獨一無二的Flexagon，這個概念稱為模式匹配（pattern matching）與一般化（generalisation）。

最後，到底這個Flexagon的範例，要如何用正確的圖形來表示翻面的路徑呢？底下提供一種畫法，也許你繪製出來的圖長相不盡相同，但仔細檢查一下，節點跟邊的組合其實仍然是一模一樣的。

這個單元所提到的圖形概念，與旅遊嚮導、勇者之旅也有相關之處

練習題：

下載下方PDF檔，請學生裁切後再製作一個新的六角變形體，並試著繪製出翻折的有向圖。

(註：一個檔案有四個一樣的圖，可以裁切給四個學生使用，如果擔心學生弄壞了它的作品，也可以一個人擁有一份)

延伸資源：提供更多FLEXAGON模版的網站

http://flexagon.net/#

繪製圖形輔助程式:

http://163.22.72.196/html5/html5_graph/html5_graph.html

http://163.19.104.4/cstt/html5_graph/graph.html

使用輔助程式繪製六角變形體的破解圖形，並輸出為PNG檔。操作方式為「按一下」、「長按」與「拖曳」。