大學算法教程

目 錄
第1章 引言
1.1 算法
1.2 表述算法的偽代碼
1.3 現狀
1.4 未來發展
備考
本章習題
第2章 算法涉及的基本數學概念
2.1 定義、記號和基本結論
2.2 數學歸納法
2.3 算法分析
2.4 遞推關系
2.5 圖
2.6 樹
備考
本章習題
第3章 數據結構
3.1　抽象數據類型
3.2 堆棧和隊列
3.3 鏈接表
3.4 二叉樹
3.5 優先隊列，二分堆陣，堆陣排序
3.6 不相交集
備考
本章習題
第4章 搜索
4.1 對分搜索
4.2 深度優先搜索
4.3 廣度優先搜索
4.4 拓撲排序
4.5 回溯法
備考
本章習題
第5章 分而治之
5.1 平鋪問題
5.2 歸並排序
5.3 尋找最近點對
5.4 Strassen的矩陣乘法算法
備考
本章習題
第6章 排序和選擇
6.1 插入排序
6.2 快速排序
6.3 排序問題的下界
6.4 計數排序和基數排序
6.5 選擇
備考
本章習題
第7章 貪心算法
7.1 硬幣兌換
7.2 Kruskal算法
7.3 Prim算法
7.4 Dijkstra算法
7.5 霍夫曼編碼
7.6 連續背包問題
備考
本章習題
第8章 動態規劃算法
8.1 計算斐波那契數列
8.2 硬幣兌換問題再探討
8.3 矩陣乘法
8.4 最長公共子串問題
8.5 Floyd算法和Warshall算法
備考
本章習題
第9章 文本搜索
9.1 簡單的文本搜索
9.2 Rabin-Karp算法
9.3 Knuth-Morris-Pratt算法
9.4 Boyer-Moore-Horspool算法
9.5 近似模式匹配
9.6 正則表達式匹配
備考
本章習題
……

算法是涉及“計算”的眾多學科的一個共同話題。它包括算法的設計、分析、實現和應用。算法的基本問題是︰什麼樣的問題能有效地用計算機自動地加以解決；什麼樣的問題則不能。自20世紀30年代以來，這個原本由數學家關心、研究的課題，已經發展成為計算機科學的有力武器。算法已是今天計算機科學技術專業及相關專業的重要基礎課程。實際上，它對于這些專業領域的從業人員來說，往往是終身要與之打交道的一門學問。因為任何一個計算機應用系統，都要經歷“問題的提出——數學模型的建立——算法的設計與評測——程序代碼的編制——計算機系統上的實現”幾個階段，這整個過程中，算法處于承上啟下的關鍵地位。但是在我國大學相關專業的課程設置中，即使是計算機專業，算法的系統學習和訓練也是被安排為本科高年級或研究生課程。實際上，算法的理念應當貫穿于專業教學的全過程。
要把算法教科書編寫得有血有肉、生動有趣(更不用說是出神入化)，確實需要相當的功底。本書作者R．Johnsonbaugh等人長期講授算法課程，有著豐富的教學經驗積累。實踐證明，使用恰當的實例，將會起到穿針引線的作用。本書就是選用了大量的發生在生活、學習中的應用實例，理論結合實際地進行闡述。書中除了少數章節和習題需要概率論和數學分析知識外，盡量使用初等方法，由淺入深、由此及彼地進行分析，努力做到循循善誘，全書不乏引人之處。300多個經過驗證的實例有助于學生抓住各種算法的精神實質，領會應用，並逐步學會設計和評價算法。
本教材主要由以下幾個部分組成。第1部分包括第l～3章，是有關算法的一些基礎知識的復習和回顧。其中包括算法的偽代碼描述介紹、算法的表示、正確性證明以及算法分析中常用的數學方法及各種常用記號的表示。這部分還講述了本書用到的基本數據結構，包括圖、樹、鏈接表、隊列和堆等。
第2部分包括第4～9章，是一些常用算法和應用，包括搜索、排序和選擇，以及分治、貪心、動態規劃等基本方法。這部分的內容相當豐富，除常見的廣度優先搜索、深度優先搜索、拓撲排序、歸並排序、快速排序、計數排序、基數排序外，還包括文本搜索、近似模式匹配、正則表達式匹配和回溯。對分治法的介紹是結合平鋪問題、最近點對尋找問題、矩陣乘法問題的實例進行的。貪心算法是結合硬幣兌換、Huffman編碼和連續背包問題進行討論的。動態規劃方法的介紹從計算Fibonacci數列開始，並針對硬幣兌換問題將動態規劃算法和貪心算法作了比較，然後進入矩陣乘法、最長公共子串問題的動態規劃方法的討論，並在有關部分介紹了許多行之有效的算法名著或結果。
第3部分包括第10-1l章，討論了P與NP問題，以及NP完全性問題的處理方法。這是本書內容中相當精彩的部分，包括不確定算法和NP；NP完全性問題和歸約；各種各樣的NP完全性問題，例如獨立集和團、圖的著色、移動電話網絡、背包問題、調度問題、掃雷游戲、縱橫字謎、裝箱問題、密碼問題、蛋白質褶和計算生物學等等，以及它們之間的等價性。所用的方法包括蠻干法、隨機方法、近似方法、參數化和啟發式試探方法等。
第4部分包括第12章，介紹了並行和分布算法。從求最大值的並行化方法著手，介紹並行隨機存取機器(PRAM)時，涉及了半群算法和加速級聯、並行前綴、指針跳轉等方法；介紹排序網絡時，引入了雙調排序、歸並和排序、排序網絡的0—1原理等；在介紹並行體系結構時，討論了並行體系多處理器之間的拓撲結構及其標記問題等；在介紹分布式算法時，討論了網上廣播和主播機的選擇等問題。
在上述各個部分，除了闡明眾所周知的許多經典算法外，還循序漸進地介紹了相關算法的改進和最新成果。每章還附有一個“備考”欄目，介紹有關專題的歷史沿革和最新進展，供讀者進一步查閱，以擴充加深自己的知識和技能。
全書共有1100多道節後習題，有助于學生理解相關內容，檢查自己對知識的掌握程度。各章末都有本章習題，共有350多道。從整體上說，它們比節後習題要稍難些。其中有些題目相當難，甚至可以當作一個小的課題，可能需要教師的適當指導才能完成。
本書由方存正、曹曼、華明三位老師翻譯，方存正負責序言、第l章、第5～7章，華明負責第2～4章，曹曼負責第8～12章，習題選解由各章譯者分別完成。方存正老師還對書的後半部分的譯稿作了訂正。吳洪來老師負責全書統稿和審校。雖然譯者盡了努力，但仍可能存在不妥和謬誤之處，殷切期望讀者和老師們不吝賜教。