董文永,邵艷玲,劉樹波,郭 松
(1.武漢大學(xué) 計(jì)算機(jī)學(xué)院,湖北 武漢 430072;(2.南陽(yáng)理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,河南 南陽(yáng) 473000)
算法設(shè)計(jì)類課程的主要教學(xué)目的是學(xué)生掌握基本的算法設(shè)計(jì)技術(shù),掌握算法的時(shí)間和空間復(fù)雜度分析,并通過常用的算法設(shè)計(jì)策略用某種特定的計(jì)算機(jī)語(yǔ)言解決實(shí)際問題。為實(shí)現(xiàn)該目標(biāo),需要學(xué)生進(jìn)行大量的編程題目練習(xí)。實(shí)際上,僅靠傳統(tǒng)物理課堂的講解沒有辦法完成該任務(wù),即使有上機(jī)實(shí)踐類課程,學(xué)生往往停留在對(duì)程序設(shè)計(jì)語(yǔ)言語(yǔ)法的掌握或編譯器的掌握上。另一方面,目前很多在線的MOOC 資源,題目設(shè)置比較傳統(tǒng),如選擇題、判斷題和一些簡(jiǎn)單的編程題。這些題目往往以考試為目的,不能以解決問題為出發(fā)點(diǎn),題目設(shè)計(jì)比較粗糙,不能體現(xiàn)算法的精髓所在,更不能針對(duì)實(shí)際問題鍛煉學(xué)生設(shè)計(jì)算法的能力。同時(shí),很多學(xué)校都有自己的在線程序測(cè)評(píng)網(wǎng)站,比如武漢大學(xué)、北京大學(xué)、南陽(yáng)理工學(xué)院等的OJ(Online Judge)系統(tǒng)。這些網(wǎng)站能夠進(jìn)行學(xué)生程序設(shè)計(jì)的訓(xùn)練、參賽隊(duì)員的訓(xùn)練和選拔,但這些專用的在線評(píng)測(cè)系統(tǒng)局限于參加程序設(shè)計(jì)大賽的隊(duì)員,普及面窄,造成資源的浪費(fèi)。因此如何利用在線評(píng)測(cè)系統(tǒng)輔助算法設(shè)計(jì)類教學(xué),在減輕教師工作量的同時(shí),進(jìn)一步規(guī)范課程的教學(xué),使學(xué)生能夠深度掌握算法的精髓,是算法設(shè)計(jì)分析類課程教學(xué)要解決的關(guān)鍵問題。
深度學(xué)習(xí)是一種主動(dòng)探究性的學(xué)習(xí)方式,要求學(xué)生進(jìn)行深度的信息加工、主動(dòng)的知識(shí)建構(gòu)、批判性的高階思維、有效的知識(shí)轉(zhuǎn)化與遷移應(yīng)用及實(shí)際問題的解決。本研究正是把深度學(xué)習(xí)策略應(yīng)用到算法設(shè)計(jì)分析類課程以開展線上線下混合式教學(xué):在線上,除了可以預(yù)習(xí)或復(fù)習(xí)相關(guān)教學(xué)視頻和PPT、進(jìn)行題目練習(xí)測(cè)試以外,還可以展開討論,協(xié)作學(xué)習(xí);在線下,物理課堂以問題驅(qū)動(dòng)為導(dǎo)向,教師進(jìn)行問題的引導(dǎo)和深度分析探討,面對(duì)面答疑解惑。讓學(xué)生利用在線測(cè)試平臺(tái),以彌補(bǔ)物理課堂學(xué)時(shí)和空間的限制,把物理課堂延伸到線上來,并給師生提供個(gè)性化的學(xué)習(xí)交流平臺(tái)。基于在線評(píng)測(cè)平臺(tái)的設(shè)計(jì)主要包括算法設(shè)計(jì)分析課程內(nèi)容、平臺(tái)測(cè)試和討論區(qū)。在線下課堂,教師通過案例進(jìn)行問題提出,啟發(fā)引導(dǎo)學(xué)生通過所了解的算法知識(shí)解決實(shí)際問題,引起學(xué)生的學(xué)習(xí)興趣;在教師的引導(dǎo)下對(duì)案例進(jìn)行分析研討,提出解決方案并進(jìn)行應(yīng)用;對(duì)解決方案進(jìn)行分析評(píng)價(jià),逐漸增大知識(shí)理解的范圍,可以激發(fā)學(xué)生的內(nèi)驅(qū)力,促進(jìn)學(xué)生反思,有利于加深新舊知識(shí)的聯(lián)系與新知識(shí)的進(jìn)一步理解與建構(gòu),達(dá)到深度學(xué)習(xí)的目的。
在進(jìn)行試題庫(kù)的設(shè)計(jì)過程中,出題人要充分考慮各類學(xué)生的接受水平,因此試題庫(kù)應(yīng)包含若干難易程度不同的試題。圖1 是武漢大學(xué)“千練萬(wàn)花”在線評(píng)測(cè)主系統(tǒng)問題Problem 界面。從圖中可以看出題目的難易是不同的,其中“A+B”問題比較簡(jiǎn)單,能夠通過的人數(shù)很多(300 人)。圖2 描述了整個(gè)試題的具體細(xì)節(jié)展示,試題設(shè)計(jì)和目前國(guó)際競(jìng)賽試題接軌,包括試題描述、輸入數(shù)據(jù)格式描述、輸出數(shù)據(jù)格式描述,以及輸入數(shù)據(jù)和輸出數(shù)據(jù)樣例。因此,整個(gè)試題庫(kù)的設(shè)計(jì)需要符合算法描述規(guī)范,還要能夠清楚地描述實(shí)際要解決的問題,可以看出題庫(kù)的設(shè)計(jì)在整個(gè)在線平臺(tái)中非常關(guān)鍵。
圖1 武漢大學(xué)“千練萬(wàn)花”在線評(píng)測(cè)主系統(tǒng)問題Problem 界面
圖2 問題樣例
為了方便用戶的使用,本研究的目標(biāo)是設(shè)計(jì)并實(shí)現(xiàn)一個(gè)功能完備、高可用的算法設(shè)計(jì)分析類課程輔助教學(xué)系統(tǒng)。對(duì)于代碼評(píng)測(cè)部分,目標(biāo)是設(shè)計(jì)一個(gè)通用可擴(kuò)展的代碼評(píng)測(cè)核心,支持市面上的常見開發(fā)語(yǔ)言,并可以擴(kuò)展支持部分對(duì)于教學(xué)有用的硬件描述語(yǔ)言或者匯編語(yǔ)言。對(duì)于作業(yè)方面,目標(biāo)是設(shè)計(jì)一個(gè)便于使用的作業(yè)提交平臺(tái),并支持在線預(yù)覽、打分、打包下載等功能,同時(shí)提供一種便于使用的交流或者通知手段。對(duì)于出題過程中存在的困難,目標(biāo)是設(shè)計(jì)一個(gè)易于使用的試題編寫平臺(tái)。
該課程輔助教學(xué)系統(tǒng)采用瀏覽器/服務(wù)器(B/S)模式,學(xué)生與教師通過瀏覽器即可輕松使用本系統(tǒng)。系統(tǒng)模塊之間通過JSON-RPC 來實(shí)現(xiàn)通信。服務(wù)器基于Docker 部署,網(wǎng)頁(yè)前端使用Vue.js 框架來實(shí)現(xiàn)。系統(tǒng)包括前端網(wǎng)頁(yè)展示和教學(xué)核心平臺(tái),教學(xué)核心平臺(tái)包括Problem CI 試題維護(hù)、試題評(píng)測(cè)、比賽、作業(yè)、小組以及試題存儲(chǔ)等子系統(tǒng),教學(xué)核心平臺(tái)中的試題維護(hù)系統(tǒng)、試題編輯系統(tǒng)、試題評(píng)測(cè)系統(tǒng)獨(dú)立編寫,試題存儲(chǔ)使用Git 完成版本管理。
前端網(wǎng)頁(yè)采用單頁(yè)應(yīng)用模式。相比于傳統(tǒng)網(wǎng)頁(yè),其犧牲首次加載時(shí)間以換取后續(xù)使用的流暢性,當(dāng)用戶在不同的頁(yè)面切換時(shí),僅需加載與頁(yè)面直接相關(guān)的內(nèi)容,無需下載已經(jīng)在初次載入處理完畢的網(wǎng)頁(yè)框架內(nèi)容,從而降低用戶消耗的流量。Problem CI 與“千練萬(wàn)花”平臺(tái)均基于ElementUI 的用戶界面,試題編輯系統(tǒng)考慮到未來可能發(fā)布客戶端版本,使用更適合客戶端的基于Vuetify 的Material 風(fēng)格界面。當(dāng)用戶使用不同尺寸的屏幕時(shí),均會(huì)自動(dòng)調(diào)整布局以盡最大可能滿足用戶在不同設(shè)備上使用系統(tǒng)的需求。
“千練萬(wàn)花”教學(xué)核心平臺(tái)是整個(gè)教學(xué)系統(tǒng)的核心,承載了整個(gè)系統(tǒng)面向終端用戶的全部功能,如試題閱讀、代碼提交,作業(yè)提交、批改,參加比賽、參加小組等,在高峰時(shí)期,需要承載極高的并發(fā)請(qǐng)求數(shù)量。
武漢大學(xué)現(xiàn)在對(duì)外有兩個(gè)在線評(píng)測(cè)系統(tǒng):面向所有人,供研究、訓(xùn)練、交流的WOJ 系統(tǒng)和用于大四“編程實(shí)踐課”評(píng)測(cè)任務(wù)的WOJWeblearn 系統(tǒng)。由于維護(hù)、管理起來十分不便,同時(shí)大量重復(fù)的試題存在導(dǎo)致存儲(chǔ)空間的浪費(fèi),為解決這些問題,“千練萬(wàn)花”教學(xué)核心平臺(tái)對(duì)外使用“小組”作為基本單位,各個(gè)小組之間擁有較為獨(dú)立的用戶系統(tǒng),包括完全獨(dú)立的題庫(kù)、評(píng)測(cè)、比賽、作業(yè)功能。用戶使用現(xiàn)有賬號(hào)即可登錄使用,亦可以根據(jù)小組管理員設(shè)置加入小組。
3.2.1 Problem CI試題維護(hù)系統(tǒng)
Problem CI 即CI for Algorithm Contest Problems,即面向算法競(jìng)賽試題的持續(xù)集成系統(tǒng),通過與Git 版本倉(cāng)庫(kù)深度集成以實(shí)現(xiàn)當(dāng)試題產(chǎn)生改動(dòng),即可以主動(dòng)觸發(fā)相應(yīng)的變化。
Problem CI 試題維護(hù)系統(tǒng)提供用戶添加、編輯試題和更新等維護(hù)功能。當(dāng)試題出錯(cuò)時(shí),可以查看出錯(cuò)的原因,也可以便捷地返回到上一個(gè)正確的版本。版本管理概念的出現(xiàn),極大程度提升了出題的魯棒性。同時(shí),試題維護(hù)系統(tǒng)無需關(guān)心試題的實(shí)現(xiàn)等數(shù)據(jù),可以一鍵從Problem CI 中導(dǎo)入已經(jīng)由Problem CI 編排好的HTML 格式的題面文檔。在試題發(fā)生更新時(shí),只需要重新導(dǎo)入試題,不用再次檢查排版、時(shí)限、樣例等是否與評(píng)測(cè)數(shù)據(jù)一致。另外,Problem CI 引入了名為“ACL Key”的子模塊,用于控制試題的訪問權(quán)限,以在不透露密碼的情況下,方便地調(diào)用外部程序進(jìn)行試題的操作,同時(shí)還可以撤銷之前分發(fā)的ACL Key,在大賽場(chǎng)景下,可以充分保證試題的安全以避免未授權(quán)人員訪問試題內(nèi)容。
3.2.2 Final Judger試題評(píng)測(cè)子系統(tǒng)
Final Judger 的試題評(píng)測(cè)核心子系統(tǒng)包含試題編譯功能、代碼評(píng)測(cè)功能、試題測(cè)試功能3 個(gè)功能。當(dāng)用戶提交試題之后便觸發(fā)提交子系統(tǒng)。提交子系統(tǒng)主要負(fù)責(zé)將用戶的代碼封裝為Problem CI 的評(píng)測(cè)任務(wù)對(duì)象,并處理由Problem CI 回調(diào)得到的評(píng)測(cè)結(jié)果,并推送到用戶前端。根據(jù)歷史數(shù)據(jù),用戶提交數(shù)量遠(yuǎn)小于試題訪問的數(shù)量,不會(huì)成為試題的瓶頸,但一個(gè)快速、穩(wěn)定的提交結(jié)果推送仍然是有利于提升用戶的使用體驗(yàn)。另一方面,用戶代碼在比賽過程中的安全極為重要,因此提交子系統(tǒng)還負(fù)責(zé)了極其復(fù)雜的用戶訪問權(quán)限控制,比如在比賽過程中,用戶的提交不能被任何用戶(包括自己)查看,也不能得到除了提交編譯信息之外的信息,而在比賽結(jié)束后,比賽過程中的所有代碼、結(jié)果都會(huì)公開,以方便用戶之間的分享交流。
代碼評(píng)測(cè)功能是在線測(cè)試平臺(tái)的基本功能。在編寫試題的過程中,往往會(huì)添加、刪除評(píng)測(cè)數(shù)據(jù),或是修改標(biāo)程以實(shí)現(xiàn)更好的復(fù)雜度。在以往的試題編寫過程當(dāng)中,這一系列操作一般由人力完成,在涉及一定規(guī)模的比賽當(dāng)中,單個(gè)試題的評(píng)測(cè)數(shù)據(jù)可能會(huì)多達(dá)百余組甚至數(shù)百組,這樣大量的測(cè)試過程費(fèi)時(shí)費(fèi)力,同時(shí)由于多人協(xié)作,各人手上可能擁有的數(shù)據(jù)并不總是一致,這樣就會(huì)帶來漏測(cè)、誤測(cè)的問題,輕則影響出題效率,重則導(dǎo)致試題數(shù)據(jù)出錯(cuò)。為了避免這一問題,在整合試題編譯器和代碼評(píng)測(cè)器的功能的基礎(chǔ)上,開發(fā)除了試題測(cè)試功能,其向上對(duì)接Problem CI 試題倉(cāng)庫(kù),向下對(duì)接Git 代碼倉(cāng)庫(kù),當(dāng)有新的版本被同步到Git 時(shí),試題測(cè)試模塊即會(huì)收到Git 倉(cāng)庫(kù)的推送,并自動(dòng)拉取試題,完成編譯、測(cè)試的過程。在試題中,可以指定特殊的代碼必須通過或者不通過,或者評(píng)測(cè)機(jī)必須返回代碼出現(xiàn)了怎樣的錯(cuò)誤。在測(cè)試完成之后,該模塊會(huì)將測(cè)試的結(jié)論以及測(cè)試過程中出現(xiàn)的問題上傳到Problem CI 的數(shù)據(jù)庫(kù)當(dāng)中,以禁止或者推薦某一個(gè)試題版本成為最終使用的試題版本。
3.2.3 比賽子系統(tǒng)
無論是比賽或是平時(shí)涉及編程的作業(yè),都需要比賽子系統(tǒng)的支持。比賽子系統(tǒng)的榜單采用了可擴(kuò)展性的操作,計(jì)算在客戶端完成。用戶可編寫一個(gè)適合特定的分?jǐn)?shù)計(jì)算腳本以用于計(jì)算排名,除了用戶名、排名之外,其他各列都能更改,如可以設(shè)計(jì)特定比賽專用的欄目,如“得分”“罰時(shí)”“獎(jiǎng)勵(lì)分”或者選手子集中的排名等,相比于市面上的類似系統(tǒng)大多使用服務(wù)器計(jì)算的方式,在客戶端計(jì)算分?jǐn)?shù)可以降低服務(wù)器的負(fù)載,同時(shí)給用戶更方便的定制操作。
3.2.4 小組(域)子系統(tǒng)
小組(域)子系統(tǒng)是本輔助教學(xué)系統(tǒng)中極其重要的一個(gè)組成部分。不同于傳統(tǒng)的在線評(píng)測(cè)系統(tǒng),基于域的輔助教學(xué)系統(tǒng)可以充分實(shí)現(xiàn)評(píng)測(cè)基礎(chǔ)設(shè)施的復(fù)用,使其在用戶端體驗(yàn)近似于賬號(hào)共享的分離系統(tǒng)。同時(shí),相比于部分同類產(chǎn)品對(duì)比賽采用獨(dú)立賬號(hào)的做法,本系統(tǒng)允許用戶綁定不同小組(域)中的同一賬號(hào)。
對(duì)于前文中提到的部分聊天工具提供“公告”或“置頂”的功能,由于篇幅有限,難以提供長(zhǎng)篇幅的消息的情況,本系統(tǒng)中允許教師在小組首頁(yè)填寫長(zhǎng)篇重要文字,同時(shí)小組內(nèi)尚未截止提交的作業(yè)、即將開始的比賽(考試)等,都將在相應(yīng)的列表置頂以保證相應(yīng)的曝光度,避免學(xué)生遺忘重要事項(xiàng)。
3.2.5 作業(yè)子系統(tǒng)
作業(yè)子系統(tǒng)是供教師在課程上布置作業(yè)使用,目的是為了方便教師評(píng)閱部分無法由機(jī)器評(píng)測(cè)的試題,在作業(yè)子系統(tǒng)中,教師可以創(chuàng)建、修改作業(yè),也可以一鍵導(dǎo)出學(xué)生的作業(yè)提交,并自動(dòng)打包為壓縮文件,省去了傳統(tǒng)作業(yè)提交工作流中學(xué)生—學(xué)習(xí)委員—教師/教輔這一路徑,將學(xué)生提交的作業(yè)直接送達(dá)教師。
對(duì)于教師而言,一個(gè)常見的問題在于,縱然反復(fù)強(qiáng)調(diào)平時(shí)作業(yè)的按時(shí)提交,仍有學(xué)生忘記作業(yè)的完成日期,或者提交錯(cuò)誤的文件名。為此,在本系統(tǒng)中通過設(shè)定嚴(yán)格的作業(yè)截止日期,與自動(dòng)重命名來解決這些問題。當(dāng)學(xué)生提交作業(yè)之后,他的作業(yè)將自動(dòng)被重命名存儲(chǔ);當(dāng)打包下載后,不同學(xué)生的作業(yè)也分文件夾存放;當(dāng)同時(shí)收集多項(xiàng)作業(yè)時(shí),也可以在作業(yè)后臺(tái)看到每一個(gè)學(xué)生的提交狀態(tài)。對(duì)于常見的作業(yè)類型,如PDF、圖片、代碼或者文本等,還可以直接在線上瀏覽批改作業(yè),并導(dǎo)出成績(jī),既方便了師生使用,而常見的登分錯(cuò)誤的問題也可以因此避免。
本系統(tǒng)通過發(fā)布Docker 鏡像和Docker Compose 部署配置文件,可以輕松地在數(shù)分鐘之內(nèi)搭建并部署一個(gè)完整地在線評(píng)測(cè)系統(tǒng)。通過進(jìn)一步擴(kuò)展,可以為整個(gè)系統(tǒng)實(shí)現(xiàn)高可用方案、高可用狀態(tài)下的集群結(jié)構(gòu),如圖3 所示。另一方面,通過引入持續(xù)集成(即CI)系統(tǒng),對(duì)于系統(tǒng)源代碼的任何修改都將實(shí)時(shí)地反饋到鏡像當(dāng)中,而當(dāng)版本完成測(cè)試,功能較為穩(wěn)定而錯(cuò)誤較少的時(shí)候,即可直接發(fā)布新版本,真正實(shí)現(xiàn)了自動(dòng)化部署,方便了系統(tǒng)的使用者測(cè)試或者更新。
圖3 高可用實(shí)現(xiàn)方案
本評(píng)測(cè)系統(tǒng)的壓力測(cè)試為3 000 人同時(shí)在線的數(shù)據(jù)。系統(tǒng)部署在同一個(gè)服務(wù)器上。如圖4 所示當(dāng)使用單機(jī)部署時(shí),本系統(tǒng)可以支撐超過3 000 人同時(shí)在線,并在2 分鐘之內(nèi)完成了25 萬(wàn)請(qǐng)求數(shù),由于人數(shù)遞增,可以得知在最后階段系統(tǒng)承載了較測(cè)試前期更多的用戶請(qǐng)求數(shù)。
相比于傳統(tǒng)使用的在線評(píng)測(cè)系統(tǒng),本系統(tǒng)將試題維護(hù)、評(píng)測(cè)工作從整個(gè)系統(tǒng)中獨(dú)立出來,成為近乎完全獨(dú)立的新系統(tǒng)。獨(dú)立的試題維護(hù)工作帶來了更高的安全性。眾所周知,實(shí)現(xiàn)一個(gè)完全安全的計(jì)算機(jī)系統(tǒng),成本最低的方案是使含有機(jī)密信息的計(jì)算機(jī)脫網(wǎng)運(yùn)行。本系統(tǒng)通過將試題維護(hù)、評(píng)測(cè)工作獨(dú)立,允許了用戶在出題時(shí)使用獨(dú)立的Problem CI 實(shí)例,當(dāng)真正比賽時(shí),再接入公開的“千練萬(wàn)花”系統(tǒng)運(yùn)行,前后的切換不會(huì)讓平臺(tái)終端用戶體驗(yàn)有所下降。
圖4 “千練萬(wàn)花2.0”系統(tǒng)性能測(cè)試
另一方面,現(xiàn)有的許多開源在線評(píng)測(cè)系統(tǒng)缺乏一個(gè)易用的出題輔助工具,為了出題,教師往往需要復(fù)雜的命令行操作,而復(fù)雜的命令行操作對(duì)于非專業(yè)運(yùn)維人員而言不甚友好,還帶來了誤操作的問題。此外,其他系統(tǒng)常常要求用戶了解系統(tǒng)的評(píng)測(cè)規(guī)范細(xì)節(jié)。Problem CI 的試題編輯器雖然提供了復(fù)雜操作的能力,但對(duì)于大多數(shù)試題,用戶不需要對(duì)評(píng)測(cè)原理有任何了解,只需要上傳數(shù)據(jù)、選擇比較器、設(shè)置時(shí)間限制、編寫試題等必需的操作,即可構(gòu)造一道合法的試題,簡(jiǎn)便的試題管理操作方便了教師的使用,還允許了學(xué)生用于日常自我訓(xùn)練、測(cè)試使用。真正實(shí)現(xiàn)了輔助教學(xué)系統(tǒng)中的“教”“學(xué)”兩大功能。
目前,該教學(xué)模式已經(jīng)在武漢大學(xué)算法設(shè)計(jì)課程以及南陽(yáng)理工學(xué)院C 語(yǔ)言程序設(shè)計(jì)等課程推廣,其中在線評(píng)測(cè)系統(tǒng)可以用于平時(shí)的作業(yè)測(cè)試、競(jìng)賽以及考試,題庫(kù)模塊中包含編程題數(shù)據(jù)800 余條。自從2018 年度采用基于深度學(xué)習(xí)模式策略的算法設(shè)計(jì)分析類課程混合教學(xué)模式以來,普通學(xué)生學(xué)習(xí)算法和程序設(shè)計(jì)的熱情高漲,課程的目標(biāo)達(dá)成度明顯提升且極大減輕了教師的工作量。
為了實(shí)現(xiàn)算法設(shè)計(jì)分析類課程中學(xué)生通過常用的算法設(shè)計(jì)策略用某種特定的計(jì)算機(jī)語(yǔ)言解決實(shí)際問題能力,通過研究基于在線評(píng)測(cè)系統(tǒng)的算法設(shè)計(jì)分析類課程混合教學(xué)設(shè)計(jì)和實(shí)踐,筆者提出基于深度學(xué)習(xí)策略的線上線下混合教學(xué)模式、試題庫(kù)的設(shè)計(jì)方案以及開發(fā)了一個(gè)在線評(píng)測(cè)教學(xué)平臺(tái)。通過教學(xué)實(shí)踐證明,該課程設(shè)計(jì)方案適合算法設(shè)計(jì)分析類特征,能激發(fā)出學(xué)生的學(xué)習(xí)熱情,提升廣大學(xué)生的編程素養(yǎng)和課程目標(biāo)達(dá)成度,也減輕了任課教師的工作量。