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

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

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

0 引言

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

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

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

2 試題庫的設計

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

3 在線評測教學平臺的設計

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

圖2 問題樣例

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

該課程輔助教學系統(tǒng)采用瀏覽器/服務器（B/S）模式，學生與教師通過瀏覽器即可輕松使用本系統(tǒng)。系統(tǒng)模塊之間通過JSON-RPC 來實現(xiàn)通信。服務器基于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)頁采用單頁應用模式。相比于傳統(tǒng)網(wǎng)頁，其犧牲首次加載時間以換取后續(xù)使用的流暢性，當用戶在不同的頁面切換時，僅需加載與頁面直接相關的內容，無需下載已經(jīng)在初次載入處理完畢的網(wǎng)頁框架內容，從而降低用戶消耗的流量。Problem CI 與“千練萬花”平臺均基于ElementUI 的用戶界面，試題編輯系統(tǒng)考慮到未來可能發(fā)布客戶端版本，使用更適合客戶端的基于Vuetify 的Material 風格界面。當用戶使用不同尺寸的屏幕時，均會自動調整布局以盡最大可能滿足用戶在不同設備上使用系統(tǒng)的需求。

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

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

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

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

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

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

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

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

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

3.2.3 比賽子系統(tǒng)

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

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

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

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

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

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

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

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

4.1 系統(tǒng)部署

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

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

4.2 壓力測試結果

本評測系統(tǒng)的壓力測試為3 000 人同時在線的數(shù)據(jù)。系統(tǒng)部署在同一個服務器上。如圖4 所示當使用單機部署時，本系統(tǒng)可以支撐超過3 000 人同時在線，并在2 分鐘之內完成了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ù)、選擇比較器、設置時間限制、編寫試題等必需的操作，即可構造一道合法的試題，簡便的試題管理操作方便了教師的使用，還允許了學生用于日常自我訓練、測試使用。真正實現(xiàn)了輔助教學系統(tǒng)中的“教”“學”兩大功能。

5 教學效果

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

6 結語

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