算法設計與分析

前言

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

內容概要

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

書籍目錄

第1章 算法分析技術§1.1 算法及其復雜性§1.2 漸近估計技術及基本規(guī)則§1.3 遞歸算法分析1.3.1 合并排序算法分析1.3.2 一類遞推方程的一般解§1.4 大整數相乘的遞歸算法§1.5 練習第2章 算法設計技術§2.1 分而治之§2.2 貪心技術§2.3 動態(tài)規(guī)劃§2.4 回溯技術2.4.1 對策樹搜索與a／B-刪除2.4.2 一般樹的回溯搜索與分支定界§2.5 局部搜索技術§2.6 練習第3章 P類、NP類及NPC類§3.1 問題與算法§3.2 確定型圖靈機與P類§3.3 非確定型計算與NP類§3.4 多項式變換與NPC類§3.5 庫克定理§3.6 練習第4章 證明問題屬于NPC類的技術§4.1 基本的NPC問題§4.2 證明NP-完全性的典型技術4.2.1 限制技術4.2.2 局部替換技術4.2.3 分支設計技術§4.3 練習第5章 NPC問題子問題的復雜性§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 復雜性類之間的關系§6.5 圖靈歸約和NP-難解問題§6.6 練習第7章 NP-難解問題近似算法§7.1 近似算法及其性能評估§7.2 近似算法設計7.2.1 滿足三角不等式的貨郎問題及其近似算法7.2.2 滿足三角不等式的貨郎問題的最小生成樹算法7.2.3 多任務排工問題的近似算法7.2.4 獨立任務排工問題§7.3 NP-難解問題可近似計算復雜性§7.4 多項式時間近似方案§7.5 練習第8章 近似算法設計技術§8.1 組合技術8.1.1 MaxSAT問題8.1.2 Maxk-SAT問題8.1.3 圖頂點覆蓋問題8.1.4 整數排列與換位移動排序8.1.5 集合覆蓋問題§8.2 線性規(guī)劃技術8.2.1 頂點覆蓋近似算法8.2.2 集合覆蓋近似算法§8.3 原始對偶技術8.3.1 集合覆蓋8.3.2 擊中集問題8.3.3 最短路問題8.3.4 Steiner樹問題§8.4 局部搜索技術8.4.1 Max-3SAT問題的局部搜索算法8.4.2 K-median問題的局部搜索算法8.4.3 設施定位問題的局部搜索近似算法§8.5 隨機近似算法8.5.1 MaxSAT問題的隨機算法8.5.2 歐氏平面上貨郎問題的隨機算法§8.6 練習參考文獻

章節(jié)摘錄

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

編輯推薦

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

圖書封面

評論、評分、閱讀與下載

---

    算法設計與分析 PDF格式下載

---