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

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

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

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

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

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

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

7、只能載一個;若農(nó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)造一個連通圖，直觀表達出遍歷的最短路徑，10種狀態(tài)為頂點，每次過河用有向邊表示，如下圖所示。由上圖直接觀察出來，兩條最短路之一為：（1111）（0101）（1101）（0001）（1011）（0010）（1010）（0000）。（二）算

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

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