算法設(shè)計與分析

前言

進入21世紀，各國高科技發(fā)展突飛猛進，對教育資源、人才資源的爭奪也日益激烈，計算機軟件開發(fā)人才更是處在核心競爭地位。培養(yǎng)應(yīng)用型軟件開發(fā)人才成為提高國家科技實力的重要步驟。國家973信息技術(shù)與高性能軟件基礎(chǔ)規(guī)劃項目首席科學(xué)家顧鈞教授和中國工程院院士李國杰教授指出：“我國的軟件開發(fā)要算法先行，這樣才能推動軟件技術(shù)的研究與開發(fā)，提高我國企業(yè)軟件產(chǎn)品的技術(shù)競爭力和市場競爭力。”算法設(shè)計與分析是一門理論性與實踐性相結(jié)合的課程，是計算機科學(xué)與計算機應(yīng)用專業(yè)的核心課程。學(xué)習(xí)算法設(shè)計可以在分析解決問題的過程中，培養(yǎng)學(xué)生抽象思維和縝密概括的能力，提高學(xué)生的軟件開發(fā)設(shè)計能力。本書共包含4篇：（1） 第1篇“引入篇”共兩章，從認識算法開始，介紹問題求解的步驟及算法在其中的重要地位，講解了算法效率分析的基本方法，對當(dāng)前常用的算法軟件進行了簡要概述（可作為選修）。（2） 第2篇“基礎(chǔ)篇”，對算法的重復(fù)操作機制——循環(huán)和遞歸的設(shè)計要點、算法中數(shù)據(jù)結(jié)構(gòu)的選擇和提高算法效率的基本技巧做了講解，這些都是算法設(shè)計的重要基礎(chǔ)。（3） 第3篇“核心篇”共兩章，主要介紹了幾種常用的算法策略，如遞推法、枚舉法、分治法、貪婪算法、動態(tài)規(guī)劃及與圖搜索有關(guān)的算法策略，并對算法策略進行了總結(jié)比較。（4） 第4篇“應(yīng)用篇”，以問題為節(jié)，每節(jié)中針對同一問題采用不同的數(shù)學(xué)模型、不同數(shù)據(jù)結(jié)構(gòu)或不同的算法策略進行算法設(shè)計，并進行效率分析。這部分內(nèi)容是對算法設(shè)計學(xué)習(xí)的實踐。本教材建設(shè)的理念是“實用、適用”。書中的例題選擇力求簡單但具有代表性，例題講解注重解題的思維過程，這樣做有利于培養(yǎng)學(xué)生“設(shè)計”算法的能力，而不是“記憶” 算法的能力，并力爭淺顯易懂地講解較深奧的算法設(shè)計策略和算法分析方法。本書的主要特點有:1） 重系統(tǒng)性教材的第3篇“核心篇”摒棄同類教材中離散地羅列例題的方法，通過對算法策略特點的概括和歸納，以同一策略下的應(yīng)用差別來劃分章節(jié)，使得教材結(jié)構(gòu)更合理、講解更系統(tǒng)、更加符合認知規(guī)律。同時，在各章末尾對算法進行比較、總結(jié)，使學(xué)生能方便、全面地掌握算法策略的本質(zhì)及算法應(yīng)用體系。2） 重啟發(fā)性本書中例題都是經(jīng)過問題分析、數(shù)學(xué)建模、數(shù)據(jù)結(jié)構(gòu)設(shè)計后，才給出算法設(shè)計和算法分析。這樣講解解題的思維過程，富有啟發(fā)性，不僅培養(yǎng)了學(xué)生算法設(shè)計的思維方式，而且還能改變學(xué)生被動接受知識的習(xí)慣。書中多處提出供讀者深入思考的問題，旨在培養(yǎng)學(xué)生主動學(xué)習(xí)的意識，進而提高創(chuàng)新能力。3） 重適用性第2篇“基礎(chǔ)篇”是從程序設(shè)計到算法設(shè)計承上啟下的內(nèi)容，對問題求解的基本方法、算法基本工具的使用及提高算法效率的基本技巧做了必要的總結(jié)、歸納。相信這些內(nèi)容會給普通院校的廣大學(xué)生有較大的裨益，促進其打好學(xué)習(xí)算法設(shè)計的基礎(chǔ)。彌補了以往教材缺乏課程間銜接內(nèi)容的缺陷，增強了學(xué)生學(xué)習(xí)該課程的自信心，提高了教學(xué)效率。4） 重開放性教材在第1篇中對現(xiàn)代算法進行了概覽，旨在擴大學(xué)生的知識面，提高其對算法設(shè)計的學(xué)習(xí)興趣。教材還獨特地介紹了從算法到程序轉(zhuǎn)換的要點，引導(dǎo)學(xué)生不能僅停留在形式化的算法描述階段，而是要大膽上機實現(xiàn)，提高學(xué)生學(xué)習(xí)本學(xué)科的興趣。5） 重實踐性第4篇“應(yīng)用篇”是本教材的一大亮點。該篇以問題為節(jié)，每節(jié)中針對同一問題采用不同的數(shù)學(xué)模型、不同的數(shù)據(jù)結(jié)構(gòu)或不同的算法策略進行算法設(shè)計，擴展學(xué)生解決問題的思路，學(xué)會靈活運用算法知識，而不是生搬硬套教材中的算法。同時，也可以通過對多種算法設(shè)計的分析比較認識算法的優(yōu)劣，從而設(shè)計出質(zhì)量優(yōu)良的算法。在學(xué)習(xí)算法設(shè)計的過程中，可能有讀者感到所學(xué)的內(nèi)容和大多例題都離現(xiàn)實問題較遠，似乎用途不大。這是因為現(xiàn)實中的實際問題往往較復(fù)雜，需要具備豐富的領(lǐng)域知識、算法設(shè)計方法和技巧規(guī)范及軟件工程的開發(fā)規(guī)范等綜合技能。所以，只能通過一些簡單、抽象的例子，對基礎(chǔ)的算法策略進行講解。待打好算法設(shè)計基礎(chǔ)且有足夠的問題領(lǐng)域知識儲備后，才能去解決實際應(yīng)用問題。附錄“算法設(shè)計與分析課程設(shè)計大綱”中給出一些與現(xiàn)實結(jié)合相對較緊的練習(xí)，區(qū)別于章節(jié)習(xí)題，希望讀者廣開思路。隨著信息化時代的到來，計算機開發(fā)平臺日新月異，軟件應(yīng)用拓展到了各個領(lǐng)域，各類算法和技巧層出不窮，本書只能是管中窺豹。若能達到本書的初衷——使讀者能掌握到算法設(shè)計的基本方法和技巧，打好軟件開發(fā)的基礎(chǔ)，就深感滿意了。山西大學(xué)及作者所在的計算機與信息技術(shù)學(xué)院在教材的建設(shè)中給予了充分支持，為本書的寫作和教學(xué)實踐提供了良好的環(huán)境。教材出版單位清華大學(xué)出版社的編輯們更是為此書傾注了大量心血。在此，向各位關(guān)心和支持本書出版的人士表示衷心的感謝！由于水平有限，雖然力爭精確，仍難免存在缺點和錯誤，書中不當(dāng)之處敬請專家和讀者指正。

內(nèi)容概要

本教材的內(nèi)容遵循《中國計算機科學(xué)與技術(shù)學(xué)科教程2002》（China Computing Curricula 2002，CCC2002）的知識體系，介紹算法及其設(shè)計、分析的基礎(chǔ)知識，并通過大量例題，講解枚舉法、遞推法、分治法、貪婪算法、動態(tài)規(guī)劃及與圖搜索有關(guān)的算法策略。除此之外，還對算法設(shè)計基本工具的使用和算法設(shè)計中的技巧做了講解。最后通過例題進行算法設(shè)計的實踐。算法用了接近自然語言（英語）的符號，可讀性強，適合于不同程序設(shè)計語言背影的讀者學(xué)習(xí)。    本書可以作為高等院校計算機及其相關(guān)專業(yè)高年級本科生和研究生算法設(shè)計課程的教材，也可作為計算機工作者、廣大程序設(shè)計愛好者和信息學(xué)愛好者的參考書。

書籍目錄

第1篇　引入篇　第1章　算法概述　　1.1　用計算機求解問題與算法　　1.2　算法描述　　1.3　現(xiàn)代常用算法概覽　第2章　算法分析基礎(chǔ)　　2.1　算法分析體系及計量　　2.2　算法分析實例第2篇　基礎(chǔ)篇　第3章　算法基本工具和優(yōu)化技巧　　3.1　循環(huán)與遞歸　　　3.2　算法與數(shù)據(jù)結(jié)構(gòu)　　3.3　優(yōu)化算法的基本技巧　　3.4　優(yōu)化算法的數(shù)學(xué)模型　　習(xí)題第3篇　核心篇　第4章　基本的算法策略　　4.1　迭代算法　　4.2　蠻力法　　4.3　分而治之算法　　4.4　貪婪算法　　4.5　動態(tài)規(guī)劃　　4.6　算法策略間的比較　　習(xí)題　第5章　圖的搜索算法　　5.1　圖搜索概述　　5.2　廣度優(yōu)先搜索　　5.3　深度優(yōu)先搜索　　5.4　回溯法　　5.5　分支限界法　　5.6　圖的搜索算法小結(jié)　　習(xí)題第4篇　應(yīng)用篇　第6章　算法設(shè)計實踐　　6.1　循環(huán)賽日程表（4種）　　6.2　求3個數(shù)的最小公倍數(shù)（4種）　　6.3　猴子選大王（4種）　　6.4　最大子段和問題（5種）　　6.5　背包問題（11種）附錄　算法設(shè)計與分析課程設(shè)計大綱

章節(jié)摘錄

插圖：

編輯推薦

《算法設(shè)計與分析(第2版)》由清華大學(xué)出版社出版。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法設(shè)計與分析 PDF格式下載

---