算法設計與分析

前言

　  前言　  作者1982年2月畢業(yè)于上海交通大學，2010年1月退休，在上海第二工業(yè)大學工作了近三十年。在此期間，主要從事“編譯程序”和“算法”這兩門學科的教學和科研。2005年4月清華大學出版社出版了由本人編著的《編譯原理實用教程》，該書至今仍用于我校和國內其他普通高等院校“編譯原理”課程的教學。相對于“編譯原理”課程而言，“算法設計與分析”課程教材的數量不多，輔助教材更少。多年來，我校“算法設計與分析”課程使用的是由電子工業(yè)出版社出版的《算法設計技巧與分析》一書，作者是國際著名算法專家M.H.Alsuwaiyel［沙特］。該書涉及范圍廣、難度大，可稱得上是“算法設計與分析”課程的經典教材。使用該教材，在教學中存在一定難度。為了提高“算法設計與分析”課程的教學水平，同時也想拋磚引玉和同行教師交流教學經驗，退休后打算根據自己的教學心得寫一本該書的輔助教材。在清華大學出版社的大力支持下，我的愿望終于得以實現?！? 根據課程教學要求，本書對應《算法設計技巧與分析》中的7章。它們是：第1章 算法分析基本概念，第4章 堆和不相交集數據結構，第5章 歸納法，第6章 分治，第7章 動態(tài)規(guī)劃，第8章 貪心算法和第13章 回溯法。主要內容為：各章的主要算法（包括算法說明、算法偽代碼描述、算法分析和算法程序實現）、習題解答和上機題。在書中出現的所有源程序，可以從清華大學出版社指定網站下載。在習題答案中，凡是用偽代碼描述的具有一定難度的答案，都有相應的源程序，也可以從清華大學出版社指定的網站下載。另外，由本人編寫的“算法設計與分析”課程的電子教案可從“中國高等學校教學資源網”下載?！? 本書既可作為“算法設計與分析”課程的主講教材，也可作為“算法設計與分析”課程的輔助教材。上海第二工業(yè)大學教師閆季鴻參與了各章習題答案的編寫，原上海第二工業(yè)大學學生董淑芳參與了各章上機題的編寫?！? 由于時間所限，書中存在錯誤和遺漏之處在所難免，希望廣大讀者批評指正。　  溫敬和 2011年3月

內容概要

　　本書根據課程教學要求編寫，內容包括算法分析基本概念、堆和不相交集數據結構、歸納法、分治法、動態(tài)規(guī)劃法、貪心法和回溯法。各章的主要算法（包括算法說明、算法偽代碼描述、算法分析和算法實現程序）、習題解答和上機題以及書中出現的所有源程序均可以從清華大學出版社網站(www.tup.com.cn)下載。
　　本書既可作為“算法設計與分析”課程的主講教材，也可作為其輔助教材，還可以作為軟件工程師學習算法設計的參考教材。

書籍目錄

第1章 算法分析基本概念
　1.1 主要算法及程序實現
　　1.1.1 二分搜索
　　1.1.2 合并兩個已排序的表
　　1.1.3 選擇排序法
　　1.1.4 插入排序法
　　1.1.5 自底向上合并排序法
　1.2 習題答案
　1.3 上機實習題
　　1.3.1 選擇排序法實現
　　1.3.2 自底向上合并排序法實現
第2章 堆和不相交集數據結構
　2.1 主要算法及程序實現
　　2.1.1 堆上的運算
　　2.1.2 創(chuàng)建堆
　　2.1.3 堆排序法
　　2.1.4 Union-Find算法
　2.2 習題答案
　2.3 上機實習題
　　2.3.1 插入排序法實現
　　2.3.2 堆排序法實現
第3章 歸納法
　3.1 主要算法及程序實現
　　3.1.1 選擇排序法
　　3.1.2 插入排序法
　　3.1.3 基數排序法
　3.2 習題答案
　3.3 上機實習題
　　3.3.1 基數排序法實現
　　3.3.2 漢諾塔問題實現
第4章 分治法
　4.1 主要算法及程序實現
　　4.1.1 尋找最大值和最小值
　　4.1.2 二分搜索
　　4.1.3 合并排序法
　　4.1.4 尋找中項和第k小元素
　　4.1.5 劃分算法
　　4.1.6 快速排序法
　4.2 習題答案
　4.3 上機實習題
第5章 動態(tài)規(guī)劃法
　5.1 主要算法及程序實現
　　5.1.1 最長公共子序列問題
　　5.1.2 所有點對的最短路徑問題
　　5.1.3 背包問題
　5.2 習題答案
　5.3 上機實習題
　　5.3.1 最長公共子序列問題實現
　　5.3.2 所有點對的最短路徑問題實現
　　5.3.3 背包問題實現
第6章 貪心法
　6.1 主要算法及程序實現
　　6.1.1 最短路徑問題
　　6.1.2 最小耗費生成樹（Kruskal算法）
　　6.1.3 最小耗費生成樹（Prim算法）
　　6.1.4 文件壓縮
　6.2 習題答案
　6.3 上機實習題
　　6.3.1 最短路徑問題實現
　　6.3.2 最小耗費生成樹（Prim算法）實現
　　6.3.3 Huffman算法實現
第7章 回溯法
　7.1 主要算法及程序實現
　　7.1.1 圖的3著色問題
　　7.1.2 4皇后問題
　7.2 習題答案
　7.3 上機實習題
　　7.3.1 圖的3著色問題實現
　　7.3.2 4皇后問題實現
參考文獻

章節(jié)摘錄

版權頁：插圖：

圖書封面

評論、評分、閱讀與下載

---

    算法設計與分析 PDF格式下載

---