賈 穎，方 向，劉欣榮

（山東工商學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，山東 煙臺 264005）

0 引言

在當(dāng)前信息技術(shù)、互聯(lián)網(wǎng)技術(shù)、大數(shù)據(jù)、人工智能技術(shù)大規(guī)模沖擊傳統(tǒng)產(chǎn)業(yè)，以新技術(shù)、新業(yè)態(tài)、新產(chǎn)業(yè)為特點的新經(jīng)濟蓬勃發(fā)展形勢下，高校如何培養(yǎng)具備更高創(chuàng)新創(chuàng)業(yè)能力和跨界整合能力的新型工程技術(shù)人才，已成為當(dāng)前高等院校工程教育改革的重中之重。在此背景下，“新工科”的概念應(yīng)運而生，經(jīng)歷了“復(fù)旦共識”“天大行動”“北京指南”三步走[1]，人們對于新工科的內(nèi)涵、特征和建設(shè)發(fā)展的路徑已經(jīng)有了統(tǒng)一的認(rèn)識。新工科教育如何落地，需要高校從專業(yè)設(shè)置、人才培養(yǎng)方案、教學(xué)內(nèi)容、教學(xué)方法與手段各個方面進行改革。工程教育認(rèn)證畢業(yè)要求的12條能力[2]正是一個工程專業(yè)是否達(dá)到新工科人才培養(yǎng)目標(biāo)的準(zhǔn)繩。新工科是工科專業(yè)和信息技術(shù)的深度融合，對于非計算機專業(yè)的工科專業(yè)，計算機通識課在新工科人才培養(yǎng)過程中扮演著重要的角色。如何使計算機通識課支撐工程教育認(rèn)證的12 條畢業(yè)能力要求[2]，是計算機通識課程改革亟待思考的問題。

1 新工科建設(shè)對大學(xué)計算機課程改革的新要求

大學(xué)計算機作為全校公共基礎(chǔ)課，是大學(xué)生入學(xué)接觸的第一門計算機課，對學(xué)生建立計算思維、數(shù)字化思維方式起著重要作用。大學(xué)計算機為學(xué)生將來的專業(yè)課學(xué)習(xí)提供了一種強有力的思維工具，幫助學(xué)生建立在面對專業(yè)問題求解時應(yīng)有的信息素養(yǎng)。

新工科要求學(xué)生具有復(fù)雜工程問題解決能力，這就要求大學(xué)計算機教學(xué)要堅持問題導(dǎo)向的教學(xué)模式，通過實際案例，培養(yǎng)學(xué)生的問題求解能力。同時，大學(xué)計算機是面向各專業(yè)的通識課程，應(yīng)該注重計算機問題求解的通用能力培養(yǎng)，即抽象、建模、自動化。

新工科要求學(xué)生具有學(xué)科交叉融合能力。新工科培養(yǎng)復(fù)合型人才，不僅在某一學(xué)科專業(yè)上學(xué)業(yè)精深，而且還具有“學(xué)科交叉融合”的特征[3]。學(xué)科融合不是簡單的計算機應(yīng)用，而是計算思維給廣泛的學(xué)科問題求解所帶來的一種思想、策略、方式和手段上的變化[4]。因此，大學(xué)計算機教學(xué)要從思想、方法、策略的高度教授學(xué)生計算機問題求解的通用方法。

2 新工科與計算思維

大學(xué)計算機的教學(xué)目標(biāo)是培養(yǎng)計算思維。計算思維是2006 年由美國卡內(nèi)基·梅隆大學(xué)的周以真教授提出的，她指出計算思維是運行計算機科學(xué)的基礎(chǔ)概念進行問題求解、系統(tǒng)設(shè)計以及人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動。計算思維通常表現(xiàn)為人們在問題求解時對計算、算法、數(shù)據(jù)及其組織、程序、自動化等概念的潛意識的應(yīng)用[4]?？梢钥闯?，計算思維與新工科的人才培養(yǎng)目標(biāo)不謀而合。計算思維的主要方法：抽象、分解、簡約、遞歸等，就是復(fù)雜工程問題求解的基本方法，而計算思維的本質(zhì)是抽象、建模、自動化，就是工程問題計算機求解的一般思路。

3 新工科+工程教育認(rèn)證背景下大學(xué)計算機教學(xué)案例設(shè)計

為了達(dá)到新工科的人才培養(yǎng)目標(biāo)，大學(xué)計算機的教學(xué)要具有跨學(xué)科特征，教學(xué)案例要體現(xiàn)實用性和普遍性。教學(xué)案例要擺脫純數(shù)學(xué)的、理想化的情景設(shè)置，并要將日常生活和工作中的各種問題求解背后隱藏的算法原理揭示出來。大學(xué)計算機教學(xué)要將工程教育認(rèn)證中對學(xué)生素質(zhì)的基本要求結(jié)合到教學(xué)案例中，將復(fù)雜問題求解的常用思想和方法融入教學(xué)案例。

3.1 將復(fù)雜問題分而治之的思想

分治是把一個復(fù)雜的問題分解成若干個相對獨立而規(guī)模較小的子問題，如果子問題還是比較復(fù)雜，再把子問題分解成更小的子問題，直到分解后的每個子問題都能簡單地直接求解為止[4]。如果子問題只是規(guī)模較小的原問題，則可以采用遞歸的方法解決。分治的思想廣泛地應(yīng)用于復(fù)雜問題求解方案中，通過一個案例——快速排序，展示分治和遞歸的計算機實現(xiàn)。

排序是日常生活和工作中常常要面對的問題。商品按價格高低排序，姓名按拼音字母順序排序，電影按評分高低排序，電子郵件按收到的時間排序等?？焖倥判蚴且环N利用分治的思想對一個序列進行排序的有效手段。它的方法是，用序列中的一個數(shù)（通常取第一個數(shù)）將序列分成左右兩部分，使左邊的數(shù)都小于或等于這個數(shù)，而右邊的數(shù)都大于或等于這個數(shù)，這樣原序列就被分割成了兩個獨立的子序列。再分別對這兩個獨立的子序列采用上述的方法進行分割，直到子序列里只有一個數(shù)，不能再分割，這時原序列就已經(jīng)排好序了。這個過程是遞歸的?？焖倥判虻钠骄鶗r間復(fù)雜度是nlogn，是最有效的排序算法之一。快速排序非常好地體現(xiàn)了分而治之的思想，即將大問題分解為互相獨立的小問題再逐個擊破。分治的思想在復(fù)雜的大工程建設(shè)和人事組織機構(gòu)的管理中都是很重要的思想。

3.2 并行處理的思想

通常能實現(xiàn)分治的問題，就可以采用并行處理來提高效率。例如，快速排序?qū)⒁粋€大的序列分成了相互獨立的兩個序列，在單處理器的情況下，這兩個序列是被依次處理，效率還不是很高。因為兩個序列相互獨立，如果被并行處理，效率將大大提高?？焖倥判蛩惴ú⑿谢囊粋€簡單思想是，對每次劃分過后所得的兩個序列分別使用兩個處理器完成遞歸排序。例如對一個長度為n的序列，首先劃分得到長度為n/2 的序列，將其交給兩個處理器分別處理；然后進一步化為得到4 個長度為n/4 的序列，再分別交給4 個處理器處理；如此遞歸下去最終得到排序好的序列[5]。目前的計算機CPU 一般采用多核技術(shù)，利用并行的方法提高計算機運行速度。在大項目的處理上，還會用到多機分布式系統(tǒng)。對于分治和并行，最主要考慮的是負(fù)載均衡，合理分配任務(wù)和資源。

3.3 縮小問題求解范圍的思想

簡而言之，就是在尋找解的過程中，重復(fù)地將解的可能范圍縮小，直到可以直接找到解為止[6]。日常生活中，經(jīng)常遇到這樣的問題，比如警察破案尋找兇手，需要逐漸縮小嫌疑人的范圍；從一批產(chǎn)品中找出殘次品，也需要縮小查找范圍。教學(xué)案例——折半查找法，很好地詮釋了這一思想。折半查找的思想是：要在一組按升序排列的n個元素{K1，K2，…，Kn}中查找關(guān)鍵字K，先取中間元素元素km將序列大致平分為兩個部分{ K1，K2，,…，Km-1}和{Km+1，Km+2，…，Kn}。將km和要查找的關(guān)鍵字K作比較，比較結(jié)果有以下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 最小成本的思想

在城市間架設(shè)通訊網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、物流網(wǎng)絡(luò)的時候，通常在考慮連通性的同時，也要考慮最小成本問題。教學(xué)案例——求賦權(quán)圖的最小代價生成樹，就很好地解決了這個問題。

可以將城市之間架設(shè)的通訊網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、物流網(wǎng)絡(luò)想象成為一個賦權(quán)圖，兩個城市之間架設(shè)網(wǎng)絡(luò)的造價就是圖中兩點之間邊的權(quán)值。圖G 的最小代價生成樹T 滿足如下特征：

T 包含G 的所有頂點。

T 為連通圖。

T 包含的邊數(shù)最少。

T 各邊的權(quán)值之和最小。

求一個賦權(quán)圖的最小代價生成樹的方法，筆者會給學(xué)生介紹Kruskal 算法和Prim 算法，這兩種算法都屬于貪心算法。對于一個具有n個頂點的連通圖，兩者都是從樹T 為空開始，逐條加入n-1 條邊，最后得到該圖的最小代價生成樹。

Kruskal 算法的基本思想是對于具有n個頂點的賦權(quán)圖G，將圖中的邊按權(quán)值由小到大的順序選取，若選擇該邊后不形成回路，則保留該邊，若形成回路，則除去該邊，直到選夠n-1 條邊為止，即可得到圖的最小代價生成樹T。T 的各邊代價之和，就是將圖G 中所有頂點的連通的最小代價。

Prim 算法較為復(fù)雜，在此不再贅述。

3.5 環(huán)保意識和節(jié)約意識

工程教育認(rèn)證的12 條畢業(yè)要求中指出，要求畢業(yè)生能夠理解和評價復(fù)雜工程問題的專業(yè)工程實踐對環(huán)境、社會可持續(xù)發(fā)展的影響[2]。節(jié)約、高效、性價比是學(xué)生在復(fù)雜工程問題解決方案設(shè)計和評價中應(yīng)當(dāng)考慮的問題。在大學(xué)計算機教學(xué)中，算法的時間復(fù)雜度和空間復(fù)雜度計算能讓學(xué)生更好地理解和體會節(jié)約、高效的重要性。這個教學(xué)目標(biāo)是由教學(xué)案例——“比較桶排序、冒泡排序和快速排序的算法復(fù)雜度”完成的。

排序的算法有很多種，沒有哪一種是絕對好或絕對不好的，要看具體的應(yīng)用場景而定。要對一個n個元素的序列進行升序排序，桶排序的基本思想是：創(chuàng)建m個桶，每一個桶代表一個區(qū)間范圍，里面可以承載一個或多個元素。這些桶代表的區(qū)間范圍是由小到大并且連續(xù)的。然后遍歷原始序列，把每個元素對號入座放入各個桶中，如果每個桶中的元素個數(shù)大于1，則每個桶內(nèi)部的元素再分別排序，這時可以隨意選擇合適排序算法。最后遍歷所有的桶，依次輸出各個桶中元素，則完成排序。桶排序是一種速度很快的排序算法，將待排序集合中的元素映射到各個桶上的過程并不存在元素之間的比較和交換操作。分析一下算法時間復(fù)雜度：創(chuàng)建m個桶需要m次運算，將n個元素映射到桶內(nèi)需要n次運算，桶內(nèi)排序采用歸并排序的話，每個桶內(nèi)的元素平均個數(shù)為n/m個，因此總的時間復(fù)雜度為即O(m+n+n(log2n-log2m))?？梢钥闯鐾芭判虻臅r間復(fù)雜度是線性的。再來分析其空間復(fù)雜度，桶排序需要申請額外的存儲空間作為桶來保存元素。當(dāng)待排序的元素值大小相差較大且分布不均時，需要的桶的數(shù)量較大，且存在大量的空桶，存儲空間浪費極大。因此，桶排序比較適合對元素比較集中的序列排序。

冒泡排序是一種經(jīng)典的排序算法。它的基本思想是：每次比較兩個相鄰的元素，如果它們的順序錯誤就把它們交換過來。n個元素{K1，K2，…，Kn}進行冒泡升序排序，第一遍，從最后一個元素Kn開始，相鄰的兩個元素比較大小，小的元素冒到上面（兩個數(shù)進行交換），第一遍結(jié)束之后，最小的數(shù)被冒到第一個位置，共進行了n-1 次比較。第二遍，對剩下的{K2，…，Kn}進行冒泡排序，將次小的元素冒到第二個位置，共進行n-2 次比較。依次進行上述過程，直到倒數(shù)第二小的元素也歸位。這時共進行了n-1 遍的冒泡排序，共發(fā)生的比較次數(shù)為(n-1)+(n-2)+…+1，即n(n-1)/2 次。因此，冒泡排序的時間復(fù)雜度為O(n2)。冒泡排序是一個時間復(fù)雜度非常高的排序算法。假如我們的計算機每秒中可以運行10 億次，那么對1 億個數(shù)進行排序，桶排序只需要0.1 秒，而冒泡排序則需要1 千萬秒，長達(dá)115天之久。對于空間復(fù)雜度來說，因為冒泡排序是原地排序，所以空間復(fù)雜度就是O(n)，并且冒泡排序?qū)Υ判驍?shù)據(jù)的范圍和分布都沒有要求。

快速排序的基本思想前面已經(jīng)介紹過，相比冒泡排序的相鄰兩個數(shù)交換，快速排序每次交換是跳躍式的，平均時間復(fù)雜度是nlog2n。快速排序的分割元素選擇非常重要，當(dāng)分割元素可以將待排序序列大致地平均分為兩部分時，快速排序算法執(zhí)行是最快的。如果選擇不當(dāng)，分割元素總是將原序列分為長度為0 和長度為n-1 兩部分，那么快速排序的時間復(fù)雜度將和冒泡排序相同。快速排序也是原地排序，所以空間復(fù)雜度也是O(n)。

通過比較3 種排序算法的時間復(fù)雜度和空間復(fù)雜度，學(xué)生可以學(xué)習(xí)到一個問題可以有多個解決方法，沒有哪個方法是永遠(yuǎn)最優(yōu)的，要根據(jù)問題的實際情況選擇最適合的解決方法。

4 結(jié)語

上述案例雖然沒有特別明顯的專業(yè)知識情景，卻體現(xiàn)了復(fù)雜問題求解中具有共性的方法和思路。學(xué)生們可以通過這些案例，以小見大，舉一反三，將這些通用的思維方式應(yīng)用到自己的專業(yè)領(lǐng)域問題求解和日常生活問題解決當(dāng)中。

這些案例存在不足之處：體現(xiàn)了通用的問題求解思路，但缺乏問題導(dǎo)入的案例情景，缺乏代入感和親切感，可能導(dǎo)致學(xué)生學(xué)習(xí)興趣不高或遷移能力差。這是下一步需要解決的問題。

新工科建設(shè)明確了大學(xué)計算機通識課為專業(yè)問題求解提供思想、方法和技術(shù)上的支持的教學(xué)目標(biāo)。在進一步的教學(xué)實踐中，我們將繼續(xù)挖掘計算思維與專業(yè)問題求解的結(jié)合點，給予新工科建設(shè)更好的支持。