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

內(nèi)容概要

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

書(shū)籍目錄

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

章節(jié)摘錄

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








圖書(shū)封面






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



還沒(méi)讀過(guò)(86)
勉強(qiáng)可看(626)
一般般(106)
內(nèi)容豐富(4430)
強(qiáng)力推薦(363)


 


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