知識圖譜程序設計訓練系統的設計與開發

浙江萬里學院大數據與軟件工程學院 朱夢涵 陳斌格 柴本成

程序設計是一個對于待定問題提出解決方案的過程，是軟件構造活動中的重要組成部分。其通常以某種程序設計語言為工具，給出這種語言下的一定程序。而程序設計的過程包含有分析、設計、編碼、測試、操作等不同的階段，對程序設計者進行多方面的要求。在與計算機相關的課程學習中，程序設計扎根于每一種課程的學習之中，不僅占據舉足輕重的地位，更起到了思維訓練的效果。

1 程序設計的特點

程序設計的過程同其他設計活動一樣，都是在各種約束條件和需要之間尋找一種平衡，以實現在客觀條件允許的范圍內解決問題。一般而言，因為早期對于機器資源的限制，我們對程序要求往往側重于時間和空間代價這兩個方面。而隨著硬件技術的飛速發展和軟件規模的日益龐大，程序的結構性、可維護性、復用性、可拓展性等因素日益重要，對于程序設計多方面的需求推動著其快速發展。

程序設計的過程一般要求設計者擁有以下能力（1）分析問題：對于接受的課題能夠做出合理的分析，找出問題的本質規律并選擇合適的解決方法。（2）設計算法：設計出合適的解題方法與具體步驟，在時間復雜度和空間復雜度上能夠適應待定問題的客觀條件。（3）編寫程序：使用某種程序設計語言，完成源程序的編輯、編譯。（4）運行結果，分析結果：對于可執行的程序，能夠對于其運行結果進行分析，判斷其是否符合要求，并對于程序中的故障進行調試處理。在此之上，一般將程序設計的方法分為三種方法：面向過程、面向對象、面向切面，要求程序設計者能夠對于不同的生成環境選擇合適的生成方法解決問題。程序設計的過程是一個自由度高、綜合性強的逐步推進型過程，因此其對于學習者而言往往需要掌握大量的算法知識，具有較高的分析、編程能力，才能較好地實現一個設計過程。因此，對于一個程序設計的學習者而言，程序設計過程的不斷訓練，成為其拓展能力的直接渠道。

2 程序設計訓練的問題

問題的局限性，程序設計的過程離不開問題的先一步提出，只有對于特定的問題進行分析之后，我們才能針對問題提出相對的解題方法。出于訓練的目的性，對于問題的構造往往離不開涉及該問題的知識點以及出題人的主觀性，由于出題人的主觀性，問題的設置以及知識點的運用通常局限于出題人的理解范疇，這往往會導致學習者的片面認識，無論是對于知識點的理解還是知識點的拓展運用，都會有局限性。除此之外，因學習平臺的多樣化，經典問題往往較為分散，在缺乏有效整合的情況下，學習者往往被問題的重復性與局限性所困擾，缺乏高效刷題學習的方法。

知識點的拓展性受限，算法與數據結構是程序設計過程中的靈魂，只有掌握一定的算法與數據結構知識，才能對于特定的問題構造更加合理、有效的解決方案，這是程序設計過程之中的共性認識。而算法與數據結構的認知過程除了局限于教材的教學內容限制之外，還缺少大范圍內對于算法與數據結構的網狀聯系構架。簡單的可以認知為，知識點與知識點之間的聯系性松散，當局部知識點的學習結束后，因為沒有強聯系網絡的搭建，缺乏高效的學習拓展手段。

代碼設計過程的枯燥性，代碼是實現程序的基本手段，因此也是程序設計者最基本的能力之一，熟練的代碼設計技巧往往逃不開長時間的訓練與學習，我們往往強調通過增加學習者的程序設計次數與代碼設計長度來提高學習者的代碼設計能力，但這個過程往往伴隨著長時間的書寫與調試，容易對學習者造成消極影響，打擊學習者的積極性，是學習興趣低迷，直至最后喪失信心。因此問題的趣味性、學習過程的合理性、書寫技巧的訓練都至關重要，我們需要通過適當的方法，訓練學習者的代碼能力。

綜上所述，程序設計的過程中，問題、知識點、代碼設計過程三個方面的問題，嚴重制約并影響了學習過程中的效率。如何提高問題與問題、問題與知識點等方面的聯系性，剪除由客觀事物所造成的局限性、重復性等內容；如何更好地幫助學習者構建知識網絡，進行高效的學習與拓展，成為了更好地進行程序設計訓練的基本問題。

3 以程序設計為中心的知識圖譜

程序設計的訓練過程中，主要是算法與數據結構知識點的學習與特定題目的解答過程兩部分構成，在兩者相互作用的過程中，起到鍛煉思維能力、代碼能力的作用。通常我們將算法與數據結構中的內容進行拆分，進行一個循序漸進的過程性學習以掌握部分內容，其大致可以劃分為基礎算法（枚舉、模擬、遞歸、分治、貪心、前綴和、差分、二分、倍增、構造），搜索、動態規劃、字符串、數學、圖論、計算幾何、數據結構、圖論等內容。除了其中硬性的算法與數據結構知識之外，還有部分需要發散思維的思考技巧即一定的思維能力，這些內容共同構建了程序設計所涉及到的算法知識點，這些知識點之間存在著相關性?？梢岳斫鉃橹R點與知識點之間存在著前置內容、組合內容等相關關系。例如：差分技巧常用于樹上公共祖先的權值處理之中，DFS序、線段樹、輕重鏈等算法與概念則成為了成功樹鏈剖分這一算法知識點得到前置內容。由此我們可以發現，建立客觀可見的知識圖譜網絡，有助于學習者理解知識點與知識點之間最本質的聯系，大大地提升了知識之間的拓展性與學習的高效性。

知識圖譜的網狀構造對于前置內容的設置起到的極大的推動作用，但對于組合內容的設置體現并不直觀，組合內容的使用更多的是在于對于特定問題模型的多方面處理之中，通過解決問題這一過程能過更好地實現對于組合內容的認知。例如：GRE官方指南中的GRE Words就運用到了AC自動機、Fail樹、線段樹、DFS序、動態規劃等內容，進行了多方面的維護操作實現了程序設計。將問題加入網狀結構有助于深化知識圖譜中各種知識點的組合聯系，通過學習者對于問題解決方法的進步，解決問題數量的增加，形成用于判斷學習者知識體系掌握情況的依據，進而進一步構架專屬于學習者個人的知識網絡。

而這一套理論能夠建立的前提就是知識圖譜構架的知識網絡能夠在充分維護問題與知識點聯系的同時，恰如其分地體現學習者個人的學習情況，這對于判斷依據提出了更加嚴格的要求。此處提出以問題涵蓋知識點作為范圍判斷標準，以問題難度賦予一定的權值作為水平判斷標準，再加上一定的前置知識點要求，設置一個帶權的知識圖譜機制，以實現知識點學習掌握進度的逐步推進與學習者個人知識網絡的構架，如圖1所示。

圖1 問題和知識點架構的知識圖譜結構

由相關關系的問題作為判斷回饋機制，前置關系為約束的知識圖譜構架，能較好地表述學習者的知識網絡。

4 訓練系統的拓展性質

以學習者程序設計訓練的目的性進行拓展，進一步加強對于學習者的服務且調動學習者的訓練積極性，達到拓展系統功能與強化學習的重要目的。

程序設計學習者的基本目的主要區分為學業性學習、競賽性學習與就業性學習，三者在程序設計訓練方向的側重性是不同的，應針對不同的學習方向，提供精確性的向導功能，使學習者的知識網絡具有偏重性。對于學業性學習而言，結合相對應的課程內容知識點，達到專題性的訓練即可；對于競賽性學習而言，除了強化賽事相對知識點相關學習之外，還要對賽事信息進行一定程度的整合，方便學習者了解相關內容；對于就業性學習而言，除了相同的強化就業相關知識點之外，還要有就業信息的整合和當前行業的動態信息。

綜上所述，拓展性質的本質是實現局部知識點的強化以及更高程度的信息整合，強化對于學習者的服務功能，其實用性很大程度取決于知識圖譜內容相關性的設置與信息整合程度的高低?？紤]強化知識圖譜的構架，引入以程序設計相關數據、程序設計相關競賽（藍橋杯、ICPC、CCPC）、互聯網公司（嗶哩嗶哩、騰訊、網易）等內容的相關信息，加強其與知識點以及問題之間的關聯性，方便用戶對學習方向做出選擇并得到側重性強的學習過程。對于知識圖譜網絡的進一步構架，如圖2所示。

圖2 拓展偏向性后的知識圖譜結構

5 訓練系統的構建過程

基于上述的知識圖譜構建，本團隊以“競賽偏向的訓練系統”為例，構建了一個知識圖譜實例?；诖罱▽嵗幕A性，我們嘗試手工構建簡單的知識圖譜構架。主要從準備工作、主體搭建、成果檢驗三個方面進行闡述。

5.1 搭建知識圖譜的前期準備工作

該工作主要涉及的內容有相關知識素材的收集與整合、開發平臺的選擇與存儲方式的選擇等?；谡n程學習的內容，我們選擇基于.NET Framework的Web平臺的腳本語言ASP+，其參照Java、VB語言的開發優勢加入許多新的特色，同時也修正以前ASP版本的運行錯誤等故障。而知識圖譜的存儲方式則采用了基于SQL Server數據庫下的sql文件，并且使用Python組合作為信息收集工具，用于實現多方面的信息采集工作。在關于相關知識點的收集工作中，我們參考了經典的知識整合站點OI Wiki對于競賽知識的整理歸類方式，而賽事內容的獲取，則參考了相對熱門的codeforces、?？偷日军c的訓練獲取。

5.2 知識圖譜主題內容搭建

其主題內容的構建主要包含兩個方面：知識點其屬性與知識點與知識點之間的關系構架、問題與知識點的相關性以及權值配比。在知識點的梳理中，主要劃分為了語言基礎、算法基礎、搜素、動態規劃、字符串、數學、數據結構、圖論、計算幾何等9塊內容，其中包含了前置關系這一條件，構架知識點與知識點之間的聯系。而問題零散且廣泛，大致可以以難度與知識相關性進行梳理，其與知識點之間構建相關性的邏輯關系。引入競賽信息相關構架與知識點和問題之間的需求關系。在此，我們梳理了前置關系、相關關系、需求關系三塊內容。

5.3 知識圖譜的檢驗與評價

在知識圖譜基礎構建完成之后，需要對其的適用性與正確性進行評估，保證知識圖譜的質量。其檢驗過程一般包含有語義一致性檢驗和用戶自定義的一致性檢驗。在該知識圖譜的構架中，只含有“問題”、“知識點”、“競賽信息”三個概念，其概念之間的關系比較明確，其一致性上基本上不會產生問題。而為了避免用戶自定義產生的邏輯矛盾，會對于環形前置關系進行topo判斷，并采用向用戶提出聲明的方式輔助用戶進行規避。

6 訓練系統中的知識圖譜應用

基于知識圖譜構架的訓練系統最本質的特點即為不同學習者能根據自己的學習方向和學習進度獲取不同的知識網絡構建，以便于學習者能根據自身情況得到不同的推薦學習內容。具體表現可以理解為，在同一個頁面不同的學習者能夠看到不同的學習內容，做到最大程度地適應學習者的學習情況，進一步找到最合適的強化學習途徑。而其知識圖譜對于學習者的引導主要分為下述兩個方面。

6.1 指向性地為學習者提供呈現內容，支持學習者進行開拓式學習

系統會根據知識圖譜的構架與用戶當前的學習情況相結合，構架出學習者個人的網狀知識構架，為其確定已掌握內容、推薦掌握內容、未掌握內容三塊知識點構架。如K1和K2為K3的前置知識點，那么對于學習者而言，當K1和K2的評價達到掌握的程度之后，K3才會進入推薦掌握板塊。對于三塊內容的抉擇上，已掌握內容的信息推薦上，采取鞏固加深的思路，采取難度更高的問題進入學習者的學習范圍，并給出相應的拓展性知識強化學習；而推薦掌握內容則以已掌握內容中知識點作為前置知識的知識點為主，主要推薦相對入門的問題以及經典問題，輔助學習者進行新知識點的學習與入門；最后對于未掌握內容則簡單實行簡單的從易到難排序機制，主要偏向于讓學習者了解這一快內容的存在，加強學習者對于知識范疇系統性的認知。

6.2 在指向性提供內容呈現的同時，對于問題等學習資源進一步的進行細化處理

我們以學習者當前在該知識點所得到的權值和作為評判學習資源提供方式的標準：①首先以經典問題作為主要推薦方向，經典問題的學習有助于學習者對于當前知識點的本質理解，在學習途徑中起到至關重要的地位。②以當前的權值和作為評價標準，設計相應的分值臺階，如S1，S2，S3，S4，S5五個評價等級，根據不同的等級推薦不同難度的題目用于強化訓練，低等級的題目并不做舍棄處理，而是將優先級下降。通過較為簡單且有效的二級排序方式，我們可以基本地建立一個相對合理的學習過程。

以上的論述中，本課題的知識圖譜以較為簡單的關系模式，建立了行之有效的推薦學習和強化學習機制，為學習者的訓練學習過程提供了極大的自動性，并且具有較高的學習效率。

當前而言，通過知識圖譜構建，采用適應性學習機制的訓練系統，不失為一種有效的學習途徑。但是，該訓練系統的泛化行不強、長期使用的合理性驗證不足，模型的優化有待加強等問題并沒有得到有效解決。本研究只是建立并確定了一個較為合理的知識圖譜的邏輯結構，一定程度上實驗了知識圖譜對于學習訓練方式的促進作用。

研究團隊將會圍繞該課題的知識圖譜進行深入的研究，著力于泛化知識圖譜構架模型，進一步實現知識圖譜對于學習過程的輔助效果。