算法設(shè)計與分析

前言

計算機是一種現(xiàn)代化的信息處理工具，它對信息進行處理并提供所需結(jié)果，其結(jié)果取決于所接受的信息及相應(yīng)的處理算法。算法是以計算機能夠理解的語言描述的解題過程。當(dā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ǔ)課。近半個世紀(jì)以來，算法研究始終是計算機科學(xué)的一個研究熱點。以E.W.Dijkstra、S.A.Cook、R.M.Karp、J.H.Hopcroft及R.E.Tariall等為代表的一批計算機科學(xué)家，以創(chuàng)造性工作推動著算法研究不斷深入發(fā)展。在研究過程中，算法理論研究與軟件技術(shù)研究之間產(chǎn)生了鴻溝，使得算法研究缺乏足夠的實驗支持，而實驗工作又沒有充分的理論分析。這種現(xiàn)狀弓I起了人們的憂慮。在1996年的ACM計算理論學(xué)術(shù)年會（STOC’96）上，一些計算機科學(xué)家提出“算法工程”的概念，強調(diào)研究算法實現(xiàn)技術(shù)的重要性，呼吁算法研究者應(yīng)重視理論與實踐的結(jié)合，將算法設(shè)計、分析、實現(xiàn)、測試及改進等過程一體化、工程化。這種研究思路越來越受到人們的關(guān)注，促使算法研究健康發(fā)展。本書原稿寫于20世紀(jì)80年代中期、筆者在山東大學(xué)為計算機專業(yè)研究生講授“算法設(shè)計與分析”課程期間，先后幾經(jīng)修改，于1992年定稿并由山東大學(xué)出版社正式出版。此后一直使用本書作為計算機科學(xué)與技術(shù)專業(yè)的學(xué)位課教材，由筆者和朱大銘教授共同為研究生講授，效果尚好。經(jīng)過20多年的研究沉淀，算法設(shè)計與分析雖然沒有太多變遷，但其研究內(nèi)容更加豐富和成熟。

內(nèi)容概要

　　《算法設(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ù)，等等?！　　端惴ㄔO(shè)計與分析》包括了算法與復(fù)雜性領(lǐng)域的主要內(nèi)容，可以作為高等學(xué)校計算機專業(yè)高年級本科生和研究生學(xué)習(xí)計算機算法設(shè)計的教材，也可供廣大工程技術(shù)人員和自學(xué)者學(xué)習(xí)參考。

書籍目錄

第1章 算法分析技術(shù)§1.1 算法及其復(fù)雜性§1.2 漸近估計技術(shù)及基本規(guī)則§1.3 遞歸算法分析1.3.1 合并排序算法分析1.3.2 一類遞推方程的一般解§1.4 大整數(shù)相乘的遞歸算法§1.5 練習(xí)第2章 算法設(shè)計技術(shù)§2.1 分而治之§2.2 貪心技術(shù)§2.3 動態(tài)規(guī)劃§2.4 回溯技術(shù)2.4.1 對策樹搜索與a／B-刪除2.4.2 一般樹的回溯搜索與分支定界§2.5 局部搜索技術(shù)§2.6 練習(xí)第3章 P類、NP類及NPC類§3.1 問題與算法§3.2 確定型圖靈機與P類§3.3 非確定型計算與NP類§3.4 多項式變換與NPC類§3.5 庫克定理§3.6 練習(xí)第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 練習(xí)第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 練習(xí)第6章 擬多項式變換和圖靈歸約§6.1 判定問題、語言和編碼方案§6.2 擬多項式時間算法和強NPC類§6.3 用擬多項式變換證明強NP-完全性§6.4 復(fù)雜性類之間的關(guān)系§6.5 圖靈歸約和NP-難解問題§6.6 練習(xí)第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 練習(xí)第8章 近似算法設(shè)計技術(shù)§8.1 組合技術(shù)8.1.1 MaxSAT問題8.1.2 Maxk-SAT問題8.1.3 圖頂點覆蓋問題8.1.4 整數(shù)排列與換位移動排序8.1.5 集合覆蓋問題§8.2 線性規(guī)劃技術(shù)8.2.1 頂點覆蓋近似算法8.2.2 集合覆蓋近似算法§8.3 原始對偶技術(shù)8.3.1 集合覆蓋8.3.2 擊中集問題8.3.3 最短路問題8.3.4 Steiner樹問題§8.4 局部搜索技術(shù)8.4.1 Max-3SAT問題的局部搜索算法8.4.2 K-median問題的局部搜索算法8.4.3 設(shè)施定位問題的局部搜索近似算法§8.5 隨機近似算法8.5.1 MaxSAT問題的隨機算法8.5.2 歐氏平面上貨郎問題的隨機算法§8.6 練習(xí)參考文獻

章節(jié)摘錄

插圖：第1章 算法分析技術(shù)計算機的計算是在程序控制下進行的。程序和數(shù)據(jù)存放在存儲器中，中央處理器執(zhí)行程序規(guī)定的操作步驟，計算出所要解答問題的結(jié)果。設(shè)計程序首先需要明確程序要解答什么樣的問題，這就要形式化地描述問題的輸入數(shù)據(jù)、輸出數(shù)據(jù)和輸出數(shù)據(jù)應(yīng)滿足的條件。好的程序不僅是正確的，還應(yīng)該是高效的。計算機運行一個程序，輸出正確結(jié)果或有效結(jié)果需要多少時間和多少存儲空問，是標(biāo)志這個程序解答問題優(yōu)劣的主要量化指標(biāo)。影響程序運行的計算時間和存儲空間的因素很多，僅從程序在具體計算機上運行一次或幾次所花費的時間和占用的存儲空問難以斷定程序的優(yōu)劣。要客觀地評價程序，就要脫離具體的計算機，分析程序解答一定規(guī)模的問題實例所使用的基本操作次數(shù)和占用的存儲單元個數(shù)。脫離了具體的計算機、只描述解答問題的基本操作和操作順序的計算過程就叫做解答問題的算法。實際上算法并不能真正脫離計算機，設(shè)想所有算法都在一個通用的計算模型上運行，這個計算模型就是第3章將會講述到的圖靈機模型。分析算法在計算模型上解答問題需要多少基本操作、多少存儲單元，有助于客觀、精確地評價算法，還有助于我們設(shè)計更好的算法。但在實際的算法分析中，通常不會去分析算法在計算模型上運行所需要的操作次數(shù)和存儲單元個數(shù)，只需要脫離具體計算機，分析算法解答問題所使用的基本操作次數(shù)和占用的存儲單元數(shù)，就足夠了。1.1 算法及其復(fù)雜性所謂問題（problem），就是一個要求給出解答的一般性提問。它由兩個要素組成：第一個要素描述問題的所有參量和參量格式，稱為實例；第二個要素陳述問題解的格式和應(yīng)當(dāng)滿足的條件，稱為詢問。所謂算法（algorithm）是一個過程，這個過程是若干語句的集合，每條語句都由明確指定計算機操作和操作順序的規(guī)則構(gòu)成。只要按照語句一步步地執(zhí)行，便可得到問題的解。通?？蓪⒊绦颍╬rogram）看成是算法在具體計算機上運行的描述形式。在本書中，常常將程序和算法兩個詞混用。如果一個算法能應(yīng)用于問題的任何實例，并保證得到正確的解，那么稱這個算法解答了該問題。問題的實例又稱為算法的輸入，而問題的詢問又稱為算法的輸出。評價算法的好壞，是算法分析（algorithm analysis）的中心內(nèi)容。

編輯推薦

《算法設(shè)計與分析》特色：面向問題介紹算法與復(fù)雜性的有關(guān)概念與方法，易于讀者理解。從討論問題的計算復(fù)雜性和設(shè)計解答問題的算法兩個方面，介紹研究計算問題的方法，注重啟發(fā)讀者的解題智慧，鼓勵讀者尋找解決問題的最佳途徑。書中涉及大量的計算問題，雖然不能涵蓋算法與復(fù)雜性領(lǐng)域的所有問題，但能夠使讀者在實踐中借鑒解決老問題的方法克服新的困難。

圖書封面

評論、評分、閱讀與下載

---

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

---