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

時(shí)慧琨

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

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

中圖分類(lèi)號(hào)：G642? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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è)計(jì)與分析課程

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

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

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

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

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

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

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

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