浙江萬里學(xué)院大數(shù)據(jù)與軟件工程學(xué)院 朱夢涵 陳斌格 柴本成

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

1 程序設(shè)計的特點

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

程序設(shè)計的過程一般要求設(shè)計者擁有以下能力（1）分析問題：對于接受的課題能夠做出合理的分析，找出問題的本質(zhì)規(guī)律并選擇合適的解決方法。（2）設(shè)計算法：設(shè)計出合適的解題方法與具體步驟，在時間復(fù)雜度和空間復(fù)雜度上能夠適應(yīng)待定問題的客觀條件。（3）編寫程序：使用某種程序設(shè)計語言，完成源程序的編輯、編譯。（4）運行結(jié)果，分析結(jié)果：對于可執(zhí)行的程序，能夠?qū)τ谄溥\行結(jié)果進行分析，判斷其是否符合要求，并對于程序中的故障進行調(diào)試處理。在此之上，一般將程序設(shè)計的方法分為三種方法：面向過程、面向?qū)ο蟆⒚嫦蚯忻?，要求程序設(shè)計者能夠?qū)τ诓煌纳森h(huán)境選擇合適的生成方法解決問題。程序設(shè)計的過程是一個自由度高、綜合性強的逐步推進型過程，因此其對于學(xué)習(xí)者而言往往需要掌握大量的算法知識，具有較高的分析、編程能力，才能較好地實現(xiàn)一個設(shè)計過程。因此，對于一個程序設(shè)計的學(xué)習(xí)者而言，程序設(shè)計過程的不斷訓(xùn)練，成為其拓展能力的直接渠道。

2 程序設(shè)計訓(xùn)練的問題

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

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

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

綜上所述，程序設(shè)計的過程中，問題、知識點、代碼設(shè)計過程三個方面的問題，嚴(yán)重制約并影響了學(xué)習(xí)過程中的效率。如何提高問題與問題、問題與知識點等方面的聯(lián)系性，剪除由客觀事物所造成的局限性、重復(fù)性等內(nèi)容；如何更好地幫助學(xué)習(xí)者構(gòu)建知識網(wǎng)絡(luò)，進行高效的學(xué)習(xí)與拓展，成為了更好地進行程序設(shè)計訓(xùn)練的基本問題。

3 以程序設(shè)計為中心的知識圖譜

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

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

而這一套理論能夠建立的前提就是知識圖譜構(gòu)架的知識網(wǎng)絡(luò)能夠在充分維護問題與知識點聯(lián)系的同時，恰如其分地體現(xiàn)學(xué)習(xí)者個人的學(xué)習(xí)情況，這對于判斷依據(jù)提出了更加嚴(yán)格的要求。此處提出以問題涵蓋知識點作為范圍判斷標(biāo)準(zhǔn)，以問題難度賦予一定的權(quán)值作為水平判斷標(biāo)準(zhǔn)，再加上一定的前置知識點要求，設(shè)置一個帶權(quán)的知識圖譜機制，以實現(xiàn)知識點學(xué)習(xí)掌握進度的逐步推進與學(xué)習(xí)者個人知識網(wǎng)絡(luò)的構(gòu)架，如圖1所示。

圖1 問題和知識點架構(gòu)的知識圖譜結(jié)構(gòu)

由相關(guān)關(guān)系的問題作為判斷回饋機制，前置關(guān)系為約束的知識圖譜構(gòu)架，能較好地表述學(xué)習(xí)者的知識網(wǎng)絡(luò)。

4 訓(xùn)練系統(tǒng)的拓展性質(zhì)

以學(xué)習(xí)者程序設(shè)計訓(xùn)練的目的性進行拓展，進一步加強對于學(xué)習(xí)者的服務(wù)且調(diào)動學(xué)習(xí)者的訓(xùn)練積極性，達到拓展系統(tǒng)功能與強化學(xué)習(xí)的重要目的。

程序設(shè)計學(xué)習(xí)者的基本目的主要區(qū)分為學(xué)業(yè)性學(xué)習(xí)、競賽性學(xué)習(xí)與就業(yè)性學(xué)習(xí)，三者在程序設(shè)計訓(xùn)練方向的側(cè)重性是不同的，應(yīng)針對不同的學(xué)習(xí)方向，提供精確性的向?qū)Чδ埽箤W(xué)習(xí)者的知識網(wǎng)絡(luò)具有偏重性。對于學(xué)業(yè)性學(xué)習(xí)而言，結(jié)合相對應(yīng)的課程內(nèi)容知識點，達到專題性的訓(xùn)練即可；對于競賽性學(xué)習(xí)而言，除了強化賽事相對知識點相關(guān)學(xué)習(xí)之外，還要對賽事信息進行一定程度的整合，方便學(xué)習(xí)者了解相關(guān)內(nèi)容；對于就業(yè)性學(xué)習(xí)而言，除了相同的強化就業(yè)相關(guān)知識點之外，還要有就業(yè)信息的整合和當(dāng)前行業(yè)的動態(tài)信息。

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

圖2 拓展偏向性后的知識圖譜結(jié)構(gòu)

5 訓(xùn)練系統(tǒng)的構(gòu)建過程

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

5.1 搭建知識圖譜的前期準(zhǔn)備工作

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

5.2 知識圖譜主題內(nèi)容搭建

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

5.3 知識圖譜的檢驗與評價

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

6 訓(xùn)練系統(tǒng)中的知識圖譜應(yīng)用

基于知識圖譜構(gòu)架的訓(xùn)練系統(tǒng)最本質(zhì)的特點即為不同學(xué)習(xí)者能根據(jù)自己的學(xué)習(xí)方向和學(xué)習(xí)進度獲取不同的知識網(wǎng)絡(luò)構(gòu)建，以便于學(xué)習(xí)者能根據(jù)自身情況得到不同的推薦學(xué)習(xí)內(nèi)容。具體表現(xiàn)可以理解為，在同一個頁面不同的學(xué)習(xí)者能夠看到不同的學(xué)習(xí)內(nèi)容，做到最大程度地適應(yīng)學(xué)習(xí)者的學(xué)習(xí)情況，進一步找到最合適的強化學(xué)習(xí)途徑。而其知識圖譜對于學(xué)習(xí)者的引導(dǎo)主要分為下述兩個方面。

6.1 指向性地為學(xué)習(xí)者提供呈現(xiàn)內(nèi)容，支持學(xué)習(xí)者進行開拓式學(xué)習(xí)

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

6.2 在指向性提供內(nèi)容呈現(xiàn)的同時，對于問題等學(xué)習(xí)資源進一步的進行細化處理

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

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

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

研究團隊將會圍繞該課題的知識圖譜進行深入的研究，著力于泛化知識圖譜構(gòu)架模型，進一步實現(xiàn)知識圖譜對于學(xué)習(xí)過程的輔助效果。