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

前言

計(jì)算機(jī)是一種現(xiàn)代化的信息處理工具，它對(duì)信息進(jìn)行處理并提供所需結(jié)果，其結(jié)果取決于所接受的信息及相應(yīng)的處理算法。算法是以計(jì)算機(jī)能夠理解的語(yǔ)言描述的解題過(guò)程。當(dāng)算法作用于所求解問(wèn)題的給定輸入集或作用于問(wèn)題自身的描述上，將產(chǎn)生唯一確定的有限動(dòng)作序列。此序列或終止于給定問(wèn)題的解，或終止于對(duì)此輸入信息無(wú)解。對(duì)于給定的問(wèn)題，基于對(duì)其的深刻理解，可設(shè)計(jì)出解答該問(wèn)題的一個(gè)算法。在這個(gè)意義上，設(shè)計(jì)算法是將有關(guān)問(wèn)題的知識(shí)，轉(zhuǎn)化為解決問(wèn)題的智慧。知識(shí)誠(chéng)可貴，智慧價(jià)更高。設(shè)計(jì)算法就是揭示所研究問(wèn)題的基本特征，以尋求其解答策略的過(guò)程，這是一項(xiàng)艱苦的創(chuàng)造性工作。對(duì)于給定的問(wèn)題，有可能設(shè)計(jì)出多個(gè)算法，但不同的算法質(zhì)量會(huì)不一樣。衡量算法質(zhì)量的主要因素是算法執(zhí)行所耗費(fèi)的時(shí)間和所需存儲(chǔ)空間，以及算法適用范圍等。對(duì)算法質(zhì)量的分析研究稱為算法分析。算法設(shè)計(jì)和算法分析是計(jì)算機(jī)科學(xué)的核心基礎(chǔ)。國(guó)內(nèi)外大學(xué)的計(jì)算機(jī)專業(yè)中，都將“算法設(shè)計(jì)與分析”作為專業(yè)基礎(chǔ)課。近半個(gè)世紀(jì)以來(lái)，算法研究始終是計(jì)算機(jī)科學(xué)的一個(gè)研究熱點(diǎn)。以E.W.Dijkstra、S.A.Cook、R.M.Karp、J.H.Hopcroft及R.E.Tariall等為代表的一批計(jì)算機(jī)科學(xué)家，以創(chuàng)造性工作推動(dòng)著算法研究不斷深入發(fā)展。在研究過(guò)程中，算法理論研究與軟件技術(shù)研究之間產(chǎn)生了鴻溝，使得算法研究缺乏足夠的實(shí)驗(yàn)支持，而實(shí)驗(yàn)工作又沒(méi)有充分的理論分析。這種現(xiàn)狀弓I起了人們的憂慮。在1996年的ACM計(jì)算理論學(xué)術(shù)年會(huì)（STOC’96）上，一些計(jì)算機(jī)科學(xué)家提出“算法工程”的概念，強(qiáng)調(diào)研究算法實(shí)現(xiàn)技術(shù)的重要性，呼吁算法研究者應(yīng)重視理論與實(shí)踐的結(jié)合，將算法設(shè)計(jì)、分析、實(shí)現(xiàn)、測(cè)試及改進(jìn)等過(guò)程一體化、工程化。這種研究思路越來(lái)越受到人們的關(guān)注，促使算法研究健康發(fā)展。本書原稿寫于20世紀(jì)80年代中期、筆者在山東大學(xué)為計(jì)算機(jī)專業(yè)研究生講授“算法設(shè)計(jì)與分析”課程期間，先后幾經(jīng)修改，于1992年定稿并由山東大學(xué)出版社正式出版。此后一直使用本書作為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)位課教材，由筆者和朱大銘教授共同為研究生講授，效果尚好。經(jīng)過(guò)20多年的研究沉淀，算法設(shè)計(jì)與分析雖然沒(méi)有太多變遷，但其研究?jī)?nèi)容更加豐富和成熟。

內(nèi)容概要

　　《算法設(shè)計(jì)與分析》以算法設(shè)計(jì)策略為知識(shí)單元，系統(tǒng)地介紹計(jì)算機(jī)算法的設(shè)計(jì)方法與分析技巧，以期為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生提供廣泛而堅(jiān)實(shí)的計(jì)算機(jī)基礎(chǔ)知識(shí)。主要內(nèi)容包括算法分析技術(shù)，算法設(shè)計(jì)技術(shù)，P類、NP類及NPC類，證明問(wèn)題屬于NPC類的技術(shù)，NPC問(wèn)題子問(wèn)題的復(fù)雜性，擬多項(xiàng)式變換和圖靈歸約，NP-難解問(wèn)題近似算法，近似算法設(shè)計(jì)技術(shù)，等等。　　《算法設(shè)計(jì)與分析》包括了算法與復(fù)雜性領(lǐng)域的主要內(nèi)容，可以作為高等學(xué)校計(jì)算機(jī)專業(yè)高年級(jí)本科生和研究生學(xué)習(xí)計(jì)算機(jī)算法設(shè)計(jì)的教材，也可供廣大工程技術(shù)人員和自學(xué)者學(xué)習(xí)參考。

書籍目錄

第1章 算法分析技術(shù)§1.1 算法及其復(fù)雜性§1.2 漸近估計(jì)技術(shù)及基本規(guī)則§1.3 遞歸算法分析1.3.1 合并排序算法分析1.3.2 一類遞推方程的一般解§1.4 大整數(shù)相乘的遞歸算法§1.5 練習(xí)第2章 算法設(shè)計(jì)技術(shù)§2.1 分而治之§2.2 貪心技術(shù)§2.3 動(dòng)態(tài)規(guī)劃§2.4 回溯技術(shù)2.4.1 對(duì)策樹搜索與a／B-刪除2.4.2 一般樹的回溯搜索與分支定界§2.5 局部搜索技術(shù)§2.6 練習(xí)第3章 P類、NP類及NPC類§3.1 問(wèn)題與算法§3.2 確定型圖靈機(jī)與P類§3.3 非確定型計(jì)算與NP類§3.4 多項(xiàng)式變換與NPC類§3.5 庫(kù)克定理§3.6 練習(xí)第4章 證明問(wèn)題屬于NPC類的技術(shù)§4.1 基本的NPC問(wèn)題§4.2 證明NP-完全性的典型技術(shù)4.2.1 限制技術(shù)4.2.2 局部替換技術(shù)4.2.3 分支設(shè)計(jì)技術(shù)§4.3 練習(xí)第5章 NPC問(wèn)題子問(wèn)題的復(fù)雜性§5.1 2SAT問(wèn)題屬于P類§5.2 幾個(gè)NPC問(wèn)題在三角化圖上的解5.2.1 三角化圖的特征5.2.2 用字典編輯廣度優(yōu)先搜索識(shí)別三角化圖5.2.3 三角化圖上著色、團(tuán)、獨(dú)立集及團(tuán)覆蓋問(wèn)題的算法§5.3 子問(wèn)題中P和NPC的分界§5.4 練習(xí)第6章 擬多項(xiàng)式變換和圖靈歸約§6.1 判定問(wèn)題、語(yǔ)言和編碼方案§6.2 擬多項(xiàng)式時(shí)間算法和強(qiáng)NPC類§6.3 用擬多項(xiàng)式變換證明強(qiáng)NP-完全性§6.4 復(fù)雜性類之間的關(guān)系§6.5 圖靈歸約和NP-難解問(wèn)題§6.6 練習(xí)第7章 NP-難解問(wèn)題近似算法§7.1 近似算法及其性能評(píng)估§7.2 近似算法設(shè)計(jì)7.2.1 滿足三角不等式的貨郎問(wèn)題及其近似算法7.2.2 滿足三角不等式的貨郎問(wèn)題的最小生成樹算法7.2.3 多任務(wù)排工問(wèn)題的近似算法7.2.4 獨(dú)立任務(wù)排工問(wèn)題§7.3 NP-難解問(wèn)題可近似計(jì)算復(fù)雜性§7.4 多項(xiàng)式時(shí)間近似方案§7.5 練習(xí)第8章 近似算法設(shè)計(jì)技術(shù)§8.1 組合技術(shù)8.1.1 MaxSAT問(wèn)題8.1.2 Maxk-SAT問(wèn)題8.1.3 圖頂點(diǎn)覆蓋問(wèn)題8.1.4 整數(shù)排列與換位移動(dòng)排序8.1.5 集合覆蓋問(wèn)題§8.2 線性規(guī)劃技術(shù)8.2.1 頂點(diǎn)覆蓋近似算法8.2.2 集合覆蓋近似算法§8.3 原始對(duì)偶技術(shù)8.3.1 集合覆蓋8.3.2 擊中集問(wèn)題8.3.3 最短路問(wèn)題8.3.4 Steiner樹問(wèn)題§8.4 局部搜索技術(shù)8.4.1 Max-3SAT問(wèn)題的局部搜索算法8.4.2 K-median問(wèn)題的局部搜索算法8.4.3 設(shè)施定位問(wèn)題的局部搜索近似算法§8.5 隨機(jī)近似算法8.5.1 MaxSAT問(wèn)題的隨機(jī)算法8.5.2 歐氏平面上貨郎問(wèn)題的隨機(jī)算法§8.6 練習(xí)參考文獻(xiàn)

章節(jié)摘錄

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

編輯推薦

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

圖書封面

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

---

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

---