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

前言

　　早在20世紀(jì)70年代，計(jì)算機(jī)科學(xué)巨匠、圖靈獎(jiǎng)獲得者D.E.Knuth曾指出，計(jì)算機(jī)科學(xué)就是研究算法的學(xué)問(wèn)。因此，算法設(shè)計(jì)與分析是計(jì)算機(jī)科學(xué)的核心問(wèn)題。計(jì)算機(jī)科學(xué)是一項(xiàng)創(chuàng)造性的思維活動(dòng)，其教育必須面向設(shè)計(jì)，而計(jì)算機(jī)算法設(shè)計(jì)與分析正是面向設(shè)計(jì)的、處于核心地位的教育課程。它應(yīng)當(dāng)立足于基礎(chǔ)課和專(zhuān)業(yè)基礎(chǔ)課堅(jiān)實(shí)的基礎(chǔ)之上，其目的是通過(guò)對(duì)計(jì)算機(jī)領(lǐng)域的許多常見(jiàn)問(wèn)題和有代表性算法的學(xué)習(xí)、研究、了解，掌握算法設(shè)計(jì)的一些主要方法，提高分析的基本技能和某些技巧，達(dá)到能獨(dú)立設(shè)計(jì)算法和對(duì)給定算法進(jìn)行復(fù)雜度分析的初級(jí)水平。無(wú)論從事計(jì)算機(jī)專(zhuān)業(yè)哪一方面的工作，這些知識(shí)都是必備的。特別是對(duì)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件等專(zhuān)業(yè)，更是必不可少的專(zhuān)業(yè)知識(shí)?！　膽?yīng)用范圍來(lái)看，算法可以分為數(shù)值算法和非數(shù)值算法兩大類(lèi)；從工作方式來(lái)看，算法又可以分為串行算法和并行算法兩大類(lèi)。因?yàn)閿?shù)值算法在《數(shù)值分析》中介紹得較多，而本書(shū)作為《數(shù)據(jù)結(jié)構(gòu)》的后繼課程，主要講述非數(shù)值算法。由于篇幅和時(shí)間的限制，本書(shū)暫只介紹串行算法。本書(shū)中的算法均用自然語(yǔ)言來(lái)表述其思路，再以類(lèi)C語(yǔ)言來(lái)描述，力求簡(jiǎn)潔明了、通俗易懂。考慮到有關(guān)排序、圖、集合的算法在《數(shù)據(jù)結(jié)構(gòu)》課程中已有較詳細(xì)的講述，本書(shū)不再重復(fù)?！　”緯?shū)共分為1l章。第1章介紹了算法的基本概念，并對(duì)分析算法的準(zhǔn)則、描述算法的語(yǔ)言以及本書(shū)用到的基本數(shù)據(jù)結(jié)構(gòu)作了簡(jiǎn)要的闡述。第2章至第6章分別介紹了常用的一些非數(shù)值算法的設(shè)計(jì)方法，它們分別是分治法、貪心法、動(dòng)態(tài)規(guī)劃法、回溯法和分支限界法。這些都是一些通用的算法，可應(yīng)用于大部分問(wèn)題之中，所以本書(shū)選取了一部分有代表意義的問(wèn)題來(lái)進(jìn)行講解。第7章主要介紹了字符串的三種匹配算法，之所以將其單獨(dú)列為一章，主要是考慮到目前計(jì)算機(jī)處理的數(shù)據(jù)類(lèi)型中，字符串占有相當(dāng)大的比重，它的處理比一般的數(shù)據(jù)類(lèi)型更為復(fù)雜。而設(shè)計(jì)一個(gè)理想的匹配算法，需要堅(jiān)實(shí)的理論基礎(chǔ)和高超的設(shè)計(jì)技巧。第8章介紹了NP完全問(wèn)題和近似算法。NP完全問(wèn)題是20世紀(jì)70年代提出的理論計(jì)算機(jī)科學(xué)中的前沿課題，而近似算法則是目前針對(duì)NP完全問(wèn)題行之有效的方法。第9章概率算法是一類(lèi)比較特殊的算法，它相對(duì)于其他確定型的算法有其獨(dú)特的優(yōu)勢(shì)和應(yīng)用范圍。第10章介紹了目前最常用的幾類(lèi)通用型數(shù)據(jù)壓縮算法，數(shù)據(jù)壓縮應(yīng)用廣泛，極具實(shí)用價(jià)值。

內(nèi)容概要

　　算法的基本概念及相關(guān)基本知識(shí)；常用的一些非數(shù)值算法的設(shè)計(jì)方法（分治法、貪心法、動(dòng)態(tài)規(guī)劃法、回溯法和分支限界法）；字符串的匹配算法；NP完全問(wèn)題的近似算法；概念算法；目前常見(jiàn)的通用型數(shù)據(jù)壓縮算法；公鑰密碼學(xué)的基礎(chǔ)。　　《算法設(shè)計(jì)與分析》可作為計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的本科生教材；也可供有關(guān)計(jì)算機(jī)工作者閱讀。

書(shū)籍目錄

1 引論1.1 什么是算法1.2 分析算法的準(zhǔn)則1.3 描述算法的語(yǔ)言和基本的數(shù)據(jù)結(jié)構(gòu)思考題與習(xí)題2 分治與遞歸2.1 折半查找2.2 搜索二叉排序樹(shù)2.2.1 二叉排序樹(shù)的定義2.2.2 搜索二叉排序樹(shù)2.2.3 向二叉排序樹(shù)中插入新結(jié)點(diǎn)2.2.4 從二叉排序樹(shù)中刪除一個(gè)結(jié)點(diǎn)2.2.5 平衡的二叉排序樹(shù)2.3 快速排序2.4 歸并排序2.5 大整數(shù)乘法2.6 矩陣乘積的Strassen算法思考題與習(xí)題3 貪心算法3.1 最小生成樹(shù)3.2 單源最短路徑3.3 旅行商問(wèn)題思考題與習(xí)題4 動(dòng)態(tài)規(guī)劃4.1 動(dòng)態(tài)規(guī)劃在最短路徑中的應(yīng)用4.2 矩陣連乘積問(wèn)題4.3 求最長(zhǎng)公共子序列4.4 凸多邊形的最優(yōu)三角形剖分4.5 旅行商問(wèn)題思考題與習(xí)題5 回溯法5.1 樹(shù)的深度優(yōu)先遍歷5.2 數(shù)的全排列5.3 八皇后問(wèn)題5.4 0-1背包問(wèn)題5.5 旅行商問(wèn)題思考題與習(xí)題6 分支限界法6.1 最小耗費(fèi)搜索6.2 背包問(wèn)題6.3 旅行商問(wèn)題思考題與習(xí)題7 字符串7.1 串概念及簡(jiǎn)單串匹配算法7.1.1 字符串的概念7.1.2 串的匹配7.1.3 簡(jiǎn)單串模式匹配算法7.2 Knuth-Morris-Pratt（KMP）算法7.2.1 KMP算法7.2.2 改進(jìn)的KMP算法7.3 Boyer.Moore算法7.3.1 Boyer-Moore算法7.4 Karp-Rabin串匹配隨機(jī)算法思考題與習(xí)題8 NP完全問(wèn)題與近似算法8.1 確定型圖靈機(jī)8.2 非確定型圖靈機(jī)8.3 Cook定理和NP完全理論8.3.1 NP完全理論8.3.2 Cook定理8.3.3 若干NP完全問(wèn)題8.4 。NP完全問(wèn)題的近似算法8.4.1 0-1背包問(wèn)題8.4.2 旅行商問(wèn)題思考題與習(xí)題9 概率算法9.1 隨機(jī)抽樣9.2 判定素?cái)?shù)的概率算法9.2.1 Fermat素?cái)?shù)測(cè)試法9.2.2 MiLler-Rabin素?cái)?shù)判定概率算法思考題與習(xí)題10 數(shù)據(jù)壓縮算法10.1.ASCII碼壓縮算法10.2 哈夫曼編碼10.3 字典法10.4 LZ算法10.4.1 LZ77算法10.4.2 LZ78算法10.4.3 LZW算法思考題與習(xí)題11 公鑰密碼學(xué)基礎(chǔ)11.1 公鑰密碼體制的應(yīng)用與基本思想11.2 背包公鑰密碼11.3 RSA公鑰密碼體制10.4 數(shù)字簽名和Hash算法思考題與習(xí)題參考文獻(xiàn)

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

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

---

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

---