演算法
滄海書局
戴顯權
1.是一本以方法為導向的演算法教科書。
2.採用簡單範例,介紹演算法的基本設計方法,讓讀者易學易懂。
3.內容完整,包含所有大學生應該具備的演算法常識。
4.提供許多難易不等的習題,可供讀者依程度不同來做練習。
(節錄自二版序)
這本書的內容比我在成大電機所與電通所教的淺而且少。但是,這本書不是任何一本書的濃縮本。所有我覺得該介紹到的演算法之基本設計方法都介紹了,但是只採用簡單的範例。畢竟我們要學生學的是演算法的設計方法與觀念,而不是難得一蹋糊塗的範例。不僅如此,凡是會牽涉到另一個專門領域的專業知識的範例,我也小心地避免,因此,我舉的範例都不牽涉到太深的圖論定理。
中央研究院資訊所的高明達研究員認為書儘管簡單,NP-完備的觀念還是需要介紹。我介紹了,而且在參考了各種介紹NP-完備理論的文獻後,我採取了最簡單(但是,觀念正確)的介紹方式。我的目的當然是讓讀者正確地了解NP-完備理論,但是不用那麼辛苦。
這本書的內容雖然比較簡單,但是習題的部分有難有易,為的是讓教師可以依學生的程度選擇給學生做。其中有許多題目其實是我過去在成大設計用來考學生的題目,包括期中考、期末考、入學考試、資格考等。這些題目中即使是最難的也只需要花時間仔細想過就可以解出來,甚至於有些題目只是引導學生去讀一些課外書籍的範例而已。
這本書不以任何程式語言來描述演算法,我們採用虛擬碼。一方面是因為我個人不想因為程式語言的關係把演算法弄得錙銖必較,另一方面也希望學生建立起一個觀念:真正設計演算法的人是不見得需要會寫程式的。把演算法編寫成程式的這些小事留給程式設計師做就可以了,我們要做的是比較高階的部分:設計或選擇出比較好的演算法。這是一般沒學過演算法設計的人做不到的事。
我的恩師李家同教授對於這本書有著許多的期許與鼓勵;另一位恩師杜敏文教授慷慨地指正了這本書一版的幾處錯誤,並且毫無保留地提供了正確的演算法;中央大學資工系何錦文教授對於本書的淘汰與搜尋法提供了許多建設性的意見;中央研究院資訊所高明達研究員、中山大學資工系楊昌彪教授、中興大學資科系曾怜玉教授也都曾直接或間接地提供許多寶貴的建議,讓我一併謝謝他們...
戴顯權
現任:國立成功大學電機工程學系暨電腦與通信工程研究所 教授
學歷:國立清華大學資訊博士、國立台灣大學電機碩士、國立台灣大學電機學士
第一章 介紹
第二章 演算法與問題之分析
第三章 貪婪演算法
第四章 淘汰與搜尋法
第五章 分而治之法
第六章 動態規劃
第七章 NP-完備理論
第八章 處理NP-完備問題
附錄一 中英對照表
附錄二 部分習題解答