Дональд Кнут: Коли ж, нарешті, вийде четвертий том

«Зараз зрозуміло, що з тією швидкістю, з якою я пишу, я не закінчу весь проект до свого дев'яностоліття.»



Прочитайте і оцініть обсяг робіт. І не квапте дідуся Батога, він так прагне.

Підтримка публікації — компанія 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-х, з якої я можу взяти пропозиції і фрази, щоб омолодити книгу.

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

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

0 коментарів

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