算法設計與分析

第1章 算法引論
　1.1 算法與程序
　1.2 表達算法的抽象機制
　1.3 描述算法
　1.4 算法復雜性分析
　小結
　習題
第2章 遞歸與分治策略
　2.1 遞歸的概念
　2.2 分治法的基本思想
　2.3 二分搜索技術
　2.4 大整數的乘法
　2.5 Strassen矩陣乘法
　2.6 棋盤覆蓋
　2.7 合並排序
　2.8 快速排序
　2.9 線性時間選擇
　2.10 最接近點對問題
　2.11 循環賽日程表
　小結
　習題
第3章 動態規劃
　3.1 矩陣連乘問題
　3.2 動態規劃算法的基本要素
　3.3 最長公共子序列
　3.4 凸多邊形最優三角剖分
　3.5 多邊形游戲
　3.6 圖像壓縮
　3.7 電路布線
　3.8 流水作業調度
　3.9 0-1背包問題
　3.10 最優二叉搜索樹
　小結
　習題
第4章 貪心算法
　4.1 活動安排問題
　4.2 貪心算法的基本要素
　　4.2.1 貪心選擇性質
　　4.2.2 最優子結構性質
　　4.2.3 貪心算法與動態規劃算法的差異
　4.3 最優裝載
　4.4 哈夫曼編碼
　　4.4.1 前綴碼
　　4.4.2 構造哈夫曼編碼
　　4.4.3 哈夫曼算法的正確性
　4.5 單源最短路徑
　　4.5.1 算法基本思想
　　4.5.2 算法的正確性和計算復雜性
　4.6 最小生成樹
　　4.6.1 最小生成樹性質
　　4.6.2 Prim算法
　　4.6.3 Kruskal算法
　4.7 多機調度問題
　4.8 貪心算法的理論基礎
　　4.8.1 擬陣
　　4.8.2 帶權擬陣的貪心算法
　　4.8.3 任務時間表問題
　小結
　習題
第5章 回溯法
第6章 分支限界法
第7章 概率算法
第8章 NP完全性理論
第9章 近似算法
第10章 算法優化策略
第11章 在線算法設計
詞匯索引
參考文獻

21世紀是知識經濟的時代，是人才競爭的時代。隨著21世紀的到來，人類已步人信息社會，信息產業正成為全球經濟的主導產業。計算機科學與技術在信息產業中佔據了最重要的地位，這就對培養21世紀高素質創新型計算機專業人才提出了迫切的要求。

為了培養高素質創新型人才，必須建立高水平的教學計劃和課程體系。在　多年跟蹤分析ACM和IEEE計算機課程體系的基礎上，緊跟計算機科學與技術的發展潮流，及時制定並修正教學計劃和課程體系是尤其重要的。計算機科學與技術的發展對高水平人才的要求，需要我們從總體上優化課程結構，精煉教學內容，拓寬專業基礎，加強教學實踐，特別注重綜合素質的培養，形成“基礎課程精深，專業課程寬新”的格局。

為了適應計算機科學與技術學科發展和計算機教學計劃的需要，要采取多種措施鼓勵長期從事計算機教學和科技前沿研究的專家教授積極參與計算機專業教材的編著和更新，在教材中及時反映學科前沿的研究成果與發展趨勢，以高水平的科研促進教材建設。同時適當引進國外先進的原版教材。

為了提高教學質量，需要不斷改革教學方法與手段，倡導因材施教，強調知識的總結、梳理、推演和挖掘，通過加快教案的不斷更新，使學生掌握教材中未及時反映的學科發展新動向，進一步拓廣視野。教學與科研相結合是培養學生實踐能力的有效途徑。高水平的科研可以為教學提供最先進的高新技術平台和創造性的工作環境，使學生得以接觸最先進的計算機理論、技術和環境。高水平的科研還可以為高水平人才的素質教育提供良好的物質基礎。學生在課題研究中不但能了解科學研究的艱辛和科研工作者的奉獻精神，而且能燻陶和培養良好的科研作風，鍛煉和培養攻關能力和協作精神。

進入21世紀，我國高等教育進人了前所未有的大發展時期，時代的進步與發展對高等教育質量提出了更高、更新的要求。2001年8月，教育部頒發了《關于加強高等學校本科教學工作，提高教學質量的若干意見》。文仵指出，本科教育是高等教育的主體和基礎，抓好本科教學是提高整個高等教育質量的重點和關鍵。隨著高等教育的普及和高等學校的擴招，在校大學本科計算機專業學生的人數將大量上升，對適合21世紀大學本科計算機科學與技術學科課程體系要求的，並且適合中國學生學習的計算機專業教材的需求量也將急劇增加。為此，中國計算機學會和清華大學出版社共同規劃了面向全國高等院校計算機專業本科生的“21世紀大學本科計算機專業系列教材”。本系列教材借鑒美國ACM和IEEE最新制定的Computing Curricula 2005（簡稱CC2005）課程體系，反映當代計算機科學與技術學科水平和計算機科學技術的新發展、新技術，並且結合中國計算機教育改革成果和中國國情。

中國計算機學會教育專業委員會和全國高等學校計算機教育研究會，在清華大學出版社的大力支持下，跟蹤分析CC2001，並結合中國計算機科學與技術學科的發展現狀和計算機教育的改革成果，研究出了《中國計算機科學與技術學科教程2002》（ChinaComputing Curricula 2002，簡稱CCC2002），該項研究成果對中國高等學校計算機科學與技術學科教育的改革和發展具有重要的參考價值和積極的推動作用。

“21世紀大學本科計算機專業系列教材”正是借鑒美國ACM和IEEE CC2005課程體系，依據CCC2002基本要求組織編寫的計算機專業教材。相信通過這套教材的編寫和出版，能夠在內容和形式上顯著地提高我國計算機專業教材的整體水平，繼而提高我國大學本科計算機專業的教學質量，培養出符合時代發展要求的具有較強國際競爭力的高素質創新型計算機人才。