本書是國際著名算法專傢李德財教授主編的係列叢書"Lecture Notes Series on Computing”中的一本。本書涵蓋瞭絕大多數算法設計中的一般技術,在錶達每一種技術時,闡述它的應用背景,注意用與其他技術比較的方法說明它的特徵,並提供大量相應實際問題的例子。全書分七部分19章,從算法設計和算法分析的基本概念和方法入手,先後介紹瞭遞歸技術、分治、動態規劃、貪心算法、圖的遍曆等技術,對NP完全問題進行瞭基本但清楚的討論。
作者簡介
硃洪,復旦大學計算機科學係教授,中國計算機學會理論專業委員會常委,中國人工智能學會離散數學專委會主任,中國密碼學會理事。 M. H. Alsuwaiyel在沙特阿拉伯的Kin g Fahd University of Petroleum&Minerals;(KFUPM,皇傢法哈德石油礦業大學)完成大學學業,在南加州(USC)大學獲得計算機科學碩士和博士學位。作者曾任KFUPM的計算機科學係主任、工程與計算機學院院長。他在沙特阿拉伯有廣泛的學術影響,是政府(包括內務部和國防部在內)的高級顧問。
序言 多年來,我一直在尋找一本適閤國內計算機專業學生用的有關算法方麵的國外教材。盡管在國內引進瞭一些不錯的國外教材,但總有篇幅過多,內容不夠新穎或數據結構內容夾雜其中等等這樣那樣的不甚滿意之處。 不久前我有幸看到世界科學圖書齣版社齣版的由M.H.Alsuwaiyel撰寫的“Algorithms Design Techniques and Analysis”,它是以國際著名算法專傢,我國颱灣齣身的李德財教授所主編的係列從書“LectureNotesSeriesonComputing”中的一本。雖然此書不是美國的大學教材,而是沙特阿拉伯的大學計算機係教材,但是我很快就被該書的組織簡明、概括,且包含當前市麵上算法較少涉及的概率算法和近似算法的基本內容所吸引。它是一本適閤本科生學習算法的好書。 該書涉及數據結構的部分較少,即使有一些,描述上也很快與算法中比較復雜的集閤查找和閤並運算等相結閤,讓讀者不會感到和已經學過的數據結構重復。這比較適閤國內大學計算機係中數據結構和算法分成兩門課開設的實際狀況。 對於想瞭解NP完全問題基本概念的讀者,本書的篇幅給瞭他們基本但又清楚的描述。本書還包括計算幾何一章,其取材也是適中的。 概率算法和近似算法是近20年來算法研究迅猛發展的領域,本書給予瞭足夠的重視,這是本書特色之一,是我嚮國內學生特彆推薦的主要原因。 本書的另一特色是以算法的設計技術為綱,講述一個又一個的算法技術,然後分析其算法復雜性。 我希望該書(簡體中文版)的齣版能彌補短期內暫時無閤適中文算法教材的空白。誠摯地嚮國內的廣大算法老師推薦采用本書作為教材。 本書由上海應用技術學院的吳偉昶老師在算法界的老前輩方世昌教授的協助下翻譯。吳偉昶多年來對算法很專研,在翻譯過程中對原著的少量錯誤進行瞭糾正。方世昌教授是算法名著“The Design and Analysis of Computer Algorithms by Aho,Hopcroft and Ullman(1974)”我國最早譯本之一的譯者,雖然該書至今還沒有理想的譯本正式齣版,但是方的譯本在20世紀80年代的我國高校計算機係師生中廣泛流傳,對算法在我國的普及做齣瞭不可磨滅的貢獻。我堅信本譯本的齣版將對我國高校計算機係的算法教學起到很大的推動作用。 硃洪 復旦大學 譯者序 算法設計與分析是計算機科學技術中處於核心地位的一門專業基礎課,越來越受到重視。本書係統地介紹瞭一些常用的、經典的算法設計技術,並給齣瞭詳細的復雜性分析。全書分七部分19章,內容含有遞歸技術、分治、動態規劃、貪心算法、圖的遍曆等,同時也包括瞭近年來發展迅速的近似算法、概率算法和幾何算法,對於NP完全問題等復雜性理論的基礎內容,也做瞭基本的、清楚的描述。本書結構閤理,選材適度,陳述簡明易讀,每章附有適量的各種類型練習,沒有過難或研討性題目,適閤於教學和自學。齣版後已被許多大學選做本科和研究生的教材及參考書。 多年來,我一直在尋找一本適閤國內計算機專業學生用的有關算法方麵的國外教材。盡管在國內引進瞭一些不錯的國外教材,但總有篇幅過多,內容不夠新穎或數據結構內容夾雜其中等等這樣那樣的不甚滿意之處。 不久前我有幸看到世界科學圖書齣版社齣版的由M.H.Alsuwaiyel撰寫的“Algorithms Design Techniques and Analysis”,它是以國際著名算法專傢,我國颱灣齣身的李德財教授所主編的係列從書“LectureNotesSeriesonComputing”中的一本。雖然此書不是美國的大學教材,而是沙特阿拉伯的大學計算機係教材,但是我很快就被該書的組織簡明、概括,且包含當前市麵上算法較少涉及的概率算法和近似算法的基本內容所吸引。它是一本適閤本科生學習算法的好書。 該書涉及數據結構的部分較少,即使有一些,描述上也很快與算法中比較復雜的集閤查找和閤並運算等相結閤,讓讀者不會感到和已經學過的數據結構重復。這比較適閤國內大學計算機係中數據結構和算法分成兩門課開設的實際狀況。 對於想瞭解NP完全問題基本概念的讀者,本書的篇幅給瞭他們基本但又清楚的描述。本書還包括計算幾何一章,其取材也是適中的。 概率算法和近似算法是近20年來算法研究迅猛發展的領域,本書給予瞭足夠的重視,這是本書特色之一,是我嚮國內學生特彆推薦的主要原因。 本書的另一特色是以算法的設計技術為綱,講述一個又一個的算法技術,然後分析其算法復雜性。 我希望該書(簡體中文版)的齣版能彌補短期內暫時無閤適中文算法教材的空白。誠摯地嚮國內的廣大算法老師推薦采用本書作為教材。 本書由上海應用技術學院的吳偉昶老師在算法界的老前輩方世昌教授的協助下翻譯。吳偉昶多年來對算法很專研,在翻譯過程中對原著的少量錯誤進行瞭糾正。方世昌教授是算法名著“The Design and Analysis of Computer Algorithms by Aho,Hopcroft and Ullman(1974)”我國最早譯本之一的譯者,雖然該書至今還沒有理想的譯本正式齣版,但是方的譯本在20世紀80年代的我國高校計算機係師生中廣泛流傳,對算法在我國的普及做齣瞭不可磨滅的貢獻。我堅信本譯本的齣版將對我國高校計算機係的算法教學起到很大的推動作用。