具体数学(计算机科学基础英文版原书第2版典藏版)/经典原版书库

《具体数学：计算机科学基础(第 2版)》是一本在大学中广泛使用的经典数学教科书。书中讲解了许多计算机科学中用到的数学知识及技巧，教你如何把一个实际问题一步步演化为数学模型，然后通过计算机解决它，特别着墨于算法分析方面。其主要内容涉及和式、整值函数、数论、二项式系数、特殊的数、生成函数、离散概率、渐近式等，都是编程所必 备的知识。另外，《具体数学：计算机科学基础(第 2版)》包括了六大类500 多道习题，并给出了所有习题的解答，有助读者加深书中内容的理解。 《具体数学：计算机科学基础(第 2版)》面向从事计算机科学、计算数学、计算技术诸方面工作的人员，以及高等院校相关专业的师生

葛立恒（Ronald L. Graham） 数学家，美国加州大学圣迭戈分校计算机与信息科学专业教席（Jacobs Endowed Chair），AT&T实验室研究中心荣誉首席科学家，美国数学学会前任主席。Graham于1999年成为美国计算机学会会士，2003年获得美国数学学会的斯蒂尔终身成就奖，2012年成为美国数学学会会士。他还曾获得美国数学学会颁发的Lester R. Ford奖和Carl Allendoerfer奖以及其他众多奖项。 高德纳（Donald E. Knuth） 计算机科学家，算法与程序设计技术的先驱者、斯坦福大学计算机系荣休教授、计算机排版系统TEX和METAFONT字体系统的发明人，因诸多成就以及大量富于创造力和具有深远影响的著作（19部书，1160篇论文）而誉满全球。Knuth教授获得过许多奖项和荣誉，包括美国计算机学会图灵奖、美国国家科学奖章、美国数学学会的斯蒂尔奖，以及因发明先进技术于1996年荣获的京都奖。1996年，设立了以其名字命名的Donald E. Knuth奖，授予那些为计算机科学基础做出杰出贡献的人。 奥伦•帕塔什尼克（Oren Patashnik） 计算机科学家，BibTeX的创始人之一。他在1976年毕业于耶鲁大学，后来在斯坦福大学师从高德纳，1980年就职于贝尔实验室。1985年与Leslie Lamport合作创建了BibTeX（LaTeX的一种工具，用于管理文献、产生文献目录）。

1　递归问题1 1.l　汉诺塔问题1 1.2　直线划分平面问题4 1.3　约瑟夫问题8 习题17 2　求和21 2.1　表示法21 2.2　求和与递归25 2.3　求和的运算方法30 2.4　多重求和34 2.5　求和方法一览41 2.6　差分与求导47 2.7　无穷项求和问题56 习题62 3　整数函数67 3.1　向上取整函数和向下取整函数67 3.2　取整函数的应用70 3.3　取整函数的递归表示法78 3.4　mod：二元运算81 3.5　取整函数的求和86 习题95 4　数论102 4.1　整除性102 4.2　素数105 4.3　素数示例107 4.4　阶乘的因子111 4.5　互质115 4.6　mod：同余关系123 4.7　独立余数126 4.8　应用129 4.9　欧拉函数与默比乌斯函数133 习题144 5　二项式系数153 5.1　基本恒等式153 5.2　基本练习172 5.3　应用技巧186 5.4　生成函数196 5.5　超几何函数204 5.6　超几何变换216 5.7　超几何部分求和223 5.8　算法化求和229 习题242 6　特殊数257 6.1　斯特林数257 6.2　欧拉数267 6.3　调和数272 6.4　调和级数求和279 6.5　伯努利数283 6.6　斐波那契数列290 6.7　连续式301 习题309 7　生成函数320 7.1　多米诺理论与零钱支付方案320 7.2　基本策略331 7.3　递归式求解337 7.4　特殊生成函数350 7.5　卷积运算353 7.6　指数型生成函数364 7.7　狄利克雷生成函数370 习题371 8　离散概率381 8.1　定义381 8.2　均值与方差387 8.3　概率生成函数394 8.4　掷硬币401 8.5　哈希法411 习题427 9　渐近理论439 9.1　渐近量级440 9.2　O记法443 9.3　O运算450 9.4　两个渐近技巧463 9.5　欧拉求和公式469 9.6　结论476 习题489 A　习题答案497 B　参考文献604 C　习题来源632 Contents 1 Recurrent Problems 1 1.1 The Tower of Hanoi 1 1.2 Lines in the Plane 4 1.3 The Josephus Problem 8 Exercises 17 2 Sums 21 2.1 Notation 21 2.2 Sums and Recurrences 25 2.3 Manipulation of Sums 30 2.4 Multiple Sums 34 2.5 General Methods 41 2.6 Finite and Infinite Calculus 47 2.7 Infinite Sums 56 Exercises 62 3 Integer Functions 67 3.1 Floors and Ceilings 67 3.2 Floor/Ceiling Applications 70 3.3 Floor/Ceiling Recruuences 78 3.4 'mod': The Binary Operation 81 3.5 Floor/Ceiling Sums 86 Exercises 95 4. Number Theory 102 4.1 Divisibility 102 4.2 Primes 105 4.3 Prime Examples 107 4.4 Factorial Factors 111 4.5 Relative Primality 115 4.6 'mod': The Congruence Relation 123 4.7 Independent Residues 126 4.8 Additional Applications 129 4.9 Phi and Mu 133 Exercises 144 5 Binomaial Coefficients 153 5.1 Basic Indentities 153 5.2 Basic Practice 172 5.3 Tricks of the Trade 186 5.4 Generating Functions 196 5.5 Hypergeometric Functions 204 5.6 Hypergeometric Transformations 216 5.7 Pratial Hypergeometric Sums 223 5.8 Mechanical Summation 229 Exercises 242 6 Special Numbers 257 6.1 Stirling Numbers 257 6.2 Eulerian Numbers 267 6.3 Harmonic Numbers 272 6.4 Harmonic Summation 279 6.5 Bernoulli Numbers 283 6.6 Fibonacci Numbers 290 6.7 Continuants 301 Exercises 309 7 Generating Functions 320 7.1 Domino Theory and Change 320 7.2 Basic Maneuvers 331 7.3 Solving Recurrences 337 7.4 Special Generating Functions 350 7.5 Convolutions 353 7.6 Exponential Generating Functions 364 7.7 Dirichlet Generating Functions 370 Exercises 371 8 Discrete Probability 381 8.1 Definitions 381 8.2 Mean and Variance 387 8.3 Probability Generating Functions 394 8.4 Flipping Coins 401 8.5 Hashing 411 Exercises 427 9 Asymptotics 439 9.1 A Hierarchy 440 9.2 O Notation 443 9.3 O Manipulation 450 9.4 Two Asymptotic Tricks 463 9.5 Euler's Summation Formula 469 9.6 Final Summations 476 Exercises 489 A Answers to Exercises 497 B Bibliography 604 C Credits for Exercises 632