算法技術(shù)手冊(cè)

前言

算法，神秘而晦澀的詞匯。算法，是計(jì)算機(jī)科學(xué)中最重要同時(shí)也是最基礎(chǔ)的一環(huán)。從開始學(xué)習(xí)計(jì)算機(jī)，我們就深知，算法是整個(gè)計(jì)算機(jī)科學(xué)的核心。然而直至我們工作數(shù)年后，能夠真正學(xué)好算法的人，卻依舊是風(fēng)毛麟角。這并不是計(jì)算機(jī)教育的錯(cuò)，也不是計(jì)算機(jī)從業(yè)人員的錯(cuò)，更不是算法的錯(cuò)。長(zhǎng)久以來，算法就像古老的咒語，算法背后高深的數(shù)學(xué)知識(shí)更讓人望而生畏。其實(shí)，我們始終沒有找到一條從理論走向?qū)嵺`的路。 在這里，我們很高興能向大家介紹本書。它正是能夠帶領(lǐng)你學(xué)好算法的一本不可多得的好書。 本書的三位作者是伍斯特理工學(xué)院的教授，其中GeorgeT．Heineman畢業(yè)于達(dá)特茅斯學(xué)院和哥倫比亞大學(xué)，曾經(jīng)獲得過GE、IBM和AT&T的研究獎(jiǎng)金，在軟件工程方面有獨(dú)到的研究。而Gary Pollice曾經(jīng)供職于Rational Sonware，Sun等多家巨頭，有著豐富的工業(yè)界經(jīng)驗(yàn)，知道如何將學(xué)術(shù)和工業(yè)結(jié)合起來。Stanley M．Selkow畢業(yè)于卡內(nèi)基梅隆大學(xué)和賓夕法尼亞大學(xué)，擅長(zhǎng)圖論和算法設(shè)計(jì)。本書由這三位伍斯特理工學(xué)院計(jì)算機(jī)理論專家合著，向我們展示了工業(yè)界和學(xué)術(shù)界對(duì)算法的不同看法以及如何高效地將理論和實(shí)踐相結(jié)合。本書搭建了一條真正屬于開發(fā)者的路。 本書的讀者主要面向本科生以及程序設(shè)計(jì)人員，同樣也適用于產(chǎn)品和項(xiàng)目管理人員。由于譯者的知識(shí)和經(jīng)驗(yàn)有限，翻譯中難免有疏漏或錯(cuò)誤，敬請(qǐng)廣大讀者諒解井批評(píng)指正。

內(nèi)容概要

　　開發(fā)健壯的軟件需要高效的算法，然后程序員們往往直至問題發(fā)生之時(shí)，才會(huì)去求助于算法?！端惴夹g(shù)手冊(cè)》講解了許多現(xiàn)有的算法，可用于解決各種問題。通過閱讀它，可以使您學(xué)會(huì)如何選擇和實(shí)現(xiàn)正確的算法，來達(dá)成自己的目標(biāo)。另外，書中的數(shù)學(xué)深淺適中，足夠使您可以了解并分析算法的性能?！　≥^之理論而言，本書更專注于應(yīng)用。《算法技術(shù)手冊(cè)》提供了高效的代碼解決方案，使用多種語言進(jìn)行編寫，讓您可以輕松地將其應(yīng)用于特定的工程當(dāng)中。通過本書，您可以：　　·解決特定代碼的問題，或者提升既有解決方案的性能　　·快速找到與您所解決的問題相關(guān)的算法，并決定哪個(gè)算法才是最適合的那一個(gè)　　·探索使用C、C++、Java以及Ruby實(shí)現(xiàn)的算法解決方案以及開發(fā)小貼士　　·了解算法預(yù)期的性能，以及它達(dá)到最高性能時(shí)所需要的條件　　·發(fā)現(xiàn)不同算法之間相似的設(shè)計(jì)哲學(xué)　　·學(xué)習(xí)高級(jí)數(shù)據(jù)結(jié)構(gòu)，來提升算法的性能　　通過《算法技術(shù)手冊(cè)》，您能學(xué)到如何提升算法的性能，這將是您的軟件應(yīng)用程序走向成功的關(guān)鍵?！　∽髡吆?jiǎn)介：George T.Heineman，Gary Pollice和Stanley Selkow均為 Woree ste r PolYteChniC In stitute（伍斯特理工學(xué)院）計(jì)算機(jī)科學(xué)系的教授。George是《Component—B ased Software Engineering：Putting the Pieces Together》（Addison—Wesley（的合編者，Gary則是《Head First Object-Oriented Analysis and Design》（O'Reilly）的合著者。

作者簡(jiǎn)介

George T.Heineman，Gary Pollice和Stanley Selkow均為 Woree ster PolYteChniC In stitute（伍斯特理工學(xué)院）計(jì)算機(jī)科學(xué)系的教授。George是《Component—B ased Software Engineering：Putting the Pieces Together》（Addison—Wesley（的合編者，Gary則是《Head First Object-Oriented Analysis and Design》（O'Reilly）的合著者。

書籍目錄

前言 第一部分 　第1章　算法真的很重要 　　理解問題 　　如果需要，盡可能用實(shí)踐檢驗(yàn) 　　解決問題的算法 　　花絮 　　故事的寓意 　　參考文獻(xiàn) 　第2章　算法的數(shù)學(xué)原理 　　問題樣本的規(guī)模 　　函數(shù)的增長(zhǎng)率 　　最好最壞和平均情況下的性能分析 　　性能指標(biāo) 　　混合操作 　　基準(zhǔn)測(cè)試 　　最后一點(diǎn) 　　參考文獻(xiàn) 　第3章　模式和領(lǐng)域 　　模式：一種交流語言 　　算法模式的格式 　　偽代碼模式的格式 　　設(shè)計(jì)格式 　　基于經(jīng)驗(yàn)的評(píng)價(jià)格式 　　領(lǐng)域和算法 　　浮點(diǎn)計(jì)算 　　手動(dòng)內(nèi)存分配 　　選擇一門編程語言 　　參考文獻(xiàn) 第二部分 　第4章　排序算法 　　概述 　　插入排序 　　中值排序 　　快速排序 　　選擇排序 　　堆排序 　　計(jì)數(shù)排序 　　選擇排序算法的標(biāo)準(zhǔn) 　　參考文獻(xiàn) 　第5章　查找 　　概述 　　順序查找 　　二分查找 　　基于散列的查找 　　二叉查找樹 　　參考文獻(xiàn) 　第6章　圖算法 　　概述 　　深度優(yōu)先搜索 　　廣度優(yōu)先搜索 　　單源最短路徑 　　所有點(diǎn)對(duì)最短路徑 　　最小生成樹算法 　　參考文獻(xiàn) 　第7章　人工智能中的尋路， 　　概述 　　深度優(yōu)先搜索 　　廣度優(yōu)先搜索 　　A*搜索 　　比較 　　Minimax 　　NegMaX 　　AlphaBeta 　　參考文獻(xiàn) 　第8章　網(wǎng)絡(luò)流算法 　　概述 　　最大流 　　二部圖匹配 　　在增廣路上的深入思考 　　最小開銷流 　　轉(zhuǎn)運(yùn)問題 　　運(yùn)輸問題 　　任務(wù)分配問題 　　線性編程 　　參考文獻(xiàn) 　第9章　計(jì)算幾何 　　概述 　　凸包掃描 　　線段掃描 　　最近點(diǎn)查詢 　　范圍查詢 　　參考文獻(xiàn) 第三部分 　第10章　最后的招數(shù) 　　另類算法 　　近似算法 　　離線算法 　　并行算法 　　隨機(jī)算法 　　結(jié)果可能出錯(cuò)卻可以衰減錯(cuò)誤率的算法 　　參考文獻(xiàn) 　第11章　尾聲 　　概述 　　原則：了解數(shù)據(jù) 　　原則：將問題分解至更小的問題 　　原則：選擇正確的數(shù)據(jù)結(jié)構(gòu) 　　原則：空間換時(shí)間 　　原則：如果沒有顯而易見的解法，使用搜索 　　原則：如果沒有顯而易見的解法，將問題歸約為另一個(gè)有解的問題 　　原則：編寫算法難，測(cè)試算法更難 第四部分 附錄基準(zhǔn)測(cè)試

章節(jié)摘錄

插圖：這個(gè)方法的總開銷取決于你在每個(gè)槽中是元素列表還是nil值（表示沒有列表）。當(dāng)一個(gè)槽只有一個(gè)元素時(shí)，它可以使用列表來存取。作為我們的第一個(gè)近似的解決方案，我們將會(huì)使用這種方法并且在性能成為瓶頸時(shí)改進(jìn)它。驅(qū)動(dòng)因素選擇散列函數(shù)是在實(shí)現(xiàn)基于散列的查找之前必須做的第一個(gè)決定。散列已經(jīng)被研究多年，并且有大量的描述高效散列函數(shù)的論文，不過用在查找上使用這些函數(shù)簡(jiǎn)直是殺雞用牛刀。例如，某些特定的散列函數(shù)對(duì)于加密非常重要。對(duì)于查找來說，一個(gè)散列函數(shù)必須要有一個(gè)好的分布，并且計(jì)算速度非?？臁４鎯?chǔ)器空間是設(shè)計(jì)基于散列查找時(shí)需要考慮的另外一個(gè)因素。主存儲(chǔ)器A必須能夠足夠大，以存下所有的查找鍵值，并且要給沖突鍵值留下足夠的空間。A的大小通常是一個(gè)素?cái)?shù)。但是，如果我們不使用開放定址的話（見接下來的“變種”一節(jié)），我們能夠使用任何數(shù)字作為A的大小。實(shí)踐中一個(gè)好的選擇是2k-1，即使這個(gè)值并不是素?cái)?shù)。存儲(chǔ)在散列表的元素對(duì)內(nèi)存有直接的影響。考慮圖5-3的是如何在鏈表中存儲(chǔ)每個(gè)字符串的，所以存儲(chǔ)在A中的元素看做鏈表元素。堆中包含著指向元素的指針。每一個(gè)鏈表都有存儲(chǔ)的開銷，包含著指向鏈表中的第一個(gè)和最后一個(gè)元素。如果你使用Java的LinkedList類，一些很重要的附加字段和類使得實(shí)現(xiàn)非常靈活。程序員可以寫一個(gè)簡(jiǎn)單得多的鏈表類，只提供必需的功能，但是確實(shí)給基于散列查找算法帶來了額外的開銷。如果你使用Linked List類，假設(shè)指針是四個(gè)字節(jié)，那么A中的每一個(gè)非空元素都需要12字節(jié)內(nèi)存。每個(gè)字符串元素不可以直接轉(zhuǎn)換成ListElement，需要12個(gè)額外字節(jié)。對(duì)于之前的那個(gè)有213 557個(gè)單詞的例子，我們需要5005488字節(jié)的額外存儲(chǔ)。

媒體關(guān)注與評(píng)論

“作者完成了一項(xiàng)了不起的工作，將晦澀的學(xué)術(shù)加以精煉，完美地在理論和實(shí)踐之間取得了平衡，從而使本書成為了一本不可或缺的指南。從此，徹底領(lǐng)悟算法就變得十分簡(jiǎn)單了?！薄　　狹atthew Russell. Digital ReasOning Systems高級(jí)技術(shù)總監(jiān)，《D0jo權(quán)威指南》（O’Reilly）的作者

編輯推薦

《算法技術(shù)手冊(cè)》是由機(jī)械工業(yè)出版社出版的。

圖書封面

圖書標(biāo)簽Tags

無

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

---

    算法技術(shù)手冊(cè) PDF格式下載

---