算法導(dǎo)論pdf第2版中文文字版 附帶答案

算法導(dǎo)論pdf第2版是一款中文高清版的電子書(shū)籍，軟件包中附帶福昕閱讀器能夠幫助讀者方便的打開(kāi)pdf文件。書(shū)中主要介紹了許多常用的數(shù)據(jù)結(jié)構(gòu)和有效的算法，討論了線性規(guī)劃，介紹了動(dòng)態(tài)規(guī)劃的兩個(gè)應(yīng)用，隨機(jī)化和線性規(guī)劃技術(shù)的近似算法等等，力圖讓讀者能夠輕松的掌握。其中第1章是對(duì)算法及其在現(xiàn)代計(jì)算系統(tǒng)中地位的一個(gè)綜述。第2章給出了書(shū)中的第一批算法，它們解決的是對(duì)n個(gè)數(shù)進(jìn)行排序的問(wèn)題。第3章給出了這種表示法的準(zhǔn)確定義，稱(chēng)為漸近表示。第4章更深入地討論了第2章引入的分法方法以及解決遞歸式的方法。第5章介紹了概率分析和隨機(jī)化算法。更多的內(nèi)容請(qǐng)讀者下載觀看。

注意事項(xiàng)：軟件包中附帶了算法導(dǎo)論第2版的答案，請(qǐng)須知。

目錄列表節(jié)選：

第一部分 基礎(chǔ)知識(shí)

引言

第1章 算法在計(jì)算中的作用

1.1 算法

1.2 作為一種技術(shù)的算法

第2章 算法入門(mén)

2.1 插入排序

2.2 算法分析

2.3 算法設(shè)計(jì)

2.3.1 分治法

2.3.2 分治法分析

第3章 函數(shù)的增長(zhǎng)

3.1 漸近記號(hào)

3.2 標(biāo)準(zhǔn)記號(hào)和常用函數(shù)

第4章 傳歸式

4.1 代換法

4.2 遞歸樹(shù)方法

4.3 主方法

4.4 主定理的證明

4.4.1 取正合冪時(shí)的證明

4.4.2 上取整函數(shù)和下取整函數(shù)

第5章 概率分析和隨機(jī)算法

5.1 雇用問(wèn)題

5.2 指示器隨機(jī)變量

5.3 隨機(jī)算法

5.4 概率分析和指示器隨機(jī)變量的進(jìn)一步使用

5.4.1 生日悖論

5.4.2 球與盒子

5.4.3 序列

章節(jié)節(jié)選

在計(jì)算機(jī)科學(xué)中，排序是一種基本的操作（很多程序都將它用作一種中間步驟），因此，迄今為止，科研人員提出了多種非常好的排序算法。對(duì)于一項(xiàng)特定的應(yīng)用來(lái)說(shuō)，如何選擇最佳的排序算法要考慮多方面的因素，其中最主要的是考慮待排序的數(shù)據(jù)項(xiàng)數(shù)、這些數(shù)據(jù)項(xiàng)已排好序的程度、對(duì)數(shù)據(jù)項(xiàng)取值的可能限制、打算采用的存儲(chǔ)設(shè)備的類(lèi)型（內(nèi)存、盤(pán)、帶）等如果一個(gè)算法對(duì)其每一個(gè)輸入實(shí)例，都能輸出正確的結(jié)果并停止，則稱(chēng)它是正確的，我們說(shuō)一個(gè)正確的算法解決了給定的計(jì)算問(wèn)題。不正確的算法對(duì)于某些輸入來(lái)說(shuō)，可能根本不會(huì)停止，或者停止時(shí)給出的不是預(yù)期的結(jié)果。然而，與人們對(duì)不正確算法的看法相反，如果這些算法的錯(cuò)誤率可以得到控制的話，它們有時(shí)也是有用的。關(guān)于這一點(diǎn)，在第 31 中研究用于尋找大質(zhì)數(shù)的算法時(shí)介紹了--個(gè)例子，但是，一般而言，我們還是僅關(guān)注正確的法。算法可以用英語(yǔ)、以計(jì)算機(jī)程序或甚至是硬件設(shè)計(jì)等形式來(lái)表達(dá)。不論采用哪種形式，唯一的要求就是算法的規(guī)格說(shuō)明必須提供關(guān)于待執(zhí)行的計(jì)算過(guò)程的精確描述。算法可以解決愿些類(lèi)型的問(wèn)糖？

研究人員并不僅僅是針對(duì)排序這一計(jì)算問(wèn)題設(shè)計(jì)了大的算法（讀者在看到本書(shū)的厚度時(shí)可能也會(huì)這么猜想的）。算法的實(shí)際應(yīng)用面很廣，例如。人類(lèi)基因項(xiàng)目的目標(biāo)是找出人類(lèi) DNA 中的所有 100 000 種基因，確定構(gòu)成人類(lèi) DNA的30 億種化學(xué)基對(duì)的各種序列，將這些信息存儲(chǔ)在數(shù)據(jù)庫(kù)中，并開(kāi)發(fā)出用于進(jìn)行這方面數(shù)據(jù)分析的工具，這些步驟中的每一個(gè)都需要復(fù)雜的算法。該項(xiàng)目所涉及的各個(gè)問(wèn)題的解決方案已超出了本書(shū)的范圍，但本書(shū)中有好幾章中的思想在解決這些生物問(wèn)題時(shí)都用到了，這樣就使得科學(xué)家們可以有效地利用已有資源來(lái)完成任務(wù)，并且，當(dāng)利用實(shí)驗(yàn)室技術(shù)可以提取出更多的信息時(shí)，就可以帶來(lái)人、財(cái)、物、時(shí)間等方面的節(jié)約。因特網(wǎng)使得全世界的人們都能夠快速地訪問(wèn)和檢索大量的信息。為了能實(shí)現(xiàn)這一目的人們采用了巧妙的算法來(lái)管理和操縱大量的數(shù)據(jù)。這方面必須解決的問(wèn)題包括尋找好的數(shù)據(jù)傳輸路徑（第 24 章將介紹解決這些間題的技術(shù)）用索引警來(lái)快地找到包含特定信息的網(wǎng)頁(yè)等（有關(guān)技術(shù)將在第 11 章和第32 章中介紹）電子商務(wù)使得商品和服務(wù)可以以電子的形式進(jìn)行談判和交易。然而，電子商務(wù)要想得到廣泛應(yīng)用的話，非常重要的一點(diǎn)就是保持信用卡號(hào)、密碼、銀行結(jié)單等信息的私密性公共密鑰加密技術(shù)和數(shù)簽名術(shù)（將在第 31 中紹）是這一領(lǐng)域內(nèi)所使用的核心技術(shù)，它們的基礎(chǔ)就是數(shù)值算法和數(shù)論理論。

在制造業(yè)和其他商業(yè)應(yīng)用中，是否能有效地分配稀有資源常常是非常重要的，例如，石油公司可能希望確定該在何處打井，以求最大化預(yù)期效益。美國(guó)總統(tǒng)候選人可能希望確定該把競(jìng)選宣傳的資金花在何處，以使贏得競(jìng)選勝利的可能性最大，航空公司可能希勢(shì)以盡可能小的代價(jià)來(lái)將機(jī)組人員分配到不同的航班上，以便做到既到考慮到每一個(gè)航班又不會(huì)違反政府有關(guān)航空人員調(diào)度的規(guī)定，因特網(wǎng)服務(wù)提供商可能希望確定該把額外的資源置于何處，以便能夠更有效地服務(wù)其客戶(hù)。所有這些都是可以利用線性規(guī)劃求解間題的例子，這一技術(shù)將在第 29 章中介紹。盡管這些例子中某些細(xì)節(jié)已經(jīng)超出了本書(shū)的范圍，我們?nèi)越o出了適用于這些問(wèn)題和問(wèn)題領(lǐng)底層支撐技術(shù)。此外，在本書(shū)中，我們還說(shuō)明了如何解決許多具體的問(wèn)題，例如：給定一幅道路交通圖，上面標(biāo)注出了每一對(duì)相鄰交叉路口之間的距離。我們的目標(biāo)就是確定-個(gè)交叉路口到另一個(gè)交又路口之間的最短路線。即使不允許每一條路線自我交叉可能的路線數(shù)量也會(huì)是巨大的。在所有可能的路線中，該如何來(lái)選出最短的路線呢？這里，用一個(gè)圖來(lái)對(duì)道路交通圖進(jìn)行建模（前者本身就是對(duì)實(shí)際道路的一種建模，有關(guān)圖的內(nèi)容將在第 10 章和附錄 B中介紹），希望在圖中找出一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)之間的最短路徑。在第 24 章中，將看到如何來(lái)有效地解決這一問(wèn)題。給定由 n個(gè)所組成的一個(gè)列（A1，A2，”，A確其AAA為矩陣乘法是可以結(jié)合的，因而存在著若干合法的乘法順序。例如，如果 n-4，可以按照以下幾種順序來(lái)執(zhí)行矩陣乘法：（A1（A2（A3A4））），（A1（（AA2AA3）A4）），（（A1A2）（A3A4）），（A1（A2A3））A4），（（A1A2）A3）A4）。如果這些是正方形矩陣（因而其大小都是一樣的），乘法的順序?qū)仃嚦朔▽⒒ǘ嗌贂r(shí)間是沒(méi)有影響的。然而，如果這些矩陣的大小不同的話（但其大小對(duì)矩陣乘法來(lái)說(shuō)是相容的），那么，乘法的順序如何就會(huì)帶來(lái)很大的差別了?？赡艿某朔ńY(jié)合順序的數(shù)量是 n 的指數(shù)級(jí)的，因此，要嘗試所有可能順序的話，可能會(huì)花很長(zhǎng)的時(shí)間。在第 15 章中，我們將會(huì)看到，如何用一種稱(chēng)為動(dòng)態(tài)規(guī)劃的技術(shù)來(lái)更為有效地解決這一問(wèn)題，給定一個(gè)方程az=b（mod ），其中an 都是，希出所有（在 時(shí)）滿(mǎn)足該方程的整數(shù) z。方程的解可能有零個(gè)、一個(gè)或多個(gè)。可以簡(jiǎn)單地嘗試依次用=0,1，”?！保琻1來(lái)代該方程，但第 31 中給出了種更為有效的方法給定平面上 n個(gè)點(diǎn)，希望找出這些點(diǎn)的凸亮，即包含這些點(diǎn)的最小凸多邊形，從直觀上看，可以將每一個(gè)點(diǎn)看成是由一塊板上突起的一個(gè)釘子表示的。因而，包圍這些點(diǎn)的凸亮可以看成是一根包圍了所有這些釘子的繃緊的橡皮繩。每一個(gè)令橡皮繩發(fā)生方向變化