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

內(nèi)容概要

　　本書內(nèi)容共分四部分，第一部分算法概述，給出了算法的基本概念及算法分析的相關(guān)基礎(chǔ)；第二部分六大經(jīng)典算法的設(shè)計(jì)與分析技術(shù)，包括遞歸與分治策略、動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法、隨機(jī)算法，從算法設(shè)計(jì)和算法分析的理論入手，根據(jù)各類算法的基本技術(shù)原理，給出算法的分析方法和證明過程，并將經(jīng)典算法與應(yīng)用問題相結(jié)合，提供多類別應(yīng)用的范例；第三部分NP完全性理論，從計(jì)算本質(zhì)的角度討論計(jì)算模型的意義與作用，并分析NP完全問題的求解技術(shù)；第四部分神經(jīng)網(wǎng)絡(luò)智能算法，反映了近年來智能算法研究的新發(fā)展。各章附有大量算法示例和習(xí)題，這些解決問題的范例有利于學(xué)習(xí)者對書中內(nèi)容的理解和應(yīng)用。附錄中編排了綜合試題并附有參考答案提示，便于學(xué)習(xí)者總結(jié)與提高。
　　《現(xiàn)代信息科學(xué)技術(shù)基礎(chǔ)：算法設(shè)計(jì)與分析》可作為高等院校計(jì)算機(jī)算法設(shè)計(jì)與分析相關(guān)課程的本科生或研究生教學(xué)參考書，也可供計(jì)算機(jī)理論研究人員、計(jì)算機(jī)算法設(shè)計(jì)人員學(xué)習(xí)參考。

作者簡介

　　耿國華，教授，博士生導(dǎo)師，高等學(xué)校教學(xué)名師，享受國務(wù)院政府津貼，西北大學(xué)信息科學(xué)與技術(shù)學(xué)院副院長，教育部文科計(jì)算機(jī)基礎(chǔ)教學(xué)指導(dǎo)委員會副主任，陜西省計(jì)算機(jī)學(xué)會副理事長，陜西省計(jì)算機(jī)教育學(xué)會副理事長，陜西省計(jì)算機(jī)學(xué)會人工智能與模式識別專業(yè)委員會副主任，西北大學(xué)計(jì)算機(jī)軟件開發(fā)中心主任，長期從事智能信息處理、模式識別、信息可視化技術(shù)研究。

書籍目錄

第1章 算法概述
1.1 算法的概念
1.1.1 算法的定義和特性
1.1.2 求解問題的基本過程
1.1.3 算法設(shè)計(jì)示例——計(jì)算最大公約數(shù)
1.2 算法設(shè)計(jì)與分析任務(wù)
1.3 算法分析準(zhǔn)則
1.4 算法分析基礎(chǔ)
1.4.1 常用數(shù)學(xué)術(shù)語
1.4.2 對數(shù)與指數(shù)
1.4.3 數(shù)學(xué)證明法
1.5 算法復(fù)雜性分析方法
1.5.1 復(fù)雜度函數(shù)
1.5.2 最好、最壞和平均情況
1.5.3 漸進(jìn)分析
1.5.4 階的證明方法
小結(jié)
習(xí)題
第2章 遞歸與分治策略
2.1 遞歸的概念
2.2 具有遞歸特性的問題
2.3 遞歸過程的設(shè)計(jì)與實(shí)現(xiàn)
2.4 遞歸算法分析
2.4.1 替換法
2.4.2 遞歸樹法
2.4.3 主方法
2.5 分治法的基本思想
2.6 分治法的適用條件
2.7 分治法的基本步驟
2.8 分治法典型示例
2.8.1 n個(gè)數(shù)中求出最大／最小值
2.8.2 快速排序
2.8.3 大整數(shù)乘法
2.8.4 折半查找
2.8.5 矩陣乘法
小結(jié)
習(xí)題
第3章 動態(tài)規(guī)劃
3.1 動態(tài)規(guī)劃基礎(chǔ)
3.1.1 動態(tài)規(guī)劃的基本思想
3.1.2 動態(tài)規(guī)劃的基本要素
3.1.3 動態(tài)規(guī)劃的基本步驟
3.1.4 動態(tài)規(guī)劃示例——組合數(shù)問題
3.2 線性動態(tài)規(guī)劃——合唱隊(duì)形問題
3.3 區(qū)域動態(tài)規(guī)劃——矩陣連乘問題（最佳次序）
3.4 背包動態(tài)規(guī)劃——0－1背包問題
3.5 樹形動態(tài)規(guī)劃——最優(yōu)二叉搜索樹
小結(jié)
習(xí)題
第4章 貪心算法
4.1 貪心算法基礎(chǔ)
4.1.1 貪心算法的基本思想
4.1.2 貪心算法的基本要素
4.1.3 貪心算法適合的問題
4.1.4 貪心算法的基本步驟
4.1.5 貪心算法示例——背包問題
4.2 汽車加油問題
4.3 最優(yōu)服務(wù)次序問題
4.4 區(qū)間相交問題
4.5 單源最短路徑
小結(jié)
習(xí)題
第5章 回溯法
第6章 分支限界法
第7章 隨機(jī)算法
第8章 NP完全性理論
第9章 神經(jīng)智能算法
附錄 試題及參考答案
參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁：插圖：遞歸與迭代是計(jì)算機(jī)科學(xué)中重要的數(shù)學(xué)理論方法，也是程序設(shè)計(jì)的本質(zhì)技術(shù)。當(dāng)計(jì)算機(jī)求解的問題規(guī)模較大，直接求解困難甚至根本沒辦法直接求解，往往會考慮能否將該問題劃分為若干子問題，對這些子問題進(jìn)行求解。如果被劃分后得到的子問題規(guī)模仍然不夠小，則可以將每個(gè)子問題繼續(xù)劃分為更小的子問題，以此類推，直到劃分得到的問題規(guī)模足夠小，能夠較容易求出解為止。根據(jù)上述分治法的指導(dǎo)思想，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到容易求解。由于分治法產(chǎn)生的子問題往往是原問題的較小模式，子問題與原問題的類型一致，因此，在分治法中經(jīng)常使用遞歸技術(shù)求解問題，遞歸與分治之間是相輔相成的。2.1 遞歸的概念遞歸是計(jì)算機(jī)科學(xué)的一個(gè)重要概念，是程序設(shè)計(jì)中的一種有效的方法，在程序設(shè)計(jì)語言中被廣泛應(yīng)用。它是指函數(shù)、過程、子程序在運(yùn)行過程中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象。采用遞歸編寫程序能使程序變得簡潔和清晰，使人容易理解。遞歸算法描述簡捷，結(jié)構(gòu)清晰，算法的正確性比較容易證明。但是，遞歸算法的執(zhí)行效率低，空間消耗多，有時(shí)還會受到一些軟、硬件環(huán)境條件限制，不能使用遞歸技術(shù)，因此，在某些時(shí)候.還需要將遞歸算法轉(zhuǎn)換為非遞歸算法。

編輯推薦

《算法設(shè)計(jì)與分析》是現(xiàn)代信息科學(xué)技術(shù)基礎(chǔ)。

圖書封面

評論、評分、閱讀與下載

---

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

---