基于軟件工程專業《離散數學》課程中建模算法的研究

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

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

關鍵詞：軟件工程;離散數學;建模算法;案例;DFS算法

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

一、研究背景及意義

（一）研究背景

近年來，隨著人工智能、互聯網大數據、云計算和密碼學等新領域和新應用的興起，科技革命對各類工程人才提出了新的挑戰和要求，尤其要求人才的跨界、融合、創新。離散數學作為軟件工程的核心基礎課程，是數據結構、數據庫原理、算法設計、面向對象程序設計等高級課程的先修課程，它的教學設計和教學效果直接影響軟件工程專業的后續課程學習。但在課堂教學中，大多教師仍采用傳統的重數學理論推導證明、輕實踐建模的教學模式，顯然不能滿足計算機類學科的發展，尤為突出影響了是軟件工程專業課程的需求。

（二）研究意義

應用技術型本科高校注重培養學生解決問題的能力，就我校“校企合作”的軟件工程專業來說，有針對性對離散數學教學進行改革是必要的。

1.為專業課打下良好基礎，提高學生解決實際問題能力

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

2.學以致用，把建模算法應用到項目開發中

還可以依靠校企共育優勢，建立科研興趣工作室，在項目開發中讓學生參與解決實際問題的全過程，增強實踐操作技術能力，進一步夯實應用技術型本科高校軟件工程專業的人才培養目標。

二、研究內容與方法

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

三、離散數學中經典案例的建模算法

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

（一）建模過程

1.問題描述

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

2.問題分析

根據題意我們可以得出一下結論：三樣東西必須都過河，但是一次只能載一個;若農夫不在場，狼羊不能在一起，羊草不能在一起，而狼草可以在一起。

3.模型建立

我們可將農夫和狼羊草過河問題抽象成圖論問題來解決。假設農夫、狼、羊、草在此岸的狀態依次都為1，成功渡河后狀態依次都為0。最終方案就是初始狀態（1111）→結束狀態（0000）所經過的路徑。我們可列出16種在岸上的狀態，如下表所示：

根據題意可知紅色的6種狀態是不允許出現的。我們構造一個連通圖，直觀表達出遍歷的最短路徑，10種狀態為頂點，每次過河用有向邊表示，如下圖所示。

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

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

（二）算法實現

1.算法設計

近幾年，《農夫和狼羊草過河問題》吸引了很多編程愛好者的研究，也給出了的很多算法設計，可謂是仁者見仁智者見智，總結來基本是用遞歸法、廣度優先搜索（BFS）法和深度優先搜索（DFS）法三種方法。以深度優先搜索（DFS）為例，首先建立結點，包含農夫、狼、羊、草四個屬性，最初狀態均是1。設visited數組對已訪問的頂點進行標記（圖的遍歷），逐層存放下一步可能的安全狀態;設isSafe函數確定狀態的安全性，通過位置分布的代碼來判斷當前狀態是否安全，不安全返回false，否則返回true;調用遞歸函數遍歷Visited數組，標記該狀態是否已訪問過，若訪問過，則記錄前驅狀態值，直至輸出安全路徑。

2.編程運行結果

對于軟件工程專業學生可結合數據結構知識，利用C++、Java、Python三種程序語言都可以得出運行結果。

四、結語

在軟件工程專業的離散數學課程中加入案例的建模算法，正好彌補了軟件工程專業只會編程不會問題建模的短板;通過建模算法的案例教學實踐，課下討論互動多了，有效地調動學生主動學習的積極性和自我挑戰精神;離散數學與軟件工程專業課程的學科交叉和知識點融合，潛移默化的增強了綜合素質，實現離散數學理論的應用推廣，提高了教學效果。雖然建模算法案例在離散數學教學中初見成效，但教學方法和案例選取上需要進一步完善和研究。

參考文獻：

[1]王衛紅，李曲，鄭宇軍，等.離散數學.北京：清華大學出版社，2013.

[2]耿素云，屈婉玲，張立昂.離散數學.北京：清華大學出版社，2013.

[3]屈婉玲，劉田，張立昂，等.算法設計與分析.北京：清華大學出版社，2016.

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

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

[6]彭穎君.基于數學思維與計算機應用能力培養的“離散數學”教學設計.科學文匯，2016（4）：40-41.

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

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

[9]甄鵬華，于振梅.計算機科學中的算法設計與數據結構的離散性.微型機與應用，2016，35（22）：18-21.

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

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