定 價:24 元
叢書名:普通高等教育“十一五”國家級規(guī)劃教材
- 作者:朱大銘,馬紹漢 著
- 出版時間:2009/1/1
- ISBN:9787040258714
- 出 版 社:高等教育出版社
- 中圖法分類:TP301.6
- 頁碼:244
- 紙張:膠版紙
- 版次:1
- 開本:16開
《算法設(shè)計與分析》是普通高等教育“十一五”國家級規(guī)劃教材。
《算法設(shè)計與分析》以算法設(shè)計策略為知識單元,系統(tǒng)地介紹計算機算法的設(shè)計方法與分析技巧,以期為計算機科學(xué)與技術(shù)專業(yè)的學(xué)生提供廣泛而堅實的計算機基礎(chǔ)知識。主要內(nèi)容包括算法分析技術(shù),算法設(shè)計技術(shù),P類,NP類及NPC類,證明問題屬于NPC類的技術(shù),NPC問題子問題的復(fù)雜性,擬多項式變換和圖靈歸約,NP-難解問題近似算法,近似算法設(shè)計技術(shù),等等。
《算法設(shè)計與分析》包括了算法與復(fù)雜性領(lǐng)域的主要內(nèi)容,可以作為高等學(xué)校計算機專業(yè)高年級本科生和研究生學(xué)習計算機算法設(shè)計的教材,也可供廣大工程技術(shù)人員和自學(xué)者學(xué)習參考。
計算機是一種現(xiàn)代化的信息處理工具,它對信息進行處理并提供所需結(jié)果,其結(jié)果取決于所接受的信息及相應(yīng)的處理算法。算法是以計算機能夠理解的語言描述的解題過程。當算法作用于所求解問題的給定輸入集或作用于問題自身的描述上,將產(chǎn)生唯一確定的有限動作序列。此序列或終止于給定問題的解,或終止于對此輸入信息無解。對于給定的問題,基于對其的深刻理解,可設(shè)計出解答該問題的一個算法。在這個意義上,設(shè)計算法是將有關(guān)問題的知識,轉(zhuǎn)化為解決問題的智慧。知識誠可貴,智慧價更高。設(shè)計算法就是揭示所研究問題的基本特征,以尋求其解答策略的過程,這是一項艱苦的創(chuàng)造性工作。
對于給定的問題,有可能設(shè)計出多個算法,但不同的算法質(zhì)量會不一樣。衡量算法質(zhì)量的主要因素是算法執(zhí)行所耗費的時間和所需存儲空間,以及算法適用范圍等。對算法質(zhì)量的分析研究稱為算法分析。算法設(shè)計和算法分析是計算機科學(xué)的核心基礎(chǔ)。國內(nèi)外大學(xué)的計算機專業(yè)中,都將“算法設(shè)計與分析”作為專業(yè)基礎(chǔ)課。
近半個世紀以來,算法研究始終是計算機科學(xué)的一個研究熱點。以E.W.Dijkstra、S.A.Cook、R.M.Karp、J.H.Hopcroft及R.E.Tarjan等為代表的一批計算機科學(xué)家,以創(chuàng)造性工作推動著算法研究不斷深入發(fā)展。在研究過程中,算法理論研究與軟件技術(shù)研究之間產(chǎn)生了鴻溝,使得算法研究缺乏足夠的實驗支持,而實驗工作又沒有充分的理論分析。這種現(xiàn)狀引起了人們的憂慮。在1996年的ACM計算理論學(xué)術(shù)年會(STOC‘96)上,一些計算機科學(xué)家提出“算法工程”的概念,強調(diào)研究算法實現(xiàn)技術(shù)的重要性,呼吁算法研究者應(yīng)重視理論與實踐的結(jié)合,將算法設(shè)計、分析、實現(xiàn)、測試及改進等過程一體化、工程化。這種研究思路越來越受到人們的關(guān)注,促使算法研究健康發(fā)展。
本書原稿寫于20世紀80年代中期、筆者在山東大學(xué)為計算機專業(yè)研究生講授“算法設(shè)計與分析”課程期間,先后幾經(jīng)修改,于1992年定稿并由山東大學(xué)出版社正式出版。此后一直使用本書作為計算機科學(xué)與技術(shù)專業(yè)的學(xué)位課教材,由筆者和朱大銘教授共同為研究生講授,效果尚好。經(jīng)過20多年的研究沉淀,算法設(shè)計與分析雖然沒有太多變遷,但其研究內(nèi)容更加豐富和成熟。這期間我們始終堅持在這個研究方向上從事教學(xué)和科研工作,連續(xù)主持了10多項國家自然科學(xué)基金課題,培養(yǎng)了一批博士、碩士研究生。為適應(yīng)培養(yǎng)創(chuàng)新型人才的需要,經(jīng)過反復(fù)醞釀,決定由朱大銘教授執(zhí)筆,重新修改編著這本書,增加近10年來的研究成果,使之能反映21世紀以來算法設(shè)計與分析的研究現(xiàn)狀?梢哉f,本書是山東大學(xué)計算機科學(xué)與技術(shù)學(xué)院兩代人堅持不懈、刻苦努力完成的。在本書寫作過程中,得到朱洪教授的指導(dǎo)和幫助,在此表示感謝。
本書主要面向計算機相關(guān)專業(yè)的高年級本科生和研究生。全書共分8章,其中:第1、2章討論算法分析技術(shù)和算法設(shè)計技術(shù);第3、4、5、6章論述NP-完全性理論,特別強調(diào)多項式變換和多項式圖靈歸約的方法及應(yīng)用;第7章論述NP-難解問題近似算法的基本概念和設(shè)計NP-難解問題近似算法的基本方法;第8章討論近似算法設(shè)計的基本理論與技術(shù)。
算法研究是一項富有挑戰(zhàn)性的工作,對提高計算機學(xué)科的研究水平極為重要,希望能有更多的有識之士投身這項工作。由于我們學(xué)術(shù)水平有限,本書內(nèi)容必有疏漏、欠妥、謬誤之處,敬請讀者指正。
第1章 算法分析技術(shù)
1.1 算法及其復(fù)雜性
1.2 漸近估計技術(shù)及基本規(guī)則
1.3 遞歸算法分析
1.3.1 合并排序算法分析
1.3.2 一類遞推方程的一般解
1.4 大整數(shù)相乘的遞歸算法
1.5 練習
第2章 算法設(shè)計技術(shù)
2.1 分而治之
2.2 貪心技術(shù)
2.3 動態(tài)規(guī)劃
2.4 回溯技術(shù)
2.4.1 對策樹搜索與a/p-刪除
2.4.2 一般樹的回溯搜索與分支定界
2.5 局部搜索技術(shù)
2.6 練習
第3章 P類、NP類及NPC類
3.1 問題與算法
3.2 確定型圖靈機與P類
3.3 非確定型計算與NP類
3.4 多項式變換與NPC類
3.5 庫克定理
3.6 練習
第4章 證明問題屬于NPC類的技術(shù)
4.1 基本的NPC問題
4.2 證明NP-完全性的典型技術(shù)
4.2.1 限制技術(shù)
4.2.2 局部替換技術(shù)
4.2.3 分支設(shè)計技術(shù)
4.3 練習
第5章 NPC問題子問題的復(fù)雜性
5.1 2SAT問題屬于P類
5.2 幾個NPC問題在三角化圖上的解
5.2.1 三角化圖的特征
5.2.2 用字典編輯廣度優(yōu)先搜索識別三角化圖
5.2.3 三角化圖上著色、團、獨立集及團覆蓋問題的算法
5.3 子問題中P和NPC的分界
5.4 練習
第6章 擬多項式變換和圖靈歸約
6.1 判定問題、語言和編碼方案
6.2 擬多項式時間算法和強NPC類
6.3 用擬多項式變換證明強NP-完全性
6.4 復(fù)雜性類之間的關(guān)系
6.5 圖靈歸約和NP-難解問題
6.6 練習
第7章 NP-難解問題近似算法
7.1 近似算法及其性能評估
7.2 近似算法設(shè)計
7.2.1 滿足三角不等式的貨郎問題及其近似算法
7.2.2 滿足三角不等式的貨郎問題的最小生成樹算法
7.2.3 多任務(wù)排工問題的近似算法
7.2.4 獨立任務(wù)排工問題
7.3 NP-難解問題可近似計算復(fù)雜性
7.4 多項式時間近似方案
7.5 練習
第8章 近似算法設(shè)計技術(shù)
8.1 組合技術(shù)
8.1.1 MaxSAT問題
8.1.2 Maxk-SAT問題
8.1.3 圖頂點覆蓋問題
參考文獻