1978 罗伯特·弗洛伊德

shiyi18

Robert W. Floyd

PHOTOGRAPHS
BIRTH:
June 8, 1936, New York

DEATH:
September 25, 2001, California

EDUCATION:
BA (Liberal Arts, University of Chicago, 1953); BSc (Physics, University of Chicago, 1958).

EXPERIENCE:
Staff member, Armour Research Foundation, now IIT Research Institute (1953-1962)); Senior Project Scientist at Computer Associates (1962-1965); Assistant Professor (Carnegie Mellon University, 1965-1968); Stanford University (Associate Professor, 1968-1970; Full Professor, 1970-1994; Chairman, Computer Science, 1973-1976).

HONORS AND AWARDS:
Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, and the Association for Computing Machinery; appointed, for one year, as the first Grace Murray Hopper Professor at the Naval Postgraduate School; ACM Turing Award (1978); IEEE Computer Pioneer Award (1992).

ROBERT (BOB) W FLOYD DL Author Profile link
United States – 1978
CITATION
For having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
Bob Floyd was born in New York in 1936. He was a very bright child and was recognized as a prodigy when he was 6. Despite moving many times during his school years, he completed high school at age 14 and was admitted into a special program for gifted children at the University of Chicago. He received a BA degree in 1953 when he was only 17. He started working to support himself and, at the same time, completed a second bachelor’s degree in physics in 1958.

His introduction to computing came from an early job as a computer operator at the Armour Research Foundation of the Illinois Institute of Technology. His curiosity led him to become a programmer by reading the manuals, and he quickly advanced to being a senior programmer and analyst. At the same time he started his research career by publishing a paper on radio interference [1]. At Armour he became interested in the compilers that translate high level languages into machine code. He published a paper describing a new notation for symbol manipulation systems that could be used to construct compilers. He then published a paper on a new method of scanning arithmetic expressions that results in more efficient machine code. [2]

In 1962 he became Senior Project Scientist at Massachusetts-based Computer Associates. He worked on compilers and published additional papers in the area. In 1966 Donald Knuth was preparing the chapter of his famous book series The Art of Computer Programming dealing with compilers and syntax analysis, and he noticed that “only five really good papers about compilers had been written so far, and Bob had been the author of all five”. Floyd is the most cited author in The Art series.

In 1967 Floyd built on earlier work of Alan Perlis, Saul Gorn and John McCarthy for proving programs correct. He developed a notation, initially for flowcharts and later for real programs, that assigned conditions at each branch and entry point in the program. Some conditions related to the value of variables, and ensured that if these conditions were true upon entry then they could be proven true at exit. Other conditions proved a program would halt, by requiring that, at each step, some value would decrease that could not decrease indefinitely. Before this approach, ensuring that a program satisfies its specifications required testing with different data, examining the output, fixing bugs, and then trying it again. While sometimes effective, this debugging process could not test every possible situation.  Errors were often found in large programs years after they had been put into production. Floyd’s mathematical analysis was the beginning of a long series of attempts by him and others to prove a program correct before it was released to users. His paper on this topic [3] was very influential and inspired Tony Hoare to develop a system known as Hoare triples that furthered this work.

Bob also invented many important practical algorithms. Best known are those that find the shortest paths through networks, compute the median of data, and render gray scale images with binary pixels using error diffusion—the Floyd-Steinberg algorithm.

Early in his career Floyd met Donald Knuth and they became both collaborators and friends. Floyd was the main proof reader and critic for Knuth’s famous The Art of Computer Programming before it expanded from a single book into a series. The collaboration grew stronger, and Knuth sponsored Floyd’s application for a position at Stanford University. Floyd was appointed as an Associate Professor at Stanford in 1968, which was unusual for someone without a graduate degree. Floyd used to joke that he intended to get his PhD via the “green stamp” method—collecting the envelopes of all the letters he received addressed to “Dr. R. Floyd,” and when he had enough he would trade them for a real degree. He was promoted to Full Professor in 1970, and became Chair of the Department of Computer Science in 1973.

Bob had a strong social conscience and was a leading member of Amnesty International. He used his influence to help release former Chilean Minister of Education Fernando Flores from imprisonment by the military junta. Flores subsequently joined the Stanford computer science department as a researcher.

Bob loved hiking and rock climbing. He was an avid backgammon player, and studied the game carefully. He had his middle name changed to the single letter “W”, but he often wrote it as an abbreviation with a period (“W.”). He was married and divorced twice, and had a daughter and three sons.

When he retired in 1994, he and Richard Biegel published a book The Language of Machines: An Introduction to Computability and Formal Languages [4], describing a machine-based theory of computational complexity.  It gave him great satisfaction to see it translated into other languages.

Sometime shortly before his retirement in 1994 Floyd was stricken with a neurodegenerative disease that began to rob him of both his mental and physical facilities. His intellectual abilities were so strong that he managed to continue with his research, but at a slower pace. In a few years his condition had deteriorated to the point that he became unresponsive. He died in 2001.

When he died a memorial resolution was created by his colleagues at Stanford. That resolution includes other details of his life and work and can be found here.

Don Knuth, a colleague and close friend, wrote another memorial piece describing their relations and Bob’s effect on Knuth’s work. It was published as “Robert W Floyd, In Memoriam,” ACM SIGACT News, Volume 34, Issue 4, December 2003, pp. 3-13 and is available here .



Robert W. Floyd

照片
出生地：纽约
1936年6月8日，纽约

逝世。
2001年9月25日，加利福尼亚

学历。
文学士（芝加哥大学文科，1953年）；理学士（芝加哥大学物理学，1958年）。

工作经历：阿莫尔研究基金会工作人员。
Armour研究基金会的工作人员，现在是IIT研究所（1953-1962））；计算机协会的高级项目科学家（1962-1965）；助理教授（卡内基梅隆大学，1965-1968）；斯坦福大学（副教授，1968-1970；正式教授，1970-1994；计算机科学主席，1973-1976）。

荣誉和奖项。
美国艺术与科学学院、美国科学促进会和计算机械协会研究员；被任命为海军研究生院第一位格雷斯-默里-霍普教授，为期一年；ACM图灵奖（1978）；IEEE计算机先锋奖（1992）。

ROBERT (BOB) W FLOYD DL作者简介链接
美国 - 1978年
褒奖
对创建高效和可靠的软件的方法有明显的影响，并帮助创立了计算机科学的以下重要分支领域：解析理论、编程语言的语义学、自动程序验证、自动程序合成和算法分析。

简短注释
书目
亚马逊图灵奖
讲座
研究
主题
额外的
材料
鲍勃-弗洛伊德1936年出生在纽约。他是一个非常聪明的孩子，在他6岁的时候就被认为是一个神童。尽管他在上学期间多次搬家，但他在14岁时完成了高中学业，并被芝加哥大学的天才儿童特别课程录取。1953年他获得了学士学位，当时他只有17岁。他开始工作以养活自己，同时，在1958年完成了第二个物理学学士学位的学习。

他对计算机的认识来自于早期在伊利诺伊技术研究所的阿莫尔研究基金会担任计算机操作员的工作。他的好奇心使他通过阅读手册成为一名程序员，并迅速晋升为高级程序员和分析员。同时，他发表了一篇关于无线电干扰的论文，开始了他的研究生涯[1]。在Armour，他开始对将高级语言翻译成机器代码的编译器感兴趣。他发表了一篇论文，描述了一种可用于构建编译器的符号操作系统的新符号。随后，他发表了一篇关于扫描算术表达式的新方法的论文，该方法可产生更有效的机器代码。[2]

1962年，他成为位于马萨诸塞州的计算机协会的高级项目科学家。他从事编译器的工作，并发表了该领域的其他论文。1966年，唐纳德-克努斯正在准备他的著名系列丛书《计算机编程的艺术》中涉及编译器和语法分析的章节，他注意到 "到目前为止，只有五篇关于编译器的真正好的论文，而鲍勃是所有五篇论文的作者"。弗洛伊德是《艺术》系列中被引用最多的作者。

1967年，弗洛伊德在Alan Perlis、Saul Gorn和John McCarthy的早期工作基础上，证明了程序的正确性。他开发了一种符号，最初用于流程图，后来用于真正的程序，在程序的每个分支和入口点分配条件。一些条件与变量的值有关，并确保如果这些条件在进入时为真，那么它们在退出时也能被证明为真。其他条件证明程序会停止，要求在每一步中，一些数值会减少，但不能无限减少。在这种方法之前，确保一个程序满足其规格需要用不同的数据进行测试，检查输出，修复错误，然后再试一次。虽然有时很有效，但这种调试过程不可能测试所有可能的情况。 在大型程序投入生产多年后，经常会发现其错误。弗洛伊德的数学分析是他和其他人在程序发布给用户之前证明其正确性的一系列长期尝试的开始。他关于这个主题的论文[3]非常有影响力，并启发了Tony Hoare开发一个被称为Hoare triples的系统，进一步推动了这项工作。

鲍勃还发明了许多重要的实用算法。最著名的是那些寻找网络最短路径、计算数据的中位数，以及利用误差扩散渲染二进制像素的灰度图像的算法--弗洛伊德-斯坦伯格算法。

在他职业生涯的早期，弗洛伊德遇到了唐纳德-克努斯，他们成为了合作者和朋友。弗洛伊德是诺思著名的《计算机编程艺术》的主要校对者和评论者，当时该书还没有从单行本扩展到系列。双方的合作越来越紧密，Knuth赞助了Floyd在斯坦福大学的职位申请。1968年，弗洛伊德被任命为斯坦福大学的副教授，这对没有研究生学位的人来说是不寻常的。弗洛伊德曾经开玩笑说，他打算通过 "绿色邮票 "的方法来获得博士学位--收集所有他收到的写给 "R.弗洛伊德博士 "的信件的信封，当他收到足够的信件时，他将用它们来换取真正的学位。1970年，他被提升为正教授，1973年成为计算机科学系主任。

鲍勃有强烈的社会良知，是大赦国际的主要成员。他利用自己的影响力，帮助智利前教育部长费尔南多-弗洛雷斯从军政府的监禁中获释。弗洛雷斯后来加入了斯坦福大学计算机科学系，成为一名研究员。

鲍勃喜欢徒步旅行和攀岩。他是一个狂热的西洋双陆棋玩家，并仔细研究了这个游戏。他把自己的中间名改为单字母 "W"，但他经常把它写成带句号的缩写（"W"）。他结过婚，离过两次婚，有一个女儿和三个儿子。

1994年退休时，他和理查德-毕格尔出版了《机器的语言》一书。可计算性和形式语言简介[4]，描述了一个基于机器的计算复杂性理论。 看到这本书被翻译成其他语言，他感到非常满意。

在1994年退休前不久，弗洛伊德患上了一种神经退行性疾病，开始剥夺他的精神和身体设施。他的智力是如此强大，以至于他设法继续他的研究，但速度较慢。几年后，他的病情恶化，以至于他变得毫无反应。他于2001年去世。

当他去世时，他在斯坦福的同事们制定了一项纪念决议。该决议包括他生活和工作的其他细节，可以在这里找到。

唐-克努斯，一个同事和亲密的朋友，写了另一篇纪念文章，描述了他们的关系和鲍勃对克努斯工作的影响。它以 "Robert W Floyd, In Memoriam "的名义发表，ACM SIGACT News，第34卷，第4期，2003年12月，第3-13页，可以在这里找到。