第02章递归及分治策略.ppt

《计算机程序设计艺术》，国防工业出版社，译者：苏运霖 ISBN 978-7-118-02799-0 2009/04/17 * Donald E. Knuth Prize 授予为计算机科学基础做出杰出贡献的人，以计算机科学家高德纳（Donald E. Knuth）命名。 高德纳奖始于1996年，每1.5年颁发一次，包括5000美元奖金。现在奖项由?ACM计算机理论研讨会和IEEE计算机科学基础研讨会交替颁发。 2009/04/17 * Donald E. Knuth Prize 1996 -?Andrew Chi-Chih Yao (姚期智) 1997 -?Leslie Valiant 1999 -?László Lovász 2000 -?Jeffrey D. Ullman 2002 -?Christos Papadimitriou 2003 -?Miklos Ajtai 2005 -?Mihalis Yannakakis 2007 -?Nancy Lynch 2008 -?Volker Strassen 2009/04/17 * 课程回顾 * * 人心不足蛇吞象，世事到头螳捕蝉 * 归并排序算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 约翰·冯·诺伊曼（匈牙利语：Neumann János；英语：John von Neumann，1903年12月28日－1957年2月8日）是出生于匈牙利的美国籍犹太人数学家，现代计算机创始人之一。他在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献。量子力学.“计算机之父”。“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一。”若人们不相信数学简单，只因他们未意识到生命之复杂。”存储程序式计算机。 惊人的记忆力：六岁已能用古希腊语同父亲闲谈，还可以心算八位数除法。年少的他不但对数学很有兴趣，亦喜欢阅读历史、社会的书籍，读过的书籍和论文能很快一句不漏地将内容复述出来，而且多年以后仍是如此。 1926年以22岁的年龄获得了布达佩斯大学数学博士学位，相继在柏林大学和汉堡大学担任数学讲师。1930年接受了普林斯顿大学客座教授的职位，初来美国时，他在纽约对当地居民表演过默记电话簿的惊人记忆力，1931年成为该校终身教授。1933年转到该校的高级研究所，与爱因斯坦等人成为六教授之一，不须上课。这一年，他解决了希尔伯特第5个问题，证明了局部欧几里得紧群是李群。1937年成为美国公民，1938年获颁博修奖（B?cher Memorial Prize），一生结过两次婚，冯·诺伊曼是个不重视生活细节的人，他在一间房子住上多年，有一次却心事忡忡的问老婆杯子放在哪里。1954年任美国原子能委员会委员。1954年夏天，右肩受伤，手术时发现患有骨癌，治疗期间，依然参加每周三次的原子能委员会会议，甚至美国国防部长，陆、海、空三军参谋长聚集在病房开会。1957年2月8日，在华盛顿德里医院去世。晚年，有学生请教他做事的方法，他说：“简单”（simple）。1994年被授予美国国家基础科学奖。 计算机之父 参考存储程序型计算机1945年6月，冯·诺伊曼与戈德斯坦、勃克斯等人，联名发表了一篇长达101页纸的报告，即计算机史上著名的“101页报告”，是现代计算机科学发展里程碑式的文献。明确规定用二进制替代十进制运算，并将计算机分成五大组件，这一卓越的思想为电子计算机的逻辑结构设计奠定了基础，已成为计算机设计的基本原则。1951年，EDVAC计算机宣告完成。由于他在计算机逻辑结构设计上的伟大贡献，他被誉为“计算机之父”。 * 条件：子问题互相独立且与原问题相同。 不是互相独立的。 假设有两个任务并行执行，每个任务分别由粉色和绿色两个步骤组成。粉色和粉色之间有不能重叠的约束，绿色与绿色之间也有不能重叠的约束。求并行执行总的时间。 * * 这种图片应用了传说中的 Droste effect（德罗斯特效应），数学上叫它递归效应。Droste 是荷兰一个可可的厂牌，它运用视觉效果设计的包装，使这厂牌名闻于世。 这包装的图片含有一个小部份与与整张图片相同，如此产生无限循环，这种视觉效果就叫做Droste effect。 * * /blog/101283；/questionhtml 斐波那契是意大利的数学家。他是一个商人的儿子。儿童时代跟随父亲到了阿尔及利亚，在那里学到了许多阿拉伯的算术和代数知识，从而对数学产生了浓厚的兴趣。　　长大以后，因为商业贸易关系，他走遍了许多国家，到过埃及、叙利亚、希腊、西西里和法兰西。每到一处他都留心搜集数学知识。回国后，他把搜集到的算术和代数材料，进行研究、整理，编写成一本书，取名为《算盘之书》，于1202年正式