新工科+工程教育认证背景下的大学计算机教学案例设计

贾 颖，方 向，刘欣荣

（山东工商学院 计算机科学与技术学院，山东 烟台 264005）

0 引言

在当前信息技术、互联网技术、大数据、人工智能技术大规模冲击传统产业，以新技术、新业态、新产业为特点的新经济蓬勃发展形势下，高校如何培养具备更高创新创业能力和跨界整合能力的新型工程技术人才，已成为当前高等院校工程教育改革的重中之重。在此背景下，“新工科”的概念应运而生，经历了“复旦共识”“天大行动”“北京指南”三步走[1]，人们对于新工科的内涵、特征和建设发展的路径已经有了统一的认识。新工科教育如何落地，需要高校从专业设置、人才培养方案、教学内容、教学方法与手段各个方面进行改革。工程教育认证毕业要求的12条能力[2]正是一个工程专业是否达到新工科人才培养目标的准绳。新工科是工科专业和信息技术的深度融合，对于非计算机专业的工科专业，计算机通识课在新工科人才培养过程中扮演着重要的角色。如何使计算机通识课支撑工程教育认证的12 条毕业能力要求[2]，是计算机通识课程改革亟待思考的问题。

1 新工科建设对大学计算机课程改革的新要求

大学计算机作为全校公共基础课，是大学生入学接触的第一门计算机课，对学生建立计算思维、数字化思维方式起着重要作用。大学计算机为学生将来的专业课学习提供了一种强有力的思维工具，帮助学生建立在面对专业问题求解时应有的信息素养。

新工科要求学生具有复杂工程问题解决能力，这就要求大学计算机教学要坚持问题导向的教学模式，通过实际案例，培养学生的问题求解能力。同时，大学计算机是面向各专业的通识课程，应该注重计算机问题求解的通用能力培养，即抽象、建模、自动化。

新工科要求学生具有学科交叉融合能力。新工科培养复合型人才，不仅在某一学科专业上学业精深，而且还具有“学科交叉融合”的特征[3]。学科融合不是简单的计算机应用，而是计算思维给广泛的学科问题求解所带来的一种思想、策略、方式和手段上的变化[4]。因此，大学计算机教学要从思想、方法、策略的高度教授学生计算机问题求解的通用方法。

2 新工科与计算思维

大学计算机的教学目标是培养计算思维。计算思维是2006 年由美国卡内基·梅隆大学的周以真教授提出的，她指出计算思维是运行计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算思维通常表现为人们在问题求解时对计算、算法、数据及其组织、程序、自动化等概念的潜意识的应用[4]。可以看出，计算思维与新工科的人才培养目标不谋而合。计算思维的主要方法：抽象、分解、简约、递归等，就是复杂工程问题求解的基本方法，而计算思维的本质是抽象、建模、自动化，就是工程问题计算机求解的一般思路。

3 新工科+工程教育认证背景下大学计算机教学案例设计

为了达到新工科的人才培养目标，大学计算机的教学要具有跨学科特征，教学案例要体现实用性和普遍性。教学案例要摆脱纯数学的、理想化的情景设置，并要将日常生活和工作中的各种问题求解背后隐藏的算法原理揭示出来。大学计算机教学要将工程教育认证中对学生素质的基本要求结合到教学案例中，将复杂问题求解的常用思想和方法融入教学案例。

3.1 将复杂问题分而治之的思想

分治是把一个复杂的问题分解成若干个相对独立而规模较小的子问题，如果子问题还是比较复杂，再把子问题分解成更小的子问题，直到分解后的每个子问题都能简单地直接求解为止[4]。如果子问题只是规模较小的原问题，则可以采用递归的方法解决。分治的思想广泛地应用于复杂问题求解方案中，通过一个案例——快速排序，展示分治和递归的计算机实现。

排序是日常生活和工作中常常要面对的问题。商品按价格高低排序，姓名按拼音字母顺序排序，电影按评分高低排序，电子邮件按收到的时间排序等。快速排序是一种利用分治的思想对一个序列进行排序的有效手段。它的方法是，用序列中的一个数（通常取第一个数）将序列分成左右两部分，使左边的数都小于或等于这个数，而右边的数都大于或等于这个数，这样原序列就被分割成了两个独立的子序列。再分别对这两个独立的子序列采用上述的方法进行分割，直到子序列里只有一个数，不能再分割，这时原序列就已经排好序了。这个过程是递归的。快速排序的平均时间复杂度是nlogn，是最有效的排序算法之一。快速排序非常好地体现了分而治之的思想，即将大问题分解为互相独立的小问题再逐个击破。分治的思想在复杂的大工程建设和人事组织机构的管理中都是很重要的思想。

3.2 并行处理的思想

通常能实现分治的问题，就可以采用并行处理来提高效率。例如，快速排序将一个大的序列分成了相互独立的两个序列，在单处理器的情况下，这两个序列是被依次处理，效率还不是很高。因为两个序列相互独立，如果被并行处理，效率将大大提高。快速排序算法并行化的一个简单思想是，对每次划分过后所得的两个序列分别使用两个处理器完成递归排序。例如对一个长度为n的序列，首先划分得到长度为n/2 的序列，将其交给两个处理器分别处理；然后进一步化为得到4 个长度为n/4 的序列，再分别交给4 个处理器处理；如此递归下去最终得到排序好的序列[5]。目前的计算机CPU 一般采用多核技术，利用并行的方法提高计算机运行速度。在大项目的处理上，还会用到多机分布式系统。对于分治和并行，最主要考虑的是负载均衡，合理分配任务和资源。

3.3 缩小问题求解范围的思想

简而言之，就是在寻找解的过程中，重复地将解的可能范围缩小，直到可以直接找到解为止[6]。日常生活中，经常遇到这样的问题，比如警察破案寻找凶手，需要逐渐缩小嫌疑人的范围；从一批产品中找出残次品，也需要缩小查找范围。教学案例——折半查找法，很好地诠释了这一思想。折半查找的思想是：要在一组按升序排列的n个元素{K1，K2，…，Kn}中查找关键字K，先取中间元素元素km将序列大致平分为两个部分{ K1，K2，,…，Km-1}和{Km+1，Km+2，…，Kn}。将km和要查找的关键字K作比较，比较结果有以下3 种可能：

K=km：查找成功，返回元素的序号m。

K＜km，折半查找子序列{K1，K2，,…，Km-1}。

K＞km，折半查找子序列{ Km+1，Km+2，…，Kn}。

一直对子序列按照上述原则进行查找，直到查找成功或者要查找的子序列长度为0（没找到）。

折半查找法每次将查找范围缩小为原来的1/2，n个元素的序列，查找成功的平均检索长度约等于log2(n+1)-1。如果在10 亿个排好序的元素中进行查找，平均检索长度是25 次。

3.4 最小成本的思想

在城市间架设通讯网络、交通网络、物流网络的时候，通常在考虑连通性的同时，也要考虑最小成本问题。教学案例——求赋权图的最小代价生成树，就很好地解决了这个问题。

可以将城市之间架设的通讯网络、交通网络、物流网络想象成为一个赋权图，两个城市之间架设网络的造价就是图中两点之间边的权值。图G 的最小代价生成树T 满足如下特征：

T 包含G 的所有顶点。

T 为连通图。

T 包含的边数最少。

T 各边的权值之和最小。

求一个赋权图的最小代价生成树的方法，笔者会给学生介绍Kruskal 算法和Prim 算法，这两种算法都属于贪心算法。对于一个具有n个顶点的连通图，两者都是从树T 为空开始，逐条加入n-1 条边，最后得到该图的最小代价生成树。

Kruskal 算法的基本思想是对于具有n个顶点的赋权图G，将图中的边按权值由小到大的顺序选取，若选择该边后不形成回路，则保留该边，若形成回路，则除去该边，直到选够n-1 条边为止，即可得到图的最小代价生成树T。T 的各边代价之和，就是将图G 中所有顶点的连通的最小代价。

Prim 算法较为复杂，在此不再赘述。

3.5 环保意识和节约意识

工程教育认证的12 条毕业要求中指出，要求毕业生能够理解和评价复杂工程问题的专业工程实践对环境、社会可持续发展的影响[2]。节约、高效、性价比是学生在复杂工程问题解决方案设计和评价中应当考虑的问题。在大学计算机教学中，算法的时间复杂度和空间复杂度计算能让学生更好地理解和体会节约、高效的重要性。这个教学目标是由教学案例——“比较桶排序、冒泡排序和快速排序的算法复杂度”完成的。

排序的算法有很多种，没有哪一种是绝对好或绝对不好的，要看具体的应用场景而定。要对一个n个元素的序列进行升序排序，桶排序的基本思想是：创建m个桶，每一个桶代表一个区间范围，里面可以承载一个或多个元素。这些桶代表的区间范围是由小到大并且连续的。然后遍历原始序列，把每个元素对号入座放入各个桶中，如果每个桶中的元素个数大于1，则每个桶内部的元素再分别排序，这时可以随意选择合适排序算法。最后遍历所有的桶，依次输出各个桶中元素，则完成排序。桶排序是一种速度很快的排序算法，将待排序集合中的元素映射到各个桶上的过程并不存在元素之间的比较和交换操作。分析一下算法时间复杂度：创建m个桶需要m次运算，将n个元素映射到桶内需要n次运算，桶内排序采用归并排序的话，每个桶内的元素平均个数为n/m个，因此总的时间复杂度为即O(m+n+n(log2n-log2m))。可以看出桶排序的时间复杂度是线性的。再来分析其空间复杂度，桶排序需要申请额外的存储空间作为桶来保存元素。当待排序的元素值大小相差较大且分布不均时，需要的桶的数量较大，且存在大量的空桶，存储空间浪费极大。因此，桶排序比较适合对元素比较集中的序列排序。

冒泡排序是一种经典的排序算法。它的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。n个元素{K1，K2，…，Kn}进行冒泡升序排序，第一遍，从最后一个元素Kn开始，相邻的两个元素比较大小，小的元素冒到上面（两个数进行交换），第一遍结束之后，最小的数被冒到第一个位置，共进行了n-1 次比较。第二遍，对剩下的{K2，…，Kn}进行冒泡排序，将次小的元素冒到第二个位置，共进行n-2 次比较。依次进行上述过程，直到倒数第二小的元素也归位。这时共进行了n-1 遍的冒泡排序，共发生的比较次数为(n-1)+(n-2)+…+1，即n(n-1)/2 次。因此，冒泡排序的时间复杂度为O(n2)。冒泡排序是一个时间复杂度非常高的排序算法。假如我们的计算机每秒中可以运行10 亿次，那么对1 亿个数进行排序，桶排序只需要0.1 秒，而冒泡排序则需要1 千万秒，长达115天之久。对于空间复杂度来说，因为冒泡排序是原地排序，所以空间复杂度就是O(n)，并且冒泡排序对待排序数据的范围和分布都没有要求。

快速排序的基本思想前面已经介绍过，相比冒泡排序的相邻两个数交换，快速排序每次交换是跳跃式的，平均时间复杂度是nlog2n。快速排序的分割元素选择非常重要，当分割元素可以将待排序序列大致地平均分为两部分时，快速排序算法执行是最快的。如果选择不当，分割元素总是将原序列分为长度为0 和长度为n-1 两部分，那么快速排序的时间复杂度将和冒泡排序相同。快速排序也是原地排序，所以空间复杂度也是O(n)。

通过比较3 种排序算法的时间复杂度和空间复杂度，学生可以学习到一个问题可以有多个解决方法，没有哪个方法是永远最优的，要根据问题的实际情况选择最适合的解决方法。

4 结语

上述案例虽然没有特别明显的专业知识情景，却体现了复杂问题求解中具有共性的方法和思路。学生们可以通过这些案例，以小见大，举一反三，将这些通用的思维方式应用到自己的专业领域问题求解和日常生活问题解决当中。

这些案例存在不足之处：体现了通用的问题求解思路，但缺乏问题导入的案例情景，缺乏代入感和亲切感，可能导致学生学习兴趣不高或迁移能力差。这是下一步需要解决的问题。

新工科建设明确了大学计算机通识课为专业问题求解提供思想、方法和技术上的支持的教学目标。在进一步的教学实践中，我们将继续挖掘计算思维与专业问题求解的结合点，给予新工科建设更好的支持。