算法設(shè)計(jì)與分析

前言

民眾多好飲酒，中外概莫能外。酒館和釀酒坊伴隨飲酒客而起，人類(lèi)對(duì)酒的喜愛(ài)造就了酒文化和一個(gè)龐大的產(chǎn)業(yè)。好酒能賣(mài)好價(jià)錢(qián)，能使文人詩(shī)興大發(fā)，催生佳作，還能解人間百難。于是，釀天下名酒自然成為不少人的畢生追求。怎樣才能釀出好酒呢？國(guó)人的看法不盡相同。崇信洋酒的人主張引進(jìn)國(guó)外的生產(chǎn)工藝，學(xué)習(xí)洋人的生產(chǎn)和經(jīng)營(yíng)理念，而喜歡國(guó)酒的人則主張走自己的路，但不排除借鑒國(guó)外先進(jìn)的科學(xué)技術(shù)和管理經(jīng)驗(yàn)。這樣的爭(zhēng)論或許永遠(yuǎn)不會(huì)終結(jié)，但外國(guó)人重視科學(xué)釀酒，這一點(diǎn)是值得我們學(xué)習(xí)和借鑒的。計(jì)算機(jī)科學(xué)教育，如同釀酒工業(yè)的生產(chǎn)一樣，科學(xué)辦學(xué)迄今還只是部分學(xué)者的一種理想。與國(guó)內(nèi)一樣，國(guó)外的計(jì)算機(jī)科學(xué)教育并沒(méi)有像他們的科學(xué)釀酒業(yè)一樣，實(shí)現(xiàn)科學(xué)辦學(xué)。也許科學(xué)辦學(xué)要遠(yuǎn)比科學(xué)釀酒困難得多。譬如，怎么實(shí)現(xiàn)科學(xué)辦學(xué)？甚至怎么推出一套科學(xué)的系列教材都是一篇大文章。這套教材的創(chuàng)作始于教育部面向21世紀(jì)教育與教學(xué)改革13-22項(xiàng)目的研究。2000年，在13-22項(xiàng)目研究工作即將完成之際，一些學(xué)者開(kāi)始認(rèn)識(shí)到面對(duì)計(jì)算機(jī)科學(xué)與技術(shù)的高速發(fā)展，我們亟需一套體現(xiàn)科學(xué)辦學(xué)思想、反映內(nèi)涵發(fā)展要求、服務(wù)教育與教學(xué)改革、參與構(gòu)建學(xué)科人才培養(yǎng)科學(xué)體系的系列教材。強(qiáng)調(diào)系列教材是因?yàn)槟菚r(shí)已經(jīng)意識(shí)到計(jì)算機(jī)科學(xué)教育本質(zhì)上是一項(xiàng)科學(xué)活動(dòng)，但長(zhǎng)期以來(lái)教師向?qū)W生傳授科學(xué)技術(shù)知識(shí)的方式方法科學(xué)性不強(qiáng)。由于高等教育幾百年來(lái)一直沿襲經(jīng)驗(yàn)方式而非科學(xué)方式辦學(xué)，大學(xué)教學(xué)的方式方法仍然還停留在古代作坊式的階段，只不過(guò)今天使用的教學(xué)技術(shù)手段先進(jìn)而已。在經(jīng)驗(yàn)辦學(xué)方式下，無(wú)論是研究型大學(xué)還是教學(xué)型大學(xué)，由于種種原因，教學(xué)活動(dòng)的全過(guò)程存在著太多的漏洞和質(zhì)量上的隱患。科學(xué)辦學(xué)是對(duì)高等教育界傳統(tǒng)的一個(gè)挑戰(zhàn)，盡管在認(rèn)識(shí)上，人們不難理解，科學(xué)辦學(xué)是經(jīng)驗(yàn)辦學(xué)的最高形式，而經(jīng)驗(yàn)辦學(xué)應(yīng)該成為科學(xué)辦學(xué)的有益補(bǔ)充。

內(nèi)容概要

　　《算法設(shè)計(jì)與分析》主要取材于算法設(shè)計(jì)與分析領(lǐng)域的經(jīng)典內(nèi)容，并介紹了算法設(shè)計(jì)的發(fā)展趨勢(shì)。內(nèi)容主要包括非常經(jīng)典的算法設(shè)計(jì)技術(shù)，例如遞歸與分治、動(dòng)態(tài)規(guī)劃、貪心、回溯、分支限界、圖算法，也包括了一些高級(jí)的算法設(shè)計(jì)主題，例如網(wǎng)絡(luò)流和匹配、啟發(fā)式搜索、線性規(guī)劃、數(shù)論以及計(jì)算幾何。在算法分析方面，介紹了概率分析以及最新的分?jǐn)偡治龊蛯?shí)驗(yàn)分析方法。在算法的理論方面，介紹了問(wèn)題的下界、算法的正確性證明以及NP完全理論等方面的內(nèi)容?！端惴ㄔO(shè)計(jì)與分析》包括大量的問(wèn)題實(shí)例，并給出了相應(yīng)的設(shè)計(jì)與分析方法，書(shū)后精選了一些習(xí)題，供讀者練習(xí)，以鞏固所學(xué)的算法。工業(yè)應(yīng)用領(lǐng)域的許多實(shí)際問(wèn)題和疑難問(wèn)題都需要有效的求解算法，《算法設(shè)計(jì)與分析》提供了設(shè)計(jì)有效算法的基礎(chǔ)以及大量的可供選擇的解決途徑?！　　端惴ㄔO(shè)計(jì)與分析》內(nèi)容基本上涵蓋了目前程序設(shè)計(jì)競(jìng)賽所要掌握的算法，并在書(shū)后精選了部分ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽的題目，供大家練習(xí)?！　　端惴ㄔO(shè)計(jì)與分析》可作為計(jì)算機(jī)科學(xué)系、數(shù)學(xué)系、軟件學(xué)院等專(zhuān)業(yè)本科及研究生課程的教材，特別適合于有志于參加程序設(shè)計(jì)競(jìng)賽的學(xué)生學(xué)習(xí)和訓(xùn)練。

書(shū)籍目錄

第1章 入門(mén)1.1 問(wèn)題1.2 算法的概念1.3 算法的正確性1.4 算法的效率1.5 問(wèn)題的下界1.6 小結(jié)習(xí)題實(shí)驗(yàn)題第2章 漸近符號(hào)2.1 θ符號(hào)2.2 O符號(hào)2.3 η符號(hào)2.4 漸近符號(hào)的性質(zhì)2.5 常用函數(shù)的直觀含義2.6 小結(jié)習(xí)題第3章 算法分析方法3.1 概率分析3.2 分?jǐn)偡治?.2.1 合計(jì)方法3.2.2 記賬方法3.2.3 勢(shì)能方法3.3 實(shí)驗(yàn)分析3.4 小結(jié)習(xí)題第4章 遞歸4.1 算法思想4.1.1 遞歸算法的應(yīng)用4.1.2 遞歸與迭代4.2 遞歸方程的求解4.2.1 替換方法4.2.2 遞歸樹(shù)方法4.2.3 式：去4.3 多項(xiàng)式求值實(shí)驗(yàn)4.4 小結(jié)習(xí)題實(shí)驗(yàn)題第5章 分治算法5.1 算法思想5.2 合并排序5.3 快速排序5.4 大整數(shù)乘法5.5 矩陣乘法5.6 殘缺棋盤(pán)游戲、5.7 快速傅里葉變換(FFT)5.8 小結(jié)習(xí)題實(shí)驗(yàn)題第6章 動(dòng)態(tài)規(guī)劃6.1 算法思想6.2 裝配線調(diào)度問(wèn)題6.3 矩陣鏈乘法問(wèn)題6.4 最長(zhǎng)公共子序列問(wèn)題6.5 0／1背包問(wèn)題6.6 最優(yōu)二叉搜索樹(shù)問(wèn)題6.7 動(dòng)態(tài)規(guī)劃的基本性質(zhì)6.8 小結(jié)習(xí)題實(shí)驗(yàn)題第7章 貪心算法7.1 算法思想7.2 任務(wù)選擇問(wèn)題7.3 背包問(wèn)題7.4 哈夫曼編碼問(wèn)題7.5 緩存維護(hù)問(wèn)題7.6 任務(wù)選擇問(wèn)題實(shí)驗(yàn)7.7 小結(jié)習(xí)題實(shí)驗(yàn)題第8章 圖算法8.1 圖的搜索問(wèn)題8.1.1 寬度優(yōu)先搜索8.1.2 深度優(yōu)先搜索8.2 最小生成樹(shù)問(wèn)題8.2.1 Kruskall算法8.2.2 Prim算法8.3 最短路徑問(wèn)題8.3.1 單個(gè)源點(diǎn)的最短路徑問(wèn)題8.3.2 所有點(diǎn)對(duì)的最短路徑問(wèn)題8.4 小結(jié)習(xí)題實(shí)驗(yàn)題第9章 網(wǎng)絡(luò)流與匹配9.1 最大流問(wèn)題9.1.1 FordFulkerson方法9.1.2 最短路徑增廣算法9.1.3 Dinic算法9.1.4 MPM算法9.1.5 最大流問(wèn)題的變形9.2 最小費(fèi)用流問(wèn)題9.2.1 消除回路算法9.2.2 最小費(fèi)用路算法9.2.3 最小費(fèi)用路算法的改進(jìn)9.3 匹配問(wèn)題9.3.1 二分圖匹配9.3.2 一般圖的匹配9.4 小結(jié)習(xí)題實(shí)驗(yàn)題第10章 線性規(guī)劃10.1 線性規(guī)劃問(wèn)題10.1.1 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式10.1.2 線性規(guī)劃問(wèn)題的松弛形式10.2 求解算法10.2.1 圖解法10.2.2 單純形算法10.3 對(duì)偶10.4 小結(jié)習(xí)題實(shí)驗(yàn)題第11章 NIP完全理論11.1 判定問(wèn)題11.2 P和NP11.3 NPC11.3.1 NPC的定義11.3.2 電路可滿足性問(wèn)題11.4 NPC的證明11.4.1 可滿足性問(wèn)題11.4.2 3.CNF可滿足性問(wèn)題11。4.3 團(tuán)問(wèn)題11.4.4 頂點(diǎn)覆蓋問(wèn)題11.5 其他NP完全問(wèn)題11.6 小結(jié)習(xí)題第12章 回溯12.1 算法思想12.2 裝載問(wèn)題12.3 0／1背包問(wèn)題12.4 著色問(wèn)題12.5 n皇后問(wèn)題12.6 旅行商問(wèn)題12.7 流水作業(yè)調(diào)度問(wèn)題12.8 零件切割問(wèn)題12.9 小結(jié)習(xí)題實(shí)驗(yàn)題第13章 分支限界第14章 啟發(fā)式搜索第15章 數(shù)論第16章 計(jì)算幾何參考文獻(xiàn)

章節(jié)摘錄

插圖：從問(wèn)題下界的描述可知，要想找出所有的算法以確定問(wèn)題的下界，通常比找出有效的算法更難。1.6 小結(jié)前面我們介紹了插入排序算法的設(shè)計(jì)與分析。如果將插入排序算法用具體的程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)，就得到了程序。因此，程序與算法是有區(qū)別的，程序是用某種程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)的算法，而算法是抽象的，它不依賴(lài)于具體的程序設(shè)計(jì)語(yǔ)言和硬件，也就是說(shuō)，無(wú)論算法是用c語(yǔ)言編寫(xiě)在586上運(yùn)行還是用Basic語(yǔ)言編寫(xiě)在筆記本電腦上運(yùn)行，算法的思想都是一樣的。Turing獎(jiǎng)獲得者，Pascal語(yǔ)言之父Ni-klausWirth曾說(shuō)過(guò)“程序=數(shù)據(jù)結(jié)構(gòu)+算法”。算法是程序背后的思想，是程序的核心。從這里可以看出，程序的本質(zhì)是算法，是算法的具體體現(xiàn)。因此描述一個(gè)算法，我們不用具體的程序，而是用偽代碼，主要是因?yàn)橛脗未a描述的算法非常清。

編輯推薦

《算法設(shè)計(jì)與分析》是由國(guó)防工業(yè)出版社出版的。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

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

---