工程教育專業(yè)認證下的“算法分析與設計”課程教學改革與實踐

劉利敏，晏 軻

（湖北第二師范學院 計算機學院，武漢 430205）

1 引言

為了切實提高高等教育教學質(zhì)量、實現(xiàn)工程教育國際互認，我國2016年正式加入了《華盛頓協(xié)議》。工程教育認證強調(diào)以學生為中心、以成果為導向（Outcomes-based Education，OBE）和持續(xù)改進的理念，面對畢業(yè)生制定了12條要求，包括工程知識、問題分析、設計/開發(fā)解決方案、個人和團隊、終身學習等。[1]12條畢業(yè)要求可以概括為四個方面的能力：知識與技能、分析與設計、人文與素養(yǎng)、協(xié)作與學習。在工程教育專業(yè)背景下，教育目標圍繞學生培養(yǎng)，教學設計聚焦學生能力的培養(yǎng)，師資與教育資源滿足學生學習效果的達成；評價的焦點是對學習效果的評價。通過12條認證標準，對專業(yè)學生培養(yǎng)目標、質(zhì)量、師資隊伍、課程設置、實驗設備、教學管理、各種教學文件及原始資料等方面進行規(guī)范化評估，最終實現(xiàn)“以人為本”、成果導向的教育目標及質(zhì)量持續(xù)改進的培養(yǎng)機制。

湖北第二師范學院計算機科學與技術專業(yè)2017年開始籌備申報工程教育專業(yè)認證，并于2020年獲批國家一流專業(yè)。在工程教育專業(yè)認證及專業(yè)人才培養(yǎng)的雙重驅(qū)動下，為實現(xiàn)“以全體學生為中心”、能力提升及持續(xù)改進的教育理念，開展了“算法分析與設計”的教學改革與實踐。制定了工程教育背景下的課程教學目標、教學內(nèi)容，教學方法及評價指標體系，并進行目標達成計算，分析教學改革效果及教育質(zhì)量評價。

2 課程特點及教學存在的問題

2.1 課程特點

“算法分析與設計”作為計算機科學與技術的核心專業(yè)課之一，先修課程包括：離散數(shù)學、高級程序設計語言、數(shù)據(jù)結構等。該課程總學時為40學時，其中理論24學時，實踐16學時。課程涉及多種經(jīng)典算法求解策略的學習及典型問題的應用求解，算法策略包括：蠻力法、遞歸分治、動態(tài)規(guī)劃、貪心算法、回溯法及分支限界法等，典型問題包括：0/1背包問題、電路布線、TSP旅行商、多機調(diào)度、流水作業(yè)、裝載問題、活動安排、硬幣找零問題等，課程內(nèi)容多、難度較大，需要學生具備較強的邏輯思維及動手實踐能力。[2]其次，該課程對學生先修課程的掌握程度要求較高，很多算法思想及問題求解需要數(shù)據(jù)結構課程支撐，如分治算法中的快速排序、合并排序及二分查找，貪心算法中的哈夫曼編碼、Dijkstra單源最短路徑等問題都在數(shù)據(jù)結構課程中涉及，分支限界算法需要通過FIFO隊列或優(yōu)先隊列實現(xiàn)，回溯法需要DFS深度優(yōu)先搜索的知識基礎。再次，算法學習的最終目的是應用及解決問題，因此該課程對學生動手實踐能力要求較高，要求學生在充分理解需求的基礎上，選擇合適的數(shù)據(jù)結構及算法求解策略，通過方案設計、優(yōu)化及編碼實踐輸出結果，如果學生不具有扎實的編程基礎，在進行算法實踐方面也會存在一定的困難。

2.2 學生特點

學生普遍反映課程難度較大，通過調(diào)研分析發(fā)現(xiàn)：部分同學邏輯分析能力有限、無法建立算法思維，不能做到理論聯(lián)系實際；部分同學難以深刻理解算法策略及思路，或?qū)λ惴ǖ睦斫夂蛻脙H停留在對已知問題的處理及實現(xiàn)上，無法做到理論聯(lián)系實際；部分同學編程基礎薄弱，無法將算法思想進行工程實現(xiàn)；對于實際工程問題，無法通過比較、評價、優(yōu)化，綜合設計最優(yōu)方案；部分同學反映經(jīng)過大量實踐訓練，可有效增強對算法理論的理解及編碼實踐能力。對接受工程認證的計算機科學與技術專業(yè)近3年的學生課程結束后進行問卷調(diào)查，具體結果如表1。

表1 近3年計算機科學與技術專業(yè)學生調(diào)查問卷

2.3 課程教學問題

通過分析課程和學生特點，可以發(fā)現(xiàn)課程教學過程中存在如下問題：第一，如何兼顧算法基礎理論和學科前沿；第二，如何解決課時有限與課程難度大、內(nèi)容多、學生實踐創(chuàng)新不夠充分的矛盾；第三，如何在學生深入理解算法理論的基礎上，增強學生對算法思想及代碼實踐對應關系的理解，譬如掌握子集樹的回溯法DFS搜索過程以及代碼遞歸框架的對應；第四，如何引導學生把握算法課程整體體系，深入理解不同算法的求解策略及差異，掌握算法之間的邏輯關系及適用場景；第五，如何以學生為中心，針對具體的問題、激發(fā)學生主動思考，項目小組研討、方案設計及代碼實踐，綜合提升學生利用算法解決實際問題的能力。

3 基于能力提升及OBE理念的教學改革

工程教育專業(yè)背景下，課堂教學目標圍繞學生培養(yǎng)，教學設計聚焦能力提升，課程評價圍繞能力效果的評價，師資及教學以滿足學習效果達成為要目的。結合課程及學生特點，通過深化課程教學改革，提高教學質(zhì)量，達成培養(yǎng)目標。針對以上存在的問題，在能力素養(yǎng)提升及OBE理念驅(qū)動下，根據(jù)“算法分析與設計”課程的特點，通過專題探究、課程小組討論及網(wǎng)絡平臺線上線下混合式教學方法，重構教學目標、重組教學內(nèi)容、創(chuàng)新教學方法和改進評價指標體系等幾個方面進行改革，并利用青軟U+平臺進行課程目標達成度分析。

3.1 工程教育背景下培養(yǎng)目標

為達成工程教育人才培養(yǎng)理念，制定算法分析與設計課程培養(yǎng)目標：培養(yǎng)學生系統(tǒng)掌握算法研究領域的基本概念與原理，理解和掌握常用算法的設計策略、算法差異、適用場景、算法的復雜度分析；增強學生的邏輯思維能力及終身學習能力；針對復雜工程問題，能夠綜合運用所學，獨立地以計算機算法視角分析問題，通過比較、評價、優(yōu)化，設計出最優(yōu)算法解決方案，開發(fā)滿足符合軟件項目需求的系統(tǒng)模塊或算法流程。具體可細化為3個目標，對應支撐畢業(yè)要求的1.4（工程知識，H支撐）、2.3（問題分析，H支撐）及3.2（設計/開發(fā)解決方案能力，M支撐）。同時引入思政元素，強化課程育人導向，堅持立德樹人，綜合運用啟發(fā)式教學、討論式教學、混合式教學、課外自學等教學模式，將與課程相關行業(yè)應用現(xiàn)狀、行業(yè)法律案例、行業(yè)關注熱點、社會文化趨勢等融合到課程學習中，引導學生探討相關問題，形成正確的人生觀、價值觀以及職業(yè)道德，培養(yǎng)學生嚴密的邏輯思維、吃苦耐勞的精神及終身學習的意識。

3.2 教學內(nèi)容改革

當前大部分算法分析與設計的教材的教學內(nèi)容，主要集中在三部分：一是算法基礎理論及復雜度分析；二是經(jīng)典算法求解策略以及典型問題的求解應用，包括分治遞歸、動態(tài)規(guī)劃、貪心、回溯及分支限界等；三是困難問題的求解，包括隨機算法、概率算法和近似算法、計算機NP復雜性理論等。但對當前學科的一些新型算法及研究熱點鮮有涉及，但該部分對實際工程問題求解及科學研究而言都是非常重要的手段。

為培養(yǎng)創(chuàng)新人才，服務學生后期發(fā)展及能力提升，對課程教學內(nèi)容進行改革。從學科特點出發(fā)，兼顧基礎理論及學科前沿，在傳統(tǒng)授課內(nèi)容的基礎上，引入一些學科研究熱點及相關應用成果的介紹，引導學生關注學科領域前沿動態(tài)、拓寬科技視野，增強科學素養(yǎng)；同時融入思政元素，深化學生職業(yè)理想和職業(yè)道德教育，培養(yǎng)學生良好的職業(yè)品格并自覺實踐和職業(yè)規(guī)范。當前人工智能在很多領域應用成效顯著，如醫(yī)療、科技、金融、智能家居等，且已上升到國家戰(zhàn)略；因此在傳統(tǒng)算法基礎及內(nèi)容學習的基礎上，引入關于機器學習、人工智能及深度學習理論及相關應用的內(nèi)容，包括分類、聚類、回歸、推薦等。同時為了培養(yǎng)學生主動學習的能力，布置學生查閱若干機器學習及人工智能應用項目案例，組織學生分組協(xié)作討論、分享；在掌握學科基本理論的基礎上，加深對學科前沿內(nèi)容的理解。

3.3 教學模式改革

課程從培養(yǎng)學生計算機算法思維出發(fā)，培養(yǎng)學生解決復雜工程問題的能力，讓學生能夠綜合運用所學，進行算法比較、評價、優(yōu)化、設計，并編碼實踐開發(fā)解決問題的算法模塊。注重以“學生為中心”，實現(xiàn)OBE理念的“成果導向”，設計了融合專題探究、課程小組討論、項目驅(qū)動及混合式的教學模式，具體如下。

3.3.1 專題探究

專題教學是實現(xiàn)教材體系向教學體系轉(zhuǎn)變。主流算法教材在內(nèi)容組織主要以算法策略為邏輯單元，以王曉東編著的《計算機算法設計與分析》（第5版）為例，第一章算法概述、第二章遞歸與分治策略、第三章動態(tài)規(guī)劃等。某些問題可以利用多種算法求解，所以在傳統(tǒng)按照算法策略為邏輯單元的教學組織中，在不同算法章節(jié)中分別學習該問題的求解。如0/1背包問題，在動態(tài)規(guī)劃法、回溯法以及分支限界法中，又分別進行了學習。但這樣的授課方法，學生無法對該問題的多種不同的求解策略進行深入對比分析。而專題教學，可以突破按章節(jié)體系依序授課的局限，把相關教學內(nèi)容進行整合、提煉、概括充實，形成獨立專題，可以增強不同算法策略過程及復雜度的對比分析，加深學生對問題的理解。根據(jù)課程內(nèi)容，在以算法策略為邏輯單元學習的基礎上，增設部分專題，如：0/1背包多算法求解專題、復雜裝載問題多算法求解專題、硬幣找零問題多算法求解專題等。通過對比專題問題不同算法的求解思路、求解過程、求解結果及算法復雜度分析，加深學生對不同算法策略及適應情形的理解和掌握。

例如：0/1背包專題，分別利用動態(tài)規(guī)劃、回溯法、分支限界法進行問題求解，分析算法策略及編碼方法，并進行不同方法的對比及復雜度分析；同時討論是否可以利用貪心算法進行求解，以及存在的問題。硬幣找零問題：如現(xiàn)有硬幣面值1元、3元、4元，需要找零6元，請問如何找零使得硬幣個數(shù)最少？分別利用蠻力法、貪心算法、動態(tài)規(guī)劃算法進行方案設計；可以發(fā)現(xiàn)貪心算法需要3枚硬幣，dp算法需要2枚硬幣，得最優(yōu)解不同，對比分析不同算法求解差異及算法復雜度，得出哪些算法適合求解該問題的結論。

3.3.2 課程小組討論及項目實踐

為提高學生在課程教學中的參與度，構建“以學生為中心”的教學理念，教師根據(jù)班級人數(shù)劃分課程學習小組，每組人數(shù)控制在6人左右。教師發(fā)布若干討論主題及實際工程項目任務，各小組領取相關任務。通過組內(nèi)討論協(xié)作的方式，完成主題討論、實際工程項目的實踐及演示答辯。通過討論及項目答辯演示環(huán)節(jié)，增強學生表達能力、團隊合作能力及獨立學習解決問題的能力。

3.3.3 項目驅(qū)動

表1調(diào)研結果表明，算法學習效果好的學生，在課下均進行了大量實踐練習，實踐也可進一步增進對算法理論理解。為增強學生算法應用及實踐能力，課程利用“項目驅(qū)動”法，引入LeetCode 題庫，根據(jù)課程學習專題，布置LeetCode 的相關題目作為課后項目實踐。通過大量專題分類訓練，增強學生對算法思想的理解，讓學生建立起算法理論與代碼之間的轉(zhuǎn)換關系；在實踐形成自己求解方案的同時，學會借鑒學習優(yōu)秀解題思路，思考優(yōu)化及改進策略，提升解決實際問題的能力。

3.3.4 混合式教學

為增強學生自主學習及分析問題的意識，通過混合式模式將傳統(tǒng)課堂教學及在線學習平臺相結合。[3]課前發(fā)布MOOC 視頻學習任務、思考及討論題；課上通過引入思考及組織討論，重點介紹算法思想及問題求解思路，并針對線上學習難點進行答疑，通過“重點+難點”相結合的方法提升學生學習效果；課后布置作業(yè)任務，包括算法分析涉及類題目及LeetCode平臺實踐等。此外算法學習較為抽象，在教學過程中要注重理論聯(lián)系實際，將抽象的問題轉(zhuǎn)換成實際問題，一方面易于激發(fā)學生的學習興趣，另一方面也易于理解。如最小生成樹問題，可以通過如下案例：若干個城市修建高鐵，城市之間修建成本已知，規(guī)劃一個修建方案使得成本最低？單源最短路徑問題，[4]可以如下案例說明：已知若干個城市之間的連同關系及交通成本，指定一個城市作為出發(fā)點分別去其他城市旅游，求解到其他城市各自的最短路徑及線路。

3.4 評價指標與體系改革

工程教育認證強調(diào)學生能力提升及學習效果達成評價，考核要求針對全體學生可量化的能力評價，既包括過程性評價又包括綜合性評價。針對如上要求，對該課程評價手段進行設計，主要包括四個方面，具體見表2。

隨堂測試、討論及作業(yè)環(huán)節(jié)。課程討論、課堂測驗，主要來源于課前預習或課堂授課環(huán)節(jié)。通過在線學習平臺發(fā)布問題，引導學生思考參與討論，構建開放式、問題式及對話式課堂環(huán)境；發(fā)布測驗，考查學生對問題的理解及應用。課后作業(yè)，主要是課堂內(nèi)容的延伸和深化，要求學生針對具體問題進行更為深入的思考、設計及對比分析，作業(yè)布置如案例1。學生測驗、討論及課后作業(yè)，可通過在線學習平臺進行采集記錄；該部分占總評分的10%。

課堂小組項目實踐及演示，該部分主要考查學生的團隊協(xié)作能力、問題分析及算法設計能力、算法分析及創(chuàng)新能力、代碼編寫實踐能力以及演示答辯時PPT組織、演講表達能力等；該部分占總評分的10%。

實驗環(huán)節(jié)，共包括8個設計類實驗，培養(yǎng)學生應用分治、動態(tài)規(guī)劃、貪心、回溯及分支限界等算法思想解決實際問題并進行編程實踐的能力，該部分考核主要通過實驗驗收答辯及實驗報告。

期末考試，主要以閉卷形式考核學生利用所學算法理論、算法策略進行實際問題分析及方案設計的能力；題型以算法分析設計及程序分析設計題為主，客觀題不超過15%。

以上四個環(huán)節(jié)的考核，從過程與結果兩個層面對學生應用算法解決問題的能力進行考核，既包含了對算法知識理解、應用等初級認知學習的考核，也包括對問題進行分析、算法評價、優(yōu)化及創(chuàng)新方面深層認知學習的考核，同時也涉及了對學生個人和團隊、溝通、終身學習等非技術能力的考核。

4 課程目標達成計算

持續(xù)改進是推動課程教學質(zhì)量持續(xù)提升的基礎保障。教學效果評價聚焦課程目標的達成，通過達成度分析，發(fā)現(xiàn)當前教學存在的問題及不足，進行針對性持續(xù)改進。工程教育專業(yè)認證采用定量達成度評價授課對象對各課程目標的達成情況，[6]本課程4個考核環(huán)節(jié)對3個課程目標的支撐總評分及占比見表3。表3明確列出各課程目標的總評分M，以及4種考核對其支撐權重；如課程目標j，其總評得分為：

其中Ci為第i 種考核方式總評分，wij為第i 種考核方式對第j 種課程目標支撐權重。

表2 課程成績評價組成

本文以2019級計科專業(yè)86名學生的各分項成績，進行目標達成度計算。首先按照各考核環(huán)節(jié)相應的評分標準，評定每名學生的4種考核下的定量得分。利用表3中各考核指標對3個課程目標的支撐權重計算各課程目標達成得分，獲取每名學生各個課程目標的達成度A，計算公式見式（2）。

表3 課程目標達成考核與評價方式及成績評定對照表

其中：Aj表示課程目標j 的達成度，si表示第i 種考核的實際得分，wij表示第i 種考核方式對第j 種課程目標支撐權重。

全體學生平均課程目標達成度，si為全體學生的實際平均得分。通過定量評價，3個課程目標的達成度分別為：0.734、0.759、0.763。同時以散點圖形式將每名同學3個課程目標的達成度進行可視化，以課程目標2為例，達成情況散點圖如圖1。從圖1發(fā)現(xiàn)，大部分學生均能達成課程目標，但是其中一個學生未達成，該學生總評成績也小于60分。

圖1 全體學生課程目標2達成度

5 結語

工程教育認證以學生為中心、以能力提升為核心，以持續(xù)改進質(zhì)量提升為目標。本文為落實工程認證人才培養(yǎng)內(nèi)涵，針對“算法分析與設計”進行教學改革，通過制定工程認證背景下的教學目標、教學內(nèi)容、教學模式、評價指標體系，并進行課程目標達成評價。結合課程特點及學生調(diào)查問卷，分析了學生特點及教學過程中存在的普遍問題；根據(jù)學生能力提升及OBE教學理念，制定了工程認證教育下的課程培養(yǎng)目標，設計了融合專題探究、課程小組討論、項目驅(qū)動及“學生為中心”的混合式教學的新模式，構建了學生“產(chǎn)出導向”的評價指標及體系。通過改革實踐，利用青軟U+平臺進行課程目標達成度分析，服務后期持續(xù)改進；結果表明：該教學改革可以達成課程目標、獲得良好的教學效果；教學模式和改革方法，對其他接受工程認證的課程建設可提供借鑒和參考。