2022年程序员的数学修养 .pdf

《2022年程序员的数学修养 .pdf》由会员分享，可在线阅读，更多相关《2022年程序员的数学修养 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序员的数学修养可能有很多朋友在网上看过google 公司早几年的招聘广告，它的第一题如下了:first 10- digit prime found in consecutive digits ， e 中出现的连续的第一个10 个数字组成的质数。据说当时这个试题在美国很多地铁的出站口都有大幅广告，只要正确解答了这道题，在浏览器的地址栏中输入这个答案，就可以进入下一轮的测试，整个测试过程如同一个数学迷宫，直到你成为google 的一员。又如 Intel某年的一道面试题目: 巴拿赫病故于1945 年 8 月 31 日。他的出生年份恰好是他在世时某年年龄的平方，问: 他是哪年出生的?这道看似很简单的

2、数学问题，你能不能能快地解答呢? 下面则是一道世界第一大软件公司微软的招聘测试题: 中间只隔一个数字的两个素数被称为素数对，比如5 和 7，17 和 19，证明素数对之间的数字总能被 6 整除 (假设这两个素数都大于6) ，现在证明没有由三个素数组成的素数对。这样的试题还有很多很多，这些题目乍初看上去都是一些数学问题。但是世界上一些著名的公司都把它们用于招聘测试，可见它们对新员工数学基础的重视。 数学试题与应用程序试题是许多大型软件公司面试中指向性最明显的一类试题，这些试题就是考察应聘者的数学能力与计算机能力。某咨询公司的一名高级顾问曾说: 微软是一家电脑软件公司，当然要求其员工有一定的计算机

3、和数学能力， 面试中自然就会考察这类能力。微软的面试题目就考察了应聘人员对基础知识的掌握程度、对基础知识的应用能力，甚至暗含了对计算机基本原理的考察。所以，这样的面试题目的确很“毒辣”，足以筛选到合适的人。四川大学数学学院的曹广福教授曾说过: “一个大学生将来的作为与他的数学修养有很大的关系”。 大学计算机专业学生都有感触，计算机专业课程中最难的几门课程莫过于离散数学 、编译原理 、数据结构 ，当然像 组合数学 、密码学 、计算机图形学等课程也令许多人学起来相当吃力，很多自认为数据库学得很好的学生在范式、函数依赖、 传递依赖等数学性比较强的概念面前感到力不从心，这些都是因为数学基础或者说数学知

4、识的缺乏所造成的。数学是计算机的基础，这也是为什么考计算机专业研究生数学都采用最难试题(数学一 ) 的原因，当然这也能促使一些新的交叉学科如数学与应用软件、信息与计算科学专业等飞速发展。许多天才程序员本身就是数学尖子，众所周知，Bill Gates的数学成绩一直都很棒，他甚至曾经期望当一名数学教授，他的母校湖滨中学的数学系主任弗雷福赖特曾这样谈起过他的学生: “他能用一种最简单的方法来解决某个代数或计算机问题，他可以用数学的方法来找到一条处理问题的捷径，我教了这么多年的书，没见过像他这样天分的数学奇才。他甚至可以和我工作过多年的那些优秀数学家媲美。当然，比尔也各方面表现得都很优秀，不仅仅是数学

5、，他的知识面非常广泛， 数学仅是他众多特长之一。”。影响一代中国程序人的金山软件股份有限公司董事长求伯君当年高考数学成绩满分进一步说明了问题。很多数学基础很好的人，一旦熟悉了某种计名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 算机语言， 他可以很快地理解一些算法的精髓，使之能够运用自如，并可能写出时间与空间复杂度都有明显改善的算法。程序设计当中解决的相当一部分问题都会涉及各种各样的科学计算，这需要程序员具有什么样的基础呢 ?实

6、际问题转换为程序，要经过一个对问题抽象的过程，建立起完善的数学模型，只有这样，我们才能建立一个设计良好的程序。从中我们不难看出数学在程序设计领域的重要性。算法与计算理论是计算机程序设计领域的灵魂所在，是发挥程序设计者严谨，敏锐思维的有效工具，任何的程序设计语言都试图将之发挥得淋漓尽致。程序员需要一定的数学修养，不但是编程本身的需要，同时也是培养逻辑思维以及严谨的编程作风的需要。数学可以锻炼我们的思维能力，可以帮助我们解决现实中的问题。可以帮助我们更高的学习哲学。为什么经常有人对一些科学计算程序一筹莫展，他可以读懂每一行代码，但是却无法预测程序的预测结果，甚至对程序的结构与功能也一知半解，给他一

7、个稍微复杂点的数学公式，他可能就不知道怎么把它变成计算机程序。很多程序员还停留在做做简单的MIS，设计一下 MDI ， 写写简单的Class 或用 SQL语句实现查询等基础的编程工作上，对于一些需要用到数学知识的编程工作就避而远之，当然实现一个累加程序或者一个税率的换算程序还是很容易的，因为它们并不需要什么高深的数学知识。一名有过10 多年开发经验的老程序员曾说过: “所有程序的本质就是逻辑。技术你已经较好地掌握了，但只有完成逻辑能力的提高，你才能成为一名职业程序员。打一个比方吧，你会十八般武艺，刀枪棍棒都很精通，但就是力气不够，所以永远都上不了战场，这个力气对程序员而言就是逻辑能力( 其本质

8、是一个人的数学修养，注意，不是数学知识) 。” 程序员的数学修养不是一朝一夕就可以培养的。数学修养与数学知识不一样，修养需要一个长期的过程， 而知识的学习可能只是一段短暂的时间。下面是一些我个人对于程序员如何提高与培养自己的数学修养的基本看法。首先， 应该意识到数学修养的重要性。作为一个优秀的程序员，一定的数学修养是十分重要也是必要的。 数学是自然科学的基础，计算机科学实际上是数学的一个分支。计算机理论其实是很多数学知识的融合，软件工程需要图论，密码学需要数论，软件测试需要组合数学，计算机程序的编制更需要很多的数学知识，如集合论、排队论、离散数学、统计学，当然还有微积分。计算机科学一个最大的特

9、征是信息与知识更新速度很快，随着数学知识与计算机理论的进一步结合，数据挖掘、模式识别、神经网络等分支科学得到了迅速发展，控制论、模糊数学、耗散理论、分形科学都促进了计算机软件理论、信息管理技术的发展。严格的说， 一个数学基础不扎实的程序不能算一个合格的程序员，很多介绍计算机算法的书籍本身也就是数学知识的应用与计算机实现手册。其次， 自身数学知识的积累，培养自己的空间思维能力和逻辑判断能力。数学是一门分支众名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - -

10、- - - - - - 多的学科， 我们无法在短暂的一生中学会所有的数学知识，像泛函理论、 混沌理论以及一些非线性数学问题不是三五几天就可以掌握的。数学修养的培养并不在与数学知识的多少，但要求程序员有良好的数学学习能力，能够很快地把一些数学知识和自己正在解决的问题联系起来，很多理学大师虽然不是数学出身，但是他们对数学有很强的理解能力和敏锐的观察力，于是一系列新的学科诞生了，如计算化学、计算生物学、生物信息学、化学信息学、计算物理学，计算材料学等等。数学是自然学科的基础，计算机技术作为理论与实践的结合，更需要把数学的一些精髓融入其中。从计算机的诞生来看它就是在数学的基础上产生的，最简单的0、1

11、进制就是一个古老的数学问题。 程序设计作为一项创造性很强的职业，它需要程序员有一定的数学修养，也具有一定的数学知识的积累，可以更好地把一些数学原理与思想应用于实际的编程工作中去。学无止境，不断的学习是提高修养的必经之路。第三，多在实践中运用数学。有些高等学校开设了一门这样的课程数学建模 。我在大学时期也曾学过，这是一门内容很丰富的课程。它把很多相关的学科与数学都联系在一起，通过很多数学模型来解决实际的生产生活问题，很多问题的解决需要计算机程序来实现。我在大学和研究生阶段都参加过数学建模竞赛，获得了不少的经验，同时也进一步提高了自己的数学修养。实际上， 现在的程序设计从某些角度来看就是一个数学建

12、模的过程，模型的好坏关系到系统的成败，现在数学建模的思想已经用于计算机的许多相关学科中，不单只是计算机程序设计与算法分析。应该知道， 数学是一门需要在实践中展示其魅力的科学，而计算机程序也是为帮助解决实际问题而编制的，因此，应该尽量使它们结合起来，在这个方面，计算机密码学是我认为运用数学知识最深最广泛的，每一个好的加密算法后面都有一个数学理论的支持，如椭圆曲线、 背包问题、素数理论等。 作为一名优秀的程序员，应该在实际工作中根据需要灵活运用数学知识，培养一定的数学建模能力，善于归纳总结，慢慢使自己的数学知识更加全面，数学修养得到进一步提高。第四， 程序员培养制度与教学的改革。许多程序员培养体制

13、存在很多缺陷，一开始就要求学员能够快速精通某种语言，以语言为中心，对算法的核心思想与相关的数学知识都一笔带过，讲得很少， 这造成很多程序员成为背程序的机器，这样不利于程序员自身的快速成长，也不利于程序员解决新问题。我在长期的程序员培训与计算机教学工作采用了一些与传统方式不一致的方法，收到了一定的效果。很多初学程序的人往往写程序时有时候会有思维中断，或者对一些稍难的程序觉得无法下手，我采用了一些课前解决数学小问题的方法来激励大家的学习兴趣，这些小问题不单单是脑筋急转弯，其中不少是很有代表意义的数学思考题。通过数学问题来做编程的热身运动， 让学员在数学试题中激发自己的思维能力，记得有位专家曾经说过

14、，经常做做数学题目会使自己变聪明，很长时间不去接触数学问题会使自己思维迟钝。通过一些经典的数学问题来培养学员的思维的严谨性和跳跃性。很多人可能不以为然，其实有些看似简单的问题并不一定能够快速给出答案，大脑也是在不断的运用中变更加灵活的。不信吗?大家有兴趣可以做做下面这道题目， 看看能不能在1 分钟之内想到答案，这只是一道小学数学课后习题。很多人认为自己的数学基础很好，但是据说这道题目90% 以上的人不能在一个小时内给出正确答案。试试，如果你觉得我说的是错的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

15、 - - - - 第 3 页，共 8 页 - - - - - - - - - 证明 :AB+ACDB+DC(D 为三角形 ABC的一个内点 ) 。最后，多学多问，多看好书，看经典。我在这里向大家推荐两部可能大家已经很熟悉的经典的计算机算法教材，它们中间很多内容其实就是数学知识的介绍。第一部是算法导论 ，英文名称 : Introduction to Algorithms，作者 :Thomas H. Cormen ，Charles E. Leiserson ，Ronald L. Rivest ，Clifford Stein。本书的主要作者来自麻省理工大学计算机，作者之一Ronald L.Rives

16、t 由于其在公开秘钥密码算法RSA上的贡献获得了图灵奖。这本书目前是算法的标准教材，美国许多名校的计算机系都使用它，国内有些院校也将本书作为算法课程的教材。另外许多专业人员也经常引用它。本书基本包含了所有的经典算法，程序全部由伪代码实现，这更增添了本书的通用性， 使得利用各种程序设计语言进行程序开发的程序员都可以作为参考。语言方面通俗，很适合作为算法教材和自学算法之用。另一部是很多人都应该知道的Donald.E.Knuth所著计算机程序设计艺术 ，英文名称 : The Art of Computer Programming。 Donald.E.Knuth人生最辉煌的时刻在斯坦福大学计算机系渡过

17、，美国计算机协会图灵奖的获得者，是本领域内当之无愧的泰斗。 有戏言称搞计算机程序设计的不认识Knuth 就等于搞物理的不知道爱因斯坦，搞数学的不知道欧拉，搞化学的不知道道尔顿。被简称为TAOCP 的这本巨著内容博大精深，几乎涵盖了计算机程序设计算法与理论最重要的内容。现在发行的只有三卷，分别为 基础运算法则，半数值算法 ，以及 排序和搜索 ( 在写本文之际，第四卷已经出来了，我也在第一时间抢购了一本) 。本书结合大量数学知识，分析不同应用领域中的各种算法，研究算法的复杂性，即算法的时间、空间效率， 探讨各种适用算法等，其理论和实践价值得到了全世界计算机工作者的公认。书中引入的许多术语、 得到的

18、许多结论都变成了计算机领域的标准术语和被广泛引用的结果。另外， 作者对有关领域的科学发展史也有深入研究，因此本书介绍众多研究成果的同时，也对其历史渊源和发展过程做了很好的介绍，这种特色在全球科学著作中是不多见的。至于本书的价值我觉得Bill Gates 先生的话足以说明问题 : “如果你认为你是一名真正优秀的程序员读Knuth 的计算机程序设计艺术 ，如果你能读懂整套书的话，请给我发一份你的简历”。作者数学方面的功底造就了本书严谨的风格，虽然本书不是用当今流行的程序设计语言描述的，但这丝毫不损伤它“程序设计史诗”的地位。道理很简单，它内涵的设计思想是永远不会过时的。除非英语实在有困难，否则建议

19、读者选用英文版。我个人就是阅读的该书的英文版，虽然花了不少money和时间， 但是收获颇丰，值得。总之， 要想成为一名有潜力有发展前途的程序员，或者想成为程序员中的佼佼者，你一定要培养良好的数学修养。切记: 对于一名能够灵活自如编写各种程序的人，数学是程序的灵魂注： Donald.E.Knuth ( 唐纳德 .E. 克努特 ) 算法和程序设计技术的先驱者，计算机排版系统TEX（ telegraph exchange）和 METAFONT的发明者，他因这些成就和大量创造性的影响深远的著作(19 部书和160 篇论文 ) 而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，他当前正全神贯注

20、于完成其关于计算机科学的史诗性的七卷集。这一伟大工程在1962 年他还是加利福尼亚理工学院的研究生时就开始了。 Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 奖 (ACM Turing Award)，美国前总统卡特授予的科学金奖(Medal of Science)，美国数学学会斯蒂尔奖(AMS Steele Prize)，以及 1996 年 11 月由于发明先进技术荣获

21、的极受尊重的京都奖(KyotoPrize)。现与其妻Jill生活于斯坦福校园内。Donald Knuth自传的开头这样写道：“ Donald Knuth真的只是一个人么？”作为世界顶级计算机科学家之一，Knuth教授已经完成了编译程序、属性文法和运算法则的前沿研究，并编著完成了已在程序设计领域中具有权威标准和参考价值的书目的前三卷。在完成该项工作之余，Knuth 还用了十年时间发明了两个数字排版系统，并编写了六本著作对其做了详尽的解释说明，现在, 这两个系统已经被广泛地运用于全世界的数学刊物的排版中。随后，Knuth 又发明了文件程序设计的两种语言，以及“文章性程式语言”相关的方法论。到目前为

22、止，Knuth已经出版发行了17 部书籍，一百五十余篇论文，包括了巴比伦算法、圣经、字母“ s”的历史等多方面的内容。作为一名数学家， Knuth曾开创了几门新的课程，为纯计算数学做出了很大贡献。他所获得的奖项和荣誉数不胜数，其中最值得注目的有1974 年美国计算机协会图灵奖 (ACM Turing Award)， 1979 年美国前总统卡特授予的科学金奖(Medal of Science)以及 1996 年 11 月由于发明先进技术荣获的极受尊重的京都奖 (Kyoto Prize)。在不多的业余时间里，Knuth不仅写小说，还是一个音乐家、作曲家、管风琴设计师。是 Knuth 独特的审美感决

23、定了他兴趣广泛、富有多方面造诣的特点，Knuth传奇般的生产力也是源于这一点。对于Knuth 来说，衡量一个计算机程序是否完整的标准不仅仅在于它是否能够运行，他认为一个计算机程序应该是雅致的、甚至可以说是美的。计算机程序设计应该是一门艺术，一个算法应该像一段音乐，而一个好的程序应该如一部文学作品一般。早期经历Knuth ，1938 年 1 月 10 日生于美国威斯康星州密尔沃基市。他在模式方面辨别和熟练操作的能力在八年级的时候开始显现出来。当时， 当地的一家糖果制造商举办了一项比赛，比赛要求选手用其品牌“ Zieglers Giant Bar”中的字母组成新的单词，规定时间内组成单词数量最多者

24、获胜。Knuth 参加了比赛，并以单词总数4500 余个远远超过了裁判的2500 个的标准，轻松赢得头奖。赛后，Knuth说道，如果自己当初想到回答时用些省略符号的话，还能写出更多。这次比赛Knuth为学校赢得了一台电视机，还为每个同学赢得了一根糖果棒。Knuth 多产的出版事业开始于他的高中时代，当时他的科技设计被Westinghouse Science Talent Search 光荣提及。他的“ Potzebie System of Weights and Measures ”的基础章节被登在“ Mad ”杂志第26 号，“ Power”的基础章节被叫作“ whatmeworry”。“M

25、ad ”的编辑认识到了年轻的Donald著作的重要性，以25 美元买下了他的文章，并刊登在了其1957 年 6 月的期刊上。高中的时候，Knuth 对数学并没多大兴趣，而是把主要精力放在主修的课程：听音乐和作曲上。他在高中的乐队里吹萨克斯、大号时，曾把Dragnet 、 Howdy Doody Time 和名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - Brylcream的主题曲联成一段新的音乐。这位著名的科学家在近期评论自己的

26、早期作品时承认：“对于版权，我一无所知。” 虽然 Knuth 的 GPA是学校历史上最高的，但是他和他的指导老师还是对他能否成功学习大学数学持怀疑态度。Knuth 说在他高中阶段和大学早期一直有一种自卑感，这个问题一度是他的一个障碍。作为一个大学新生，Knuth没有对于失败的恐惧，他花了许多时间攻克额外的数学难题，几个月后，他在这方面的能力已经远远超过了其他同学。高等教育和早期的计算机工作当 Knuth 在 Case 科学院（现在的Case Western Reserve）获得物理奖学金时，梦想成为一个音乐家的计划改变了。Knuth回去继续研究数学是在大二，当时一个爱出难题的教授提出了一个特殊

27、的问题，并说哪个学生能解决这个问题就立刻记成绩“A”。Knuth跟大多数同学一样，也认为那是道解不出来的题目，直到有一天，他错过了公共汽车，只能步行去看一个演出，Knuth 利用路上这点空闲时间决定尝试一下。那阵子他运气真的是非常好，不仅问题很快就解开了，得到了“A”，还成功地经常逃课。虽然 Knuth也承认，逃课让他有负罪感，但是很明显，他完全有能力补上落下的功课，接下来的一学年，他的离散数学就又得了个“ A”，而且还获得了给自己不能参加的课程评定论文等级的工作机会。1956 年，作为Case 的新生，Knuth第一次接触到了计算机，那是一台IBM 650 。 Knuth 说直到一年后，女孩

28、才进入了他的生活。这又是计算机科学界一直以来亏欠科学家们的一个事例之一。Knuth 熬夜读IBM 650的说明手册，自学基本的程序设计。那时，在高等计算机语言发明之前，程序编写只能用第二代或是汇编语言。这个工作既耗时又困难，因为指令必须根据每台机器特定的构造编写，而实际上指令只须一步就可从二进制0、 1 系列转存到计算机硬盘上。Knuth说，有了第一次使用650 的经历，他便肯定自己能编写出比说明手册上介绍的更好的程序。Knuth 很快便开始“闲逛”，编写可以执行数学函数的程序。他的第一个程序是把数字转化为素数，第三个是做井字游戏（或者说是让计算机在改正每次输的错误的过程来学会玩井字游戏）。作

29、为学校篮球队的经理，Knuth编写了一个根据不同成绩标准评定每个运动员对球队贡献等级的程序，他的努力赢来了那些认为这样做有助于球队赢得同盟冠军的教练的好评（虽然，无庸质疑，不是每一个运动员都这样认为）。Knuth的成就成了新闻周刊的标志，他和教练、计算机的照片也被刊登在IBM650 后来的说明手册上。1960 年， Knuth 从 Case 毕业时享有着最高荣誉，在由全体教员参加的选举上，他因其公认的出众成就获得了硕士学位。1963 年， Knuth 回到加利福尼亚理工学院攻取了数学博士学位，之后成为了该院的数学教授。在加利福尼亚理工学院任教期间，Knuth作为 Burroughs 公司的顾问

30、继续从事软件开发工作。1968 年，他加入了斯坦福大学，九年后坐上了该校计算机科学学科的第一把交椅。1993 年， Knuth 成为斯坦福大学“the Art of Computer Programming”（计算机程序设计艺术）的荣誉退休教授。早期成就和计算机程序设计艺术的开端名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 1962 年， Knuth 还是个研究生的时候就开始了他计算机程序的工作。那时，他已经开始了个人咨询，为

31、不同的机器编写编译程序。编译程序是一种翻译原始或高级语言和对象或二进制机器语言的中间语言。在不知道众多软件公司正高额寻求成百上千的编辑者的情况下， Knuth 编写了一个程序，赚得5000 美元，他的名字立刻响誉了整个行业。世界上一流的出版社Addison-Wesley找到 Knuth ，请他写一本关于编译程序的书。到1966 年， Knuth 已经发表了3000 页的手写设计草图，并且发明了一种综合方法，用于分析或决定结构翻译所客观需要的文法规则。最近，关于他的那第一部著作，Knuth 自己这样评述：“用三年半的时间写第一章可并不是件好事。” 当 Knuth 的出版商计算出他的那3000 页

32、的笔迹打印成文章大约需要2000 页时， 大家才发现这实际上是一项多么大的工程。Knuth决定将它详述，成为一部更大的关于程序设计科学的纵览，共分为七个部分。一部巨著就这样诞生了。计算机程序设计艺术，至今仍是各程序类图书书架上标志性的书籍。微软首席执行官比尔. 盖茨在1995 年接受一次采访时说，“如果你认为你是一名真正优秀的程序员，就去读第一卷，确定可以解决其中所有的问题。”值得注意的是，盖茨本人读这本书时用去了几个月的时间，并同时进行了难以置信的训练。盖茨还说：“如果你能读懂整套书的话，请给我发一份你的简历。”依 Knuth 本人所讲，计算机程序设计艺术是他毕生最重要的事业，其目的是“组织

33、和总结所知道的计算机方法的相关知识，并打下坚实的数学、历史基础”。Knuth撰写的前三卷被翻译成多种语言，到1976 年为止，已卖出超过一百万册。他目前正全神贯注地编写第四卷，他期望第四卷的篇幅约为2000 页，并分为三个独立的章节。为了完成丛书的其余部分，Knuth现在进入了一种引退的状态，全身心地投入这项工作。Knuth说，一般说来，他更喜欢在一段时间内集中精神完成一项工作，正像他自己在书中提出的：按“一批”的模式。Knuth 从他主要的工作计划中拿出了十年，即从 1976 年起，致力于对数字排版的研究，设计了著名的文件准备TeX 系统， 字体生成程序METAFONT 。这项工作带来的值得

34、注意的副产品是用于结构文件和“文章性程式语言”附随方法论的WEB和 CWEB 语言。现在， Knuth和他的妻子Jill，两个孩子John 和 Jennifer一起，住在斯坦福大学校园里。他继续着计算机程序设计艺术第四卷的编写工作。虽然说Knuth是全身心的投入这一项工作，但他还是能挤出时间研究MMIX的设计，那是一台64 位 RISC（精简指令集计算机）。而他的业余爱好仍然是音乐，还一直邀请那些能够即兴演奏四手联弹钢琴曲的人们给他留下便条，以便安排一些活动。成就简要回顾编译程序编译程序能够实现高级语言和二进制机器语言之间的翻译。二十世纪六十年代初期，Knuth教授致力于这方面的研究，虽然现代

35、的软件已经可以使其变的简单一些，但编写编译程序仍被认为是一项极为困难的工作。Knuth教授在这方面最著名的成就是LR(k) 分析的研究，那是一个能使确定一串字符文法规则的过程更加顺畅的值得注目的方法。属性文法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 在编译程序的工作之后，Knuth教授走上了形式上定义程序语言意义、语义的研究道路。他建立起一个更加经济的方法去通译联合规则，他把这种方法称作“属性规则”。该方法创立的同时，计算

36、机科学的子域被称作“属性文法”。算法也许 Knuth 教授在计算机科学领域最原创的贡献就是他对于算法的分析。算法是编写一个程序，使之能去完成一项任务的基础，例如搜索或分类等。在加利福尼亚理工学院时，Knuth教授在一个毕业生的协作下，开发了用来探究数学公理推论的Knuth-Bendix算法。1968 年， Knuth 教授在斯坦福，和他的一个学生开发了Knuth-Morris-Pratt算法，该法则使计算机在文章中搜索一串字符的过程更加连贯。他所著的计算机程序设计艺术是一个详尽的算法实践和科学的概观。数字化排版“数学书籍和杂志已经不像从前那样漂亮了。”Knuth教授在一篇早期关于数学排版的文章

37、中这样写道。由于对计算机排版的校样的低质量感到无法忍受， Knuth教授从他史诗性的七卷集巨著的编写过程中拿出了十年时间，来开发一个高质量的计算机排版系统。其间， Knuth 开发了两个用于文件排版和字体生成的软件系统，这两个系统现在已被世界大多数出版社运用。它们分别是TeX，用于出版业的科学排版，和“优美文章”的产品；METAFONT ，一个字体生成程序。结构化文件和文章性程式语言Knuth 教授的排版研究，引领他发明了文件构造的两种语言和一个方法论，叫作“文章性程式语言”。语言分别是WEB和 CWEB ，它们促进了程序编写向“文学作品，是用来阅读的”这个方向发展。这两种语言的结合，一种是文件格式化，另一种是程序设计，这就使程序员能够同时创建两个不同的系统程序，一个面向人，另一个面向机器。当一条过程清楚地描述程序并促进其维护时，另外一个则产生一个机器可执行的程序。这些工作就是 Knuth 教授在实现其使程序设计为读者易懂、甚至感觉漂亮的目标的过程中，在计算机领域里所做出的巨大贡献。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -