具体数学:计算机科学基础:第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部书，160篇论文）而誉满全球。近些年，他将精力全部投入到《计算机程序设计艺术》七卷集的史诗般创作中。Knuth教授获得过许多奖项和荣誉，包括美国计算机协会图灵奖、美国国家科学奖章、美国数学学会的斯蒂尔奖，以及因发明先进技术于1996年荣获的京都奖。1996年，设立了以其名字命名的Donald E. Knuth奖，授予那些为计算机科学基础做出杰出贡献的人。
Oren Patashnik：著名计算机科学家，BibTeX的创始人之一，是位于拉荷亚的通信研究中心的研究员。他1976年毕业于耶鲁大学，后来在斯坦福大学师从Knuth，1980年就职于贝尔实验室。1985年与Leslie Lamport合作创建了BibTeX（LaTeX的一种工具，用于管理文献、产生文献目录）。
张明尧：1945年12月出生，安徽大学数学系毕业并获得中国科学院数学研究所博士学位。长期从事解析数论、代数数论以及计算数论方面的研究工作，参与翻译的著作有《数论中未解决的问题（第2版）》（R. K. Guy著）、《纯数学教程（纪念版）》（G. H. Hardy著）、《哈代数论（第6版）》（G. H. Hardy著）和《算术探索》（C. F. Gauss著）等。
张凡：1982年7月出生，加拿大Concordia大学数学系毕业，并获得统计专业硕士学位。参与翻译的著作有《数论导引（第5版）》（G. H. Hardy著）和《哈代数论（第6版）》（G. H. Hardy著）等。

《具体数学:计算机科学基础:第2版》
第1章 　递归问题　　1
1.1 　河内塔　　1
1.2 　平面上的直线　　4
1.3 　约瑟夫问题　　7
习题　　14
第2章 　和式　　18
2.1 　记号　　18
2.2 　和式和递归式　　21
2.3 　和式的处理　　25
2.4 　多重和式　　28
2.5 　一般性的方法　　35
2.6 　有限微积分和无限微积分　　39
2.7 　无限和式　　47
习题　　52
第3章 　整值函数　　56
3.1 　底和顶　　56
3.2 　底和顶的应用　　58
3.3 　底和顶的递归式　　66
3.4 　mod：二元运算　　68

　　经过半年多的艰苦努力，这部《具体数学》中文译稿终于完成了！
　　这部书的几位作者都是各自领域久负盛名的专家． R. L. Graham（葛立恒）是加利福尼亚大学圣地亚哥分校计算机科学以及工程系Irwin和Joan Jacobs教授，他在数学以及计算机的多个领域都有丰硕的成果．D. E. Knuth（高德纳）是斯坦福大学荣誉教授，享誉世界的著名计算机专家，当今计算机上广泛使用的数学文献编辑排版系统TeX的创造者，他的长篇巨著The Art of Computer Programming（《计算机程序设计艺术》，现已出版前三卷和第四卷的第一部分）为他赢得“算法分析之父”的美誉．第三位作者O. Patashnik（帕塔许尼克）也是一位计算机专家，1976年毕业于耶鲁大学，1980年进入贝尔实验室工作，1988年协助Graham和Knuth完成了《具体数学》一书，1985年与L. Lamport一道创立了文献目录系统BibTeX，1990年在Knuth指导下获得计算机科学博士学位，现在在位于加利福尼亚州圣地亚哥市拉荷亚的通信研究中心工作．
　　这部《具体数学》是当代计算机科学基础方面的一部重要著作，也是一部极好的教材，其内容由作者们以及若干学生和同行多年来在斯坦福大学以及其他多所大学开设的同名课程累积而成，内容涉及递归式、和式、几个取整数值的函数、初等数论基础、二项式系数、若干特殊的数、生成函数方法、初等概率论以及渐近分析初步等，共计九章．书中的解说深入浅出，妙趣横生；习题丰富，层次分明，且均附有或详或简的解答；书末还附有非常详尽的参考文献，可供有兴趣的读者进一步研读参考．这部书既可作为计算机科学基础教学，又是数学、计算机等专业各层次研究工作者颇有参考价值的参考书，值得向读者广为推荐．
　　这部书中在许多页含有页边涂鸦，这些涂鸦有的是来自过去时代某位著名学者的手笔，有的来自作者的学生们或其他人的评论．这些涂鸦或平淡，或深刻；或严肃，或幽默．相当多的涂鸦中含有双关语，并涉及拉丁语、俄语、德语、法语以及较早时代的英语等多种语言（其中虽有少量希腊语涂鸦，但给出了中文翻译）．译者虽然早就懂得语言对于一位致力于科学研究的工作者开阔视野极其重要，也曾在多年学习和工作的过程中勉力学习多种外语，但从未学习过拉丁文以及希腊文，对稍早时代的英语也素无研究，所以这部书在语言方面也成了译者有生以来翻译过的最感困难的一部著作．幸好有原书前两位作者的大力帮助，尤其是Knuth教授，耐心地回答了我们在翻译这本书的过程中提出的无数问题，才终于使我们完成了这部著作的翻译工作．在此，我们首先要向作者在翻译过程中提供的慷慨帮助表示衷心的感谢！此外，我们还要向家人表示深深的谢意，他们为我们的翻译工作提供了不受干扰的环境和安逸的生活，使我们的工作速度有了可靠的保证．最后，我们还要向这本中文书的编辑们在编辑和出版这部中文版的过程中所给予的大力支持和鼓励表示感谢．图灵公司多年来一直致力于出版引进高水平的学术著作，我们已与他们愉快地合作过多次，他们的敬业和奉献精神同样值得赞赏和钦佩！
　　顺便指出，译者在本书的翻译过程中发现的个别错误或不当之处得到了原作者的确认并在中文版中做了相应的修正.（作为原作者的事先承诺，Knuth教授还慷慨地通过他的秘书给译者寄来了支票，奖励所发现的问题．）此外，为了帮助读者理解书中的某些习语或内容，我们在认为必要的地方添加了译者注，希望能对读者有所帮助．尽管尽了最大的努力，由于译者水平限制，书中不免仍会有不足甚至谬误之处，欢迎读者不吝赐教．来信可发送至myzhang@ecust.edu.cn．
　　我们一生的理想是：传授科学思想，宣传民主理念，为在中国实现民主政治和强国梦想而奋斗!愿这部中文版的出版能对中国学生和数学爱好者有所帮助，也算是对我们一生理想的一点小小的贡献吧！
　　张明尧
　　

　　本书成形于斯坦福大学的同名课程讲义，该课自1970年以来每年都会开设．每年大约有50名学生选学这门课，有本科生，主要是研究生．他们毕业后逐渐在各地开设了类似的课程．由此看来，向更为广泛的读者（包含大学二年级学生）提供教材的时机已经成熟了．
　　具体数学诞生之际，正逢一个黑暗的、暴风骤雨般动荡的十年．在那些骚动不安的岁月里，长期秉承的价值观频频受到质疑，大学校园成了争论的温床．大学课程本身也受到挑战，数学同样难逃严重细究之厄运．John Hammersley刚刚写了一篇发人深省的文章“On the enfeeblement of mathematical skills by‘Modern Mathematics’and by similar soft intellectual trash in schools and universities”（《论中学和大学中被“现代数学”以及类似的软智力垃圾弄得日益衰弱的数学技巧》）[176]，其他颇感担忧的数学家们[332]甚至发问：“数学能得到拯救吗？”本书作者高德纳（Donald E. Knuth）撰写了名为The Art of Computer Programming（《计算机程序设计艺术》）的系列专著．在写第一卷时，他发现一些数学工具从他的数学武库中消失了．为透彻而扎实地理解计算机程序，他所需要的数学已经与他读大学数学专业时所学习的内容迥然不同．所以，他引入了一门新的课程，讲授他认为本该有人教授他的那些内容．
　　这门冠名“具体数学”的课程起初是为矫正“抽象数学”而设置的，那时，具体的经典结果正在被接踵而至的俗称“新数学”的抽象思想迅速摒弃在现代数学课程表之外．抽象数学是一个奇妙的主题，其中没有任何谬误，它既漂亮、通用，又实用．但是，它的拥护者们误以为，数学的其余部分都是低劣而不再值得关注的了．一般化的目标变得如此时髦，使得整整一代数学家变得不会欣赏具体数学之美，不能享受求解数量型问题的挑战，也不再重视技术手段之价值．抽象数学于是变得排外，并逐渐失去与现实的联系．数学教育需要增加具体的砝码以保持健康的平衡．
　　高德纳在斯坦福大学第一次讲授具体数学这门课时，说他打算讲授一门硬性而非软性的数学课，这也解释了这个略显古怪的课程名称．他宣称，与某些同事的期望相反，他既不打算讲授集合论，也不打算讲授Stone嵌入定理，甚至不讲授Stone- ech紧致化．（几位土木工程系的学生于是站起来，安静地离开了教室．）
　　尽管具体数学的起步是针对流行趋势的反动，但是它存在的主要理由是具有积极而非消极意义的．作为一门持续受欢迎的课程，它的题材得以“充实”并在各种新的应用中被证明是有价值的．Z. A. Melzak曾出版了两卷本的著作Companion to Concrete Mathematics [267] ，从另一个角度肯定了这一课程名称的恰当性．
　　具体数学的素材初看像是一堆互不相干的技巧，但是透过实践可以把它汇集成一组严谨高效的工具．的确，这些技术有基本的一致性，且对许多人都有极强的吸引力．当另一作者葛立恒（Ronald L. Graham）在1979年首次教授这门课时，学生们都感觉很有趣，以至于决定一年后举行一次班级聚会．
　　具体数学究竟是什么呢？它融合了连续数学和离散数学． 更具体地说，它是利用一组求解问题的技术对数学公式进行有控制的操作．理解了本书的内容之后，你所需要的就是一颗冷静的头脑、一大张纸以及较为工整的书写，以便对看上去令人恐怖的和式进行计算，求解复杂的递归关系，以及发现数据中隐藏的精妙规律．你会对代数技巧得心应手，从而常常会发现，得到精确的结果比求出仅在一定意义下成立的近似解更为容易．
　　这本书要探讨的主题包括和式、递归式、初等数论、二项式系数、生成函数、离散概率以及渐近方法．其重点是强调处理技术，而不是存在性定理或者组合推理，目的是使每一位读者熟悉离散性运算（如最大整数函数以及有限求和），就好像每一位学习微积分的学生都熟悉连续性运算一样（如绝对值函数以及不定积分）．
　　注意，这些主题与当今大学本科中的“离散数学”课程的内容截然不同．因此，这门课程需要一个不同的名称，而“具体数学”可谓恰如其分．
　　最初在斯坦福大学教授“具体数学”的教材是The Art of Computer Programming[207]中的“Mathematical Preliminaries”（数学预备知识）一节．但是，那110页的内容相当简洁，所以另一位作者欧伦·帕塔许尼克（Oren Patashnik）受到启发，撰写了一套长篇幅的补充笔记．
　　这本书就是那些笔记的产物，它扩充了“数学预备知识”中的资料，也更从容地引出了这些预备知识，其中略去了那些较高深的部分，同时又包含了笔记里未提及的主题，使得书的内容更为完整．
　　我们很享受一起写这本书，因为这门课程就在我们眼前逐渐定型，获得了生命，它就看似是自己写就的．此外，我们这些年来在若干地方采用的非常规方法看起来也十分妥帖，让人忍不住认为，这本书正好宣告了我们所喜爱的做数学的方式．所以我们想，这本书就像讲述数学之美之奇的故事，希望读者能够分享我们写作中的愉悦，哪怕只有ε那么一点点．
　　自从本书在大学环境中诞生以来，我们就一直尝试以非正式的风格来体现当代课堂教学的精神．有些人认为数学是一项严肃的工作，必须是冷冰冰的，但是我们认为数学是娱乐，而且并不羞于承认这个事实．为什么要把工作和娱乐截然分开呢？具体数学充满了引人入胜的模式，其演算推理并非总是轻而易举，然而答案却可能极具魅力．数学工作的欢乐和忧伤都鲜明地反映在这本书中，因为它们是我们生活的一部分．
　　学生们总是比老师们更有头脑，所以我们请这个教材的首批学生提出他们坦诚的意见，即旁注中的“涂鸦”．在这些“涂鸦”中，有一些仅仅是套话，有一些则很深奥；有一些提醒区分歧义或者含混之处，有一些则是后排那些聪明家伙爱做的点评；有一些是正面的，有一些是负面的，还有一些则不偏不倚．但是，它们都是情感的真实表现，应该有助于读者理解正文内容．（这种旁注的灵感来自名为Approaching Stanford（《走近斯坦福》）的学生手册．在这本手册中，官方的大学信息与即将离校的学生评论相映成趣．例如，斯坦福大学说：“在斯坦福大学这个无定型的生活方式中，有一些东西是你不能错过的．”而旁注中写道：“无定型……鬼知道是什么意思？这里到处都是典型的伪理智主义．” 斯坦福大学说：“一群住在一起的学生，他们的潜力是无穷尽的．”而涂鸦则声称：“斯坦福大学的宿舍就像无人管理的动物园．”）
　　旁注中也直接引用了著名数学家们的话，这些话是他们在宣布某些重大发现时所说的．看起来，将莱布尼茨、欧拉、高斯等人的话与那些继续其研究工作的人的话混在一起是合适的．数学是身处各地的人进行的不间断的探索研究，涓涓细流才能汇成浩瀚的海洋．
　　这本书包含了500多道习题，分成如下六大类．
　　热身题：这是每一位读者在第一次阅读本书时就应完成的习题．
　　基础题：这些习题揭示出了，通过自己的推导而不是他人的推导来学习最好．
　　作业题：是加深理解当前章节内容的问题．
　　考试题：一般同时涉及两章以上的内容，可作为家庭测试题（不作为课堂上的限时考试）．

　　“希望这本书能说服计算机科学以及数学领域的众多教育工作者，开设这样的课程定能取得成效！”
　　——J. H. Van Lint，《国际教育评论》
　　“翻阅这本书总是心情愉悦，书中充满了对数学的细致解释和满腔热忱的描述。”
　　——Volker Strehl，美国《数学评论》
　　“这本书可能是我读过的最精美的书了，其中的所有证明都是那么地优雅，逻辑清晰，笔意酣畅，这大概是作者采用了优雅、有效的符号的缘故。”
　　——亚马逊评论
　　“这本书非常值得一读，无论是书中清晰阐述的数学概念，还是穿插其中的风趣幽默的涂鸦。”
　　——亚马逊评论
　　“仅仅考虑它的实用性，这本书也值得你永久保留。”
　　——亚马逊评论
　　“很喜欢这本书的写作风格！作者不仅讲述数学问题和技巧，而且教人解决问题的方法，以一种令人觉得有趣的方式，带有一点感情色彩，而不是一味的灌输。”
　　——豆瓣评论
　　“我经常被书中美妙的公式和结论所打动，领略到数学的美丽和奇妙。”
　　——豆瓣评论