算法引論

前言

編寫(xiě)本書(shū)的動(dòng)機(jī)來(lái)源于我在教學(xué)實(shí)踐中常常無(wú)法為給定算法給出清晰解析的困惑。與許多教師一樣，我發(fā)現(xiàn)對(duì)一些學(xué)生來(lái)說(shuō)，要他們親自動(dòng)手解決一些簡(jiǎn)單問(wèn)題有困難，而讓他們理解給定問(wèn)題的解決方案同樣有困難。我相信，事物的兩個(gè)方面——?jiǎng)?chuàng)造和解釋——是相關(guān)而不可分離的。為了完全了解一個(gè)問(wèn)題，考察最后的答案遠(yuǎn)遠(yuǎn)不夠，我們必須了解問(wèn)題的求解過(guò)程。 本書(shū)強(qiáng)調(diào)了算法設(shè)計(jì)的創(chuàng)造性方面，其主要目的是要告訴讀者如何去設(shè)計(jì)一個(gè)新的算法。本書(shū)描述算法的順序不是“問(wèn)題X、算法A、算法A'、程序P、程序P'”，而是像（但并不總是）“問(wèn)題X、直接明了的問(wèn)題求解算法、缺點(diǎn)、改進(jìn)這些缺點(diǎn)的困難、（可能包含一些錯(cuò)誤的）好的算法、進(jìn)一步的改進(jìn)、分析以及其他方法和算法的關(guān)系”。本書(shū)的目標(biāo)不是給出一個(gè)容易轉(zhuǎn)換為程序代碼的算法，而是希望讀者理解算法的原理。算法因此被解釋為創(chuàng)造過(guò)程而不是最終產(chǎn)品。我們講授算法的目標(biāo)不僅是說(shuō)明如何求解特定的問(wèn)題，還包括傳授如何求解未來(lái)將產(chǎn)生或遇到的新問(wèn)題的技術(shù)。可以說(shuō)，講授算法設(shè)計(jì)的思維過(guò)程與講授問(wèn)題求解細(xì)節(jié)是同樣重要的。

內(nèi)容概要

本書(shū)是國(guó)際算法大師烏迪·曼博（Udi Manber）博士撰寫(xiě)的一本享有盛譽(yù)的著作。全書(shū)共分12章：第1章到第4章為介紹性?xún)?nèi)容，涉及數(shù)學(xué)歸納法、算法分析、數(shù)據(jù)結(jié)構(gòu)等內(nèi)容；第5章提出了與歸納證明進(jìn)行類(lèi)比的算法設(shè)計(jì)思想；第6章到第9章分別給出了4個(gè)領(lǐng)域的算法，如序列和集合的算法、圖算法、幾何算法、代數(shù)和數(shù)值算法；第10章涉及歸約，也是第11章的序幕，而后者涉及NP完全問(wèn)題；第12章則介紹了并行算法；最后是部分習(xí)題的答案及參考文獻(xiàn)。本書(shū)的特色有二，旨在提高讀者的問(wèn)題求解能力，使讀者能夠理解算法設(shè)計(jì)的過(guò)程和思想：一是強(qiáng)調(diào)算法設(shè)計(jì)的創(chuàng)造性過(guò)程，注重算法設(shè)計(jì)背后的創(chuàng)造性思想，而不拘泥于某個(gè)具體算法的詳細(xì)討論；二是將算法設(shè)計(jì)類(lèi)比于定理歸納證明，揭示了算法設(shè)計(jì)的基本思想和本質(zhì)。    本書(shū)的組織結(jié)構(gòu)清晰且易于理解，強(qiáng)調(diào)了創(chuàng)造性，具有濃郁特色，時(shí)至今日仍有其巨大的價(jià)值，并且適合作為計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)算法和高級(jí)算法課程的教材。

作者簡(jiǎn)介

曼博（Udi Manber）美國(guó)著名的計(jì)算機(jī)科學(xué)家，國(guó)際公認(rèn)的算法大師，在線信息搜索引擎的先驅(qū)。1982年于華盛頓大學(xué)獲得計(jì)算機(jī)科學(xué)博士學(xué)位，曾是美國(guó)亞利桑那大學(xué)計(jì)算機(jī)專(zhuān)業(yè)教授。離開(kāi)學(xué)校后在雅虎公司擔(dān)任執(zhí)行官，閆前是亞馬遜（Amazon.com）的副總裁和首席算法師（CAO），也是亞馬遜旗下搜索網(wǎng)站A9.corn的首席執(zhí)行官。他提出的UDI測(cè)試已經(jīng)成為衡量搜索引擎質(zhì)量的評(píng)估標(biāo)準(zhǔn)。

書(shū)籍目錄

第1章  引論第2章　數(shù)學(xué)歸納法　2.1  引言　2.2　三個(gè)簡(jiǎn)單的例子　2.3　平面內(nèi)區(qū)域的計(jì)數(shù)　2.4　簡(jiǎn)單的著色問(wèn)題　2.5　復(fù)雜一些的加法題　2.6　一個(gè)簡(jiǎn)單的不等式　2.7　歐拉公式　2.8　圖論中的一個(gè)問(wèn)題　2.9　格雷碼　2.10　在圖上尋找無(wú)重邊的路　2.11　數(shù)學(xué)平均數(shù)和幾何平均數(shù)定理　2.12　循環(huán)不變量：將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)　2.13　常見(jiàn)的錯(cuò)誤　2.14　小結(jié)第3章　算法分析　3.1　引言　3.2　符號(hào)O　3.3　時(shí)間與空間復(fù)雜度　3.4　習(xí)之和　3.5　遞推關(guān)系　　3.5.1　巧妙地猜測(cè)　　3.5.2　分治關(guān)系　　3.5.3　涉及全部歷史的遞推關(guān)系　3.6　一些有用的證明論據(jù)　3.7　小結(jié)第4章　數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介　4.1  引言　4.2　基本數(shù)據(jù)結(jié)構(gòu)　　4.2.1　元素　　4.2.2　數(shù)組　　4.2.3　記錄　　4.2.4　鏈表　4.3　樹(shù)　　4.3.1  樹(shù)的表示　　4.3.2　堆　　4.3.3　二叉搜索樹(shù)　　4.3.4　AVL樹(shù)　4.4　散列　4.5　合并碴找問(wèn)題　4.6  圖　4.7　小結(jié)第5章　基于歸納的算法設(shè)計(jì)　5.1  引言　5.2　多項(xiàng)式求值　5.3　最大導(dǎo)出子圖　5.4　尋找一對(duì)一映射　5.5　社會(huì)名流問(wèn)題　5.6　分治算法：輪廓問(wèn)題　5.7　在二叉樹(shù)中計(jì)算平衡因子　5.8　尋找最大連續(xù)子序列　5.9　增強(qiáng)歸納假設(shè)　5.10　動(dòng)態(tài)規(guī)劃：背包問(wèn)題　5.11　常見(jiàn)的錯(cuò)誤　5.12　小結(jié)第6章　序列和集合的算法　6.1  引言　6.2　二叉搜索的幾種形式　　6.2.1  純二叉搜索　　6.2.2　循環(huán)序列的二叉搜索　　6.2.3　二叉搜索特殊下標(biāo)　　6.2.4　二叉搜索長(zhǎng)度未知的序列　　6.2.5　重疊子序列問(wèn)題　　6.2.6　解方程　6.3  內(nèi)插搜索　6.4　排序　　6.4.1　桶排序和基數(shù)排序　　6.4.2　插入排序和選擇排序　　6.4.3　歸并排序　　6.4.4　快速排序　　6.4.5　堆排序　　……第7章　圖算法第8章　幾何算法第9章　代數(shù)和數(shù)值算法第10章　歸約第11章　NP完全問(wèn)題第12章　并行算法部分習(xí)題答案參考文獻(xiàn)

章節(jié)摘錄

插圖：在《韋氏大學(xué)詞典（第九版）》中，算法的解釋是“求解數(shù)學(xué)問(wèn)題（如尋找最大公約數(shù)）的一個(gè)過(guò)程，該過(guò)程步驟有限，通常還涉及重復(fù)的操作；廣義地說(shuō)，算法是按部就班解決一個(gè)問(wèn)題或完成某個(gè)目標(biāo)的過(guò)程。本書(shū)取廣義的算法來(lái)定義。算法設(shè)計(jì)是一個(gè)古老的研究領(lǐng)域。自古以來(lái)，人們總是對(duì)發(fā)現(xiàn)更好的目標(biāo)求解方法充滿興趣，不論是取火、建造金字塔還是對(duì)郵件進(jìn)行排序。而計(jì)算機(jī)算法的研究當(dāng)然是一個(gè)新的領(lǐng)域。一些計(jì)算機(jī)算法采用的方法早在計(jì)算機(jī)發(fā)明之前就存在，但大多數(shù)計(jì)算機(jī)算法的設(shè)計(jì)需要新的方法和技術(shù)。首先，告訴計(jì)算機(jī)諸如“察看小山，如果發(fā)現(xiàn)敵情就拉響警報(bào)”是不夠的。一臺(tái)計(jì)算機(jī)必須了解“察看”的確切含義，知道如何識(shí)別敵情，懂得如何拉響警報(bào)（基于技術(shù)原因，拉響警報(bào)是最容易的）。一臺(tái)計(jì)算機(jī)可接受的指令應(yīng)當(dāng)是定義明確、長(zhǎng)度有限的基本操作序列。將通常的命令轉(zhuǎn)換為計(jì)算機(jī)可以理解的指令是一個(gè)困難的過(guò)程，而該過(guò)程就是編程，目前有成百萬(wàn)的程序員正在不同層次上進(jìn)行編程。計(jì)算機(jī)上的編程，所需要的不僅僅是將那些為人所理解的命令轉(zhuǎn)換為計(jì)算機(jī)可以理解的語(yǔ)言。在大多數(shù)情況下，程序員必須設(shè)計(jì)出完全嶄新的算法來(lái)求解問(wèn)題。只學(xué)習(xí)與計(jì)算機(jī)交談所用的怪異語(yǔ)言會(huì)使編程變得困難，因?yàn)橹挥杏?jì)算機(jī)才知道你說(shuō)了什么。計(jì)算機(jī)不僅能以極快的速度執(zhí)行先前由人完成的操作，它還可以做得更多。計(jì)算機(jī)能處理數(shù)十億、數(shù)萬(wàn)億比特單位的信息，能在一秒內(nèi)完成數(shù)百萬(wàn)條基本指令。在這個(gè)數(shù)量級(jí)上進(jìn)行算法設(shè)計(jì)是一種嶄新的實(shí)踐，有很多方面會(huì)與我們的直覺(jué)相反，因?yàn)槲覀兺ǔＶ粚?duì)自己能感知的事物進(jìn)行思考。遺憾的是，一些能很好解決小問(wèn)題的程序在處理大問(wèn)題時(shí)就變得很糟。因此當(dāng)進(jìn)行大規(guī)模計(jì)算時(shí)不要忽視算法的復(fù)雜度和有效性。

編輯推薦

《算法引論:一種創(chuàng)造性方法》是國(guó)際算法大師烏迪·曼博（UdiManber）博士撰寫(xiě)的一本享有盛譽(yù)的著作，強(qiáng)調(diào)了算法設(shè)計(jì)的創(chuàng)造性方面，通過(guò)算法開(kāi)發(fā)步驟來(lái)描述算法設(shè)計(jì)過(guò)程。此外，《算法引論:一種創(chuàng)造性方法》創(chuàng)造性地將算法設(shè)計(jì)過(guò)程同定理歸納證明過(guò)程進(jìn)行類(lèi)比，揭示了算法設(shè)計(jì)的基本思想和本質(zhì)，旨在提高讀者的問(wèn)題求解以及理解算法設(shè)計(jì)的過(guò)程和思想的能力?！端惴ㄒ?一種創(chuàng)造性方法》特點(diǎn)：包括經(jīng)典算法以及流行算法算法設(shè)計(jì)技巧及其綜合應(yīng)用并行算法設(shè)計(jì)犬多數(shù)算法的偽代碼表示500多道習(xí)題，其中四分之一給出了答案將算法實(shí)現(xiàn)細(xì)節(jié)和算法思想盡可能分離

圖書(shū)封面

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

無(wú)

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

---

    算法引論 PDF格式下載

---