基于軟件工程專業(yè)《離散數(shù)學(xué)》課程中建模算法的研究

1、    基于軟件工程專業(yè)離散數(shù)學(xué)課程中建模算法的研究    魏文英 楊翠 李小敏 劉翠煥 張波摘 要：針對(duì)應(yīng)用型本科高校軟件工程專業(yè)離散數(shù)學(xué)課程教學(xué)過程中存在的問題，分析原因所在，提出建模算法思維的引入，將經(jīng)典問題的建模過程和算法求解融入教學(xué)中，提高學(xué)生算法設(shè)計(jì)能力，從而系統(tǒng)地幫助學(xué)生用專業(yè)知識(shí)解決實(shí)際問題，打通離散數(shù)學(xué)與軟件工程專業(yè)之間的任督二脈。關(guān)鍵詞：軟件工程;離散數(shù)學(xué);建模算法;案例;dfs算法隨著互聯(lián)網(wǎng)大數(shù)據(jù)與人工智能迅速發(fā)展，應(yīng)用技術(shù)型本科高校對(duì)計(jì)算機(jī)學(xué)科課程提出了更高要求，這引起很多學(xué)者參與離散數(shù)學(xué)課程的改革，他們基本的觀點(diǎn)是培養(yǎng)計(jì)算思維和

2、增加實(shí)驗(yàn)學(xué)習(xí)，得到一些效果。事實(shí)上，獲得圖靈獎(jiǎng)的pascal之父尼古拉斯·沃斯于早在1976年就提出著名的“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，算法是程序的靈魂。建模算法的思想在于分析解決問題的整體思維，包括：?jiǎn)栴}描述;問題建模;算法求解。算法思維也是軟件開發(fā)的源動(dòng)力，因此對(duì)軟件工程專業(yè)學(xué)生來說培養(yǎng)建模算法思維更有實(shí)際意義。目前國內(nèi)大部分應(yīng)用技術(shù)型本科高校軟件工程專業(yè)離散數(shù)學(xué)課程的教學(xué)理念仍側(cè)重?cái)?shù)學(xué)理論推導(dǎo)，輕實(shí)際案例的解決應(yīng)用，缺乏建模算法案例的應(yīng)用，不能將分析問題、解決問題的建模算法應(yīng)用到計(jì)算機(jī)類軟件工程專業(yè)后續(xù)課程學(xué)習(xí)中，教學(xué)效果不能充分體現(xiàn)離散數(shù)學(xué)在軟件工程專業(yè)課程體系中的支撐作用。一、

3、研究背景及意義（一）研究背景近年來，隨著人工智能、互聯(lián)網(wǎng)大數(shù)據(jù)、云計(jì)算和密碼學(xué)等新領(lǐng)域和新應(yīng)用的興起，科技革命對(duì)各類工程人才提出了新的挑戰(zhàn)和要求，尤其要求人才的跨界、融合、創(chuàng)新。離散數(shù)學(xué)作為軟件工程的核心基礎(chǔ)課程，是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、算法設(shè)計(jì)、面向?qū)ο蟪绦蛟O(shè)計(jì)等高級(jí)課程的先修課程，它的教學(xué)設(shè)計(jì)和教學(xué)效果直接影響軟件工程專業(yè)的后續(xù)課程學(xué)習(xí)。但在課堂教學(xué)中，大多教師仍采用傳統(tǒng)的重?cái)?shù)學(xué)理論推導(dǎo)證明、輕實(shí)踐建模的教學(xué)模式，顯然不能滿足計(jì)算機(jī)類學(xué)科的發(fā)展，尤為突出影響了是軟件工程專業(yè)課程的需求。（二）研究意義應(yīng)用技術(shù)型本科高校注重培養(yǎng)學(xué)生解決問題的能力，就我?！靶Ｆ蠛献鳌钡能浖こ虒I(yè)來說，有針對(duì)性

4、對(duì)離散數(shù)學(xué)教學(xué)進(jìn)行改革是必要的。1.為專業(yè)課打下良好基礎(chǔ)，提高學(xué)生解決實(shí)際問題能力利用離散數(shù)學(xué)中的問題案例建立數(shù)學(xué)模型并用算法程序語言實(shí)現(xiàn)，再應(yīng)用到離散數(shù)學(xué)教學(xué)中，讓學(xué)生參與了數(shù)學(xué)建模、數(shù)學(xué)實(shí)驗(yàn)、算法應(yīng)用求解結(jié)果的全過程，使學(xué)生獲得抽象思維和邏輯推理能力，還培養(yǎng)了解決實(shí)際問題的建模算法能力，潛移默化將算法建模思維和方法延伸到軟件工程專業(yè)課的學(xué)習(xí)中，為軟件工程專業(yè)課程學(xué)習(xí)打下基礎(chǔ)，提高學(xué)生解決實(shí)際問題的能力。2.學(xué)以致用，把建模算法應(yīng)用到項(xiàng)目開發(fā)中還可以依靠校企共育優(yōu)勢(shì)，建立科研興趣工作室，在項(xiàng)目開發(fā)中讓學(xué)生參與解決實(shí)際問題的全過程，增強(qiáng)實(shí)踐操作技術(shù)能力，進(jìn)一步夯實(shí)應(yīng)用技術(shù)型本科高校軟件工程專業(yè)

5、的人才培養(yǎng)目標(biāo)。二、研究?jī)?nèi)容與方法基于以上問題，以我校軟件工程專業(yè)開展研究，在離散數(shù)學(xué)的四大模塊：數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論中分別找出經(jīng)典案例進(jìn)行整理優(yōu)化數(shù)學(xué)模型，然后列出與軟件工程專業(yè)課程相關(guān)聯(lián)知識(shí)的實(shí)際問題案例，建立出數(shù)學(xué)模型，利用分治、遞歸、bfs、dijkstra、網(wǎng)絡(luò)流、ao*等算法進(jìn)行算法分析設(shè)計(jì)，最后針對(duì)案例的不同算法，利用c+、java、python等軟件工程語言編程實(shí)現(xiàn)，反復(fù)實(shí)驗(yàn)并優(yōu)化算法設(shè)計(jì)，形成完整的離散數(shù)學(xué)實(shí)例應(yīng)用程序，最終將建模算法案例應(yīng)用到離散數(shù)學(xué)的教學(xué)中，并延伸應(yīng)用到軟件工程專業(yè)課程中。三、離散數(shù)學(xué)中經(jīng)典案例的建模算法基于軟件工程專業(yè)與離散數(shù)學(xué)相關(guān)聯(lián)問題的建

6、模算法案例設(shè)計(jì)是研究的關(guān)鍵。建模算法案例要體現(xiàn)離散數(shù)學(xué)的知識(shí)點(diǎn)在軟件工程的應(yīng)用，并用軟件工程語言編程實(shí)現(xiàn)問題的解決。同時(shí)問題案例要具有可操作性，又可以激發(fā)學(xué)生學(xué)習(xí)離散數(shù)學(xué)和軟件編程的興趣。例如離散數(shù)學(xué)中圖論部分的經(jīng)典案例農(nóng)夫和狼羊草過河問題，下面給出農(nóng)夫和狼羊草過河問題的建模算法設(shè)計(jì)實(shí)例。（一）建模過程1.問題描述一個(gè)農(nóng)夫帶著一匹狼、一只羊和一些草要過河，農(nóng)夫可以用船載著他們過河。條件1：船的空間有限，只能容下農(nóng)夫和另一樣?xùn)|西（或狼或羊或草）;條件2：若農(nóng)夫不在場(chǎng)看管，狼會(huì)吃掉羊，羊會(huì)吃掉草。問：農(nóng)夫如何將狼羊草安全帶過河。2.問題分析根據(jù)題意我們可以得出一下結(jié)論：三樣?xùn)|西必須都過河，但是一次

7、只能載一個(gè);若農(nóng)夫不在場(chǎng)，狼羊不能在一起，羊草不能在一起，而狼草可以在一起。3.模型建立我們可將農(nóng)夫和狼羊草過河問題抽象成圖論問題來解決。假設(shè)農(nóng)夫、狼、羊、草在此岸的狀態(tài)依次都為1，成功渡河后狀態(tài)依次都為0。最終方案就是初始狀態(tài)（1111）結(jié)束狀態(tài)（0000）所經(jīng)過的路徑。我們可列出16種在岸上的狀態(tài)，如下表所示：根據(jù)題意可知紅色的6種狀態(tài)是不允許出現(xiàn)的。我們構(gòu)造一個(gè)連通圖，直觀表達(dá)出遍歷的最短路徑，10種狀態(tài)為頂點(diǎn)，每次過河用有向邊表示，如下圖所示。由上圖直接觀察出來，兩條最短路之一為：（1111）（0101）（1101）（0001）（1011）（0010）（1010）（0000）。（二）算

8、法實(shí)現(xiàn)1.算法設(shè)計(jì)近幾年，農(nóng)夫和狼羊草過河問題吸引了很多編程愛好者的研究，也給出了的很多算法設(shè)計(jì)，可謂是仁者見仁智者見智，總結(jié)來基本是用遞歸法、廣度優(yōu)先搜索（bfs）法和深度優(yōu)先搜索（dfs）法三種方法。以深度優(yōu)先搜索（dfs）為例，首先建立結(jié)點(diǎn)，包含農(nóng)夫、狼、羊、草四個(gè)屬性，最初狀態(tài)均是1。設(shè)visited數(shù)組對(duì)已訪問的頂點(diǎn)進(jìn)行標(biāo)記（圖的遍歷），逐層存放下一步可能的安全狀態(tài);設(shè)issafe函數(shù)確定狀態(tài)的安全性，通過位置分布的代碼來判斷當(dāng)前狀態(tài)是否安全，不安全返回false，否則返回true;調(diào)用遞歸函數(shù)遍歷visited數(shù)組，標(biāo)記該狀態(tài)是否已訪問過，若訪問過，則記錄前驅(qū)狀態(tài)值，直至輸出安全路

9、徑。2.編程運(yùn)行結(jié)果對(duì)于軟件工程專業(yè)學(xué)生可結(jié)合數(shù)據(jù)結(jié)構(gòu)知識(shí)，利用c+、java、python三種程序語言都可以得出運(yùn)行結(jié)果。四、結(jié)語在軟件工程專業(yè)的離散數(shù)學(xué)課程中加入案例的建模算法，正好彌補(bǔ)了軟件工程專業(yè)只會(huì)編程不會(huì)問題建模的短板;通過建模算法的案例教學(xué)實(shí)踐，課下討論互動(dòng)多了，有效地調(diào)動(dòng)學(xué)生主動(dòng)學(xué)習(xí)的積極性和自我挑戰(zhàn)精神;離散數(shù)學(xué)與軟件工程專業(yè)課程的學(xué)科交叉和知識(shí)點(diǎn)融合，潛移默化的增強(qiáng)了綜合素質(zhì)，實(shí)現(xiàn)離散數(shù)學(xué)理論的應(yīng)用推廣，提高了教學(xué)效果。雖然建模算法案例在離散數(shù)學(xué)教學(xué)中初見成效，但教學(xué)方法和案例選取上需要進(jìn)一步完善和研究。參考文獻(xiàn)：1王衛(wèi)紅，李曲，鄭宇軍，等.離散數(shù)學(xué).北京：清華大學(xué)出版社，2013.2耿素云，屈婉玲，張立昂.離散數(shù)學(xué).北京：清華大學(xué)出版社，2013.3屈婉玲，劉田，張立昂，等.算法設(shè)計(jì)與分析.北京：清華大學(xué)出版社，2016.4左孝凌.離散數(shù)學(xué)的形成、發(fā)展及其在計(jì)算機(jī)科學(xué)中的作用和地位.自然雜志，7（6）：414-417.5蒲興成，尹幫勇.基于實(shí)踐教學(xué)的離散數(shù)學(xué)課程改革.重慶理工大學(xué)學(xué)報(bào)，2012.26（12）：93-96.6彭穎君.基于數(shù)學(xué)思維與計(jì)算機(jī)應(yīng)用能力培養(yǎng)的“離散數(shù)學(xué)”教學(xué)設(shè)計(jì).科學(xué)文匯，2016（4）：40-41.7陳建新，宋琦.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科課程離散數(shù)學(xué)教學(xué)思考.學(xué)術(shù)探討基金項(xiàng)目，2011，10：30-31.8鄭紅波，秦緒佳，