劉振章

摘要：針對《算法設(shè)計(jì)與分析》課程目前教學(xué)的實(shí)際情況和存在的問題，提出在算法課程教學(xué)中，重視算法理解和應(yīng)用，弱化算法邏輯推理和復(fù)雜度分析的教學(xué)理念，對課程的教學(xué)內(nèi)容、教學(xué)方法、實(shí)驗(yàn)教學(xué)和考核方式等進(jìn)行深入的探討。

關(guān)鍵詞：算法設(shè)計(jì)與分析；算法；教學(xué)改革；課程建設(shè)； ACM-ICPC

中圖分類號：G424 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）09-1995-02

《算法設(shè)計(jì)與分析》是計(jì)算機(jī)相關(guān)專業(yè)的一門重要專業(yè)基礎(chǔ)課，通過對該課程中一些基本理論和方法的學(xué)習(xí)，能夠理解主要的算法思想，掌握基本的算法設(shè)計(jì)方法，培養(yǎng)一定的算法分析能力，并學(xué)會用這些算法解決相應(yīng)的實(shí)際問題。

通過我們多年的教學(xué)實(shí)踐以及與其它任課教師的交流，普遍認(rèn)為《算法設(shè)計(jì)與分析》這門課程內(nèi)容比較抽象，知識涉及范圍比較廣，存在“教師難教，學(xué)生難學(xué)”的現(xiàn)象，教學(xué)效果不理想?！端惴ㄔO(shè)計(jì)與分析》是一門科學(xué)性與工程性、理論性與實(shí)踐性并重的課程。主要介紹常用的算法思想、典型算法問題的解決方法及算法復(fù)雜性分析，要求學(xué)生具有較好的數(shù)理基礎(chǔ)、較強(qiáng)的邏輯思維能力和扎實(shí)的數(shù)據(jù)結(jié)構(gòu)知識，并具有較強(qiáng)的編程能力。因此該課程對我們普通院校的師生而言，無疑是一個不小的挑戰(zhàn)。教師必須充分理解該門課程的特點(diǎn)，針對學(xué)生的實(shí)際情況，合理設(shè)置教學(xué)目標(biāo)，在教學(xué)內(nèi)容、教學(xué)方法、實(shí)踐教學(xué)和課程考核多方面加以研究改進(jìn)，才能達(dá)到該課程的教學(xué)目標(biāo)。

1 合理組織教學(xué)內(nèi)容

1.1 重視算法理解和應(yīng)用，弱化算法邏輯推理和復(fù)雜度分析

《算法設(shè)計(jì)與分析》課程目標(biāo)主要是使學(xué)生掌握常用的算法思想和算法設(shè)計(jì)方法，具備基本算法分析能力，進(jìn)而培養(yǎng)分析和解決實(shí)際問題的能力，為學(xué)生從事軟件系統(tǒng)開發(fā)和應(yīng)用打下良好的基礎(chǔ)。

當(dāng)前《算法設(shè)計(jì)與分析》課程教學(xué)往往過于強(qiáng)調(diào)算法的邏輯推理過程和算法的時間復(fù)雜度分析，教學(xué)內(nèi)容中涉及較多的公式推導(dǎo)和數(shù)學(xué)證明。隨著高等教育的大眾化，普通本科院校計(jì)算機(jī)相關(guān)專業(yè)學(xué)生的數(shù)學(xué)基礎(chǔ)和數(shù)學(xué)分析能力普遍不高，對復(fù)雜的算法公式推導(dǎo)和數(shù)學(xué)證明等理解困難，這極大地挫傷了學(xué)生的自信心和學(xué)習(xí)積極性。因此在我們的教學(xué)中，盡量避免大量復(fù)雜的公式推導(dǎo)和數(shù)學(xué)證明，降低理論難度，深入淺出的講解算法思想。簡化復(fù)雜的時間復(fù)雜性分析過程，甚至直接給出時間復(fù)雜度公式。重視算法理解和應(yīng)用，重點(diǎn)講授算法的基本思想、采用的數(shù)據(jù)結(jié)構(gòu)及程序?qū)崿F(xiàn)，通過更多算法應(yīng)用實(shí)例，培養(yǎng)學(xué)生的算法設(shè)計(jì)及實(shí)際應(yīng)用能力，從而提高學(xué)生的學(xué)習(xí)興趣，提高教學(xué)效果。

1.2 合理組織教學(xué)內(nèi)容

《算法設(shè)計(jì)與分析》課程教學(xué)重點(diǎn)是分治法、貪心法、動態(tài)規(guī)劃法、回溯法和分枝限界法，這些內(nèi)容對于本科生而言知識容量和難度都比較適中。在教學(xué)過程中必須詳細(xì)介紹算法的基本思想、采用的數(shù)據(jù)結(jié)構(gòu)及代碼實(shí)現(xiàn)，在不影響理解和應(yīng)用的基礎(chǔ)上，避免繁瑣的公式推導(dǎo)和數(shù)學(xué)證明。

算法教材中研究和討論的算法實(shí)例，以理論性研究居多，與實(shí)際應(yīng)用有一定距離。因此在教學(xué)中盡量選用教材上學(xué)生能夠理解和感興趣的應(yīng)用實(shí)例。為了更好的辨別理解不同的算法思想，同樣的算法問題，例如教材中的0-1背包問題可以采用多種算法思想實(shí)現(xiàn)。通過講解同一問題的不同算法實(shí)現(xiàn)，讓學(xué)生更好的理解算法思想的異同，節(jié)省問題本身介紹，提高課堂教學(xué)效率。

對于學(xué)習(xí)能力比較強(qiáng)的學(xué)生，教師在講解這些基本算法內(nèi)容的基礎(chǔ)上，可以提供一些采用這些算法解決不同領(lǐng)域問題的最新科研論文，讓學(xué)生了解這些經(jīng)典算法在不同領(lǐng)域的廣泛應(yīng)用，同時引導(dǎo)他們適當(dāng)?shù)貐⑴c科研，從而提高優(yōu)秀學(xué)生的學(xué)習(xí)興趣，培養(yǎng)學(xué)生的自主學(xué)習(xí)能力，提高其算法理論水平。

2 改進(jìn)教學(xué)方式

2.1 合理使用多媒體教學(xué)課件

多媒體教學(xué)技術(shù)在課堂教學(xué)中起到了非常重要的作用，比傳統(tǒng)板書節(jié)省時間，能在同樣的時間內(nèi)將更多的內(nèi)容展示給學(xué)生，提高了課堂效率。但是在《算法設(shè)計(jì)與分析》的教學(xué)過程中，并不是所有內(nèi)容都適合使用多媒體課件。板書仍然是必不可少的方法，對有些需要思考的內(nèi)容通過板書的方式放緩節(jié)奏，留給學(xué)生思考的時間，使學(xué)生盡量跟上教師的授課思路。在教學(xué)過程中我們應(yīng)該根據(jù)具體教授內(nèi)容揚(yáng)長避短，充分利用傳統(tǒng)粉筆黑板與多媒體演示相結(jié)合的啟發(fā)式教學(xué)方式。

2.2 使用動畫技術(shù)展示算法思想

《算法設(shè)計(jì)與分析》課程中的算法思想比較抽象，算法實(shí)現(xiàn)往往涉及到復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這使得一些邏輯思維能力不強(qiáng)，數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計(jì)基礎(chǔ)不好的學(xué)生很難透徹地理解算法思想和程序代碼?？梢酝ㄟ^BALSA、TANGO、ZEUS等算法演示系統(tǒng)軟件制作相應(yīng)的算法演示動畫，將算法的運(yùn)行過程及行為通過圖形、動畫、聲音等方式表現(xiàn)出來，生動形象地展示教材中的理論和案例，使得學(xué)生更有視覺感官效果，印象深刻，輔助學(xué)生理解算法，達(dá)到良好的教學(xué)效果。

3 加強(qiáng)實(shí)驗(yàn)教學(xué)

3.1 合理設(shè)計(jì)實(shí)驗(yàn)內(nèi)容

上機(jī)實(shí)驗(yàn)是算法課程必不可少的環(huán)節(jié)。通過實(shí)驗(yàn)幫助學(xué)生更好地掌握算法理論知識，深入理解并靈活應(yīng)用算法思想來解決實(shí)際問題，培養(yǎng)學(xué)生的實(shí)踐能力和創(chuàng)新精神。按照教學(xué)大綱的要求，《算法設(shè)計(jì)與分析》安排五個實(shí)驗(yàn)，分別涉及分治法、貪心算法、動態(tài)規(guī)劃法、回溯法和分枝限界法。考慮到學(xué)生學(xué)習(xí)情況和實(shí)際編程能力的差異，按照難度分梯度設(shè)置實(shí)驗(yàn)項(xiàng)目。針對每個算法實(shí)驗(yàn)，我們都設(shè)計(jì)了必做題和選做題。必做題包括1-2個基礎(chǔ)性的實(shí)驗(yàn)題目，以驗(yàn)證性的實(shí)驗(yàn)為主；選做題包括2-3個提高類題目，以設(shè)計(jì)類和綜合類的題目為主。一般學(xué)習(xí)能力的學(xué)生通過課堂理論知識的學(xué)習(xí)和老師的上機(jī)指導(dǎo)，有能力完成必做題目，達(dá)到教學(xué)大綱的要求；而對于那些學(xué)習(xí)能力較強(qiáng)，并且對算法設(shè)計(jì)有較大興趣的同學(xué)，則可以在教師的指導(dǎo)下，進(jìn)行選作題目的實(shí)驗(yàn)，培養(yǎng)其軟件設(shè)計(jì)和綜合應(yīng)用能力。

3.2 引入ACM-ICPC實(shí)驗(yàn)?zāi)Ｊ?/p>

由美國計(jì)算機(jī)協(xié)會組織的國際大學(xué)生程序設(shè)計(jì)競賽（ACM-ICPC））以其題目的趣味性、對抗的激烈性和團(tuán)隊(duì)精神吸引了眾多高校師生的參與。選手編寫程序的正確性和效率通過競賽評判系統(tǒng)自動評判。ACM-ICPC競賽題目多，趣味性強(qiáng)，很多題目具有很強(qiáng)的算法思想，非常適合作為算法課程實(shí)驗(yàn)的補(bǔ)充和提高。ACM-ICPC 在線判別系統(tǒng)OJ可以分析程序是否編譯通過，運(yùn)行是否成功，是否在規(guī)定的時間內(nèi)完成，輸出是否符合要求，運(yùn)行所占用的時間和內(nèi)存等，并給出各項(xiàng)評測結(jié)果。因此將ACM-ICPC模式引入到算法設(shè)計(jì)與分析的實(shí)驗(yàn)教學(xué)中，一方面可以極大的激發(fā)學(xué)生的學(xué)習(xí)興趣，增強(qiáng)學(xué)習(xí)氛圍，同時減輕了實(shí)驗(yàn)教師在實(shí)驗(yàn)驗(yàn)收和評判方面的工作量，提高了實(shí)驗(yàn)管理的效率和實(shí)驗(yàn)成績評判的公平性。

4 豐富考核方式

目前《算法設(shè)計(jì)與分析》課程的考核方式主要是由平時考核和期末考核兩部分組成，平時成績占總成績的20%-30%，期末考核基本上采取單一的理論考試形式，占總成績的 70%-80%。這種考核方式重理論輕實(shí)踐，不利于培養(yǎng)學(xué)生的實(shí)際應(yīng)用能力。我們考慮將該課程的考核分為二部分，一是平時實(shí)驗(yàn)成績占總成績的30%，其中20%考核學(xué)生的上機(jī)操作完成情況，上機(jī)操作采用ACM-ICPC 在線判別系統(tǒng)自動判分。10%考察學(xué)生的實(shí)驗(yàn)準(zhǔn)備和實(shí)驗(yàn)報(bào)告情況。期末考試分成兩部分來考核，理論考試占總成績的50%，上機(jī)考試占總成績的20%。理論考試側(cè)重于對算法理論和算法思想的考核，而上機(jī)考試則側(cè)重于對編程能力的考核。上機(jī)考試可采用北大的在線提交系統(tǒng)進(jìn)行評分。這樣的考核方式符合本課程理論與實(shí)踐相結(jié)合的教學(xué)思想，實(shí)踐考核方式公平客觀，便于操作，同時引導(dǎo)學(xué)生在深刻理解算法思想的基礎(chǔ)上重視上機(jī)實(shí)踐，提高編程和分析解決實(shí)際問題的能力。

5 結(jié)束語

在《算法設(shè)計(jì)與分析》的教學(xué)實(shí)踐中，我們強(qiáng)調(diào)算法理論與實(shí)際應(yīng)用相結(jié)合，合理組織教學(xué)內(nèi)容，重視實(shí)踐教學(xué)，改進(jìn)教學(xué)和考核方法，大大激發(fā)了學(xué)生學(xué)習(xí)興趣，提高了教學(xué)效果，達(dá)到了課程教學(xué)目標(biāo)。

參考文獻(xiàn)：

[1] 陳慧南.算法設(shè)計(jì)與分析—C++語言描述[M].北京：電子工業(yè)出版社，2006：1-10.

[2] 秦董洪，陳智勇.算法設(shè)計(jì)與分析課程教學(xué)研究[J].計(jì)算機(jī)教育，2013（11）：98-101.

[3] 王曉東.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，2003：1-10.

[4]伍宏玨.由ACM看《算法設(shè)計(jì)與分析》教學(xué)改革[J].九江學(xué)院學(xué)報(bào)，2009（6）：120-123.

[5] 張文升，周青云，周曉聰.算法演示系統(tǒng)研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2008（10）：47-49.