中文名: 算法分析論文選
原名: Selected Papers on the Analysis of Algorithms
作者: Donald E. Knuth
資源格式: DJVU
版本: 掃描版
出版社: Center for the Study of Language and Inf
書號: 1575862123
發行時間: 2000年
地區: 美國
語言: 英文
簡介:

內容簡介:
本書收錄了Donald Knuth關於算法分析的34篇經典論文。這些論文主要討論應用於各種不同算法的常用技術和各種優美的數學模型，對所采用的一些重要技術如概率論、數論、漸近分析等，文章也作了詳細介紹。
本書URL:http://www-cs-faculty.stanford.edu/~uno/aa.html
Knuth簡介: (引自:http://zzg34b.w3.c361.com/homepage/KnuthResume.htm)


1938年12月7日，Donald E. Knuth 出生於美國威斯康星州密爾沃基市。其父是個中學教師，經常在星期天到教堂演奏管風琴，小 Knuth 耳濡目染，日後也成為教師，業余愛好也是彈管風琴。
1956年進入俄亥俄州克利夫蘭的凱斯理工學院（現並入凱斯西儲大學），學習物理。
1957年大學一年級暑假在學校打工，接觸到當時很先進的IBM650 計算機，對其產生濃厚的興趣。
1958年改學數學，並從此與計算機結緣。
1960年畢業，因為成績過於出色，校方打破慣例，Knuth 被同時授予學士和碩士學位。隨後進入加州理工學院數學系。
1960-1968年，兼任 Burroughs 公司顧問。
1961年結婚，夫人小他一歲。現有一兒一女。
1963年取得博士學位，並留校任助理教授。
1964-1967年，兼任美國計算機協會刊物《程序設計語言》編輯。
1966年升為副教授。
1968年任教於斯坦福大學計算機科學系，正教授。同年，開始撰寫著名的《計算機程序設計藝術》一書。
1968年《計算機程序設計藝術》第一卷《基本算法》出版。
1969年，第二卷《半數值算法》出版。
1971年獲首屆美國計算機協會格蕾絲·赫柏獎。
1973年，第三卷《排序與搜索》出版。同年還出版了第一卷的第二版。有人曾說，看了這部書後，再談起編程序都會變得謙虛謹慎。比爾·蓋茨曾說：“如果你能讀懂整套書的話，請給我發一份你的簡歷。”同年，當選為美國科學藝術學院院士。截至到1973年的第一卷第二版，采用都是的活字排版印刷，這需要經驗豐富的活字排版工人。
1974年，因在算法分析和編程語言設計方面的突出貢獻，榮獲美國計算機協會圖靈獎，是歷史上最年輕的獲獎者。圖靈獎被稱為計算機界的諾貝爾獎。《計算機程序設計藝術》一書與牛頓的《自然哲學的數學原理》等書一起，被評為“世界歷史上最偉大的十種科學著作”之一。
1975年當選為美國國家科學院院士。
1976年出版第二卷第二版時采用了計算機排版技術。但是，當時的計算機排版與活字排版效果相差甚遠，而且前後兩卷的字體、版式和文本格式等都不一致。非常失望的 Knuth 暫停了第二卷第二版的出版，決心自己設計一個比活字排版更加優美和適用的排版軟件，這就是後來的 TeX 。
1977年5月開始構造後來被稱為 TeX 的文字處理系統，他研究了古今的排版技術，把其中最優越的部分引入 TeX 中，連 TeX 中的字體（METAFONT）全部都是他自行設計的。同年，訪問中國三周，行前姚儲楓給他起了個中文名字：高德納。（姚儲楓，姚期智的夫人，夫婦都是著名計算機科學家，2000年姚期智獲圖靈獎。）

1978年應邀在美國數學學會年會上作報告，題為“數學排版--TeX 與 METAFONT”，引起數學界關注。
1979年，Knuth 教授的著作《TeX 與 METAFONT：排版的新趨勢》，由數字設備公司和美國數學學會聯合出版。同年，榮獲美國總統卡特授予的科學金獎 [頒獎視頻]。
1980年獲國際電子電氣工程師協會計算機學會麥可道爾獎。同年，成為英國計算機學會會員。
1981年當選為美國工程院院士。
1982年使用自己設計的 TeX 軟件和字體，Knuth 如願出版了《計算機程序設計藝術》的第二卷第二版。之後，Knuth 還不遺余力地改進 TeX，並在 TeX 的穩定性上下了很大功夫。在基本式樣沒有改變的情況下，TeX 第3版又追加了很多功能。9月，公布了 DVI 驅動程序。同年，成為國際電子電氣工程師協會榮譽會員，並獲計算機先鋒獎。
1984年，艾迪生-韋斯利公司出版 Knuth 教授的《The TeXbook》，該書成為最權威的 TeX 參考書。
1985年，將 TeX 的默認字體由美國現代改為計算機現代 。
1986年榮獲美國數學學會的斯蒂爾獎。
1987年獲紐約科學研究會獎。
1988年獲富蘭克林獎。
1989年，因其對軟件理論的貢獻獲 J.D. Warnier 獎。

1990年，斯坦福大學授予他計算機科學藝術教授的稱號。
1991年，《3:16 聖經文本闡釋》一書出版，他試圖用分層隨機抽樣的方法對聖經進行分析。
1992年退休，但還是斯坦福大學和牛津大學的客座教授。他這麼早退休的原因，就是因為研究開發 TeX 系統延誤了編寫出版《計算機程序設計藝術》這部書，他估計還要花20年來完成。目前此書前三卷已出版，預計要出到第七卷。
1993年宣布不再對 TeX 和 METAFONT 進行更新。
1994年獲瑞典皇家科學院克努特獎。
1995年獲國際電子電氣工程師協會的紐曼獎和以色列的科學與藝術哈維獎。
1996年11月，由於發明先進的排版技術榮獲京都先進技術獎（日本最高終身成就獎，獎金約46萬美元，被稱為日本的諾貝爾獎）。
1997年對《計算機程序設計藝術》前三卷作了修訂。
2001年國際天文學聯合會把兩年前發現的第21656號小行星命名為“Knuth”。

2003年榮獲馬其頓大學榮譽博士，同年當選英國皇家學會的外籍院士。
2004年《計算機程序設計藝術》前三卷再版發行。

2005年11月19日，從瑞士聯邦蘇黎士高等理工學院院長手中接過榮譽博士證書。
現在，正在編寫《計算機程序設計藝術》其余幾卷。
他的所有著作都有個奇特“附加效應”，那就是任何人發現書中的錯誤，不論是技術上的或是排版上的還是歷史上的錯誤，都可以向他指出，並可領取2.56美元！可見其人幽默诙諧而且能夠聞過則喜。

為什麼是2.56美元？Knuth 教授的答案是：
“256 pennies is one hexadecimal dollar.”
從1981年夏至1996年7月1日，Knuth 教授給指出錯誤的人回信250多封，其中一半以上裝有獎勵支票。從獎勵支票清單來看，有一位名叫 Axel Böttcher 的人，曾先後5次得到兩塊五毛六的支票，3次得到五塊一毛二的支票，真可謂牛人背後有牛人。
受麥粒與棋盤的故事影響，Knuth 教授宣布，每發現一個 TeX 程序或 METAFONT 程序中的錯誤，獎勵從2.56美元開始，每年翻倍，最高為327.68美元。1995年有兩人領取了這項獎金，此後至今，還無人能夠認領！
有網友戲說，什麼是聰明：在 Knuth 的書中找到錯誤；什麼是愚蠢：去兌現那張兩塊五毛六的支票。
Knuth 教授是法國、挪威和德國科學院的外籍院士；還是牛津大學、巴黎大學、斯德哥爾摩皇家理工學院、奧斯陸大學、安特衛普大學、聖彼得堡大學和馬其頓大學等十幾所大學的榮譽博士。
Knuth 教授帶過28個研究生，擁有5項專利，出版25部著作，發表160篇論文；他的著作已有6種文字譯本，發行量超過一百萬冊。英文版的《計算機程序設計藝術》一書已再版11次，該書前三卷中文版於1978年至1992年陸續出版，由蘇運霖教授翻譯，他曾在1977年與來訪的 Knuth 教授在北京座談。
Knuth 教授愛好音樂，年輕時曾考慮報考音樂專業。在他的書房中放了一個特別定制的84管的管風琴。他還會吹薩克斯管和大號。
TeX 是二十世紀排版技術方面最重大的發明，歷經20年的歲月，TeX 在基本沒有改動的情況下被世界各地各種語言的人們廣泛使用，TeX 的優美排版效果令使用者愛不釋手。現在，世界上很多國家都有 TeX 用戶組織，TeX 不斷地被推廣和擴展。
Knuth 教授因在 TeX 及計算機編程方面的巨大貢獻和他大量創造性的影響深遠的著作而享譽全球。
Donald E. Knuth 這個名字將和 TeX 一起被載入世界科學史冊。
內容截圖:

目錄:
1. Mathematical Analysis of Algorithms
2. The Dangers of Computer Science Theory
3. The Analysis of Algorithms
4. Big Omicron and Big Omega and Big Theta
5. Optimal Measurement Points for Program Frequency Counts
6. Estimating the Efficiency of Backtrack Programs
7. Ordered Hash Tables
8. Activity in an Interleaved Memory
9. An Analysis of Alpha-Beta Pruning
10. Notes on Generalized Dedekind Sums
11. The Distribution of Continued Fraction Approximations
12. Evaluation of Porter's Constant
13. Analysis of the Subtractive Algorithm for Greatest Common Divisors
14. Length of Strings for a Merge Sort
15. The Average Height of Planted Plane Trees
16. The Toilet Paper Problem
17. An Analysis of Optimum Caching
18. A Trivial Algorithm Whose Analysis Isn't
19. Deletions That Preserve Randomness
20. Analysis of a Simple Factorization Algorithm
21. The Expected Linearity of a Simple Equivalence Algorithm
22. Textbook Examples of Recursion
23. An Exact Analysis of Stable Allocation
24. Stable Husbands
25. Shellsort With Three Increments
26. The Average Time for Carry Propagation
27. Linear Probing and Graphs
28. A Terminological Proposal
29. Postscript About NP-hard Problems
30. An Experiment in Optimal Sorting
31. Duality in Addition Chains
32. Complexity Results for Bandwidth Minimization
33. The Problem of Compatible Representatives
34. The Complexity of Nonuniform Random Number Generation