«Я думаю, что награды играют важную роль в жизни человека, как подтверждение того, что другие люди ценят вашу работу. Несмотря на то, что наша работа в большинстве случаев интересна, порою она тяжелая и приятно осознавать, что она ценится. Таким образом, вручение награды является хорошей традицией.»
Важность наград и Премия Киото (87/97)
Для меня стало важным получение Национальной научной медали США, врученной президентом Картером, что стало для меня неожиданностью. Также я получи привилегию сидеть с Ричардом Фейнманом, когда он получил свою Национальную научную медаль США. И перед тем как подняться за своей наградой, он толкнул меня плечом и сказал: «Хорошо Дон. Это твой важный момент». Он был моим героем. Я знал его с Калифорнийского технологического института, и этот день стал по-особому важным для меня.
Также я получил другие награды, представляя компьютерные науки, как, например, Премия Харви в Израиле. Опять же, эти награды доступны не только для компьютерных специалистов, но и для химиков, физиков, биологов. Людям из разных научных сфер. Некоторые награды были доступны и для гуманитариев, и я рад признать, что я получил ещё и Доктора Гуманитарных Наук за работу над языком программирования METAFONT. Это то, что удовлетворяет мою душу и даёт силы идти дальше.
Самой большой наградой, конечно же, была премия Киото, полученная лет 10 назад. Этот тот самый приз, на который надеются лучшие компьютерные учёные. Она признаёт достижения совершённые за всю жизнь в определенной области и присуждается раз в три — четыре года.
В то время я был способен взять свою семью и семью моей жены и провести несколько недель в Японии, что хорошо повлияло на нас всех. Мы были там в течение трёх недель и за это время я дал 13 лекций по 13 различным предметам, из которых восемь были подготовлены, а пять лекций мне пришлось импровизировать.
Я так же встретился с Императором и Императрицей Японии. И, знаете, Императрица была невероятно впечатляющим человеком. Я увиделся со своим кумиром Нобом — величайшим экспертом по головоломкам, с которым мы отведали горячие ванны и посетили множество регионов Японии, что стало ещё одним важным событием в жизни.
Nob Yoshigahara
[Q] И, если я не ошибаюсь, у вас есть интересные упоминания о начале вашей карьеры, так сказать, в начальной школе Милоуке. Вы пожертвовали часть вашей награды вашей начальной школе.
Ох, да, вы правы. Приз Киото так же сопровождается денежной наградой. Конечно это не Нобелевская премия, но достаточно велика, чтобы убедить мир в том, что они подумали дважды, прежде чем вручить её. Приз составил около $400.000 и мы с Джилл не хотели что бы это разрушило нашу жизнь.
Мы были счастливы и без денег, так что мы не знали что произошло бы, если бы мы их оставили себе, но понимали, что что-то плохое. Поэтому мы потратили $100.000 на поездки для нашей семьи, $100.000 пожертвовали в мою начальную школу, где я учился с первого по восьмой класс, $100.000 пожертвовали в Стэнфорд и $100.000 потратили на закупку нового органа в церковь, которую я посещаю в Пало-Альто.
Donald Knuth receives Kyoto Prize, the Japanese «Nobel»
Алгоритм Кнута-Морриса-Пратта (92/97)
У меня есть история, о которой я никогда не писал, хотя я писал довольно много, и при этом она довольна интересна.
Алгоритм стал довольно популярен, хотя лично я не уверен, что использовал его за последние лет 20. Впрочем, он упомянут во многих учебниках и является действительно хорошим способом поиска слова в объемном тексте. Например, ища слово «t-h-e», глупо искать само слово в тексте. Ну, или давайте рассмотрим на примере слова “d-i-k-r-a-n”. Начнем с любой точки в тексте и проверяем: Это ‘d’? Да. Рассматриваем следующую букву. Это ‘i’? Да. Следующая ‘k’? Нет, потому что это слово, например, “direction”. Теперь мы переходим к следующему слово, вновь проверяем. Первая буква ‘I’, a не ‘d’? Тогда пропускаем слово, переходим к следующему и опять проверяем…
Но существуют и более сложные слова, с удвоением букв, например. Профессор в Бэркли, Стив Кук, предложил ошеломляющую теорию связанную с такими случаями. Он утверждал, что если взять компьютер с очень ограниченным объемом памяти и написать решение для него, вне зависимости от того как медленно это решение будет работать, то вы сможете написать более быструю версию для нормального компьютера.
Таким образом, одна из проблем, которую мы пытались решить с таким «ограниченным» компьютером, состояла в том, что бы он мог решить является ли строка букв палиндромом, точнее соединённым каскадом палиндромы. Это было для меня просто любопытным, ведь никто всерьёз не интересовался в каскадно-соединенных палиндромов. В итоге, следуя теореме Кука, после того как я смогу написать программу для ограниченного компьютера, должно было быть более быстрое решение для распознавания таких палиндромов на обычном компьютере. Но я не мог придумать хороший способ воспроизвести это на обычном компьютере, это оказалась задача намного сложнее.
В то время я считал себя хорошим программистом, но была теорема, которая утверждала что это возможно, а я не мог придумать решение этой задачи. Это было первым таким тупиком у меня. Кто-то говорил, что есть способ сделать это лучше, а я не мог ничего придумать. Итак, я выбрал себе вечер и расписал в мельчайших деталях у себя на доске толкование Кука, которое должно было наконец дать ответ как сделать эту программу быстрее на обычном компьютере. И вдруг, ах-ха, вот и подвох. У меня наконец-то возникла идея как общая теорема подходила бы к обычному компьютеру, и я понял, что это также решает проблему поиска в тексте. Так что я упомянул это во время поездки в Бэркли, где я встречался с Воганом Праттом.
Он был одним из тех, кто совершили важнейшее значение в исследованиях, а я был всего лишь тот, который позже описал их. Позже мы узнали, что Джим Моррис обнаружил эту же идею несколькими месяцами ранее и уже использовал их в программах. Но когда другие люди смотрели на его исходники, они не понимали что это такое, поэтому ему пришлось это убрать.
Несмотря на это, этот метод довольно эффективен для поиска текста. Более того он довольно поучительный для обучения основам компьютерным наукам, так что он стал довольно популярен и стал ассоциироваться с моим именем. Но как я уже говорил, все записи, а у меня их около 160, каждая из них содержит отличительную черту, что сделало это чем то, над чем было интересно работать.
Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
Перевод: Никита Шаврин
Читать еще
- Дональд Кнут: Я сидел на задних партах и травил шутки, а учителя смирились и не часто били по заднице (1,2,3,7/97)
- Дональд Кнут: «Мой совет молодым» (93/97) и «Ощущая потребность самоутвердиться» (9/97)
- «Сюрреальные числа»: Я творил шесть дней, а на седьмой отдыхал (40,41,42/97)
- Дональд Кнут: Как создавалось «Искусство программирования» (33,38,39/97)
- Дональд Кнут: Когда же, наконец, выйдет четвертый том
- Дональд Кнут: Как я провел лето с компьютером, а не с девушками (19,20,21,22/97)
- Дональд Кнут: про ассемблер, транслятор и грамотное программирование
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
Комментарии (0)