算法設(shè)計與分析

內(nèi)容概要

本書系統(tǒng)地介紹了算法設(shè)計與分析的概念和方法，將計算機經(jīng)典問題和算法設(shè)計技術(shù)很好地結(jié)合起來，系統(tǒng)地介紹了算法設(shè)計技術(shù)及其在經(jīng)典問題中的應(yīng)用。全書共11章，第1章介紹了算法的基本概念和基本理論，第2章從算法設(shè)計的角度介紹了算法設(shè)計與分析所用到的Java基礎(chǔ)知識和數(shù)學(xué)方法，第3章～第9章分別介紹了遞歸與分治、動態(tài)規(guī)劃、貪心法、回溯法、分支限界法、線性規(guī)劃與網(wǎng)絡(luò)流問題、概率算法等算法基本設(shè)計方法，第10章介紹了NP完全性理論，第11章講述了近似算法。
書中對所有算法思想做了詳細(xì)說明，給出了偽代碼，大部分算法還給出了Java描述。本書內(nèi)容豐富，深入淺出，結(jié)合實踐，循序漸進，互相銜接，可作為高等院校計算機專業(yè)本科和研究生學(xué)習(xí)算法設(shè)計與分析的教材，也可供工程技術(shù)人員和自學(xué)讀者學(xué)習(xí)參考。

書籍目錄

第1章　算法基本概念
第2章　常用的Java基礎(chǔ)和數(shù)學(xué)方法
第3章　遞歸與分治
第4章　動態(tài)規(guī)劃
第5章　貪心算法
第6章　回溯法
第7章　分支限界法
第8章　線性規(guī)劃與網(wǎng)絡(luò)流問題
第9章　概率算法
第10章　NP完全性理論
第11章　近似算法
參考文獻

章節(jié)摘錄

　　完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度是指數(shù)關(guān)系，因此計算的時間隨問題的復(fù)雜程度成指數(shù)的增長，很快便變得不可計算了?！　∪藗儼l(fā)現(xiàn)，所有的完全多項式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內(nèi)計算，人們于是就猜想：是否這類問題，存在一個確定性算法，可以在指數(shù)時間內(nèi)，直接算出或是搜尋出正確的答案呢？這就是著名的“NP-P”的猜想?！　〗鉀Q這個猜想，無非有兩種可能，一種是找到一個這樣的算法，只要針對某個特定NP完全問題找到一個算法，所有這類問題都可以迎刃而解了，因為它們可以轉(zhuǎn)化為同一個問題。另外的一種可能，就是這樣的算法是不存在的，那么就要從數(shù)學(xué)理論上證明它為什么不存在?！　∏岸螘r間轟動世界的一個數(shù)學(xué)成果，是幾個印度人提出了一個新算法，可以在多項式時間內(nèi)，證明某個數(shù)是或者不是質(zhì)數(shù)，而在這之前，人們認(rèn)為質(zhì)數(shù)的證明，是個非多項式問題?？梢姡行┛磥砗孟袷欠嵌囗検降膯栴}，其實是多項式問題，只是人們一時還不知道它的多項式解而已?！　】梢韵氲?，人們思考問題時，有兩種方法：一種是精確搜索，就是試驗所有的可能性，找出最精確的一個方案。但它在搜索過程中不改變搜索策略，不利用搜索獲得的中間信息，盲目性大，效率差，用于小型問題還可以，用于大型問題根本不可能；另一種叫做啟發(fā)式搜索，它在搜索過程中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索向著一個比較小的范圍內(nèi)進行，加速獲得結(jié)果?！　P完全性問題屬于“計算復(fù)雜性”研究的課題。所謂計算復(fù)雜性，就是用計算機求解問題的難易程度?！　　?/pre>








圖書封面






評論、評分、閱讀與下載



還沒讀過(86)
勉強可看(626)
一般般(106)
內(nèi)容豐富(4430)
強力推薦(363)


 


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