新工科教育中離散數學教學改革探討

唐新亭, 張小峰, 楊洪勇

(魯東大學 信息與電氣工程學院, 山東 煙臺 264025)

新工科是“卓越工程師教育培養計劃”的升級版,要面向產業界、面向世界、面向未來,深化工程教育改革、加快建設新工科,促進我國工程教育加速進入世界第一方陣。從理念引領、結構優化、模式創新、質量保障、分類發展5個方面持續深化工程教育改革。在離散數學的授課與學習過程中存在明顯的誤區,認為構成計算機科學的核心是數據結構、算法和程序設計,忽略了離散數學在思維培養和實踐能力訓練中的重要性,片面強調離散數學的理論性。在一些高校進行培養方案的設計與調整時,也明顯存在壓縮離散數學課時的問題。離散數學不僅對于思維培養有很大作用,而且對于應用實踐能力培養也有非常關鍵的作用。

1 目前離散數學授課中存在的問題

和其他工程數學一樣,離散數學的內容常常因書而異、因學校而異。經過多年的實踐,對于離散數學的授課內容有了統一的認識。左孝凌老師指出,離散數學的授課內容包括5部分:數理邏輯、集合論、代數系統與布爾代數、圖論、形式語言與自動機[1]。然而,隨著計算機科學的快速發展,許多高校在設計離散數學的教學內容時,對上述內容有所取舍,并結合不同高校的專業發展特色,增加了新的內容。例如,北京大學屈婉玲教授為主的離散數學教學團隊,對代數系統內容進行壓縮,增加了組合數學的知識,對基本的計數原則、遞推式進行了介紹；河北地質大學對離散數學的授課內容進行改革,將離散數學分為3個學期上課,分別介紹數理邏輯與集合論、圖論和代數系統。

在課時的設計上,大部分高校安排的課時是72左右,但部分地方高校為了突出應用型人才培養,對離散數學的課時進行擠壓,有部分高校離散數學的課時甚至被壓縮到了32課時,這給離散數學的教學工作帶來了很大的困難。

在教學模式上,由于離散數學的特點,許多教師采取了以教師為主、滿堂灌的傳統教學模式,導致了學生在學習離散數學時,感受的只是課程的枯燥、乏味,甚至導致學生失去了學習后續專業課程的動力與興趣,這對專業學習非常不利。

2 面向新工科教育和應用實踐能力進行改革

我校是山東省內一所普通的二本院校,具有明顯的師范高校特色,2007年更名后,開始朝著綜合型、應用型大學轉型發展。

2.1 學習興趣的培養

一般而言,數學類的課程比較枯燥,如何提高學生在學習離散數學時的學習興趣,是一門學問,更是一門教學藝術。在授課過程中,借助離散數學發展史和相關學科發展的前沿知識提高學生的學習興趣,可收到較好的效果[2]。

(1) 在數理邏輯部分,介紹德摩根(Augustus de Morgan,1806—1871)對符號化推理演算的貢獻,介紹德摩根與阿達(Augusta Ada King,1815—1852,英國著名詩人拜倫的女兒)的師生關系。在消解律部分,圍繞人工智能學科的產生、發展,介紹人工智能的發展歷程,從最初的感知機,引進到神經網絡,直至最新的深度計算,讓學生對學科最前沿的知識有所了解。

(2) 在布爾代數部分,介紹數學史上的兩個天才人物伽略瓦(évariste Galois,1811—1832)和阿貝爾(Niels Henrik Abel,1802-1829),讓學生在敬仰他們取得的數學成就的同時,對數學產生興趣。

(3) 在集合論部分,介紹德國數學家康托爾(Georg Ferdinand Ludwig Philipp Cantor,1845—1918)以及馮·諾伊曼(John von Neumann,1903—1957)對集合論的貢獻,介紹羅素(Bertrand Russell,1872-1970)在集合論的公理化上的貢獻。在德摩根律部分,介紹布爾(George Boole,1815—1864)對德摩根律的貢獻,同時對問題進行進一步擴展,介紹香農(Claude Elwood Shannon,1916—2001)利用開關電路實現布爾代數,同時介紹圖靈(Alan Mathison Turing,1912—1954)設計的計算模型,為電子計算機的最終實現奠定了必要的基礎。

(4) 在圖論部分,介紹偉大數學家歐拉(Leonhard Euler,1707—1783)的傳奇人生,同時也介紹對推動四色定理證明而努力奮斗的德摩根、哈密爾頓(William Rowan Hamilton,1805—1865)、凱萊(Arthur Cayley,1821—1895)、肯普(Alfred Kempe,1849—1922)、海伍德(Percy John Heawood,1861—1955)等系列數學家。在樹部分,圍繞哈夫曼樹,介紹費諾(Robert Fano,1917—2016)與哈夫曼(David A. Huffman,1925—1999)在數據壓縮、編碼等領域的貢獻。

通過介紹離散數學的發展史和計算機的學科前沿知識,可以讓學生了解相關知識點的由來、發展,同時了解相關學者為了問題的解決而奮斗的經歷,這對提高學生的學習興趣、培養學生的創新意識非常有益。

2.2 思維訓練

離散數學不僅是數據結構、算法分析與設計等后續專業課程的基礎,而且在計算機相關專業的人才培養過程中對思維的訓練起著非常關鍵的作用,授課教師在教學過程中應該注重并強化這一點[3-5]。以德摩根律的證明來說明如何在教學過程中對學生的思維進行訓練。

德摩根律是描述集合運算間的關系,可以表述為:

在證明這2個子問題時,需要根據集合運算的性質,將一個集合從一種表現形式轉換為另一種形式。

如果授課過程中按照上述思路對問題進行分析,可以消除學生對于離散數學的恐懼心理,對后續專業課程的學習,很有幫助。

2.3 應用實踐能力培養

計算機等相關專業的一個特點是對應用實踐能力要求較高,所有的課程都應為培養學生的應用實踐能力服務。在離散數學的授課過程中,將提高學生的程序設計能力作為教學的落腳點,通過設計教學案例,將離散數學的學習與學生程序設計能力的提高結合起來,既提高了學生的學習興趣,又讓學生體會到了離散數學對后續專業課程的重要性。通過幾個簡單的例子加以說明。

(1) 張三說李四在說謊,李四說王五在說謊,王五說張三李四都在說謊[6]。這是命題邏輯中的一個非常經典的問題,一般結合主析取范式進行求解,并結合“等價”這個聯結詞的特性進行分析。在授課過程中,對該問題的求解分為3個不同的層次:(a)讓學生自行分析,培養他們思考和解決問題的方法；(b)通過主析取范式,將命題邏輯與后續課程數字電路的邏輯代數打通,方便學生推導；(c)通過編程實現,進一步提高學生的編程能力,可以將上述問題設計為如下的程序:

#include

int main()

{

int a,b,c;

for(a=0;a<=1;a++){

for(b=0;b<=1;b++){

for(c=0;c<=1;c++){

if(((a&&!b)||(!a&& b))&&((!b&&c)||(b&&!c))&&((c&&a+b!=0)||(!c&& a+b==0))){

printf(″張三%s說謊 ″,a?″在″:″沒有″);

printf(″李四%s說謊 ″,b?″在″:″沒有″);

printf(″王五%s說謊 ″,c?″在″:″沒有″);

}

}

}

}

return 0;

}

(2) 關系的復合運算滿足結合律。關系復合運算的這一性質屬于純數學范疇,學生在學習過程中由于不知道結合律的應用,因而普遍比較頭疼。在授課過程中,將復合運算的結合律與矩陣的連乘結合起來。由于關系的復合可以用矩陣的乘法進行表示,因而,關系的復合運算滿足結合律等價于矩陣的乘法運算滿足復合律。進一步,利用矩陣乘法運算的復合律,可以計算矩陣乘法運算的最優次序[7-8]。例如,對于3個矩陣來說,設矩陣A1的維數是5×10,矩陣A2的維數是10×100,矩陣A3的維數是100×20,則計算(A1A2)A3和A1(A2A3)所需要的乘法次數分別為15 000次和21 000次。通過這樣的分析和要求,可以將學生的注意力從純粹的數學性質證明轉移到算法設計上,此時可以要求學生課下通過自學去編寫相應的程序實現,可以采用遞歸、動態規劃和備忘錄算法分別實現。

(3) 鴿籠原理。鴿籠原理是組合數學上的一個經典結論,在離散數學中的最短路徑、關系的閉包運算中需要用到。然而,許多教師在授課時,僅僅是把鴿籠原理和相關應用進行簡單的介紹,不再進行深入分析。在授課過程中,除了介紹相關原理外,更注意鴿籠原理與程序設計技巧的相關結合。例如,授課過程中引入下面的例子:給定n個實數,求這n個實數在數軸上相鄰2個數之間的最大差值,設計解最大間隙問題的線性時間算法。該問題其實并不復雜,最簡單的思路是將給定的數進行排序,然后將排序后的數組掃描一下,得到2個數之間的最大間隙。問題復雜在要求的時間復雜度上,要求在O(1)時間內完成,而現在最快的排序算法時間復雜度為O(nlogn),因而該思路不滿足題目的要求。授課中,將鴿籠原理的思想與程序設計結合起來,這就需要設計相應的鴿子和籠子。假設輸入了n個數字,除去最大和最小2個元素外,剩余n-2個元素,如果將這n-2個數字分配到n-1個區間里,根據鴿籠原理,則至少有一個區間是空的。而分配在區間內部2個元素的差一定小于區間的寬度,因此,最大間隙是一定存在的。可以通過掃描空區間左邊非空區間的最大值和右邊非空區間的最小值的差得到最大間隙。介紹完實現思路后,具體的程序可以讓學生去實現。通過這樣的訓練,學生不僅掌握了鴿籠原理,還提高了程序設計的技巧。

(4) 容斥原理。容斥原理是計數問題中的典型問題,授課過程中大部分教師將重點放在容斥原理的應用上[9-12]。在授課過程中,除了考慮容斥原理的應用外,可將更多的注意力放在容斥原理的證明上。在容斥原理的證明過程中,需要用到數學歸納法。授課過程中,對數學歸納法的機理進行深入分析,將數學歸納法與遞歸算法進行對比、分析,發現數學歸納法與遞歸算法非常相似。基于這樣的分析,可以有效解決學生在學習遞歸算法時的困惑。如果學生容易接受,可以進一步分析遞歸算法的缺點,從而引出動態規劃算法和備忘錄算法,這可以讓學生課后自行學習。

3 結語

對新工科教育中面向實踐能力培養的離散數學授課模式進行了介紹,通過實踐取得了較好的效果。學生在近3年的程序設計競賽、ACM程序設計大賽中,均取得了較好的成績。在后續的教學工作中,教學團隊將進一步挖掘離散數學的相關知識點與程序設計的結合,讓學生在學習離散數學這門課程的同時,盡可能提高程序設計能力和解決問題的思路。

參考文獻(References)

[1] 左孝凌.離散數學的形成、發展及其在計算機科學中的作用與地位[J].自然雜志,1984,7(6):414-417.

[2] 張小峰,趙永升,楊洪勇,等. 離散數學[M]. 北京:清華大學出版社,2016.

[3] 張小峰, 蔡春波, 李秀芳,等.基于程序設計能力培養的離散數學教學改革[J].計算機教育,2015(2):44-47.

[4] 張小峰,李仁璞,鄒海林.面向思維培養的離散數學教學模式[J].計算機教育, 2012(13):72-75.

[5] 李秀芳,張小峰,楊洪勇,等.離散數學知識解析與習題解答[M].北京:清華大學出版社,2017.

[6] 葉青,米春橋,唐波.地方應用型本科院校離散數學研究性教學改革與實踐[J].大學數學, 2016, 32(6):53-57.

[7] 鄧秀勤,李文洲,劉海林,等.基于計算思維能力培養的離散數學課程教學改革探索[J]. 大學數學,2017,33(1):75-79.

[8] 廖偉志,李文敬,王汝涼.基于培養學生計算思維的任務驅動式“離散數學”教學模式研究[J].計算機教育,2009(21):93-95.

[9] 曹建芳,趙青杉,陳立潮,等.面向計算思維能力培養的離散數學教學模式研究[J].高師理科學刊,2014(2):79-81.

[10] 汪榮貴,王曉華,楊娟,等.離散數學及其應用[M].北京:機械工業出版社,2017.

[11] 傅彥,徐潔,吳躍.計算機專業主干課程建設與教學改革[J].電子科技大學學報(社會科學版),2002(4):103-105.

[12] 陳光喜,古天龍.“離散數學”精品課程教學改革實踐[J].桂林電子科技大學學報,2007, 27(4):300-302.

實驗教學示范中心建設