基于深度學習策略的算法設(shè)計分析類課程線上線下混合教學設(shè)計

董文永，邵艷玲，劉樹波，郭 松

（1.武漢大學 計算機學院，湖北 武漢 430072；（2.南陽理工學院 計算機與信息工程學院，河南 南陽 473000）

0 引言

算法設(shè)計類課程的主要教學目的是學生掌握基本的算法設(shè)計技術(shù)，掌握算法的時間和空間復雜度分析，并通過常用的算法設(shè)計策略用某種特定的計算機語言解決實際問題。為實現(xiàn)該目標，需要學生進行大量的編程題目練習。實際上，僅靠傳統(tǒng)物理課堂的講解沒有辦法完成該任務(wù)，即使有上機實踐類課程，學生往往停留在對程序設(shè)計語言語法的掌握或編譯器的掌握上。另一方面，目前很多在線的MOOC 資源，題目設(shè)置比較傳統(tǒng)，如選擇題、判斷題和一些簡單的編程題。這些題目往往以考試為目的，不能以解決問題為出發(fā)點，題目設(shè)計比較粗糙，不能體現(xiàn)算法的精髓所在，更不能針對實際問題鍛煉學生設(shè)計算法的能力。同時，很多學校都有自己的在線程序測評網(wǎng)站，比如武漢大學、北京大學、南陽理工學院等的OJ（Online Judge）系統(tǒng)。這些網(wǎng)站能夠進行學生程序設(shè)計的訓練、參賽隊員的訓練和選拔,但這些專用的在線評測系統(tǒng)局限于參加程序設(shè)計大賽的隊員，普及面窄，造成資源的浪費。因此如何利用在線評測系統(tǒng)輔助算法設(shè)計類教學，在減輕教師工作量的同時，進一步規(guī)范課程的教學，使學生能夠深度掌握算法的精髓，是算法設(shè)計分析類課程教學要解決的關(guān)鍵問題。

1 基于深度學習策略的線上線下混合教學模式

深度學習是一種主動探究性的學習方式，要求學生進行深度的信息加工、主動的知識建構(gòu)、批判性的高階思維、有效的知識轉(zhuǎn)化與遷移應(yīng)用及實際問題的解決。本研究正是把深度學習策略應(yīng)用到算法設(shè)計分析類課程以開展線上線下混合式教學：在線上，除了可以預(yù)習或復習相關(guān)教學視頻和PPT、進行題目練習測試以外，還可以展開討論，協(xié)作學習；在線下，物理課堂以問題驅(qū)動為導向，教師進行問題的引導和深度分析探討，面對面答疑解惑。讓學生利用在線測試平臺，以彌補物理課堂學時和空間的限制，把物理課堂延伸到線上來，并給師生提供個性化的學習交流平臺?；谠诰€評測平臺的設(shè)計主要包括算法設(shè)計分析課程內(nèi)容、平臺測試和討論區(qū)。在線下課堂，教師通過案例進行問題提出，啟發(fā)引導學生通過所了解的算法知識解決實際問題，引起學生的學習興趣；在教師的引導下對案例進行分析研討，提出解決方案并進行應(yīng)用；對解決方案進行分析評價，逐漸增大知識理解的范圍，可以激發(fā)學生的內(nèi)驅(qū)力，促進學生反思，有利于加深新舊知識的聯(lián)系與新知識的進一步理解與建構(gòu)，達到深度學習的目的。

2 試題庫的設(shè)計

在進行試題庫的設(shè)計過程中，出題人要充分考慮各類學生的接受水平，因此試題庫應(yīng)包含若干難易程度不同的試題。圖1 是武漢大學“千練萬花”在線評測主系統(tǒng)問題Problem 界面。從圖中可以看出題目的難易是不同的，其中“A+B”問題比較簡單，能夠通過的人數(shù)很多（300 人）。圖2 描述了整個試題的具體細節(jié)展示，試題設(shè)計和目前國際競賽試題接軌，包括試題描述、輸入數(shù)據(jù)格式描述、輸出數(shù)據(jù)格式描述，以及輸入數(shù)據(jù)和輸出數(shù)據(jù)樣例。因此，整個試題庫的設(shè)計需要符合算法描述規(guī)范，還要能夠清楚地描述實際要解決的問題，可以看出題庫的設(shè)計在整個在線平臺中非常關(guān)鍵。

3 在線評測教學平臺的設(shè)計

圖1 武漢大學“千練萬花”在線評測主系統(tǒng)問題Problem 界面

圖2 問題樣例

為了方便用戶的使用，本研究的目標是設(shè)計并實現(xiàn)一個功能完備、高可用的算法設(shè)計分析類課程輔助教學系統(tǒng)。對于代碼評測部分，目標是設(shè)計一個通用可擴展的代碼評測核心，支持市面上的常見開發(fā)語言，并可以擴展支持部分對于教學有用的硬件描述語言或者匯編語言。對于作業(yè)方面，目標是設(shè)計一個便于使用的作業(yè)提交平臺，并支持在線預(yù)覽、打分、打包下載等功能，同時提供一種便于使用的交流或者通知手段。對于出題過程中存在的困難，目標是設(shè)計一個易于使用的試題編寫平臺。

該課程輔助教學系統(tǒng)采用瀏覽器/服務(wù)器（B/S）模式，學生與教師通過瀏覽器即可輕松使用本系統(tǒng)。系統(tǒng)模塊之間通過JSON-RPC 來實現(xiàn)通信。服務(wù)器基于Docker 部署，網(wǎng)頁前端使用Vue.js 框架來實現(xiàn)。系統(tǒng)包括前端網(wǎng)頁展示和教學核心平臺，教學核心平臺包括Problem CI 試題維護、試題評測、比賽、作業(yè)、小組以及試題存儲等子系統(tǒng)，教學核心平臺中的試題維護系統(tǒng)、試題編輯系統(tǒng)、試題評測系統(tǒng)獨立編寫，試題存儲使用Git 完成版本管理。

3.1 前端網(wǎng)頁

前端網(wǎng)頁采用單頁應(yīng)用模式。相比于傳統(tǒng)網(wǎng)頁，其犧牲首次加載時間以換取后續(xù)使用的流暢性，當用戶在不同的頁面切換時，僅需加載與頁面直接相關(guān)的內(nèi)容，無需下載已經(jīng)在初次載入處理完畢的網(wǎng)頁框架內(nèi)容，從而降低用戶消耗的流量。Problem CI 與“千練萬花”平臺均基于ElementUI 的用戶界面，試題編輯系統(tǒng)考慮到未來可能發(fā)布客戶端版本，使用更適合客戶端的基于Vuetify 的Material 風格界面。當用戶使用不同尺寸的屏幕時，均會自動調(diào)整布局以盡最大可能滿足用戶在不同設(shè)備上使用系統(tǒng)的需求。

3.2 “千練萬花”教學核心平臺

“千練萬花”教學核心平臺是整個教學系統(tǒng)的核心，承載了整個系統(tǒng)面向終端用戶的全部功能，如試題閱讀、代碼提交，作業(yè)提交、批改，參加比賽、參加小組等，在高峰時期，需要承載極高的并發(fā)請求數(shù)量。

武漢大學現(xiàn)在對外有兩個在線評測系統(tǒng)：面向所有人，供研究、訓練、交流的WOJ 系統(tǒng)和用于大四“編程實踐課”評測任務(wù)的WOJWeblearn 系統(tǒng)。由于維護、管理起來十分不便，同時大量重復的試題存在導致存儲空間的浪費，為解決這些問題，“千練萬花”教學核心平臺對外使用“小組”作為基本單位，各個小組之間擁有較為獨立的用戶系統(tǒng)，包括完全獨立的題庫、評測、比賽、作業(yè)功能。用戶使用現(xiàn)有賬號即可登錄使用，亦可以根據(jù)小組管理員設(shè)置加入小組。

3.2.1 Problem CI試題維護系統(tǒng)

Problem CI 即CI for Algorithm Contest Problems，即面向算法競賽試題的持續(xù)集成系統(tǒng)，通過與Git 版本倉庫深度集成以實現(xiàn)當試題產(chǎn)生改動，即可以主動觸發(fā)相應(yīng)的變化。

Problem CI 試題維護系統(tǒng)提供用戶添加、編輯試題和更新等維護功能。當試題出錯時，可以查看出錯的原因，也可以便捷地返回到上一個正確的版本。版本管理概念的出現(xiàn)，極大程度提升了出題的魯棒性。同時，試題維護系統(tǒng)無需關(guān)心試題的實現(xiàn)等數(shù)據(jù)，可以一鍵從Problem CI 中導入已經(jīng)由Problem CI 編排好的HTML 格式的題面文檔。在試題發(fā)生更新時，只需要重新導入試題，不用再次檢查排版、時限、樣例等是否與評測數(shù)據(jù)一致。另外，Problem CI 引入了名為“ACL Key”的子模塊，用于控制試題的訪問權(quán)限，以在不透露密碼的情況下，方便地調(diào)用外部程序進行試題的操作，同時還可以撤銷之前分發(fā)的ACL Key，在大賽場景下，可以充分保證試題的安全以避免未授權(quán)人員訪問試題內(nèi)容。

3.2.2 Final Judger試題評測子系統(tǒng)

Final Judger 的試題評測核心子系統(tǒng)包含試題編譯功能、代碼評測功能、試題測試功能3 個功能。當用戶提交試題之后便觸發(fā)提交子系統(tǒng)。提交子系統(tǒng)主要負責將用戶的代碼封裝為Problem CI 的評測任務(wù)對象，并處理由Problem CI 回調(diào)得到的評測結(jié)果，并推送到用戶前端。根據(jù)歷史數(shù)據(jù)，用戶提交數(shù)量遠小于試題訪問的數(shù)量，不會成為試題的瓶頸，但一個快速、穩(wěn)定的提交結(jié)果推送仍然是有利于提升用戶的使用體驗。另一方面，用戶代碼在比賽過程中的安全極為重要，因此提交子系統(tǒng)還負責了極其復雜的用戶訪問權(quán)限控制，比如在比賽過程中，用戶的提交不能被任何用戶（包括自己）查看，也不能得到除了提交編譯信息之外的信息，而在比賽結(jié)束后，比賽過程中的所有代碼、結(jié)果都會公開，以方便用戶之間的分享交流。

代碼評測功能是在線測試平臺的基本功能。在編寫試題的過程中，往往會添加、刪除評測數(shù)據(jù)，或是修改標程以實現(xiàn)更好的復雜度。在以往的試題編寫過程當中，這一系列操作一般由人力完成，在涉及一定規(guī)模的比賽當中，單個試題的評測數(shù)據(jù)可能會多達百余組甚至數(shù)百組，這樣大量的測試過程費時費力，同時由于多人協(xié)作，各人手上可能擁有的數(shù)據(jù)并不總是一致，這樣就會帶來漏測、誤測的問題，輕則影響出題效率，重則導致試題數(shù)據(jù)出錯。為了避免這一問題，在整合試題編譯器和代碼評測器的功能的基礎(chǔ)上，開發(fā)除了試題測試功能，其向上對接Problem CI 試題倉庫，向下對接Git 代碼倉庫，當有新的版本被同步到Git 時，試題測試模塊即會收到Git 倉庫的推送，并自動拉取試題，完成編譯、測試的過程。在試題中，可以指定特殊的代碼必須通過或者不通過，或者評測機必須返回代碼出現(xiàn)了怎樣的錯誤。在測試完成之后，該模塊會將測試的結(jié)論以及測試過程中出現(xiàn)的問題上傳到Problem CI 的數(shù)據(jù)庫當中，以禁止或者推薦某一個試題版本成為最終使用的試題版本。

3.2.3 比賽子系統(tǒng)

無論是比賽或是平時涉及編程的作業(yè)，都需要比賽子系統(tǒng)的支持。比賽子系統(tǒng)的榜單采用了可擴展性的操作，計算在客戶端完成。用戶可編寫一個適合特定的分數(shù)計算腳本以用于計算排名，除了用戶名、排名之外，其他各列都能更改，如可以設(shè)計特定比賽專用的欄目，如“得分”“罰時”“獎勵分”或者選手子集中的排名等，相比于市面上的類似系統(tǒng)大多使用服務(wù)器計算的方式，在客戶端計算分數(shù)可以降低服務(wù)器的負載，同時給用戶更方便的定制操作。

3.2.4 小組（域）子系統(tǒng)

小組（域）子系統(tǒng)是本輔助教學系統(tǒng)中極其重要的一個組成部分。不同于傳統(tǒng)的在線評測系統(tǒng)，基于域的輔助教學系統(tǒng)可以充分實現(xiàn)評測基礎(chǔ)設(shè)施的復用，使其在用戶端體驗近似于賬號共享的分離系統(tǒng)。同時，相比于部分同類產(chǎn)品對比賽采用獨立賬號的做法，本系統(tǒng)允許用戶綁定不同小組（域）中的同一賬號。

對于前文中提到的部分聊天工具提供“公告”或“置頂”的功能，由于篇幅有限，難以提供長篇幅的消息的情況，本系統(tǒng)中允許教師在小組首頁填寫長篇重要文字，同時小組內(nèi)尚未截止提交的作業(yè)、即將開始的比賽（考試）等，都將在相應(yīng)的列表置頂以保證相應(yīng)的曝光度，避免學生遺忘重要事項。

3.2.5 作業(yè)子系統(tǒng)

作業(yè)子系統(tǒng)是供教師在課程上布置作業(yè)使用，目的是為了方便教師評閱部分無法由機器評測的試題，在作業(yè)子系統(tǒng)中，教師可以創(chuàng)建、修改作業(yè)，也可以一鍵導出學生的作業(yè)提交，并自動打包為壓縮文件，省去了傳統(tǒng)作業(yè)提交工作流中學生—學習委員—教師/教輔這一路徑，將學生提交的作業(yè)直接送達教師。

對于教師而言，一個常見的問題在于，縱然反復強調(diào)平時作業(yè)的按時提交，仍有學生忘記作業(yè)的完成日期，或者提交錯誤的文件名。為此，在本系統(tǒng)中通過設(shè)定嚴格的作業(yè)截止日期，與自動重命名來解決這些問題。當學生提交作業(yè)之后，他的作業(yè)將自動被重命名存儲；當打包下載后，不同學生的作業(yè)也分文件夾存放；當同時收集多項作業(yè)時，也可以在作業(yè)后臺看到每一個學生的提交狀態(tài)。對于常見的作業(yè)類型，如PDF、圖片、代碼或者文本等，還可以直接在線上瀏覽批改作業(yè)，并導出成績，既方便了師生使用，而常見的登分錯誤的問題也可以因此避免。

4 系統(tǒng)測試及結(jié)果分析

4.1 系統(tǒng)部署

本系統(tǒng)通過發(fā)布Docker 鏡像和Docker Compose 部署配置文件，可以輕松地在數(shù)分鐘之內(nèi)搭建并部署一個完整地在線評測系統(tǒng)。通過進一步擴展，可以為整個系統(tǒng)實現(xiàn)高可用方案、高可用狀態(tài)下的集群結(jié)構(gòu)，如圖3 所示。另一方面，通過引入持續(xù)集成（即CI）系統(tǒng)，對于系統(tǒng)源代碼的任何修改都將實時地反饋到鏡像當中，而當版本完成測試，功能較為穩(wěn)定而錯誤較少的時候，即可直接發(fā)布新版本，真正實現(xiàn)了自動化部署，方便了系統(tǒng)的使用者測試或者更新。

圖3 高可用實現(xiàn)方案

4.2 壓力測試結(jié)果

本評測系統(tǒng)的壓力測試為3 000 人同時在線的數(shù)據(jù)。系統(tǒng)部署在同一個服務(wù)器上。如圖4 所示當使用單機部署時，本系統(tǒng)可以支撐超過3 000 人同時在線，并在2 分鐘之內(nèi)完成了25 萬請求數(shù)，由于人數(shù)遞增，可以得知在最后階段系統(tǒng)承載了較測試前期更多的用戶請求數(shù)。

相比于傳統(tǒng)使用的在線評測系統(tǒng)，本系統(tǒng)將試題維護、評測工作從整個系統(tǒng)中獨立出來，成為近乎完全獨立的新系統(tǒng)。獨立的試題維護工作帶來了更高的安全性。眾所周知，實現(xiàn)一個完全安全的計算機系統(tǒng)，成本最低的方案是使含有機密信息的計算機脫網(wǎng)運行。本系統(tǒng)通過將試題維護、評測工作獨立，允許了用戶在出題時使用獨立的Problem CI 實例，當真正比賽時，再接入公開的“千練萬花”系統(tǒng)運行，前后的切換不會讓平臺終端用戶體驗有所下降。

圖4 “千練萬花2.0”系統(tǒng)性能測試

另一方面，現(xiàn)有的許多開源在線評測系統(tǒng)缺乏一個易用的出題輔助工具，為了出題，教師往往需要復雜的命令行操作，而復雜的命令行操作對于非專業(yè)運維人員而言不甚友好，還帶來了誤操作的問題。此外，其他系統(tǒng)常常要求用戶了解系統(tǒng)的評測規(guī)范細節(jié)。Problem CI 的試題編輯器雖然提供了復雜操作的能力，但對于大多數(shù)試題，用戶不需要對評測原理有任何了解，只需要上傳數(shù)據(jù)、選擇比較器、設(shè)置時間限制、編寫試題等必需的操作，即可構(gòu)造一道合法的試題，簡便的試題管理操作方便了教師的使用，還允許了學生用于日常自我訓練、測試使用。真正實現(xiàn)了輔助教學系統(tǒng)中的“教”“學”兩大功能。

5 教學效果

目前，該教學模式已經(jīng)在武漢大學算法設(shè)計課程以及南陽理工學院C 語言程序設(shè)計等課程推廣，其中在線評測系統(tǒng)可以用于平時的作業(yè)測試、競賽以及考試，題庫模塊中包含編程題數(shù)據(jù)800 余條。自從2018 年度采用基于深度學習模式策略的算法設(shè)計分析類課程混合教學模式以來，普通學生學習算法和程序設(shè)計的熱情高漲，課程的目標達成度明顯提升且極大減輕了教師的工作量。

6 結(jié)語

為了實現(xiàn)算法設(shè)計分析類課程中學生通過常用的算法設(shè)計策略用某種特定的計算機語言解決實際問題能力，通過研究基于在線評測系統(tǒng)的算法設(shè)計分析類課程混合教學設(shè)計和實踐，筆者提出基于深度學習策略的線上線下混合教學模式、試題庫的設(shè)計方案以及開發(fā)了一個在線評測教學平臺。通過教學實踐證明，該課程設(shè)計方案適合算法設(shè)計分析類特征，能激發(fā)出學生的學習熱情，提升廣大學生的編程素養(yǎng)和課程目標達成度，也減輕了任課教師的工作量。