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

內(nèi)容概要

《算法設(shè)計(jì)與分析(第2版)》系統(tǒng)地介紹算法設(shè)計(jì)與分析的概念和方法，共4部分內(nèi)容。第1部分介紹算法設(shè)計(jì)與分析的基本概念，結(jié)合窮舉法、排序問題及其他一些算法，對(duì)算法的時(shí)間復(fù)雜性的概念及復(fù)雜性的分析方法作了較為詳細(xì)的敘述；第2部分以算法設(shè)計(jì)技術(shù)為綱，從合并排序、堆排序、離散集合的union和find操作開始，進(jìn)而介紹遞歸技術(shù)、分治法、貪婪法、動(dòng)態(tài)規(guī)劃、回溯法、分支與限界法和隨機(jī)算法等算法設(shè)計(jì)技術(shù)及其復(fù)雜性分析；第3部分介紹計(jì)算機(jī)應(yīng)用領(lǐng)域里的一些算法，如圖和網(wǎng)絡(luò)流，以及計(jì)算幾何中的一些問題；第4部分介紹算法設(shè)計(jì)與分析中的一些理論問題，如NP完全問題、計(jì)算復(fù)雜性問題、下界理論問題，最后介紹了近似算法及其性能分析。
本書內(nèi)容選材適當(dāng)、編排合理、由淺入深、循序漸進(jìn)、互相銜接、逐步展開，并附有大量實(shí)例，既注重算法的思想方法、推導(dǎo)過程和正確性的證明技術(shù)，也注重算法所涉及的數(shù)據(jù)結(jié)構(gòu)、算法的具體實(shí)現(xiàn)和算法的工作過程。
《算法設(shè)計(jì)與分析(第2版)》可作為高等院校計(jì)算機(jī)專業(yè)本科生和研究生的教材，也可作為計(jì)算機(jī)科學(xué)與應(yīng)用的科學(xué)技術(shù)人員的參考資料。本書由鄭宗漢、鄭曉明編著。

書籍目錄

第1章  算法的基本概念
  1.1  引言
    1.1.1  算法的定義和特征
    1.1.2  算法設(shè)計(jì)的例子，窮舉法
    1.1.3  算法的復(fù)雜性分析
  1.2  算法的時(shí)間復(fù)雜性
    1.2.1  算法的輸入規(guī)模和運(yùn)行時(shí)間的階
    1.2.2  運(yùn)行時(shí)間的上界，O記號(hào)
    1.2.3  運(yùn)行時(shí)間的下界，Ω記號(hào)
    1.2.4  運(yùn)行時(shí)間的準(zhǔn)確界，Θ記號(hào)
    1.2.5  O記號(hào)、Ω記號(hào)、Θ記號(hào)的性質(zhì)
    1.2.6  復(fù)雜性類型和o記號(hào)
  習(xí)題
  參考文獻(xiàn)
第2章  算法的復(fù)雜性分析
  2.1  常用的函數(shù)和公式
    2.1.1  整數(shù)函數(shù)
    2.1.2  對(duì)數(shù)函數(shù)
    2.1.3  排列、組合和二項(xiàng)式系數(shù)
    2.1.4  級(jí)數(shù)求和
  2.2  算法的時(shí)間復(fù)雜性分析
    2.2.1  循環(huán)次數(shù)的統(tǒng)計(jì)
    2.2.2  基本操作頻率的統(tǒng)計(jì)
    2.2.3  計(jì)算步的統(tǒng)計(jì)
  2.3  最好情況、最壞情況和平均情況分析
    2.3.1  最好情況、最壞情況和平均情況
    2.3.2  最好情況和最壞情況分析
    2.3.3  平均情況分析
  2.4  用生成函數(shù)求解遞歸方程
    2.4.1  生成函數(shù)及其性質(zhì)
    2.4.2  用生成函數(shù)求解遞歸方程
  2.5  用特征方程求解遞歸方程
    2.5.1  k階常系數(shù)線性齊次遞歸方程
    2.5.2  k階常系數(shù)線性非齊次遞歸方程
  2.6  用遞推方法求解遞歸方程
    2.6.1  遞推
    2.6.2  用遞推法求解變系數(shù)遞歸方程
    2.6.3  換名
  2.7  算法的空間復(fù)雜性
  2.8  最優(yōu)算法
  習(xí)題
  參考文獻(xiàn)
第3章  排序問題和離散集合的操作
  3.1  合并排序
    3.1.1  合并排序算法的實(shí)現(xiàn)
    3.1.2  合并排序算法的分析
  3.2  基于堆的排序
    3.2.1  堆
    3.2.2  堆的操作
    3.2.3  堆的建立
    3.2.4  堆的排序
  3.3  基數(shù)排序
    3.3.1  基數(shù)排序算法的思想方法
    3.3.2  基數(shù)排序算法的實(shí)現(xiàn)
    3.3.3  基數(shù)排序算法的分析
  3.4  離散集合的Union_Find操作
    3.4.1  用于Union_Find操作的數(shù)據(jù)結(jié)構(gòu)
    3.4.2  union、find操作及路徑壓縮
  習(xí)題
  參考文獻(xiàn)
第4章  遞歸和分治
  4.1  基于歸納的遞歸算法
    4.1.1  基于歸納的遞歸算法的思想方法
    4.1.2  遞歸算法的例子
    4.1.3  排列問題的遞歸算法
    4.1.4  求數(shù)組主元素的遞歸算法
    4.1.5  整數(shù)劃分問題的遞歸算法
  4.2  分治法
    4.2.1  分治法的例子
    4.2.2  分治法的設(shè)計(jì)原理
    4.2.3  快速排序
    4.2.4  多項(xiàng)式乘積和大整數(shù)乘法
    4.2.5  平面點(diǎn)集最接近點(diǎn)對(duì)問題
    4.2.6  選擇問題
    4.2.7  殘缺棋盤問題
  習(xí)題
  ……
第5章  貪婪法
第6章  動(dòng)態(tài)規(guī)劃
第7章  回溯
第8章  分支與限界
第9章  隨機(jī)算法
第10章  圖和網(wǎng)絡(luò)問題
第11章  計(jì)算幾何問題
第12章  NP完全問題
第13章  計(jì)算復(fù)雜性
第14章  下界
第15章  近似算法
參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁(yè)：插圖：在前面的章節(jié)中，介紹了算法分析的一些工具和方法；對(duì)一些不同類型的問題，討論了幾種典型的算法設(shè)計(jì)技術(shù)；對(duì)一些特定的算法進(jìn)行了描述，并分析了它們的時(shí)間復(fù)雜性。此外，也說明了如果n是任意一個(gè)問題，對(duì)生存在著一個(gè)算法，其時(shí)間復(fù)雜性是（其中，n是輸入規(guī)模，k是非負(fù)整數(shù)），就認(rèn)為存在著一個(gè)解問題兀的多項(xiàng)式時(shí)間算法。多項(xiàng)式時(shí)間算法是一種有效的算法。在現(xiàn)實(shí)世界中，有很多問題存在多項(xiàng)式時(shí)間算法。但是，有更大量的問題，它們的時(shí)間復(fù)雜性是以指數(shù)函數(shù)或排列函數(shù)來衡量的，即具有以及D（胛?。┑臅r(shí)間復(fù)雜性。這一類問題，其計(jì)算時(shí)間隨著輸入規(guī)模的增長(zhǎng)而快速增長(zhǎng)，即使是對(duì)中等規(guī)模的輸入，其計(jì)算時(shí)間也是以世紀(jì)來衡量的。因此，通常把存在多項(xiàng)式時(shí)間算法的問題，稱為易解的問題：而把那些指數(shù)時(shí)間算法或排列時(shí)間算法的問題，稱為難解的問題。對(duì)于后面這一類問題，人們一直在尋找具有多項(xiàng)式時(shí)間的算法。雖然還不能給出使其獲得多項(xiàng)式時(shí)間的方法，但是卻可以證明這些問題之中，有很多問題在計(jì)算上是相關(guān)的。對(duì)這些存在著計(jì)算上相關(guān)的問題，如果其中之一可以用多項(xiàng)式時(shí)間來求解，那么其他所有同類問題也可以用多項(xiàng)式時(shí)間來求解；如果其中之一肯定不存在多項(xiàng)式時(shí)間算法，那么對(duì)與之同類的其他問題，也肯定不會(huì)找到多項(xiàng)式時(shí)間算法。于是，在這一章，從計(jì)算的觀點(diǎn)看來，不是意圖去找出求解它們的算法，而是著眼于表明它們?cè)谟?jì)算復(fù)雜性之間存在著什么樣的關(guān)系。

編輯推薦

《算法設(shè)計(jì)與分析(第2版)》：盡可能用通俗的語(yǔ)言來表達(dá)深?yuàn)W的問題，對(duì)實(shí)現(xiàn)算法的思想方法、推導(dǎo)過程、實(shí)現(xiàn)的步驟、所涉及到的數(shù)據(jù)結(jié)構(gòu)和變量的描述盡可能詳細(xì)，易于學(xué)生深刻地理解和掌握算法的工作原理，學(xué)會(huì)如何設(shè)計(jì)和實(shí)現(xiàn)算法。對(duì)算法的理論基礎(chǔ)和定理的證明給以足夠的重視，定義的敘述盡可能嚴(yán)謹(jǐn)，方法推導(dǎo)、定理證明的邏輯盡可能嚴(yán)密，培養(yǎng)學(xué)生良好的邏輯思維能力和嚴(yán)謹(jǐn)規(guī)范的科學(xué)方法。無論是算法的基本概念、算法復(fù)雜性的分析方法，還是算法的實(shí)現(xiàn)步驟，都盡可能提供大量實(shí)例加以解釋說明，用實(shí)例來模擬算法的運(yùn)行，有助于學(xué)生學(xué)以致用?！端惴ㄔO(shè)計(jì)與分析(第2版)》可作為高等院校計(jì)算機(jī)專業(yè)本科生和研究生的教材。也可作為計(jì)算機(jī)科學(xué)與應(yīng)用的科學(xué)技術(shù)人員的參考用書。

圖書封面

圖書標(biāo)簽Tags

無

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

---

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

---