Donald Knuth: About Richard Feynman, awards and the ILC algorithm

Original author: Web of Stories
  • Transfer
Knut is the first to receive the Grace Murray Hopper Award . Among his achievements - von Neumann, Turing medal, Kyoto Prize and the US National Science Medal.



“I think that awards play an important role in human life, as a confirmation that other people value your work. Despite the fact that in most cases our work is interesting, sometimes it is difficult and it is pleasant to realize that it is appreciated. Thus, the presentation of the award is a good tradition. ”

Publishing support - Edison , a company that tests critical systems for fault tolerance , and also designs and develops software for cluster computing .

Importance of the Awards and Kyoto Prize (87/97)




image


It has become important for me to receive the US National Science Medal presented by President Carter. I was privileged to sit with Richard Feynman when he received his US National Science Medal. And before rising for his award, he nudged me with his shoulder and said: “Good Don. This is your important point. ” He was my hero. I knew him from the California Institute of Technology, and this day became especially important for me.

I also received other awards, representing computer science, such as the Harvey Prizein Israel. Again, these awards are available not only for computer specialists, but also for chemists, physicists, and biologists. People from different scientific fields. Some awards were available to humanities as well, and I am pleased to admit that I also received Doctors of Humanities for their work on the METAFONT programming language. This is what satisfies my soul and gives me strength to move on.

image


The biggest award, of course, was the Kyoto Prize , received about 10 years ago. This is the prize that the best computer scientists hope for. It recognizes the achievements that have been made over a lifetime in a certain field, and is awarded every three to four years.

At that time, I was able to take my family and my wife's family and spend several weeks in Japan, which had a good impact on us all. We were there for three weeks and during this time I gave 13 lectures on 13 different subjects, of which eight were prepared, and I had to improvise five lectures.

I also met with the Emperor and Empress of Japan. And, you know, the Empress was an incredibly impressive person. I saw my idol Nob, the greatest expert on puzzles, with whom we tried hot baths and visited many regions of Japan, which was another important event in life.

image

Nob Yoshigahara

[Q] And, if I'm not mistaken, you have interesting references to the beginning of your career, so to speak, at Milouk elementary school. You donated part of your reward to your primary school.

Oh yes, you're right. The Kyoto Prize also comes with a cash reward. Of course, this is not a Nobel Prize, but it is large enough to convince the world of what they thought twice before handing it. The prize was about $ 400,000 and Jill and I did not want this to ruin our lives.

We were happy without money, so we did not know what would have happened if we had left them for ourselves, but understood that something was bad. So we spent $ 100,000 on trips for our family, donated $ 100,000 to my elementary school, where I studied from first to eighth grade, donated $ 100,000 to Stanford and spent $ 100,000 to buy a new organ at the church I visit in Palo Alto.

Donald Knuth receives Kyoto Prize, the Japanese "Nobel"

Knuth-Morris-Pratt Algorithm (92/97)




I have an interesting story that I have not mentioned before.

The algorithm has become quite popular, although I have not used it in the last 20 years. However, it is mentioned in many textbooks and is a really good way to find a word in a voluminous text. For example, looking for the word “the”, it’s foolish to look for the word in the text. Well, or let's look at the example of the word “dikran”. Let's start at any point in the text and check: Is this a 'd'? Yes. Consider the next letter. Is that an 'i'? Yes. Next 'k'? No, because this word, for example, “direction”. Now we move on to the next word, check again. The first letter is 'I', but not 'd'? Then we skip the word, move on to the next and check again ...

But there are more complex words, with doubling letters, for example. A professor at Berkeley, Steve Cooke, proposed a stunning theory related to such cases. He argued that if you take a computer with a very limited amount of memory and write a solution for it, no matter how slowly this solution works, then you can write a faster version for a normal computer.

Thus, one of the problems that we tried to solve with such a "limited" computer was that it could solve whether a string of letters is a palindrome, or rather a connected cascade of palindromes. It was just curious for me, because no one was seriously interested in cascading-connected palindromes.

As a result, following Cook's theorem, after I could write a program for a limited computer, there should have been a faster solution for recognizing such palindromes on a regular computer. But I could not think of a good way to reproduce this on a regular computer, it turned out to be a much more difficult task.

At that time I considered myself a good programmer, but there was a theorem that claimed that it was possible, and I could not come up with a solution to this problem. This was my first dead end. Someone said that there is a way to do it better, but I could not think of anything. So, I chose an evening for myself and painted Cook's interpretation on the blackboard in the smallest details, which should finally give an answer on how to make this program faster on a regular computer.

And suddenly, ah ha, here’s the catch. I finally got an idea how a general theorem would fit a regular computer, and I realized that this also solves the problem of searching in the text. So I mentioned this on a trip to Berkeley, where I met Vaughan Pratt .

image


He was one of those who made the most important in research, and I was just the one who later described them. We later learned that Jim Morris discovered the same idea a few months earlier and had already used them in programs. But when other people looked at his source code, they did not understand what it was, so he had to remove it.

Despite this, the method is quite effective for finding text. Moreover, he is quite instructive in teaching the basics of computer science, so he has become quite popular and has become associated with my name.

This little miracle - Knut-Morris-Pratt algorithm (KMP)

Translation: Nikita Shavrin

Read more



List of 97 Donald Knuth videos
Youtube playlist

1. Family history
2. Learning to read and school
3. My mother
4. My parents' finances
5. Interests in high school
6. Being a nerd of nerds at high school
7. My sense of humor
8. The Potrzebie System of Weights and Measures
9. Feeling the need to prove myself
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study at university and a time of personal challenge
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My interest in graphs and my first experience of a computer
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Wanting to be a teacher and why I chose to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with ...
32. Finding a solution to an open problem about projective planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38. The Art of Computer Programming: underestimating the size of the ...
39. The successful first release of The Art of Computer Programming
40. Inspiration to write Surreal Numbers
41.Writing Surreal Numbers in a hotel room in Oslo
42. Finishing the Surreal Numbers
43. The emergence of computer science as an academic subject
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. Moving to Stanford and wondering whether I'd made the right choice
47. Designing the house in Stanford
48. Volume Three of The Art of Computer Programming
49. Working on Volume Four of The Art of Computer Programming
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typeset and the problem with specifications
57. Working on TeX
58. Why the designer and the implementer of a program should be the ...
59. Converting Volume Two to TeX
60. Writing a users' manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose not to retain any rights to TeX and transcribed it to ...
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Chess master playing at Adobe Systems
75. Giving a lecture series on science and religion at MIT
76. Back to work at Stanford and taking early retirement
77. Taking up swimming to help me cope with stress
78 My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81.Updating Volumes One to Three of The Art of Computer Programming
82. Getting started on Volume Four of “The Art of Computer ...
83. Two final major research projects
84. My love of writing and a lucky life
85. Coping with cancer
86 Honorary doctorates
87. The importance of awards and the Kyoto Prize
88. Pipe organ music is one of the great pleasures of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on algorithms in the Soviet Union
92. The Knuth-Morris-Pratt algorithm
93. My advice to young people
94. My children: John
95. My children: Jenny
96. Working on a series of books of my collected papers
97. Why I chose analysis of algorithms as a subject

Also popular now: