離散數(shù)學分層次實驗教學設計應用論文

　　0 引言

　　離散數(shù)學作為現(xiàn)代數(shù)學的重要分支，主要研究離散量的結(jié)構(gòu)及其相互關系。離散數(shù)學作為計算機科學與技術專業(yè)的核心基礎課程，對于學生知識、能力和綜合素質(zhì)的培養(yǎng)起到承前啟后的作用。它不但為程序設計語言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯技術、人工智能、數(shù)據(jù)庫、算法設計與分析等課程的學習提供必須的數(shù)學基礎，而且有助于培養(yǎng)學生具有嚴謹?shù)目茖W研究的作風，提高學生的理論素質(zhì)和分析和解決問題的能力。

　　由于離散數(shù)學高度抽象、概念多，理論性很強，在大多數(shù)的本科教學中崇尚理論教學，基本不開設實驗課，故造成學生學得枯燥，老師教得辛苦，學生解決實際問題能力不高。為了提高學生的動手能力，在教學中加強實踐環(huán)節(jié)是很有必要的。本文分析了離散數(shù)學課程的教學現(xiàn)狀，對分層次教學的必要性進行了探討，提出了實驗設計的原則、思路和內(nèi)容，對實驗進行實施，并對實驗教學成果進行了分析。

　　1 實踐教學現(xiàn)狀

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

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

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

　�、� 有的高校實驗安排沒有層次感，內(nèi)容單調(diào)和分散，不能滿足不同學生的需求，有些高校開設了分層次實驗教學，把實驗分為驗證型實驗，應用型實驗，綜合型實驗和創(chuàng)新型實驗，但實驗與工程的結(jié)合性不強。

　�、� 由于離散數(shù)學的學習群體一般是高等院校的學生，其實踐教學未考慮本科和�？茖W生的接受能力和不同專業(yè)的側(cè)重點。比如軟件工程專業(yè)的離散數(shù)學課重點放在圖論、集合與邏輯，而網(wǎng)絡工程專業(yè)重點放在代數(shù)系統(tǒng)。

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

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

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

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

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

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

　　離散數(shù)學的實驗設計基于其課程體系，面向?qū)嶋H應用，針對計算機程序設計大賽，在實驗過程讓學生協(xié)作工作，讓每個學生的特長得以體現(xiàn)，以培養(yǎng)學生的`創(chuàng)新精神和團隊的協(xié)作意識。

　　3 實驗設計

　　3.1 分層教學的原則

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

　�、� 水平相近原則：將學習狀況相近，智力水平相同的學生為"同一層".

　　⑵ 動態(tài)變化原則：分層是動態(tài)的，進步的學生"升級",退步的學生"降級".

　�、� 化整為零原則：教學內(nèi)容進行適度合并或者分解，對學生"放""扶"并重。

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

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

　　3.2 實驗設計原則

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

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

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

　�、� 將離散數(shù)學的教學與計算機程序設計大賽相結(jié)合，藍橋杯和ACM競賽中圖論和搜索算法、網(wǎng)絡流等都與離散數(shù)學教學密切相關。

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

　　3.3 思路設計

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

　　3.3.1 數(shù)理邏輯

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

　　3.3.2 集合論

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

　　3.3.3 代數(shù)系統(tǒng)

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

　　3.3.4 圖論

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

　　3.4 內(nèi)容設計

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

　　3.4.1 驗證性實驗

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

　　3.4.2 應用型實驗

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

　　3.4.3 綜合型實驗

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

　　3.4.4 創(chuàng)新型實驗

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

　　4 實驗實施和考核

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

　　4.1 設置情景

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

　　4.2 功能分析

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

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

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

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

　　4.3 模塊算法

　　4.3.1 歐拉圖的判定算法

　�、� 給定一個圖，用并查集判定是否是連通圖，如是轉(zhuǎn)⑵；⑵ 分別求出每個節(jié)點的度數(shù)，若均為偶數(shù)，則轉(zhuǎn)4.3.2算法，否則轉(zhuǎn)4.3.3算法；⑶ 輸出此圖不連通。

　　4.3.2 Fleury算法

　　輸出歐拉回路的算法任取v0∈V（G），令P0=v0;設Pi=v0e1v1e2…eivi已經(jīng)行遍，按下面方法從中選取ei+1:⑴ ei+1與vi相關聯(lián)；⑵ 除非無別的邊可供行遍，否則ei+1不應該為Gi=G-{e1,e2,…，ei}中的橋（所謂橋是一條刪除后使連通圖不再連通的邊）；⑶ 當⑵不能再進行時，算法停止。

　　4.3.3 最小對集法

　　添加邊使非歐拉圖變成歐拉圖其算法如下：⑴ 求出圖G所有頂點之間的最短路徑和距離；⑵ 以G的所有奇次頂點為頂點集，做一完備圖，邊上的權為兩端點在原圖G中的最短距離，將此完備圖的加權圖記為G1;⑶ 求G1的最小權理想匹配M,得到奇次頂點的最佳匹配對；⑷ 在G中沿配對頂點之間的最短路徑添加重復邊得到歐拉圖G';⑸ 利用Fleury算法輸出歐拉圖G'的路徑。

　　4.3.4 功能實現(xiàn)

　　數(shù)據(jù)輸入：邊數(shù)5,點數(shù)6相關聯(lián)的點 1 21 32 54 23 24 5運行結(jié)果：存在歐拉回路 1,3,2,4,5,2,14.3.5 考核方式。

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

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

　　最后總的實驗成績分數(shù)是由基礎實驗占70%,提高實驗占30%而得。

　　5 成果分析

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

　　6 結(jié)束語

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

　　參考文獻：

　　[1] Kenneth H. Rosen,Discrete Mathematics and Its Applications[M]. NewYork:McGraw-Hill Companies,Inc,2011.

　　[2] 王志偉。離散數(shù)學教學中培養(yǎng)學生建模能力的探討[J].廣東技術師范學院學報，2014.3:99-103

　　[3] 徐潔磐。應用型計算機本科中離散數(shù)學課程目標定位與課程改革的探討[J].計算機教育，2010.5:86-91

　　[4] 常亮，徐周波，古天龍，董榮勝。離散數(shù)學教學中的計算思維培養(yǎng)[J].計算機教育，2011.14:102-107

　　[5] 徐文仲，任永泰，湯巖。提高離散數(shù)學課程課堂教學有效性方法的研究與實踐[J].東北農(nóng)業(yè)大學學報（社會科學版），2010.4:55-60

　　[6] 溫雪蓮，蘇慶，黃劍鋒。淺談在"離散數(shù)學"教學中培養(yǎng)學生的數(shù)學思維與應用能力[J].廣東工業(yè)大學學報（社會科學版），2009.S1:122-128

　　[7] 李國慶，張火林《。離散數(shù)學》課程教學優(yōu)化策略研究[C].第二屆亞太地區(qū)信息論學術會議論文集（上冊）[C],2011:300-312

　　[8] 劉寶宏。非計算機專業(yè)離散數(shù)學課程教學改革的經(jīng)驗與體會[C].

【離散數(shù)學分層次實驗教學設計應用論文】相關文章：

比應用教學設計04-04

改進應用寫作教學論文05-09

�？茖哟我魳方逃龑�業(yè)就業(yè)指導探討論文05-10

《分蘋果》教學設計7篇03-14

高職應用寫作課程改革論文07-20

計算機應用基礎教學設計05-09

看看多媒體模式下的計算機應用基礎實驗教學05-06

設計類論文提綱10-15

家具設計論文參考文獻論文07-19

科技應用文寫作的論文08-30