算法設(shè)計與分析

前言

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

內(nèi)容概要

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

書籍目錄

1 引論1.1 什么是算法1.2 分析算法的準(zhǔn)則1.3 描述算法的語言和基本的數(shù)據(jù)結(jié)構(gòu)思考題與習(xí)題2 分治與遞歸2.1 折半查找2.2 搜索二叉排序樹2.2.1 二叉排序樹的定義2.2.2 搜索二叉排序樹2.2.3 向二叉排序樹中插入新結(jié)點2.2.4 從二叉排序樹中刪除一個結(jié)點2.2.5 平衡的二叉排序樹2.3 快速排序2.4 歸并排序2.5 大整數(shù)乘法2.6 矩陣乘積的Strassen算法思考題與習(xí)題3 貪心算法3.1 最小生成樹3.2 單源最短路徑3.3 旅行商問題思考題與習(xí)題4 動態(tài)規(guī)劃4.1 動態(tài)規(guī)劃在最短路徑中的應(yīng)用4.2 矩陣連乘積問題4.3 求最長公共子序列4.4 凸多邊形的最優(yōu)三角形剖分4.5 旅行商問題思考題與習(xí)題5 回溯法5.1 樹的深度優(yōu)先遍歷5.2 數(shù)的全排列5.3 八皇后問題5.4 0-1背包問題5.5 旅行商問題思考題與習(xí)題6 分支限界法6.1 最小耗費(fèi)搜索6.2 背包問題6.3 旅行商問題思考題與習(xí)題7 字符串7.1 串概念及簡單串匹配算法7.1.1 字符串的概念7.1.2 串的匹配7.1.3 簡單串模式匹配算法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完全問題與近似算法8.1 確定型圖靈機(jī)8.2 非確定型圖靈機(jī)8.3 Cook定理和NP完全理論8.3.1 NP完全理論8.3.2 Cook定理8.3.3 若干NP完全問題8.4 。NP完全問題的近似算法8.4.1 0-1背包問題8.4.2 旅行商問題思考題與習(xí)題9 概率算法9.1 隨機(jī)抽樣9.2 判定素數(shù)的概率算法9.2.1 Fermat素數(shù)測試法9.2.2 MiLler-Rabin素數(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)

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---