Donald Knuth: about Richard Feynman, awards and algorithm of the ILC

Knut is the first to receive the Grace Murray Hopper Award . Also among his achivok are the von Neumann Medal, Turing, the Kyoto Prize, and the US National Science Medal.



“I think that rewards play an important role in a person’s life, as proof that other people value your work. Despite the fact that our work is interesting in most cases, sometimes it is hard and pleasant to know that it is appreciated. Thus, the award is a good tradition. ”

Publishing support is Edison , which tests critical systems for fault tolerance , as well as designs and develops software for cluster computing .
')

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

For me, it was important to receive the National Medal of the United States, presented by President Carter. I received the privilege of sitting with Richard Feynman when he received his US National Science Medal. And before going up for his reward, he pushed me with his shoulder and said: “Ok Don. This is your important moment. ” He was my hero. I knew him from the California Institute of Technology, and this day was especially important to me.

I also received other awards for computer science, such as the Harvey Prize in Israel. Again, these awards are available not only for computer specialists, but also for chemists, physicists, and biologists. People from different scientific fields. Some of the awards were available for the humanities, and I am pleased to admit that I also received a Doctor of the Humanities for working on the programming language METAFONT. This is what satisfies my soul and gives strength to go on.



The biggest reward, of course, was the Kyoto Prize , received 10 years ago. This is the prize that the best computer scientists hope for. She recognizes achievements accomplished in a lifetime in a particular field, and is awarded every three to four years.

At that time, I was able to take my wife’s 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 that time I gave 13 lectures in 13 different subjects, of which eight were prepared, and five lectures I had to improvise.

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


Nob yoshigahara

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

Oh yes, you are right. The Kyoto Prize is also accompanied by a cash reward. Of course, this is not the Nobel Prize, but large enough to convince the world that they thought twice before handing it over. The prize was about $ 400,000, and Jill and I didn't want it to ruin our lives.

We were happy and out of money, so we didn’t know what would have happened if we had left them to ourselves, but understood that something was bad. Therefore, we spent $ 100,000 on trips for our family, donated $ 100,000 to my primary school, where I was in the first through eighth grade, donated $ 100,000 to Stanford and spent $ 100,000 to buy a new organ to the church I attend in Palo Alto.

Donald Knuth receives Kyoto Prize, the Japanese "Nobel"

Knuth-Morris-Pratt Algorithm (92/97)

I have an interesting story that I haven’t mentioned before.

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

But there are more complex words, with doubling of letters, for example. A professor at Burkeley, Steve Cook, 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, regardless of how slowly this solution will work, then you will be able to 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 he could decide whether a string of letters is a palindrome, more precisely connected by a cascade of palindromes. It was just curious for me, because no one was seriously interested in cascade-connected palindromes.

As a result, following the Cook 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 it on a regular computer; this 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, but I could not think of a solution to this problem. This was the first such dead end for me. 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 wrote down the interpretation of Cook in my smallest detail on my blackboard, which should have finally answered how to make this program faster on a regular computer.

And suddenly, ah-ha, that's the catch. I finally had 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 during a trip to Burkeley, where I met with Vaughan Pratt .



He was one of those who made the most important research, and I was just the one who later described them. Later we learned that Jim Morris had found the same idea several months earlier and had already used them in programs. But when other people looked at its source, 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 for learning the basics of computer science, so that he became quite popular and became associated with my name.

This little miracle is the Knut-Morris-Pratt (KMP) algorithm.

Translation: Nikita Shavrin

Read more

• Donald Knut: I sat in the back row and hunted jokes, and the teachers resigned and didn't often beat on the ass (1,2,3,7 / 97)
  
• Donald Knut: “My advice to the young” (93/97) and “Feeling the need to assert oneself” (9/97)
  
• Surreal Numbers: I worked for six days, and rested on the seventh (40,41,42 / 97)
  
• Donald Knut: How the “Art of Programming” was created (33,38,39 / 97)
  
• Donald Knut: about his wife, kisses, "Concrete math" and a look at teaching at the university
• Donald Knut: When will the fourth volume finally come out?
• Donald Knut: How I spent the summer with the computer, not with the girls (19,20,21,22 / 97)
• Donald Knut: about the assembler, the translator and competent programming