突顯能力培養(yǎng)的離散數(shù)學(xué)逆向案例教學(xué)改革探索

徐周波，古天龍，常 亮

（桂林電子科技大學(xué)計(jì)算機(jī)與信息安全學(xué)院，廣西桂林541004）

2015年我國(guó)成為《華盛頓協(xié)議》正式會(huì)員，工程教育認(rèn)證為廣大工科院校開展工程應(yīng)用型人才培養(yǎng)給予了方向性指導(dǎo)，強(qiáng)調(diào)工程應(yīng)用型人才必須具備對(duì)復(fù)雜工程問(wèn)題的建模、設(shè)計(jì)、分析和求解的能力。隨著經(jīng)濟(jì)發(fā)展方式的轉(zhuǎn)變、產(chǎn)業(yè)結(jié)構(gòu)的轉(zhuǎn)型以及加快推進(jìn)創(chuàng)新型國(guó)家的建設(shè)，2017年教育部啟動(dòng)了“新工科”發(fā)展研究工作，提出著眼于未來(lái)新技術(shù)與新產(chǎn)業(yè)的人才需求，培養(yǎng)具有可持續(xù)競(jìng)爭(zhēng)力的創(chuàng)新人才。課程是高校實(shí)施教育的核心，課程教學(xué)效果的好壞直接影響著人才培養(yǎng)的質(zhì)量。近年來(lái)，我國(guó)一直以課程改革的方式來(lái)提高整體教育質(zhì)量。2013年在深圳會(huì)議發(fā)表的“計(jì)算思維教學(xué)改革宣言”意味著新一輪大學(xué)計(jì)算機(jī)課程改革的核心導(dǎo)向?yàn)橛?jì)算思維能力的培養(yǎng)[1]。計(jì)算思維是指運(yùn)用計(jì)算機(jī)科學(xué)的基本概念來(lái)求解問(wèn)題、設(shè)計(jì)系統(tǒng)和理解人類行為，包括一系列廣泛的計(jì)算機(jī)科學(xué)的思維方法[2]。在課程教學(xué)實(shí)施中培養(yǎng)學(xué)生計(jì)算思維能力、創(chuàng)新能力以及快速學(xué)習(xí)新事物能力是促進(jìn)學(xué)生能力提升的有效途徑，也是近年來(lái)課程改革關(guān)注的焦點(diǎn)[3-4]。

作為計(jì)算機(jī)類專業(yè)核心基礎(chǔ)課程的離散數(shù)學(xué)不僅是計(jì)算機(jī)后續(xù)專業(yè)課程（如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)原理、人工智能、數(shù)字邏輯等）的重要基礎(chǔ)，也是培養(yǎng)學(xué)生計(jì)算思維能力的重要基礎(chǔ)課程。但在實(shí)際教學(xué)中，任課教師更多地關(guān)注學(xué)科知識(shí)的傳授，缺乏從專業(yè)課程體系角度和計(jì)算思維能力培養(yǎng)的角度來(lái)講授課程，致使學(xué)生錯(cuò)誤地認(rèn)為離散數(shù)學(xué)課程是一門純粹的數(shù)學(xué)課程，枯燥抽象，難以引起學(xué)習(xí)興趣；此外，學(xué)生即使掌握了基本概念和定理，但仍缺乏知識(shí)遷移能力，難以運(yùn)用知識(shí)解決問(wèn)題。

1 基于課程定位，強(qiáng)調(diào)離散數(shù)學(xué)在專業(yè)課程中的應(yīng)用

離散數(shù)學(xué)是研究計(jì)算機(jī)科學(xué)的數(shù)學(xué)理論基礎(chǔ)，是研究離散量及其相互關(guān)系的一門學(xué)科，包括集合論、數(shù)理邏輯、抽象代數(shù)和圖論四部分教學(xué)內(nèi)容。離散數(shù)學(xué)課程在ACM和IEEE-CS制定的計(jì)算機(jī)科學(xué)教程以及我國(guó)高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)的計(jì)算機(jī)專業(yè)規(guī)范中均處于核心地位。

在課堂教學(xué)中需要使學(xué)生理解離散數(shù)學(xué)課程的重要地位，在引入離散數(shù)學(xué)教學(xué)內(nèi)容之前，首先要讓學(xué)生明確學(xué)習(xí)離散數(shù)學(xué)課程的目的，即培養(yǎng)運(yùn)用離散數(shù)學(xué)中的基本概念、思想和方法去構(gòu)建問(wèn)題的抽象模型并在此基礎(chǔ)上培養(yǎng)設(shè)計(jì)、分析和解決問(wèn)題的能力，以及創(chuàng)新能力和快速學(xué)習(xí)新事物的能力。數(shù)字電子計(jì)算機(jī)本身是一個(gè)離散結(jié)構(gòu)，只能處理離散的或離散化了的數(shù)量關(guān)系。因此，無(wú)論是計(jì)算機(jī)科學(xué)本身，還是與計(jì)算機(jī)密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對(duì)離散結(jié)構(gòu)建立模型或者將已用連續(xù)數(shù)量關(guān)系建立起來(lái)的模型離散化，再由計(jì)算機(jī)加以處理和實(shí)現(xiàn)的問(wèn)題。而離散數(shù)學(xué)正是其不可缺少的理論工具，需要在課程教學(xué)過(guò)程中引入案例讓學(xué)生逐步體驗(yàn)領(lǐng)會(huì)并學(xué)會(huì)應(yīng)用。

其次要讓學(xué)生明確離散數(shù)學(xué)與專業(yè)課程體系中其他課程之間的關(guān)系，如圖1所示。如命題公式可與數(shù)據(jù)結(jié)構(gòu)中的二叉樹相聯(lián)系；關(guān)系可與數(shù)據(jù)庫(kù)系統(tǒng)原理課程中的元組、表、關(guān)系代數(shù)運(yùn)算等聯(lián)系在一起；抽象代數(shù)可與幺元和程序設(shè)計(jì)中賦予變量的缺省值聯(lián)系在一起；有向圖的連通性可與操作系統(tǒng)中的進(jìn)程死鎖聯(lián)系在一起。使學(xué)生在學(xué)習(xí)學(xué)科知識(shí)的同時(shí)領(lǐng)會(huì)其在其他專業(yè)課程中的應(yīng)用，激發(fā)學(xué)生對(duì)知識(shí)遷移的感性認(rèn)知，促進(jìn)學(xué)生計(jì)算思維能力的培養(yǎng)，進(jìn)而提升學(xué)生對(duì)離散數(shù)學(xué)課程的重視度和學(xué)習(xí)興趣。

2 圍繞課程教學(xué)目標(biāo)，實(shí)施逆向案例教學(xué)，落實(shí)學(xué)生的計(jì)算思維能力培養(yǎng)

作為計(jì)算機(jī)類專業(yè)核心基礎(chǔ)課程的離散數(shù)學(xué)，其課程教學(xué)不只是簡(jiǎn)單地傳授給學(xué)生學(xué)科知識(shí)，更重要的是培養(yǎng)學(xué)生運(yùn)用所學(xué)理論去構(gòu)建問(wèn)題的抽象模型并在此基礎(chǔ)上設(shè)計(jì)、分析和解決問(wèn)題以及快速學(xué)習(xí)新事物的能力。然而，目前國(guó)內(nèi)各高校普遍存在壓縮課時(shí)的現(xiàn)象，教學(xué)內(nèi)容和教學(xué)學(xué)時(shí)的矛盾致使教師普遍在課堂教學(xué)中進(jìn)行“滿堂灌”，而無(wú)暇顧及課程目標(biāo)中的能力培養(yǎng)，課程目標(biāo)成為抽象的口號(hào)，學(xué)生學(xué)習(xí)課程之后也難以將離散數(shù)學(xué)的知識(shí)遷移到具體應(yīng)用中。案例教學(xué)是一種傳統(tǒng)教學(xué)模式，通過(guò)合理有效的案例能有效減輕學(xué)生對(duì)抽象內(nèi)容的認(rèn)知負(fù)荷，但因其漸進(jìn)式的案例分析，提高學(xué)生解決新問(wèn)題的能力及知識(shí)遷移能力的效果較差。逆向教學(xué)則將學(xué)生從單純的知識(shí)接收者轉(zhuǎn)變?yōu)樘骄空?，讓學(xué)生在探究的過(guò)程中學(xué)會(huì)獨(dú)立思考[5]。因此，將案例教學(xué)法與逆向教學(xué)法相結(jié)合，有利于培養(yǎng)學(xué)生的問(wèn)題求解能力和知識(shí)遷移能力。

2.1 逆向案例教學(xué)設(shè)計(jì)

在離散數(shù)學(xué)課程教學(xué)過(guò)程中引入逆向案例教學(xué)法，基于“提出問(wèn)題—分析問(wèn)題—引入概念—抽象建?！O(shè)計(jì)分析—程序設(shè)計(jì)”的教學(xué)設(shè)計(jì)思路，設(shè)計(jì)合理的涵蓋課程教學(xué)內(nèi)容的教學(xué)案例。在學(xué)生分析思考如何求解問(wèn)題的同時(shí)，引入所需知識(shí)點(diǎn)；在解決問(wèn)題的過(guò)程中領(lǐng)會(huì)相應(yīng)知識(shí)點(diǎn)在實(shí)際應(yīng)用和后續(xù)課程中的作用，從而提升學(xué)生運(yùn)用理論知識(shí)對(duì)問(wèn)題進(jìn)行抽象建模、設(shè)計(jì)、分析和求解的能力，通過(guò)算法設(shè)計(jì)分析，進(jìn)一步提出解決方案的改進(jìn)，提升學(xué)生的動(dòng)手能力和知識(shí)遷移能力。

由于離散數(shù)學(xué)課程一般開設(shè)在大學(xué)第二和第三學(xué)期，為此在教學(xué)案例設(shè)計(jì)時(shí)需考慮學(xué)生已有的知識(shí)體系和接受能力，保留一定的拓展空間，使其適應(yīng)于不同水平的學(xué)生。以圖論部分為例，在表1中，我們以“能力培養(yǎng)”為出發(fā)點(diǎn)，通過(guò)提出問(wèn)題、分析問(wèn)題、問(wèn)題抽象建模、問(wèn)題的算法設(shè)計(jì)與分析等逐步引入教學(xué)大綱中的知識(shí)點(diǎn)，并按逆向案例教學(xué)法從簡(jiǎn)單到復(fù)雜設(shè)計(jì)每一個(gè)案例。培養(yǎng)一名計(jì)算機(jī)專業(yè)學(xué)生，除了培養(yǎng)其強(qiáng)大的“內(nèi)功”之外，還必須培養(yǎng)能發(fā)揮其內(nèi)功的“外功”，即既需培養(yǎng)學(xué)生具備扎實(shí)的學(xué)科基礎(chǔ)理論知識(shí)，又需培養(yǎng)學(xué)生具有使用現(xiàn)代工具解決問(wèn)題的能力。因此，在每一個(gè)案例的建模求解之后，安排學(xué)生在課后去編程實(shí)現(xiàn)，這不僅提高了學(xué)生的計(jì)算思維能力和程序設(shè)計(jì)能力，而且也加深了學(xué)生對(duì)知識(shí)的理解，有利于提高學(xué)生的自學(xué)能力。但在離散數(shù)學(xué)課程中使用一種特定的編程語(yǔ)言容易干擾并分散學(xué)生對(duì)于算法問(wèn)題求解核心部分的注意力。為此，選擇已被廣泛普及應(yīng)用于計(jì)算機(jī)教學(xué)的Raptor（therapid algorithmicprototypingtoolfororderedreasoning，用于有序推理的快速算法原型工具）來(lái)編程實(shí)現(xiàn)每一個(gè)案例的算法。Raptor是一種基于流程圖的程序開發(fā)環(huán)境，通過(guò)繪制算法流程圖而不是某一具體的計(jì)算機(jī)語(yǔ)言來(lái)實(shí)現(xiàn)算法，此工具還可以將繪制的流程圖直接翻譯成具體的一種計(jì)算機(jī)語(yǔ)言，如C++語(yǔ)言、C#和Ada，便于學(xué)生對(duì)具體計(jì)算機(jī)語(yǔ)言的后續(xù)學(xué)習(xí)。通過(guò)此部分的實(shí)踐，不僅可以讓學(xué)生體會(huì)到算法設(shè)計(jì)對(duì)問(wèn)題求解有效性的評(píng)估，而且引導(dǎo)學(xué)生完成了“分析問(wèn)題—抽象建?！惴ㄔO(shè)計(jì)、分析—程序設(shè)計(jì)”的完整流程，培養(yǎng)了學(xué)生的計(jì)算思維能力和學(xué)習(xí)新事物的能力。

2.2 逆向案例教學(xué)實(shí)施過(guò)程

基于逆向案例教學(xué)設(shè)計(jì)思路，在課堂教學(xué)過(guò)程中按簡(jiǎn)單到復(fù)雜將各個(gè)案例逐個(gè)引入，通過(guò)提出問(wèn)題、分析問(wèn)題、問(wèn)題抽象建模、問(wèn)題的算法設(shè)計(jì)與分析等方式逐步引入教學(xué)大綱中的知識(shí)點(diǎn)。例如，為引入圖論的基本概念和基本定理，從哥尼斯堡七橋問(wèn)題著手提出問(wèn)題，并讓學(xué)生試著解決問(wèn)題。只在地圖上尋找答案可能會(huì)遺漏某些可行的方案，以此為開端，引入圖論的方法來(lái)求解該問(wèn)題。首先對(duì)問(wèn)題進(jìn)行分析，將陸地和島嶼看成圖中的頂點(diǎn)，將橋看成連接圖中頂點(diǎn)的邊，以此引入圖論中的一些基本概念和方法。然后建立原問(wèn)題的抽象模型——?dú)W拉圖的判定，即將哥尼斯堡七橋問(wèn)題轉(zhuǎn)化為在圖中尋找一條歐拉回路的問(wèn)題。通過(guò)引入歐拉圖的判定定理，學(xué)生很快就能給出哥尼斯堡七橋問(wèn)題無(wú)解的結(jié)論。通過(guò)對(duì)原問(wèn)題的抽象表示并應(yīng)用圖論中的理論進(jìn)行設(shè)計(jì)、分析，讓學(xué)生切實(shí)領(lǐng)會(huì)理論的指導(dǎo)意義。通過(guò)對(duì)歐拉圖的學(xué)習(xí)，學(xué)生可以在課外完成“街道清掃”“巡邏維護(hù)”等路線設(shè)計(jì)問(wèn)題，舉一反三，鞏固知識(shí)，進(jìn)一步提高知識(shí)遷移能力。

3 科研反哺教學(xué)，培養(yǎng)學(xué)生的科學(xué)素質(zhì)和創(chuàng)新能力

大學(xué)本科階段越來(lái)越注重素質(zhì)教育及創(chuàng)新能力的培養(yǎng)，離散數(shù)學(xué)在培養(yǎng)學(xué)生的創(chuàng)新能力和提高學(xué)生的科研素質(zhì)方面都有著重要作用。教師在傳授課本知識(shí)的同時(shí)，引入科研成果，拓寬教材中的知識(shí)點(diǎn)的應(yīng)用延伸，可以進(jìn)一步培養(yǎng)學(xué)生的探究學(xué)習(xí)能力，培養(yǎng)學(xué)生基本科研興趣和創(chuàng)新能力。

例如，在命題邏輯中，命題公式類型的講解一方面可以引入人工智能中歷史悠久的可滿足性問(wèn)題（SAT）和約束可滿足問(wèn)題（constraint satisfyproblem,CSP），列舉典型的SAT和CSP案例，如地圖著色問(wèn)題、機(jī)器人穿衣問(wèn)題、無(wú)線電鏈路頻率分配問(wèn)題等，給出SAT和CSP的算法框架，并提供一些參考文獻(xiàn)供學(xué)生課后學(xué)習(xí)，拓寬學(xué)生視野。另一方面可以從算法自動(dòng)執(zhí)行的角度來(lái)分析命題公式類型的判定算法，算法的好壞通常由時(shí)間和空間復(fù)雜度來(lái)衡量。從存儲(chǔ)空間角度來(lái)看，若用完全二叉樹或二維數(shù)組來(lái)存儲(chǔ)命題公式A=x1·x2，則存在大量重復(fù)的0和1，如圖2（a）、3（b）所示。利用圖的同構(gòu)性，將完全二叉樹中所有同構(gòu)的圖（子圖）合并，并利用命題公式基本定律，去掉無(wú)關(guān)命題變?cè)玫叫碌慕Y(jié)構(gòu)，稱之為二叉決策圖（binarydecision diagram,BDD）[6]，如圖2（c）所示?？梢?jiàn)，利用離散數(shù)學(xué)中的理論知識(shí)得出的BDD結(jié)構(gòu)具有更好的存儲(chǔ)效率。后續(xù)結(jié)合電路設(shè)計(jì)實(shí)際案例來(lái)詳述BDD在簡(jiǎn)化和驗(yàn)證電路設(shè)計(jì)中的優(yōu)越性以及在介紹經(jīng)典的最短路徑算法Dijkstra后，引領(lǐng)學(xué)生思考可否“并行”求解多條最短路徑問(wèn)題，并給出基于BDD的“并行”求解多條最短路徑算法。通過(guò)將科研反哺于教學(xué)，不僅能夠培養(yǎng)學(xué)生的邏輯思維能力、分析能力和創(chuàng)新能力，而且還易于讓學(xué)生意識(shí)并體會(huì)到知識(shí)的鞏固、提升在科研領(lǐng)域和生活實(shí)際中產(chǎn)生的重大影響。

圖2 對(duì)于命題公式A=x1·x2的存儲(chǔ)表示

4 結(jié)語(yǔ)

面對(duì)當(dāng)前和未來(lái)戰(zhàn)略新興產(chǎn)業(yè)的人才需求，離散數(shù)學(xué)作為計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課程，在課程教學(xué)上更應(yīng)側(cè)重學(xué)生的計(jì)算思維能力培養(yǎng)和可持續(xù)發(fā)展學(xué)習(xí)能力的培養(yǎng)。通過(guò)逆向案例教學(xué)法，從專業(yè)課程體系的角度和計(jì)算思維能力培養(yǎng)角度設(shè)計(jì)教學(xué)案例，在傳承課本知識(shí)的同時(shí)，注重科研反哺教學(xué)，這不僅有利于學(xué)生感性認(rèn)知離散數(shù)學(xué)課程的核心地位，提升學(xué)生的學(xué)習(xí)興趣，為學(xué)生繼續(xù)后續(xù)課程學(xué)習(xí)以及從事科學(xué)研究和進(jìn)行工程應(yīng)用開發(fā)奠定堅(jiān)實(shí)的理論基礎(chǔ)，也有利于培養(yǎng)學(xué)生知識(shí)遷移能力、創(chuàng)新能力和解決實(shí)際問(wèn)題的能力。