基于計算思維培養的離散數學教學探討

摘 要 計算思維是是當前計算機教育中重點研究的課題，對計算機專業的人才培養提出了更高要求。針對如何培養學生計算思維的問題，本文主要探討在離散數學的教學過程中，通過案例的巧妙設置，將抽象和自動化這兩個核心思想貫穿于教學中。

關鍵詞 計算思維 離散數學 案例抽象

中圖分類號：G424 文獻標識碼：A

Discrete Mathematics Teaching Based on

Computational Thinking Training

YANG Haiqiong， WANG Maoji

（Ningbo Dahongying University， Ningbo， Zhejiang 315175）

Abstract Computational thinking is the key research topic in current computer education， put forward higher requirements of personnel training for computer professionals. On how to develop students' computational thinking problem， this paper focuses on the teaching process of discrete mathematics， through clever settings of cases， make abstraction and automation these two core ideas throughout the teaching.

Key words computational thinking； discrete mathematics； case abstract

計算思維（Computational Thinking）是由美國卡內基·梅隆大學周以真（Jeannette M. Wing）教授于2006年3月在《Communications of the ACM》雜志上首次提出的，其定義是：運用計算機科學的基礎概念進行問題求解、系統設計以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。周以真教授認為，計算思維不僅僅是計算科學家的事情，而是每個人必備的基本能力。他認為，每個孩子在平日中培養解析能力時，不僅僅要學會閱讀、寫作和算術（Reading， Writing， and Arithmetic——3R），還要掌握計算思維。

計算思維的概念一經提出就引起了國內外教育界和科學界的廣泛關注。美國計算機協會（ACM）2008年公布對CC2001（CS2001）進行的中期審查報告（草案）中，就明確將“計算思維”與“計算機導論”課程綁定在一起，明確要求該課程講授計算思維的本質。另外，計算思維直接促成美國國家科學基金會（NSF）重大基金資助計劃CDI的產生，CDI計劃旨在使用計算思維促進美國自然科學和工程技術領域產生革命性的成果。

數據結構、編譯原理、操作系統、數據庫原理等專業課程的學習都是建立在離散數學的基礎之上，因此，離散數學在計算機專業教學中起著舉足輕重的作用，是計算機專業的核心基礎課程。并且此課程在學生抽象思維能力和邏輯思維能力的培養過程中有著重要作用。此文主要在討論通過案例的巧妙設置，加強學生計算思維能力的培養。

1 計算思維的本質和離散數學的關系

我們知道，計算思維最本質的內容是抽象化和自動化，其特點是形式化、程序化和機械化。當一個人具備了技術思維能力時，具體表現為以下四點：對于具體問題，能理解其哪些方面是可計算的；能夠對計算工具或技術與需要解決的問題之間的匹配程度進行評估，能夠將計算工具和技術用于解決新的問題；能夠識別出使用新的計算方式的機會；能夠在任何領域應用諸如分而治之等計算策略。因此計算思維的結論應該是構造性的、可操作性的或者是能行的。這和計算科學的根本問題即什么能被有效地自動進行（對象的能行性問題）是相一致的。因為連續對象（即非離散對象）是很難進行“能行”處理的，所以幾乎所有關于“能行性”的問題，都是處理離散對象的。“能行性”作為計算機學科的根本問題，直接導致了計算機本身的結構和處理對象都是離散型，并且許多連續對象都要經過離散后才能被計算機處理。所以，我們說，計算機科學與技術本質上是一門離散數學技術。

以離散數學為課程依托，培養學生的計算思維，并引導學生運用計算思維來解決學習中各種問題，這是值得筆者深思的。

2 在教學中嵌入計算思維的思想

以往的學習中，學生普遍感覺離散數學的概念多，內容雜，學習不得要領。基于此，我們嘗試在教學過程中提煉計算思維的思想，即什么是可計算的？從而揭開離散數學課程的本質。限于篇幅，僅舉兩例說明如何在教學中結合計算思維展開教學。

在講授命題邏輯時，我們通過引入實例如設計一個符合如下要求的室內照明控制線路：在房間的門外、門內及床頭分別裝有控制同一個電燈F的3個開關A、B、C。當且僅當一個開關的搬鍵向上或3個開關的搬鍵都向上時電燈亮。從計算思維的角度看，可以將決定該題的邏輯思維過程抽象為符號演算，涉及命題邏輯中的聯結詞、真值表、主析（合）取范式、等值演算等內容。即將開關向上符號化為1，向下符號化為0，F燈亮符號化為1，燈滅符號化為0，借助命題邏輯的內容，可以將該表進一步抽象化為F的邏輯表達式。

在講授歐拉圖和哈密爾頓圖時，我們也可以將計算思維融入其中。具體的，可以從圖論的起源——哥尼斯堡七橋問題談起。歐拉當時研究七橋問題時將橋的形狀、長度、寬度等因素都舍去，用一條邊表示橋，用點表示與橋連接的地點，從而構建了無向圖模型。接著，在講述歐拉當時如何思考的基礎上總結出兩條判定定理。最后讓學生通過玩一筆畫游戲深刻領會如何判定一個圖中是否有歐拉圖和歐拉通路。對于哈密爾頓圖同樣也是如此，從周游世界問題開始，引導學生通過思考抽象出該問題的本質，然后引出判定哈密爾頓圖的必要條件和充分條件。通過比較定義和判定條件的不同，對這兩個知識點進行概括總結，單詞接龍是一個很好的例子。規則是假設有多張卡片，每張卡片上都寫著一個英文單詞，現在要把這些卡片按照一定的順序連成串。要求每張卡片（第一張卡片可以除外）上的單詞的首字母恰好是前一張卡片上的單詞的尾字母，并且每張卡片只能用一次（不區分大小寫）。對此問題，學生可能會給出兩種抽象模型。第一種方法是很自然的，將每個單詞作為一個頂點，兩個單詞之間存在一條邊當且僅當前一個單詞的末字母與后一個單詞的首字母相同。這樣單詞接龍問題就轉化為尋找哈密頓通路的問題。第二種方法是將所有的英文字母看作26個節點，每個單詞看作一條有向邊，有向邊的始點是單詞的首字母，終點是單詞的尾字母。這樣單詞接龍問題就轉化為尋找歐拉路徑的問題。對比這兩種方法，第一種方法是NP難問題，第二種方法的復雜度為多項式時間。顯然第二種是更好的方法。通過這個例子，引導學生對具體問題進行抽象，并對比各種解決方法的可計算性和復雜性，從而有效訓練了學生的計算思維。

事實上，在離散數學教學中，最本質的內容是抽象和自動化這兩點，幾乎每個知識點都涉及這兩點的內容。如何將知識點用淺顯易懂的方式傳遞給學生成為教師的使命。筆者認為通過案例將計算思維的本質傳遞給學生就是一個很好的方法。

3 結語

在計算機專業課程的學習中，離散數學是一門難啃的骨頭。然而計算思維的提出給我們提供了一種改革離散數學教學內容和教學模式的新思路。在離散數學教學中結合計算思維，需要任課教師在教學實踐中不斷探索，總結經驗，將課程的本質呈現給學生，有效提高學生的邏輯思維、計算思維和創新思維等能力。

參考文獻

[1] Jeannette M.Wing. Computational Thinking[J].Communications of the ACM，2006.49（3）：33-35.

[2] CS2001 Interim Review [EB/OL].http：//wiki.acm.org/cs2001/index.php？ title=main_page，2008.

[3] 牟琴，譚良.計算思維的研究及其發展[J].計算機科學，2011.38（3）：10-15.

[4] 耿素云等.離散數學（第四版）[M].清華大學出版社，2011.