《算法設(shè)計與分析》課程教學探討

劉振章

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

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

中圖分類號：G424 文獻標識碼：A 文章編號：1009-3044（2014）09-1995-02

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

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

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

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

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

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

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

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

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

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

2 改進教學方式

2.1 合理使用多媒體教學課件

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

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

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

3 加強實驗教學

3.1 合理設(shè)計實驗內(nèi)容

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

3.2 引入ACM-ICPC實驗?zāi)Ｊ?/p>

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

4 豐富考核方式

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

5 結(jié)束語

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

參考文獻：

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

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

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

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

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