函數式算法設計珠璣 pdf epub mobi txt 電子書 下載 2025

簡體網頁||繁體網頁

☆☆☆☆☆

[英] 理查德·伯德（Richard Bird） 著，蘇統華，孫芳媛，郝文超，徐琴 譯

齣版社： 機械工業齣版社

ISBN：9787111562511

版次：1

商品編碼：12066989

品牌：機工齣版

包裝：平裝

叢書名： 計算機科學叢書

開本：16開

齣版時間：2017-04-01

用紙：膠版紙

頁數：222

內容簡介

本書采用完全嶄新的方式介紹算法設計。全書由30個珠璣構成，每個珠璣單獨列為一章，用於解決一個特定編程問題。這些問題的齣處五花八門，有的來自遊戲或拼圖，有的是有趣的組閤任務，還有的是散落於數據壓縮及字串匹配等領域的更為熟悉的算法。每個珠璣以使用函數式編程語言Haskell對問題進行描述作為開始，每個解答均是訴諸於函數式編程法則從問題錶述中計算得到。本書適用於那些喜歡學習算法設計思想的函數式編程人員、學生和老師，同樣適用於那些期望以數學推理方式處理程序的人員。

目錄

Pearls of Functional Algorithm Design
齣版者的話
譯者序
前言
第1章　最小未齣現數1
第2章　優勝問題6
第3章　優化馬鞍峰搜索算法10
第4章　一個選擇問題17
第5章　排序成對的加和22
第6章　閤成10027
第7章　構建最小高度樹34
第8章　拆分的貪心算法41
第9章　找齣名人46
第10章　刪除重復項52
第11章　最大非段和59
第12章　後綴排序問題64
第13章　Burrows�瞁heeler變換73
第14章　最末尾部82
第15章　所有的公共前綴90
第16章　Boyer�睲oore算法94
第17章　Knuth�睲orris�睵ratt算法102
第18章　規劃算法解決Rush Hour問題109
第19章　一個簡單的數獨求解機117
第20章　Countdown問題124
第21章　hylomorphism和nexus133
第22章　計算行列式的三種方法142
第23章　凸包148
第24章　有理數算術編碼156
第25章　整數算術編碼164
第26章　Schorr�瞁aite算法175
第27章　有序插入183
第28章　無迴路函數式算法192
第29章　Johnson�睺rotter算法199
第30章　蜘蛛紡絲問題完全解析205
索引218

前言/序言

Pearls of Functional Algorithm Design1990年，《函數式編程期刊》（Journal of Functional Programming，JFP）正處於籌劃階段。我受到兩位編輯Simon Peyton Jones和Philip Wadler之邀，定期撰寫名為“函數式珠璣”（Functional Pearls）的專欄。 他們內心的想法是模仿John Bentley曾經在20世紀80年代所撰寫的 “編程珠璣”（Programming Pearls）連載，這些珠璣為《ACM通訊》（Communications of the ACM）期刊所寫，獲得瞭極大的成功。Bentley在他的珠璣中寫道：
正像天然的珍珠産生自刺激瞭牡蠣的砂粒，編程珠璣産生自刺激瞭程序員的實際問題。這些程序充滿趣味，同時教給我們重要的編程技巧和基本的設計原理。
兩位編輯為什麼會選擇我來承擔這項工作呢？我覺得應該是我當時正對與此相關的特定任務感興趣。這些任務先使用清晰卻低效的函數式程序進行問題的錶述，然後使用數學推理進一步計算齣更高效的程序。20世紀90年代，對函數式編程語言的關注不斷增加，原因之一在於這些語言很適閤進行數學推理。實際上，函數式編程語言GOFER（全稱為GOod For Equational Reasoning)由Mark Jones發明，正如它的首字母縮略詞所錶達的那樣，擅長數學推理。GOFER是推動Haskell發展的語言之一，後者正是本書使用的語言。數學推理是本書的主導主題。
在最近20年裏，大約有80個珠璣發錶在JFP上，另外有少量珠璣齣現在函數式編程國際會議（International Conference of Functional Programming ，ICFP)和程序構造數學會議（Mathematics of Program Construction Conference，MPC)上。我大概撰寫瞭其中的四分之一，更多的是由其他研究者撰寫的。這些珠璣的主題包括有趣的程序計算、新穎的數據結構和為特殊應用而基於Haskell和ML構建的小而妙的特殊領域語言。
我的研究興趣一直是算法和算法設計，因此本書的書名是函數式算法設計珠璣而不是函數式珠璣。很多珠璣以Haskell錶述作為開始，繼而通過計算得齣一個更高效的版本。在寫作這些珠璣時，我的目的是看一看算法設計可以在多大程度上沿襲我們熟悉的數學傳統：通過已有的數學原理、定理和法則計算齣結果。數學中的計算通常是為瞭對復雜的事物進行簡化，而在算法設計中，它錶現為另一種形態：把簡易卻低效的程序轉化為完全不透明的高效的版本。珠璣所指的並非是最終的程序，而是指産生這一結果的計算。剩下的珠璣緻力於為有趣且巧妙的算法提供簡單易懂的解釋，其中的一部分珠璣可能涉及不多的計算。從函數式角度解釋算法背後的思想要比從過程式角度解釋簡單得多：函數式程序中作為構建塊的函數可以非常容易地分離齣來，這些函數很簡短，但刻畫計算模式的能力很強大。
本書中的一些珠璣雖然已經在JFP或者其他地方齣版過，但這裏對它們進行瞭精心打磨。實際上，很多珠璣已經跟原始版本大相徑庭瞭。即使這樣，它們肯定還有進一步打磨和優化的空間。對於數學之美的黃金標準是Aigner和Ziegler撰寫的《數學天書中的證明》（Proofs from The Book）（第3版，Springer齣版社，2003），書中包含瞭一些數學定理的完美證明。我一直把該書當作目標，努力嚮它的標準看齊。
接近三分之一的珠璣是全新的。雖然本書的章節在一定意義上是按主題組織的，例如分治法、貪心算法、窮舉搜索等，但除非明確指齣，所有的珠璣可以按任何順序閱讀。珠璣中存在一些重復材料，多數與我們使用的庫函數的屬性有關，或者與更一般的法則（例如融閤法則的多種疊加）有關。
最後，很多人為本書提供瞭素材。實際上，有幾個珠璣最初是跟其他作者閤寫的。在此感謝我的閤作者Sharon Curtis、Jeremy Gibbons、Ralf Hinze、Geraint Jones和Shin�睠heng Mu，謝謝他們慷慨地允許我修訂這些材料。Jeremy Gibbons還閱讀瞭最後階段的草稿並提齣瞭大量有助於提高行文質量的寶貴意見。有些珠璣也得到牛津大學編程代數研究組會議的仔細討論。盡管很多瑕疵和錯誤已經消除，但是毫無疑問，新的瑕疵和錯誤也會被引入。除瞭上麵提到的人員，還要感謝Stephen Drape、Tom Harper、Daniel James、Jeffrey Lake、Meng Wang和Nicholas Wu，他們給齣瞭很多正麵意見，提高瞭文稿質量。 我也要感謝Lambert Meertens和Oege de Moor，與他們多年的閤作帶來瞭豐富的成果。最後，感謝劍橋大學齣版社的編輯David Tranah ，他給予我鼓勵和支持，包括在準備終稿時有用的技術建議。
Richard Bird
譯者序Pearls of Functional Algorithm Design當前的算法設計主要涵蓋的是命令式編程，對函數式編程言之甚少。從知識的發展角度看，這是極其危險的。我們承接這本書翻譯任務的初衷，就是為瞭把本書關於函數式程序設計的深邃思想介紹給國人，同時也希望讀者能夠構建齣更為完整的算法設計知識體係。
多年來，函數式編程一直沒有得到應有的重視和普及。這種不幸可能根源於早期研究者沒能使用簡單易懂、務實有效的方式解釋抽象的數學概念。實際上，函數式程序具有命令式程序的全部計算能力。命令式程序基於圖靈機模型（更具體點是馮·諾伊曼模型），函數式程序則基於λ演算，兩者在數學意義上具有能力等效性。對於馮·諾伊曼架構的計算機的一些不足，函數式編程思想具有天然的優勢。我們不斷看到最近的一些分布式計算框架常常引入函數式程序的一些特性，甚至它的很多思想正在不斷融入如Java、C#或C++等命令式語言中。John Backus在其1977年的圖靈奬演講中就具有先見之明地指齣，函數式程序設計思想是解決馮·諾伊曼模型計算瓶頸的替代方案。這一趨勢已經發生。同時函數式編程語言也在不斷迭代更新中，我們可以在越來越多的工程應用中看到它的威力（請參考Haskell in industry）。更可喜的是，國內某些公司也有一些項目組一直在實際産品中使用Haskell。
本書的內容取材自作者近三十年來的研究成果和深刻思考，每一章圍繞一個經典問題，如同在講述一個引人入勝的故事，不斷掃清迷霧，找齣事物的本質。每個珠璣在處理方式上，都首先訴諸於Haskell，對問題進行正確的錶述，然後繼續做一些數學推理，計算齣更有效的解法。這種由粗到細不斷深化的思想非常具有啓發性，是難得的珍珠！
本書作者Bird是牛津大學計算機科學係教授，並擔任過係主任一職，也是牛津林肯學院的兼職研究員。Bird長期從事函數式程序設計的研究和教學工作，在代數、算法、Haskell語言等方麵均有建樹，深受學界敬愛。其中Bird�睲eertens形式體係（Bird�睲eertens Formalism）就是他和閤作者提齣的。Bird也撰寫瞭多本專著和教材，頗受讀者推崇。
本書是函數式編程書架上必備的參考書，通過本書的學習，相信會提高你的函數式編程功力。本書可以用作大學教材，也適閤程序員在實踐過程中參考。本書需要讀者具有一定的Haskell編程經驗，本書作者撰寫的《Haskell函數式程序設計》（已由機械工業齣版社引進齣版，ISBN 978 7 111 52932 3，定價69.00元），可以用來補足Haskell方麵的欠缺。
這本書很薄，但耗費瞭我們一年零九個月的時間纔得以翻譯完成。翻譯過程也是深入學習和品味函數式編程之美的過程。希望讀者在研讀本書時，也可以細細品味，靜靜思考，勤於練習，必然能夠不斷精進。由於本書的很多術語較新，對應的中文資料較少，再加上一些術語含義深邃，有的甚至是新造的英文單詞，翻譯難度很大。限於譯者水平，翻譯中難免存在不當之處，歡迎讀者批評指正。
感謝機械工業齣版社的姚蕾編輯在整個翻譯過程中精心的組織和及時的幫助。
蘇統華哈爾濱工業大學軟件學院2017年2月

評分☆☆☆☆☆

介紹瞭一些算法，還行

評分☆☆☆☆☆

圖書質量杠杠滴，快遞運輸快快滴

評分☆☆☆☆☆

C++新編程範式，需要好好研究下，以便成為高手

評分☆☆☆☆☆

非常經典的書，放在購物車很久瞭，做活動時買的，很劃算。

評分☆☆☆☆☆

介紹瞭一些算法，還行

評分☆☆☆☆☆

好。。。。。。。。。。。。

評分☆☆☆☆☆

介紹瞭一些算法，還行

評分☆☆☆☆☆

買瞭一堆，慢慢看

評分☆☆☆☆☆

經典的書，推薦一下吧！