21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材編委會(huì)
主任： 李曉明副主任： 蔣宗禮盧先和委員： （按姓氏筆畫為序）
馬華東馬殿富王志英王曉東寧洪
劉辰孫茂松李仁發(fā)李文新楊波
吳朝暉何炎祥宋方敏張莉金海
周興社孟祥旭袁曉潔錢樂秋黃國(guó)興
曾明廖明宏秘書： 張瑞慶



本書責(zé)任編委： 宋方敏

前言FOREWORD
以最低的成本、最快的速度、最好的質(zhì)量開發(fā)出適合各種應(yīng)用需求的軟件，必須遵循軟件工程的原則，設(shè)計(jì)出高效率的程序。一個(gè)高效的程序不僅需要編程技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法。這正是計(jì)算機(jī)科學(xué)領(lǐng)域里數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)所研究的主要內(nèi)容。一些著名的計(jì)算機(jī)科學(xué)家在有關(guān)計(jì)算機(jī)科學(xué)教育的論述中提出，計(jì)算機(jī)科學(xué)是一種創(chuàng)造性思維活動(dòng)，其教育必須面向設(shè)計(jì)。計(jì)算機(jī)算法設(shè)計(jì)與分析正是一門面向設(shè)計(jì)，且處于計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科核心地位的教育課程。通過對(duì)計(jì)算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究，理解和掌握算法設(shè)計(jì)的主要方法，培養(yǎng)對(duì)算法的計(jì)算復(fù)雜性進(jìn)行正確分析的能力，為獨(dú)立地設(shè)計(jì)算法和對(duì)給定算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ)，對(duì)從事計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件研究與開發(fā)的科技工作者是非常重要和必不可少的。為了適應(yīng)我國(guó)21世紀(jì)計(jì)算機(jī)人才培養(yǎng)的需要，結(jié)合我國(guó)高等學(xué)校教育工作的現(xiàn)狀，立足培養(yǎng)學(xué)生能跟上國(guó)際計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展水平，更新教學(xué)內(nèi)容和教學(xué)方法，本書以算法設(shè)計(jì)策略為知識(shí)單元，系統(tǒng)地介紹計(jì)算機(jī)算法的設(shè)計(jì)方法與分析技巧，以期為計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的學(xué)生提供一個(gè)廣泛而堅(jiān)實(shí)的計(jì)算機(jī)算法基礎(chǔ)知識(shí)。
全書共分11章。在第１章中首先介紹算法的基本概念，接著簡(jiǎn)要闡述算法的計(jì)算復(fù)雜性和算法的描述，然后圍繞設(shè)計(jì)算法常用的基本設(shè)計(jì)策略組織第２章至第10章的內(nèi)容。第2章介紹遞歸與分治策略，這是設(shè)計(jì)有效算法最常用的策略，是必須掌握的方法。第3章是動(dòng)態(tài)規(guī)劃算法，以具體實(shí)例詳述動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想、適用性以及算法的設(shè)計(jì)要點(diǎn)。第4章介紹貪心算法，這也是一種重要的算法設(shè)計(jì)策略，它與動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想有一定的聯(lián)系，但其效率更高。按貪心算法設(shè)計(jì)出的許多算法能導(dǎo)致最優(yōu)解，其中有許多典型問題和典型算法可供學(xué)習(xí)和使用。第５章和第６章分別介紹回溯法和分支限界法，這兩章所介紹的算法適合處理難解問題，其解題的思想各具特色，值得學(xué)習(xí)和掌握。第７章介紹概率算法，對(duì)許多難解問題提供高效的解決途徑，是有很高實(shí)用價(jià)值的算法設(shè)計(jì)策略。第８章介紹NP完全性理論和解NP難問題的近似算法。首先介紹計(jì)算模型、確定性和非確定性圖靈機(jī)，然后進(jìn)一步深入介紹NP完全性理論，最后介紹解NP難問題的近似算法，這是當(dāng)前計(jì)算機(jī)算法領(lǐng)域的熱門研究課題，具有很高的實(shí)用價(jià)值。第9章介紹有關(guān)串和序列的高效算法。第10章通過實(shí)例介紹算法設(shè)計(jì)中常用的算法優(yōu)化策略。最后，在第11章介紹算法設(shè)計(jì)中較新的研究領(lǐng)域在線算法設(shè)計(jì)。
在本書各章的論述中，首先介紹一種算法設(shè)計(jì)策略的基本思想，然后從解決計(jì)算機(jī)科學(xué)與應(yīng)用中出現(xiàn)的實(shí)際問題入手，由簡(jiǎn)到繁地描述幾個(gè)經(jīng)典的精巧算法，同時(shí)對(duì)每個(gè)算法所需要的時(shí)間和空間進(jìn)行分析。這樣使讀者既能學(xué)到一些常用的精巧算法，又能通過對(duì)算法設(shè)計(jì)策略的反復(fù)應(yīng)用，牢固掌握這些算法設(shè)計(jì)的基本策略，以期收到融會(huì)貫通之效。在為各種算法設(shè)計(jì)策略選擇用于展示其設(shè)計(jì)思想與技巧的具體應(yīng)用問題時(shí)，本書有意重復(fù)選擇某些經(jīng)典問題，使讀者能深刻地體會(huì)到一個(gè)問題可以用多種設(shè)計(jì)策略求解。同時(shí)，通過對(duì)解同一問題的不同算法的比較，更容易體會(huì)到每一個(gè)具體算法的設(shè)計(jì)要點(diǎn)。隨著本書內(nèi)容的逐步展開，讀者也將進(jìn)一步感受到綜合應(yīng)用多種設(shè)計(jì)策略可以更有效地解決問題。
本書采用面向?qū)ο蟮腏ava語(yǔ)言作為表述手段，在保持Java優(yōu)點(diǎn)的同時(shí)，盡量使算法的描述簡(jiǎn)明、清晰。
為了便于讀者加深對(duì)知識(shí)的理解，各章配有難易適當(dāng)?shù)牧?xí)題，以適應(yīng)不同程度讀者練習(xí)的需要。
在本書的編寫過程中，得到教育部高等學(xué)校計(jì)算機(jī)類專業(yè)教學(xué)指導(dǎo)委員會(huì)的關(guān)心和支持。福州大學(xué)211工程計(jì)算機(jī)與信息工程重點(diǎn)學(xué)科實(shí)驗(yàn)室和福建工程學(xué)院為本書的寫作提供了優(yōu)良的設(shè)備與工作環(huán)境。清華大學(xué)出版社負(fù)責(zé)本書編輯出版工作的全體人員為本書的出版付出了大量辛勤勞動(dòng)，他們認(rèn)真細(xì)致、一絲不茍的工作精神保證了本書的出版質(zhì)量。南京大學(xué)宋方敏教授和福州大學(xué)傅清祥教授在百忙中認(rèn)真審閱了全書，提出了許多寶貴的改進(jìn)意見。在此，謹(jǐn)向每一位曾經(jīng)關(guān)心和支持本書編寫工作的各方面人士表示衷心的謝意！
由于作者的知識(shí)和寫作水平有限，書稿雖幾經(jīng)修改，仍難免存在缺點(diǎn)。熱忱歡迎同行專家和讀者惠予批評(píng)指正，使本書在使用過程中不斷改進(jìn)，日臻完善。作者2018年6月前言算法設(shè)計(jì)與分析(第4版)