《算法設計與分析》教材建設的實施

國家973信息技術與高性能軟件基礎規劃項目首席科學家顧鈞教授和中國工程院院士李國杰教授指出：“我國的軟件開發要算法先行，這樣才能推動軟件技術的研究與開發，提高我國企業軟件產品的技術競爭力和市場競爭力”。算法設計與分析是計算機專業的核心課程，是一門理論性與實踐性相結合的課程。通過課程學習學生應掌握常用算法設計策略，提高軟件開發設計和解決計算機科學與工程領域中較復雜的實際問題的能力；同時通過學習算法復雜性分析，培養學生在軟件開發中注重效率的理念。

1亟待改進的現狀

在我校本科生課外實踐、畢業設計和研究生考試閱卷工作中，發現學生算法設計能力普遍欠缺，其它普通高校也有類似情況[1]。教材是體現教學內容和教學方法的知識載體，是進行教學的基本工具，分析現有的算法設計與分析教材，不難發現出現以上現象的根本原因。現有教材定位往往偏高，注重理論講解高深，適合研究生、重點院校本科生使用，這樣的教材往往導致學生對算法設計課程產生畏懼心理。現有教材對算法策略的講解多以問題為章節，沒有概括和歸納算法策略的特點，及在同一策略下不同問題的應用差別，學生很難系統地掌握算法策略的應用技能。另外，現有教材普遍只側重算法效率分析，而缺乏提高效率方法和技巧的介紹，綜上所述，深感有教材建設的必要性。

2本教材建設宗旨及其結構設計

根據現狀分析，本教材建設以“適用性實用性”為宗旨，定位于普通高校計算機專業本科學生，以素質教育的為需求，注重培養學生解決實際問題的能力。基于此宗旨本書分四個層次：

第一篇“引入篇”包含兩章，從問題求解的步驟開始認識算法及其重要地位、并學習算法設計的基本過程、算法效率分析方法；為提高學生的學習興趣，還對當前主流算法及軟件進行了簡要介紹(此節可作為選修)。

第二篇“基礎篇”，對算法設計基本工具循環、遞歸機制和數據結構的應用技巧和提高算法效率的方法做了講解。

第三篇“核心篇”包含兩章，主要介紹了常用的幾種算法策略，如：枚舉法、遞推法、分治法、貪婪算法、動態規劃及與圖搜索有關的算法策略，并對算法策略及其應用進行了總結比較。

第四篇“應用篇”，每節針對同一問題采用不同的數學模型、不同數據結構或不同的算法策略進行算法設計，并進行算法效率上的分析比對。

3教材建設特色

教材建設遵循《中國計算機科學與技術學科教程2002》(“China Computing Curricula 2002”，簡稱“CCC2002”)知識體系，屬于算法和復雜性(AL)的范疇。以AL1.基本算法分析和AL2.算法策略作為教材核心。

教材建設中吸收國內外同類教材[2] [3][4]的優點并加以消化，力爭淺顯易懂地講解深奧的算法設計策略和分析方法。在體現“適用性實用性”的宗旨下，本書和現有算法設計的教材相比主要特色有：

(1) 重系統性，符合認知規律

本教材結構嚴謹，章節劃分合理、層次分明。特別是教材第三篇“核心篇”摒棄同類教材中根據問題劃分章節的方法，通過對算法策略特點的概括和歸納，以同一策略下的應用差別來劃分章節，能反映知識點間的聯系，符合認知規律。同時，在各章末尾對算法進行比較、總結，使學生能方便、全面地掌握算法策略的本質及其應用體系。

(2) 重啟發性，體現創新意識

有些算法設計教材中的例題，先給出問題的算法設計結果，再去講解它們。這樣做只能使學生“知其然”而“不知其所以然”。本書中例題要經過問題分析、數學建模、數據結構設計和算法設計后，才給出算法和算法分析。這樣講解富有啟發性，利于培養學生“設計”算法的能力，而不是“記憶”算法的能力。同時，改變學生被動接受知識的習慣，養成主動學習的意識。

(3) 重適用性，提高學習效率

第二篇“基礎篇”是從程序設計到算法設計承上啟下的內容，對問題求解的基本方法、算法基本工具的使用及提高算法效率的基本技巧做了必要的總結、歸納，相信這些內容會給普通院校的廣大學生有較大的裨益，可以從根本上促使其打好學習算法設計的基礎，提高學習效率。

(4) 重開放性，培養學科興趣

第一篇中對現代算法的概覽，旨在擴大學生的知識面，提高學生對算法設計學習的興趣。教材中還介紹了從算法到程序轉換中的常見錯誤和注意事項，引導學生不能僅停留在形式化的算法描述階段，而是要大膽上機實現，檢驗算法設計的結果。這樣在提高學習本學科興趣的同時，還能盡快提高學生的實踐能力。

(5) 重實踐性，拓寬思維空間

教材中介紹的算法設計方法與現代的編程方法步調一致，有利于激發學生問題求解的欲望，增強綜合應用能力。第四篇“算法設計實踐”，每節中針對同一問題采用不同的數學模型、不同數據結構或不同的算法策略進行算法設計，旨在擴展學生解決問題的思路，促使學生靈活運用算法知識，而不是生搬硬套教材中的算法。同時，也可以通過對多種算法設計的分析比較認識算法的優劣。

4教材建設成果

教材已于2006年3月由清華大學出版社出版。教材出版后雖然僅使用一次，但教材初稿已多次作為算法設計與分析課程的講稿，學生使用后普遍反映良好，他們認為教材將復雜的算法思想進行了高度的概括歸納，以簡潔的方式呈現給讀者，具有易讀、易懂性，實例豐富，非常實用。省內其它院校進修的教師也認為這個教材(講稿)內容充實，第四篇是全書的一個亮點，非常有利于提高學生的算法設計應用能力；教材沒有過多的算法注釋，為啟發式、探究式、研究式教學方法提供了好的教學平臺。2007年6月該教材已被列入國家“十一五”規劃教材。

參考文獻

[1] 李海倫，唐全，“程序設計”課程教學改革的研究與實踐——加強算法設計教學，提高學生編程能力《 計算機教育 》2005年 7期21-22

[2] 王曉東主編《計算機算法設計與分析(第二版)》，電子工業出版社，2004

[3] (沙特)阿蘇外耶著，吳偉昶等譯，《算法設計技巧與分析》，電子工業出版社，2004.8

[4] Sara Baase，Allen Van Gelder，《計算機算法——設計與分析導論》第三版，高等教育出版社，2001.6