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

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

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

0 引言

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

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

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

2 試題庫的設計

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

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

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

圖2 問題樣例

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

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

3.1 前端網頁

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

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

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

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

3.2.1 Problem CI試題維護系統

Problem CI 即CI for Algorithm Contest Problems，即面向算法競賽試題的持續集成系統，通過與Git 版本倉庫深度集成以實現當試題產生改動，即可以主動觸發相應的變化。

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

3.2.2 Final Judger試題評測子系統

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

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

3.2.3 比賽子系統

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

3.2.4 小組（域）子系統

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

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

3.2.5 作業子系統

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

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

4 系統測試及結果分析

4.1 系統部署

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

圖3 高可用實現方案

4.2 壓力測試結果

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

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

圖4 “千練萬花2.0”系統性能測試

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

5 教學效果

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

6 結語

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