離散數學中的分層次實驗教學研究

摘 要： 從離散數學的實驗教學現狀出發，分析了進行分層次實踐教學的必要性，研究了分層次教學的原則、實驗設計原則、實驗設計思路，實驗設計內容，實驗具體實施和考核方案，最后進行了成果分析。實踐教學證明，在離散數學課程中進行分層次教學有利于培養學生的動手能力和創新精神。

關鍵詞： 實踐教學； 教學原則； 分層次教學； 團隊協作； 實驗體系

中圖分類號：G420 文獻標志碼：A 文章編號：1006-8228（2014）09-73-03

Study on layered experimental teaching in discrete mathematics

Chen Yegang

（School of Computer Engineering， Yangtze Normal University， Fuling， Chongqing 408000， China）

Abstract： Starting from present situation of the \"discrete mathematics\" experimental teaching， the necessity of layered teaching is analyzed. Research teaching principle， the principle of experimental design， experimental design， experimental design， experimental implementation and evaluation scheme are studied. The result analysis is conducted. The practice shows that teaching at different levels can improve students' practical ability and innovative spirit in the \"discrete mathematics\".

Key words： practical teaching； teaching principles； layered teaching； teaching team； experimental system

0 引言

離散數學作為現代數學的重要分支，主要研究離散量的結構及其相互關系[1]。離散數學作為計算機科學與技術專業的核心基礎課程，對于學生知識、能力和綜合素質的培養起到承前啟后的作用。它不但為程序設計語言、數據結構、操作系統、編譯技術、人工智能、數據庫、算法設計與分析等課程的學習提供必須的數學基礎，而且有助于培養學生具有嚴謹的科學研究的作風，提高學生的理論素質和分析和解決問題的能力。

由于離散數學高度抽象、概念多，理論性很強，在大多數的本科教學中崇尚理論教學，基本不開設實驗課，故造成學生學得枯燥，老師教得辛苦，學生解決實際問題能力不高。為了提高學生的動手能力，在教學中加強實踐環節是很有必要的。

本文分析了離散數學課程的教學現狀，對分層次教學的必要性進行了探討，提出了實驗設計的原則、思路和內容，對實驗進行實施，并對實驗教學成果進行了分析。

1 實踐教學現狀

以“服務社會，面向地方”培養應用型本科人才為目標，越來越多的高校在離散數學中增加了實驗教學，并取得了不錯的教學效果，但在教學與實踐的過程也顯現出一些問題。

⑴ 離散數學內容豐富，定義和定理較多，方法性較強，由于內容多且各成一體，讓學生覺得各部分間聯系不大，又由于繁多的定理和定義抽象難懂，增加了記憶的難度。

⑵ 實踐教學方式、方法單調。由于受課時的影響，實踐教學主要是通過實驗課來實現，一學期實驗課時一般在17學時左右，一般實驗課都是驗證性實驗，很少有創新項目。

⑶ 有的高校實驗安排沒有層次感，內容單調和分散，不能滿足不同學生的需求，有些高校開設了分層次實驗教學，把實驗分為驗證型實驗，應用型實驗，綜合型實驗和創新型實驗，但實驗與工程的結合性不強。

⑷ 由于離散數學的學習群體一般是高等院校的學生，其實踐教學未考慮本科和專科學生的接受能力和不同專業的側重點。比如軟件工程專業的離散數學課重點放在圖論、集合與邏輯，而網絡工程專業重點放在代數系統。

⑸ 實驗課成績在該學科期末中所占比例不大，一般占20%左右，因此學生對其重視程度不夠。同時由于信息獲取的渠道較多，因此，考試時學生存在上網抄襲別人勞動成果的情況。

2 開設分層次實驗的必要性

分層教學是面向全體因材施教的一種教學模式，它強調“教師的教要適應學生的學”，“因材施教，分層提高，讓尖子冒出來，使多數邁大步，叫后進生不落伍，達到班級整體優化”。其核心是重視學生的個體差異，使學生體驗成功的喜悅，從而激發學生的學習興趣[2-4]。

為了增強學生畢業后的競爭力與國際接軌，許多高校紛紛設立了不同類型的實驗班、提高班（如“元培班”（北大），“錢學森班”（清華））并為其配備本校的教學名師，優質的教學科研資源（如購買國外數據庫），目的是培養創新型人才。

我校從2010年9月開始招收計算機的服務外包實驗班（安博教育集團與HP集團與我校聯辦），到現在為止已有三屆學生，對入選學生的要求是英語和數學成績必須達到120分（高考成績），為其提供聯合培養、到企業參與核心項目，為每個學生配備一個教師進行全程跟蹤，通過前二屆的學生就業情況看，相對于普通班比，其首次就業率達到90%以上（50%考研）。

實驗班的學生基礎好，學習積極性高，在老師的嚴格要求下，動手能力得到了大幅度提高。針對不同水平的學生情況，本人在離散數學的教學中，為了培養學生的創新能力、動手能力和實踐能力，基于近15年的教學經驗和科研積淀，精心設計了實驗內容并建立了科學的考核機制。

離散數學的實驗設計基于其課程體系，面向實際應用，針對計算機程序設計大賽，在實驗過程讓學生協作工作，讓每個學生的特長得以體現，以培養學生的創新精神和團隊的協作意識。

3 實驗設計

3.1 分層教學的原則[5]

根據個體差異，在實驗設計中按如下原則。

⑴ 水平相近原則：將學習狀況相近，智力水平相同的學生為“同一層”。

⑵ 動態變化原則：分層是動態的，進步的學生“升級”，退步的學生“降級”。

⑶ 化整為零原則：教學內容進行適度合并或者分解，對學生“放”“扶”并重。

⑷ 適度控制原則：學生水平不一，因此教師要善于激勵、引導、精講、反思，做好分類指導。

⑸ 激勵為主原則：對學生的評價以縱向性為主。及時表揚、激勵進步大的學生并調高學生層次，鞭策后退學生，使所有學生隨時都處于最佳的學習狀態。

3.2 實驗設計原則

實驗體系的設計按如下原則。

⑴ 實驗項目是課堂內容的擴展，計算機科學與技術專業中不同的方向其內容應有相應的區別，如我校的軟件工程方向主要重點在集合、圖論和組合數學；網絡工程方向重點在代數系統和數論；物聯網方向主要在邏輯和代數系統。因此，實驗的設計與授課內容相符，可使得學生更好地解決實際問題。

⑵ 結合當前的研究和項目，拓寬學生的視野，將離散數學與程序設計相結合，同時注重算法的分析，設計高效且代價花費小的程序。將教學重點分解成模塊序列，對每個模塊進行一個程序設計項目，如數理邏輯中的合取范式和析取范式作為一個模塊，將真值表、合式公式、范式結合為一個實驗項目。

⑶ 將離散數學的教學與計算機程序設計大賽相結合，藍橋杯和ACM競賽中圖論和搜索算法、網絡流等都與離散數學教學密切相關。

⑷ 補充必要的一些知識，使學生更能品嘗成功的喜悅。

3.3 思路設計

離散數學涵蓋數理邏輯、集合論、代數系統和圖論四大部分，這四大部分相互聯系又各自獨立，根據分層次試驗教學的目的和原則，對軟件工程方向的學生要求從四個部分來闡述試驗設計的思路。

3.3.1 數理邏輯

基礎實驗是根據軟件工程方向的特點，將真值與范式，合式公式、等價證明，永真式，永假式和可滿足式等命題公式用C程序設計語言求解，使學生理解連接詞，掌握真值表和等價證明。提高實驗是利用知名的定理證明器PVS，如使用BDDs（二分決策圖）簡化命題（單詞學習propositional simplification，命題簡化，Propositional Logic命題邏輯），為了效率緩存自動改寫。用戶定義的步驟可以聯合這些原語推理來產生高層的證明策略。在實驗教學方面，要補充定理證明工具的使用和程序驗證理論。

3.3.2 集合論

集合包括并、差、交、補、異或五種運算和計數，在二元關系中笛卡爾積，關系的性質、運算和閉包，以及等價、相容、序關系，它們在數據結構、數據庫和算法分析與設計中具有廣泛的運用，基礎實驗的部分主要掌握Warshall算法，以及自反、對稱、傳遞閉包的編程。提高實驗部分的要求是單向陷門函數的編寫，以及編程實現在簡單文本中的信息檢索。在實驗教學上要補充關系數據庫的相關知識及開發，以及與集合相關的并查集、二項堆和斐波那契堆。

3.3.3 代數系統

代數系統包括半群，群，環，域，格以及布爾代數，基礎實驗部分用C程序判定群，半群，環，域，格等。提高實驗部分，會要求學生熟練使用Maple代數運算軟件，理解代數系統在網絡安全方面的應用。在實驗教學上要補充的是Maple代數運算軟件的使用和DSA算法。

3.3.4 圖論

圖論是一個古老而又運用廣泛的分支，包括傳統的問題，如：最短路徑，最優路徑，關鍵路徑，最小生成樹，哈夫曼樹，歐拉問題，哈密頓回路問題，二分圖，圖的著色問題等，也包括現代的網絡流問題。基礎實驗部分用C編寫最短路徑，最優路徑，關鍵路徑，最小生成樹，哈夫曼樹，歐拉問題，哈密頓回路問題，二分圖，最大匹配和著色。提高實驗部分安排平面圖的判斷，樹在網絡布線和物流方面的運用和最佳網絡流的實驗。在實驗教學上補充特定網絡介數和核數。

3.4 內容設計

離散數學實驗教學按分層次教學要求，將實驗首先分為驗證型實驗，應用型實驗，綜合型實驗和創新型實驗，然后根據不同學生的不同層次，又將每種類型分為基礎實驗和提高實驗兩部分。下面就以圖論為例進行說明。

3.4.1 驗證性實驗

基礎實驗有深度優先搜索算法，廣度優先搜索算法，最小生成樹，最小生成樹算法；提高實驗有關鍵路徑，拓撲排序，最短路徑，圖的著色問題。

3.4.2 應用型實驗

基礎實驗有雙向廣度搜索算法，歐拉回路，哈密爾頓回路，最優路徑；提高實驗有中國郵路問題，貨郎擔貨問題，二部圖的最大匹配。

3.4.3 綜合型實驗

基礎實驗有求圖中任意兩點的最短距離的Floyd算法以及Fleury和Hierholzer算法；提高實驗有有向歐拉圖，有約束容量的中國郵遞員問題，TSP的近似算法。

3.4.4 創新型實驗

基礎實驗有哈弗曼樹，一般圖的最大匹配，最大流最小截集的Ford，Fulkerson，Dinits算法；提高實驗有向圖的中國郵遞員問題，TPS的分支限界法，可靠網絡的設計。

4 實驗實施和考核

由于離散數學的內容設計較為復雜，因此學生不同，分配的實驗不同，其考核方法也不相同，下面僅以應用型實驗中的基礎實驗歐拉回路加以說明。

4.1 設置情景

一位郵遞員從自己所在的郵局去投遞，然后回到郵局，要求他必須經過他所管轄的每條街一次，輸出行程最短的路線圖。

4.2 功能分析

把投遞區的街道用邊表示，街道的長度用權表示，街道的交叉口用點表示，則投遞區構成一個連通無向圖。為了實現上述功能，分三步進行。

Step 1 判定此圖是否是歐拉圖。

Step 2 如果是歐拉圖，用Fleury算法輸出即可。

Step 3 如果不是歐拉圖，用最小對集法構建歐拉圖，再用Step 2方法輸出。

4.3 模塊算法

4.3.1 歐拉圖的判定算法

⑴ 給定一個圖，用并查集判定是否是連通圖，如是轉⑵；

⑵ 分別求出每個節點的度數，若均為偶數，則轉4.3.2算法，否則轉4.3.3算法；

⑶ 輸出此圖不連通。

4.3.2 Fleury算法[6]輸出歐拉回路的算法

任取v0∈V（G），令P0=v0；

設Pi=v0e1v1e2…ei vi已經行遍，按下面方法從中選取ei+1：

⑴ ei+1與vi相關聯；

⑵ 除非無別的邊可供行遍，否則ei+1不應該為Gi=G-{e1，e2，…，ei}中的橋（所謂橋是一條刪除后使連通圖不再連通的邊）；

⑶ 當⑵不能再進行時，算法停止。

4.3.3 最小對集法[2，7，8]添加邊使非歐拉圖變成歐拉圖

其算法如下：

⑴ 求出圖G所有頂點之間的最短路徑和距離；

⑵ 以G的所有奇次頂點為頂點集，做一完備圖，邊上的權為兩端點在原圖G中的最短距離，將此完備圖的加權圖記為G1；

⑶ 求G1的最小權理想匹配M，得到奇次頂點的最佳匹配對；

⑷ 在G中沿配對頂點之間的最短路徑添加重復邊得到歐拉圖G’；

⑸ 利用Fleury算法輸出歐拉圖G’的路徑。

4.3.4 功能實現

數據輸入：

邊數5，點數6

相關聯的點 1 2

1 3

2 5

4 2

3 2

4 5

運行結果：

存在歐拉回路 1，3，2，4，5，2，1

4.3.5 考核方式

為了尊重學生的勞動成果，基礎性實驗由老師評分，評分細則：難度不同的基礎實驗，視完成的情況給分，若完成指定的功能，按對應的標準給分，難度越大，分數愈高；若在完成指定功能的基礎上，還添加擴展功能，有創意，并且成功實現，給與一定的加分；未完成或有錯誤，酌情給分。

對于提高性實驗考核由團隊實現，每個難度不同的課程設計，視完成的情況給分，若完成指定的功能，按對應的標準給分，難度越大，分數愈高；若在完成指定功能的基礎上，還添加擴展功能，有創意，并且成功實現，給與一定的加分；未完成或有錯誤，酌情給分。同學加入一個團隊，其考核通過答辯的方式進行，所有學生作為評委，但須每個團隊通過協商后給出一個分數，取平均分即可。

最后總的實驗成績分數是由基礎實驗占70%，提高實驗占30%而得。

5 成果分析

對學生進行分層次實驗教學，把抽象的理論和復雜的證明化解為解決實際生活的許多問題，使不同層次學生都有收獲，同時讓學生融入團隊，培養其協作精神。這樣的實驗教學對學生參加計算機程序設計大賽也有很好的作用。在2010級，本人所輔導的學生參加ACM競賽獲得重慶市二等獎，2011級參加藍橋杯獲得重慶市兩個一等獎，2012級的學生參加藍橋杯獲得了重慶市高校第一名和一個國家二等獎和兩個國家三等獎，2013年輔導的學生參加藍橋杯獲得重慶市高校第一名。實踐教學證明，在離散數學中進行分層次教學對于提高學生的動手能力和創新能力都有重要的作用。

6 結束語

在離散數學中引入實踐教學內容，將復雜枯燥的算法和定義、定理的證明通過計算機編程來實現，使學生體驗到成功的喜悅。根據不同學生的實際情況，將實驗分為基礎性實驗和提高性實驗，讓不同層次的學生都有收獲。對考核方式做了調整，期末理論占40%，實踐占60%，讓學生既要學習理論又要結合實際。經過實踐證明，該方法是可行的，但是也存在一些局限，如基礎性實驗和提高性實驗的劃分標準不一等。實際教學中為了讓學生適應性更強，還需要我們對學生因材施教，因地制宜。

參考文獻：

[1] Kenneth H. Rosen，Discrete Mathematics and Its Applications[M].

NewYork：McGraw-Hill Companies，Inc，2011.

[2] 王志偉.離散數學教學中培養學生建模能力的探討[J].廣東技術師范

學院學報，2014.3：99-103

[3] 徐潔磐.應用型計算機本科中離散數學課程目標定位與課程改革的

探討[J].計算機教育，2010.5：86-91

[4] 常亮，徐周波，古天龍，董榮勝.離散數學教學中的計算思維培養[J].計

算機教育，2011.14：102-107

[5] 徐文仲，任永泰，湯巖.提高離散數學課程課堂教學有效性方法的研

究與實踐[J].東北農業大學學報（社會科學版），2010.4：55-60

[6] 溫雪蓮，蘇慶，黃劍鋒.淺談在“離散數學”教學中培養學生的數學思

維與應用能力[J].廣東工業大學學報（社會科學版），2009.S1：122-128

[7] 李國慶，張火林.《離散數學》課程教學優化策略研究[C].第二屆亞太

地區信息論學術會議論文集（上冊）[C]，2011：300-312

[8] 劉寶宏.非計算機專業離散數學課程教學改革的經驗與體會[C].

Proceedings of 2010 Third International Conference on Education Technology and Training（Volume 7）[C]，2010：197-203