算法設(shè)計與分析

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---