基于软件工程专业《离散数学》课程中建模算法的研究

魏文英 杨翠 李小敏 刘翠焕 张波

摘 要：针对应用型本科高校软件工程专业离散数学课程教学过程中存在的问题，分析原因所在，提出建模算法思维的引入，将经典问题的建模过程和算法求解融入教学中，提高学生算法设计能力，从而系统地帮助学生用专业知识解决实际问题，打通离散数学与软件工程专业之间的任督二脉。

关键词：软件工程;离散数学;建模算法;案例;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—），女，汉族，河北石家庄人，讲师，研究方向：软件开发。