Дональд Кнут: Когда же, наконец, выйдет четвертый том

Автор оригинала: Web of Stories
  • Перевод
«Сейчас предельно ясно, что с той скоростью с которой я пишу, я не закончу весь проект до своего девяностолетия.»



Прочитайте и оцените объем работ. И не торопите дедушку Кнута, он и так старается.

Поддержка публикации — компания Edison, которая разрабатывает корпоративные порталы и приложения для передачи видеороликов.

Volume Three of «The Art of Computer Programming» (48/97)




Третий том — о сортировке и поиске. Эта область сильно изменилась с тех пор, как я писал окончательный вариант книги. Итак я размышляю о сортировке и поиске как если бы я сейчас был в Принстоне. Вы знаете, я окончил работу над второй частью книги и я готов был приехать в Стэнфорд, но у меня постоянно появлялись новые идеи о сортировке, поскольку эта область была подвержена изменениям.

Поэтому после моего приезда в Стэнфорд мне нужно было преподавать и начинать делать совершенно новые вещи, которые я никогда не делал до этого момента. На это ушло какое-то время и я не смог закончить работу над третьей частью книги до моей поездки в Норвегию в 1972, когда у меня был академический отпуск. Вообще-то это не был настоящий академический отпуск, я его только так называю. А на самом деле это был отпуск за свой счет. Я уже три года работал в Стэнфорде и подумал, что это была бы отличная идея.

Профессора обычно работают 6 лет, потом уходят на год в академический отпуск, затем снова 6 лет работы и опять 1 год академического отпуска. Я подумал, что может я выберу 4-х годичный цикл. Я проработаю 3 года, возьму отпуск за свой счет, потом снова 3 года и затем академический отпуск. Правила Стэнфорда не препятствовали такому плану. А я получил приглашение из Университета Норвегии провести там один год в качестве приглашенного профессора и, так как мне не нужна была материальная помощь от Стэнфорда, я мог поехать туда, взяв отпуск за свой счет без всех этих проблем, связанных с оплатами.

И я любил Норвегию — мы посетили ее в 1967, верьте или нет. Это была еще одна из тех вещей, которые случились в 1967! И я влюбился в эту страну и в норвежский национальный гимн — Ja, vi elsker dette landet. Мы любим эту страну.

И я уехал в Норвегию и именно там я закончил работу над третьей частью и начал писать четвертую. В течение того года я читал лекции в университете каждую среду, в свободное время я был дома, писал книгу и читал, и проводил все остальное время со своими детьми.

И когда, в конце концов, третья часть вышла в свет, она добавила новый аспект ко всей этой идее анализа алгоритмов, потому что когда вы начинаете говорить о темах, которые описываются в третьей части, оказывается, что даже несмотря на то, что в ней описываются конкретные ситуации, сортировка, поиск — уроки, которые вы учитесь применять ко многим другим ситуациям, в ней еще очень много дополнительных тем.

И именно поэтому третья часть была особенно важна для меня. Парадигмы и методы которые мы использовали для изучения алгоритмов всех видов, казалось все они возникли в контексте сортировки. И я мог бы создать единую историю обо всем этом, но я преподаю общие принципы и одновременно могу проиллюстрировать их на примере особого предмета: сортировка и поиска.

Working on Volume Four of «The Art of Computer Programming» (49/97)




Затем я прихожу домой и думаю, ок я готов. Я буду писать четвертый том. Она о комбинаторных алгоритмах. Комбинаторный… это значит, что алгоритм оперирует неисчислимым количеством комбинаций способов выполнять действия и, как результат, существовало много, много проблем, которые люди хотели чтобы компьютеры решали за них.

Так много случаев надо было решить. Вам был нужен компьютер, чтобы сделать это, но теперь никто не мог выяснить как сделать это эффективно. А хорошая идея могла бы создать метод работающий в миллионы раз быстрее и я собирал все эти хорошие идеи, но у людей появлялись все новые и новые отличные идеи. И тогда..., есть такое понятие комбинаторные взрыв, которое означает для большинства людей, что размер проблемы увеличивается до гигантских масштабов и очень быстро.

Для меня комбинаторный взрыв означал, что исследование комбинаторных методов резко усиливалось. В 1974, 1975 и 1976, когда я работал над четвертой книгой, более чем 50% всех статей во всех технических журналах были о темах, которые описывались в ней. Другими словами это как сидеть на кипящем котле, вы не можете его контролировать. Каждый раз когда я писал что-то на одной неделе, на следующей это уже устаревало.

Вы знаете, это похоже на попытку написать книгу об интернете сегодня или что-то в этом роде. И поэтому казалось невозможным закончить четвертую книгу. Я стараюсь изо всех сил, собираю материал для нее, читаю газеты, делаю множество заметок. Наверху у меня сотни папок с этими заметками.

Когда я начал у меня было 30 папок и они были хорошо организованы, затем я создал папки под названиями Х1, Х2, Х3 и так до Х15 — не очень хорошо организованные, но просто расширения системы. А затем появился новый материал и я стал сваливать его в кучу, в надежде что однажды у меня будет время это прочесть. И я так и надеялся… Но эта область растет очень быстро.

Updating Volumes One to Three of «The Art of Computer Programming» (81/97)




Я закончил книгу «3:16», я закончил «Конкретную математику». И я все еще не могу вернуться к «Искусству программирования», потому что у меня все еще есть одно незаконченное дело и это Stanford GraphBase. Это собрание программ грамотности, которые используются для стандартных примеров, которые будут в четвертой части книги «Искусство программирования».

И чтобы сделать эту работу мне потребовалось еще несколько лет. Было необходимо выпустить эту базу до выхода самой книги, чтобы я смог закончить остальные проекты с другими людьми в разных частях света, которые способствовали написанию книги, чтобы они смогли использовать Stanford GraphBase для своей работы.

Примерно в 1995 году я смог открыть дверь той самой комнаты, куда я бросал все новые материалы для книги в течение 15 лет. Пока я работал над TeX, у меня совсем не было времени думать об этом и когда я получал что-то по почте, относящееся к четвертому, пятому или другим томам книги, я просто отправлял это в кучу, затем у меня появились коробки и еще коробки и в итоге накопилось примерно 17 футов материала в длину.

А кроме этого у меня были все те материалы, которые я собрал в предыдущие годы. Поэтому я решил, что мне нужно их все реорганизовать и на это ушел еще один год, даже больше года, чтобы просмотреть всё, каждый клочок бумаги, который попал туда, а затем отправить все в нужное место, создать компьютерный указатель, так, чтобы я мог найти все, разложить всё по тысячам маленьких папок-файлов и также скорректировать все ошибки в первого, второго и третьего томов.

image


Люди писали мне, сообщая об ошибках в первом, втором и третьем томах. У меня были письма с 1981, 1982 года, на которые я еще не ответил. И я выписал всем этим людям чеки с процентами с того дня. Вы знаете у меня была маленькая программа, которая вычисляла эти проценты и в ней была ошибка, поэтому я думаю, что выплатил чуть больше процентов. Но в любом случае я отослал сотни чеков и получил большой список опечаток для «Искусства компьютерного программирования» для первого, второго и третьего томов, которые я мог набрать с помощью TeX и сделать это правильно.

Все эти годы люди продолжали покупать книги на постоянной основе в книжных магазинах, они покупали издания, который вышел в 70-х годах, но уже в 30-м, в 40-м издании. И каждая из книг до сих пор продается в количестве примерно 4000 книг в год. Вторая часть была издана в 1981 года, та самая, в которой я не мог терпеть цифры, но математический материал был в порядке.

Когда вышла моя серия книг «Компьютеры и верстка», те 5 частей, все было сделано с новыми шрифтами, с соответствующим оформлением. В книге «Конкретная математика» я смог использовать новый шрифт, созданный Herman Zapf, а для книги «3:16» у меня был другой шрифт над которым я работал.

Поэтому в то время оставалась только книга «Искусство компьютерного программирования», в которой было уродливое оформление и все-равно я не хотел его исправлять. У меня заняло так много времени возвращение к написанию четвертой части, как мог я остановиться и переделывать первые три, не подождав еще немного?

На выручку пришел Silvio Levy, который живет в Беркли, который был очень активен во многих математических проектах и сейчас работает библиотекарем в Институте изучения математических наук. Он был большим фанатом TeX и совместно мы создали CWEB — систему грамотного программирования, используя C как язык программирования вместо Pascal.

Silvio решил, что он наберет первые три части книги в TeX ради общественного блага и он запросил у издательства символическую оплату, на что они конечно же легко согласились. Он, совместно со своей женой Sheila, провели исправление ошибок и они проделали изумительную работу, проверив все три части и соединив все ошибки в моем списке ошибок.

Затем у меня не заняло много времени… я имею ввиду на это ушло 3 или 4 месяца, но это ничто по сравнению с тем, сколько бы у меня ушло времени на эту работу, если бы я все делал один. И в итоге в 1997/1998 у нас было обновленное «Искусство программирования» с подходящей версткой и всеми 20 годами исправлений, которые раньше были в моих файлах, а теперь оказались включенными в текст.

Getting started on Volume Four of «The Art of Computer Programming» (82/97)




И тогда я был готов начать работу над четвертой частью. Но она до сих пор не вышла, не так ли? Так что же случилось. Ну, на самом деле, примерно 400 страниц книги уже выпущены в мягкой обложке, но для написания одной страницы мне требуется более одного дня. И я просто не в состоянии убедить себя согласиться просто на репродукцию материалов, которые я нахожу в своих файлах. Каждый раз, когда я смотрю на что-то из материалов, я вижу, что есть возможность улучшить их, и на это у меня уходит еще несколько дней.

Так что я добавляю множество материала по ходу написания четвертого тома, которого нет в литературе. Я не могу поддерживать, то что уже знаю, но те тома книги которые я сейчас пишу, я повторяю себе, что они настолько существенны, что они отличаются от томов, которые последуют за ними и что в следующем году я буду просто объединять те тома, которые не слишком-то оригинальны. Но на самом деле..., как например сегодня я закончу работу над каталогом для новой секции и это примерно 60 страниц, из которых я думаю только 15 страниц содержат информацию, которой нет в другой литературе.

Но также там есть и несколько отличающихся идей… Я не могу удержаться и не выйти за пределы источников, которыми я располагаю, когда я пишу настолько существенную часть книги. Так что сейчас предельно ясно, что с той скоростью с которой я пишу, я не закончу весь проект до своего 90-летия.

Но даже несмотря на то, что я не добавляю ничего, я не выхожу за рамки оглавления, которое я набросал в тот день в январе 1962, когда меня попросили написать книгу о компиляторах. У меня до сих пор хранится примерно такое же оглавление..., но эта область настолько увеличилась и теперь существует столь обширное количество хорошего материала, который я просто не могу не включить в книгу.

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

Будем надеяться, что у меня получится продолжать эту работу еще долгое время. Это интересно, поскольку мне приходится объединять работы авторов, которые даже не знали о трудах друг друга и у них появляется шанс создать настоящую связь их трудов и мне нравится находить способы представления материала.

Я понимаю, что сейчас я уже старый человек и пишу уже не так оживленно, как в молодости, но у меня до сих пор есть 3000 страниц рукописи, написанной в 60-х, из которой я могу взять предложения и фразы, чтобы омолодить книгу.

И также я осознаю, что этот материал совсем не легкое чтение, люди может будут держать эту книгу в туалете или в схожем месте, а может она будет стоять на полке, просто давая понять кому-нибудь, что они могут ее понять.

К некоторым из этих материалов нет легкого пути, что-то из него по своей сути трудно, но я почти в восторге от того как все идет. Например сегодня утром я составлял оглавление и я видел те части, написание которых далось мне нелегко. Но сейчас когда они закончены, они смотрятся как отличная история и то, что я мучился с их написанием, уже не кажется мне таким очевидным.

Читать еще



Список 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 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
Edison
99,00
Изобретаем успех: софт и стартапы
Поддержать автора
Поделиться публикацией

Комментарии 18

    0
      +11
      Молодец, дедуля! Многим в его годы такую бы трезвость ума да работоспособность!!!
        +3
        Он никогда не прекращал учить и учиться сам, для многих его работы стали фундаментом, дай Бог ему здоровья :)
        +1
        А ведь должны быть еще тома 5, 6 и 7…
          +1
          4-го тома 3 части должно быть, плюс потом он хотел переиздать 1-3 тома).В общем в Кнута-то я веря, но не уверен что сам доживу до издания 6-7 тома)
          +4
          Блин, парни, ну вы читали первые три тома то?
            +2
            Мне больше всего запомнилось, что в разделе про внешние сортировки с использованием жирной пачки лент он пишет что-то в духе «Пока я писал эту книгу появились жёсткие диски и вся эта вакханалия с лентами никому стала не нужна. Однако идеи там настолько красивы, что я их всё-таки изложу».
            Вообще это довольно монструозное учение. Многое из него уже стало неактуально, но там ещё много реальной крути (действительно очень красивых идей). В общем первый том я пропустил целиком, а из 2-го и 3-го (и 4а) смотрел многое. Том 4а вообще актуальный (ну да, там всё по-прежнему монументально).
              0
              кроме этого, он зачем-то держится за свой страшный ассемблер, который не имеет никакой пользы.

              Рядом есть книжки в которых ровно то же самое рассказывается с помощью C в разы понятнее без какой-либо потери смысла.

              Не, с лентами есть некоторый смысл: последовательный доступ вместо рандомного — это можно оправдать сегодня. Но, блин, Кнута обожают в институтах за его мудреность. Простые вещи рассказываются так, что создается ощущение академичности и за это его пиарят все преподы.
                0
                кроме этого, он зачем-то держится за свой страшный ассемблер, который не имеет никакой пользы.

                Не, он обещает переписать всё на нормальный ассемблер под RISC набор команд, но у него не хватает времени ))
                  +1
                  я уже почти собрался подготовиться к сдаче на мастера сбора по гребле, триатлону, шахматам и горным лыжам, но всё никак не хватает времени.

                  Не знаю, чем Кнут занимается, но всегда считал и считаю, что ценность его книг сегодня прежде всего в том, что они очень наукообразны и этим очень нравятся людям, которые считают что высшее образование должно идти с аурой недоступности плебсу.

                  Таких много среди преподавателей, которые считают очень разумным на первой лекции первому курсу толкнуть лекцию про кольца.
              +1
              Не читал, но осуждаю поддерживаю
                0
                Выборочно.
                  0
                  +1. Имеется куча специализированных книг, более полно раскрывающих темы + статьи. Всё в pdf, хочешь качай, хочешь — нет. Не как в те времена, когда тяжело было достать.
                  +2
                  Хотелось бы пожелать Дональду сил и творческого огня для продолжения написания его многотомника. Человек, чей труд по праву признан одной из двенадцати лучших физико-математических монографий столетия, заслуживает как минимум искренней благодарности, а по хорошему глубокого уважения к его непосильному труду. Искренне надеюсь на то, что, если он и не осилит все тома при жизни, то даст множество пищи для размышления в своих записях
                    +1
                    Сначала хотела спросить про этот список из 12 лучших монографий. Но поиск выдал его быстро:

                    Monographs Paul Dirac, Quantum Mechanics (1930)
                    Albert Einstein, The Collected Papers of Albert Einstein: The Swiss Years: Writings, 1902–09 (1930)
                    Benoit B. Mandelbrot, Fractals (1977)
                    Linus Pauling, Nature of the Chemical Bond (1939)
                    Bertrand Russell and Alfred North Whitehead, Principia Mathematica (1910–13, 3 vols.)
                    Cyril Smith, Search For Structure (1981)
                    John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior (1944)
                    Norbert Weiner, Cybernetics (1948)
                    R. B. Woodward and Roald Hoffmann, Conservation of Orbital Symmetry (1970)
                    Albert Einstein, The Meaning of Relativity (1922)
                    Richard Feynman, QED (1985)
                    Donald Knuth, The Art of Computer Programming (1968)

                    Если честно странный выбор, имена, конечно, известные, но вряд ли кто-то читал весь список полностью
                      0
                      Согласен с вами, таких людей вряд ли найдёшь. Однако книги рассчитаны на разные специальности и каждый профессионал в конкретной области обязан хотя бы иметь на слуху свою «Библию»
                    +2
                    Эмм… Тут такая мысль приходит: люди давно и успешно пишут софт, используя средства коллективной разработки. Не пора ли «всем миром»так же писать и книги? Большой серьёзный софт один человек не тянет, хороший софт он как поэма… И вот ещё — доходы с публикации можно так же делить между соавторами, как дедушка Кнут выписывает чеки за найденные ошибки. Хех, получить $1 от Кнута — это счастье ИМХО :)
                      0
                      Ну там не совсем $1
                      Там 0х100 центов = $2.56

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое