Дональд Кнут: про Річарда Фейнмана, нагороди та алгоритм КМП

Кнут — перший, хто отримав премію імені Грейс Мюррей Хоппер. Ще серед його ачивік — медаль фон Неймана, Тюрінга, премія Кіото і Національна наукова медаль США.



«Я думаю, що нагороди грають важливу роль в житті людини, як підтвердження того, що інші люди цінують вашу роботу. Незважаючи на те, що наша робота в більшості випадків цікава, часом вона важка і приємно усвідомлювати, що вона цінується. Таким чином, вручення нагороди є гарною традицією.»

Підтримка публікації — компанія Edison, яка тестує критичні системи на відмовостійкість, а також проектує і розробляє для кластерних обчислень.

Важливість нагород і Премія Кіото (87/97)


image

Для мене стало важливим здобуття Національної наукової медалі США, врученій президентом Картером, що стало для мене несподіванкою. Також я отримай привілеї сидіти з Річардом Фейнманом, коли він отримав свою Національну наукову медаль США. І перед тим як піднятися за своєю нагородою, він штовхнув мене плечем і сказав: «Добре Дон. Це твій важливий момент». Він був моїм героєм. Я знав його з Каліфорнійського технологічного інституту, і цей день став по-особливому важливим для мене.

Також я отримав інші нагороди, представляючи комп'ютерні науки, як, наприклад, Премія Харві в Ізраїлі. Знову ж таки, ці нагороди доступні не тільки для комп'ютерних фахівців, але і для хіміків, фізиків, біологів. Людям із різних наукових сфер. Деякі нагороди були доступні і для гуманітаріїв, і я радий визнати, що я отримав ще й Доктора Гуманітарних Наук за роботу над мовою програмування METAFONT. Це те, що задовольняє мою душу і дає сили йти далі.

image

Найбільшою нагородою, звичайно ж, була премія Кіото, отримана років 10 тому. Цей той самий приз, на який сподіваються кращі комп'ютерні вчені. Вона визнає досягнення вчинені за все життя у певній галузі і присуджується раз на три — чотири роки.

У той час я був здатний взяти свою сім'ю і родину моєї дружини і провести кілька тижнів у Японії, що добре вплинуло на нас всіх. Ми були там протягом трьох тижнів і за цей час я дав 13 лекцій з 13 різних предметів, з яких вісім були підготовлені, а п'ять лекцій мені довелося імпровізувати.

Я так само зустрівся з Імператором та Імператрицею Японії. І, знаєте, Імператриця була неймовірно вражаючим людиною. Я побачився зі своїм кумиром Нобом — найбільшим експертом з головоломкам, з яким ми скуштували гарячі ванни і відвідали безліч регіонів Японії, що стало ще однією важливою подією в житті.

image
Nob Yoshigahara

[Q] І, якщо я не помиляюсь, у вас є цікаві згадки про початок вашої кар'єри, так сказати, у початковій школі Милоуке. Ви пожертвували частину вашої нагороди вашої початковій школі.

Ох, так, ви праві. Приз Кіото так само супроводжується грошовою нагородою. Звичайно це не Нобелівська премія, але досить велика, щоб переконати світ у тому, що вони подумали двічі, перш ніж вручити її. Приз склав близько $400.000 і ми з Джилл не хотіли що б це зруйнувало нашу життя.

Ми були щасливі і без грошей, так що ми не знали, що сталося б, якщо б ми їх залишили собі, але розуміли, що щось погане. Тому ми витратили $100.000 на поїздки для нашої сім'ї, $100.000 пожертвували в мою початкову школу, де я навчався з першого по восьмий клас, $100.000 пожертвували в Стенфорд і $100.000 витратили на закупівлю нового органу в церкву, яку я відвідую в Пало-Альто.

Donald Батіг receives Kyoto Prize, the Japanese «Nobel»

Алгоритм Кнута-Морріса-Пратта (92/97)


У мене є історія, про яку я ніколи не писав, хоча я писав досить багато, і при цьому вона задоволена цікава.

Алгоритм став досить популярний, хоча особисто я не впевнений, що використовував його за останні років 20. Втім, він згадується у багатьох підручниках і є дійсно хорошим способом пошуку слова в об'ємному тексті. Наприклад, шукаючи слово «t-he», нерозумно шукати саме слово в тексті. Ну, або давайте розглянемо на прикладі слова «d-i-k-r-an». Почнемо з будь-якої точки в тексті і перевіряємо: Це 'd'? Так. Розглядаємо наступну букву. Це 'i'? Так. Наступна 'k'? Ні, бо це слово, наприклад, «direction». Тепер ми переходимо до наступного слово, знову перевіряємо. Перша літера 'I', a 'd'? Тоді пропускаємо слово, переходимо до наступного і знову перевіряємо…

Але існують і більш складні слова з подвоєнням букв, наприклад. Професор в Берклі, Стів Кук, запропонував приголомшливу теорію пов'язану з такими випадками. Він стверджував, що якщо взяти комп'ютер з дуже обмеженим обсягом пам'яті і написати рішення для нього, незалежно від того, як повільно це рішення буде працювати, то ви зможете написати більш швидку версію для нормального комп'ютера.

Таким чином, одна з проблем, яку ми намагалися вирішити з таким «обмеженим» комп'ютером, полягала в тому, що б він міг вирішити рядок букв паліндромом, точніше сполученим каскадом паліндроми. Це було для мене просто цікавим, адже ніхто всерйоз не цікавився каскадно-сполучених палиндромов. У підсумку, слідуючи теорема Кука, після того як я зможу написати програму для обмеженого комп'ютера, повинно було бути більш швидке рішення для розпізнавання таких палиндромов на звичайному комп'ютері. Але я не міг придумати хороший спосіб відтворити це на звичайному комп'ютері, це виявилася завдання набагато складніше.

У той час я вважав себе хорошим програмістом, але була теорема, яка стверджувала що це можливо, а я не міг придумати рішення цієї задачі. Це було першим таким глухим кутом у мене. Хтось казав, що є спосіб зробити це краще, а я не міг нічого придумати. Отже, я вибрав собі вечір і розписав в найдрібніших деталях у себе на дошці тлумачення Кука, яке повинно було нарешті дати відповідь як зробити цю програму швидше на звичайному комп'ютері. І раптом, ах-ха, от і підступ. У мене нарешті виникла ідея як загальна теорема підходила б до звичайного комп'ютера, і я зрозумів, що це також вирішує проблему пошуку в тексті. Так що я згадав це під час поїздки в Берклі, де я зустрічався з Воганом Праттом.

image

Він був одним з тих, хто здійснили найважливіше значення в дослідженнях, а я був лише той, який пізніше описав їх. Пізніше ми дізналися, що Джим Морріс виявив цю ж ідею кількома місяцями раніше і вже використовував їх у програмах. Але коли інші люди дивилися на його вихідні коди, вони не розуміли, що це таке, тому йому довелося це прибрати.

Незважаючи на це, цей метод досить ефективний для пошуку тексту. Більш того, він досить повчальний для навчання основам комп'ютерних наук, так що він став досить популярним і став асоціюватися з моїм ім'ям. Але як я вже говорив, всі записи, а у мене їх близько 160, кожна з них має відмітну рису, що зробило це ніж те, над чим було цікаво працювати.

Це маленьке диво — алгоритм Кнута-Морріса-Пратта (КМП)

Переклад: Микита Шаврін

Читати ще
Список 97 відеороликів з історіями Дональда КнутаПлейлист на Youtube

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 проективної planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Батіг-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 є поява 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 rights to any 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. Master Chess 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 Батіг-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 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.