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

魏文英 楊翠 李小敏 劉翠煥 張波

摘 要：針對應(yīng)用型本科高校軟件工程專業(yè)離散數(shù)學(xué)課程教學(xué)過程中存在的問題，分析原因所在，提出建模算法思維的引入，將經(jīng)典問題的建模過程和算法求解融入教學(xué)中，提高學(xué)生算法設(shè)計能力，從而系統(tǒng)地幫助學(xué)生用專業(yè)知識解決實際問題，打通離散數(shù)學(xué)與軟件工程專業(yè)之間的任督二脈。

關(guān)鍵詞：軟件工程;離散數(shù)學(xué);建模算法;案例;DFS算法

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

一、研究背景及意義

（一）研究背景

近年來，隨著人工智能、互聯(lián)網(wǎng)大數(shù)據(jù)、云計算和密碼學(xué)等新領(lǐng)域和新應(yīng)用的興起，科技革命對各類工程人才提出了新的挑戰(zhàn)和要求，尤其要求人才的跨界、融合、創(chuàng)新。離散數(shù)學(xué)作為軟件工程的核心基礎(chǔ)課程，是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、算法設(shè)計、面向?qū)ο蟪绦蛟O(shè)計等高級課程的先修課程，它的教學(xué)設(shè)計和教學(xué)效果直接影響軟件工程專業(yè)的后續(xù)課程學(xué)習(xí)。但在課堂教學(xué)中，大多教師仍采用傳統(tǒng)的重數(shù)學(xué)理論推導(dǎo)證明、輕實踐建模的教學(xué)模式，顯然不能滿足計算機類學(xué)科的發(fā)展，尤為突出影響了是軟件工程專業(yè)課程的需求。

（二）研究意義

應(yīng)用技術(shù)型本科高校注重培養(yǎng)學(xué)生解決問題的能力，就我?！靶Ｆ蠛献鳌钡能浖こ虒I(yè)來說，有針對性對離散數(shù)學(xué)教學(xué)進(jìn)行改革是必要的。

1.為專業(yè)課打下良好基礎(chǔ)，提高學(xué)生解決實際問題能力

利用離散數(shù)學(xué)中的問題案例建立數(shù)學(xué)模型并用算法程序語言實現(xiàn)，再應(yīng)用到離散數(shù)學(xué)教學(xué)中，讓學(xué)生參與了數(shù)學(xué)建模、數(shù)學(xué)實驗、算法應(yīng)用求解結(jié)果的全過程，使學(xué)生獲得抽象思維和邏輯推理能力，還培養(yǎng)了解決實際問題的建模算法能力，潛移默化將算法建模思維和方法延伸到軟件工程專業(yè)課的學(xué)習(xí)中，為軟件工程專業(yè)課程學(xué)習(xí)打下基礎(chǔ)，提高學(xué)生解決實際問題的能力。

2.學(xué)以致用，把建模算法應(yīng)用到項目開發(fā)中

還可以依靠校企共育優(yōu)勢，建立科研興趣工作室，在項目開發(fā)中讓學(xué)生參與解決實際問題的全過程，增強實踐操作技術(shù)能力，進(jìn)一步夯實應(yīng)用技術(shù)型本科高校軟件工程專業(yè)的人才培養(yǎng)目標(biāo)。

二、研究內(nèi)容與方法

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

三、離散數(shù)學(xué)中經(jīng)典案例的建模算法

基于軟件工程專業(yè)與離散數(shù)學(xué)相關(guān)聯(lián)問題的建模算法案例設(shè)計是研究的關(guān)鍵。建模算法案例要體現(xiàn)離散數(shù)學(xué)的知識點在軟件工程的應(yīng)用，并用軟件工程語言編程實現(xiàn)問題的解決。同時問題案例要具有可操作性，又可以激發(fā)學(xué)生學(xué)習(xí)離散數(shù)學(xué)和軟件編程的興趣。例如離散數(shù)學(xué)中圖論部分的經(jīng)典案例——農(nóng)夫和狼羊草過河問題，下面給出《農(nóng)夫和狼羊草過河問題》的建模算法設(shè)計實例。

（一）建模過程

1.問題描述

一個農(nóng)夫帶著一匹狼、一只羊和一些草要過河，農(nóng)夫可以用船載著他們過河。條件1：船的空間有限，只能容下農(nóng)夫和另一樣?xùn)|西（或狼或羊或草）;條件2：若農(nóng)夫不在場看管，狼會吃掉羊，羊會吃掉草。問：農(nóng)夫如何將狼羊草安全帶過河。

2.問題分析

根據(jù)題意我們可以得出一下結(jié)論：三樣?xùn)|西必須都過河，但是一次只能載一個;若農(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)造一個連通圖，直觀表達(dá)出遍歷的最短路徑，10種狀態(tài)為頂點，每次過河用有向邊表示，如下圖所示。

由上圖直接觀察出來，兩條最短路之一為：

（1111）→（0101）→（1101）→（0001）→（1011）→（0010）→（1010）→（0000）。

（二）算法實現(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ù)組對已訪問的頂點進(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)值，直至輸出安全路徑。

2.編程運行結(jié)果

對于軟件工程專業(yè)學(xué)生可結(jié)合數(shù)據(jù)結(jié)構(gòu)知識，利用C++、Java、Python三種程序語言都可以得出運行結(jié)果。

四、結(jié)語

在軟件工程專業(yè)的離散數(shù)學(xué)課程中加入案例的建模算法，正好彌補了軟件工程專業(yè)只會編程不會問題建模的短板;通過建模算法的案例教學(xué)實踐，課下討論互動多了，有效地調(diào)動學(xué)生主動學(xué)習(xí)的積極性和自我挑戰(zhàn)精神;離散數(shù)學(xué)與軟件工程專業(yè)課程的學(xué)科交叉和知識點融合，潛移默化的增強了綜合素質(zhì)，實現(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è)計與分析.北京：清華大學(xué)出版社，2016.

[4]左孝凌.離散數(shù)學(xué)的形成、發(fā)展及其在計算機科學(xué)中的作用和地位.自然雜志，7（6）：414-417.

[5]蒲興成，尹幫勇.基于實踐教學(xué)的《離散數(shù)學(xué)》課程改革.重慶理工大學(xué)學(xué)報，2012.26（12）：93-96.

[6]彭穎君.基于數(shù)學(xué)思維與計算機應(yīng)用能力培養(yǎng)的“離散數(shù)學(xué)”教學(xué)設(shè)計.科學(xué)文匯，2016（4）：40-41.

[7]陳建新，宋琦.計算機科學(xué)與技術(shù)學(xué)科課程《離散數(shù)學(xué)》教學(xué)思考.學(xué)術(shù)探討基金項目，2011，10：30-31.

[8]鄭紅波，秦緒佳，胡亞紅.基于計算思維培養(yǎng)的離散數(shù)學(xué)教學(xué)實踐探討.工業(yè)和信息化教育，2016，11：47-57.

[9]甄鵬華，于振梅.計算機科學(xué)中的算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)的離散性.微型機與應(yīng)用，2016，35（22）：18-21.

課題：課題類型：2020年度河北工程技術(shù)學(xué)院校級科研課題（課程編號：2020HG11）

作者簡介：魏文英（1982—），女，漢族，河北邯鄲人，講師，研究方向：大學(xué)數(shù)學(xué)教學(xué)及應(yīng)用數(shù)學(xué);楊翠（1984—），女，漢族，河北鹿泉人，講師，研究方向：大學(xué)數(shù)學(xué)教學(xué)及算子代數(shù);李小敏（1981—），女，土家族，湖南張家界人，副教授，研究方向：大學(xué)數(shù)學(xué)教學(xué)及一般拓?fù)鋵W(xué);劉翠煥（1975—），女，漢族，河北趙縣人，副教授，研究方向：軟件開發(fā)與人才培養(yǎng);張波（1983—），女，漢族，河北石家莊人，講師，研究方向：軟件開發(fā)。