算法設(shè)計(jì)與分析

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

版權(quán)頁(yè)：插圖：

圖書封面

評(píng)論、評(píng)分、閱讀與下載

---

    算法設(shè)計(jì)與分析 PDF格式下載

---