結(jié)合OJ及競賽的算法設(shè)計與分析課程教學(xué)實(shí)踐

時慧琨

摘要：針對算法設(shè)計與分析課程教學(xué)中教學(xué)以講授為主、學(xué)生缺乏實(shí)踐機(jī)會及實(shí)踐脫離應(yīng)用實(shí)際的問題，從在線測試（OJ）系統(tǒng)建設(shè)、實(shí)踐團(tuán)隊(duì)組織、教學(xué)活動開展和競賽組織參與等方面，詳細(xì)闡述了在教學(xué)過程中結(jié)合OJ以及競賽開展課程教學(xué)的實(shí)踐模式，激發(fā)學(xué)生學(xué)習(xí)主動性，引導(dǎo)培養(yǎng)學(xué)生分析問題，解決問題能力及團(tuán)隊(duì)合作能力，提高教學(xué)效果。

關(guān)鍵詞：算法設(shè)計與分析;OJ;教學(xué)實(shí)踐

中圖分類號：G642? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2021）10-0149-03

Abstract：In the teaching of algorithm design and analysis course， there are some problems such as too many theoretical teaching， lack of practical opportunities and practice divorced from real application， etc. This paper elaborates on the practical mode of combining online judge（OJ）system and competitions in the teaching process from several aspects include OJ system construction， practice team organization， teaching activities development and competition organization participation. Practices proved these measures can stimulate students' learning initiative， guide and cultivate students' ability of analyzing， problem solving and team working， so as to improve the teaching effect.

Keywords：AlgorithmDesignandAnalysis;OJ;teaching practice

1算法設(shè)計與分析課程

算法設(shè)計與分析課程是高校計算機(jī)專業(yè)學(xué)生的一門專業(yè)必修課，該課程主要學(xué)習(xí)算法設(shè)計和算法分析的基本理論及方法。通過課程的學(xué)習(xí)，掌握算法設(shè)計的一般技術(shù)，能夠?qū)o定的問題進(jìn)行分析，建立數(shù)學(xué)模型，設(shè)計解決問題的算法，并進(jìn)而將其轉(zhuǎn)換為程序。學(xué)生同時也要能夠從時間和空間角度對算法的性能進(jìn)行分析，選擇合適的算法設(shè)計方法以高效的方式解決問題，培養(yǎng)學(xué)生分析問題、解決問題的能力及編程實(shí)踐能力和創(chuàng)新能力。

算法設(shè)計與分析課程直接以用計算機(jī)技術(shù)解決實(shí)際問題為教學(xué)目標(biāo)。利用計算機(jī)技術(shù)解決問題和其他解決問題的方法不同，在解決問題時并不是針對數(shù)據(jù)實(shí)例直接處理，而是要分析問題的本質(zhì)特性，建立問題求解模型，設(shè)計問題求解的步驟或算法，并開發(fā)程序，程序由計算機(jī)執(zhí)行并得到結(jié)果。開發(fā)的程序要求能夠?qū)栴}的各種輸入都得到正確的結(jié)果，并且程序通過重復(fù)執(zhí)行和復(fù)制傳播，從而成倍的提高生產(chǎn)效率。這樣一種解決問題方法的實(shí)現(xiàn)要求學(xué)生具備更高的分析、概括和抽象思維能力，同時也要求學(xué)生具備較高的設(shè)計能力和軟件開發(fā)能力。算法設(shè)計與分析課程就是一門綜合培養(yǎng)這些能力的課程，課程的教學(xué)效果對學(xué)生的培養(yǎng)質(zhì)量有直接的影響。目前社會上對計算機(jī)專業(yè)學(xué)生的需求和學(xué)生的實(shí)際能力存在一定的脫節(jié)，部分就是因?yàn)閷W(xué)生分析問題，解決問題能力的缺乏。因此，在算法課程的教學(xué)中，研究如何提高培養(yǎng)質(zhì)量，提高學(xué)生的分析能力、實(shí)踐能力和創(chuàng)新能力非常重要。

2程序設(shè)計競賽及OJ系統(tǒng)

程序設(shè)計類競賽中最早、最有名的是ACM-ICPC（ACM國際大學(xué)生程序設(shè)計競賽），競賽歷史最早可以追溯到1970年，是一項(xiàng)旨在展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神、分析、解決問題以及編程能力的年度競賽。2018年，來自全球6大洲，111個國家，3098所大學(xué)的5萬多名選手參加了比賽。這一比賽采用3人團(tuán)隊(duì)合作利用一臺計算機(jī)解題的比賽機(jī)制，自出現(xiàn)以來，在國際上獲得了廣泛的影響，國內(nèi)也出現(xiàn)了采用類似機(jī)制的各類程序設(shè)計比賽，例如CCPC中國大學(xué)生程序設(shè)計競賽以及各省教育廳組織的程序設(shè)計競賽等。另一方面，因特網(wǎng)上出現(xiàn)了各類的Online Judge系統(tǒng)（OJ），這是一種模擬ICPC機(jī)制的在線判題系統(tǒng)。常見的OJ系統(tǒng)包括POJ、ZOJ、HDOJ、Vijos、USACO等。一些OJ系統(tǒng)的源碼，例如HUSTOJ等也在因特網(wǎng)上公開，自主開發(fā)的難度也不大，這也大大促進(jìn)了OJ系統(tǒng)的普及，為廣大師生的編程練習(xí)提供了絕佳的平臺。

3 結(jié)合OJ及競賽的算法設(shè)計與分析課程教學(xué)措施

OJ作為一個在線測試及實(shí)踐平臺，內(nèi)部包含大量練習(xí)，可以提供給學(xué)生內(nèi)容和難度各異的練習(xí)機(jī)會。學(xué)生可以在OJ系統(tǒng)中針對每一個任務(wù)進(jìn)行分析和編程，并提交代碼，OJ系統(tǒng)用內(nèi)置的數(shù)據(jù)進(jìn)行驗(yàn)證，并返回“通過”或者錯誤的原因。目前，國內(nèi)外的各種OJ系統(tǒng)主要用于學(xué)生練習(xí)和比賽，并沒有和教學(xué)緊密聯(lián)系。如何結(jié)合OJ系統(tǒng)以及程序設(shè)計競賽，提高學(xué)生學(xué)習(xí)的積極性和主動性，提高算法設(shè)計與分析課程教學(xué)的效果，在如下幾個方面給出建議，供大家參考：

3.1 OJ系統(tǒng)的建設(shè)

目前已有的各種OJ系統(tǒng)主要是針對競賽及較高水平學(xué)生學(xué)習(xí)需求設(shè)立，在題目編排、難度劃分上并不適合用于教學(xué)，缺乏層次性和教學(xué)的針對性。為此，我們在公開的OJ系統(tǒng)的基礎(chǔ)上，將算法設(shè)計與分析以及相關(guān)的高級語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)等課程的例題和課后習(xí)題加入OJ系統(tǒng)中，學(xué)生在學(xué)習(xí)完相應(yīng)內(nèi)容后，可以直接在OJ系統(tǒng)中開展練習(xí)，由OJ系統(tǒng)進(jìn)行判定[1]。為了方便大家學(xué)習(xí)，提供測試數(shù)據(jù)下載的功能，方便學(xué)生進(jìn)行檢查分析。通過這些練習(xí)，為學(xué)生掌握課程教學(xué)內(nèi)容提供了實(shí)踐機(jī)會。同時，將一些競賽材料中的試題及競賽題也輸入到系統(tǒng)中，以滿足學(xué)生進(jìn)一步學(xué)習(xí)及競賽練習(xí)的需求。除此之外，為部分學(xué)生開放權(quán)限，鼓勵學(xué)生在題庫中添加內(nèi)容，在添加內(nèi)容時可以指定題目相關(guān)的知識點(diǎn)及難度等信息，方便學(xué)生在教學(xué)過程中根據(jù)自己的需要進(jìn)行選擇。同時，也鼓勵學(xué)生注冊國內(nèi)外其他OJ平臺賬號，并在平臺上開展練習(xí)及交流。