] Автор: Кнут Дональд Эрвин (Donald Ervin Knuth). Научное издание. Перевод с английского Р.М. Кузнец, О.А. Маховая, Н.В. Третьяков, Ю.В. Тюменцев, под редакцией И.А. Маховой. Художник И.И. Куликова.
(Москва: Издательство «Мир», Издательство «ACT», 2003. - Серия «Библиотека издательских технологий»)
Скан, обработка, формат Djv: ???, предоставил: Михаил, 2016

• КРАТКОЕ ОГЛАВЛЕНИЕ:
  Предисловие редактора перевода (5).
  Предисловие (11).
  Ссылки на источники (16).
  Глава 1. Компьютерная типография (19).
  Глава 2. Математическая типография (36).
  Глава 3. Верстка абзацев (79).
  Глава 4. Сочетание текстов, читаемых справа налево и слева направо (167).
  Глава 5. Рецепты и дроби (187).
  Глава 6. Логотип системы TEX в различных шрифтах (192).
  Глава 7. Генерирование избранных страниц (194).
  Глава 8. Макро, написанные для Джил (196).
  Глава 9. Задача на субботнее утро (205).
  Глава 10. Упражнения к книге TEX: The Program (207).
  Глава 11. Мини-указатели для самодокументированных программ (235).
  Глава 12. Виртуальные шрифты. Развлечение для настоящих мастеров (256).
  Глава 13. Буква S (273).
  Глава 14. Мое первое знакомство с индийской письменностью (293).
  Глава 15. Концепция меташрифта (296).
  Глава 16. Уроки METRFONT"a (321).
  Глава 17. AMS Euler - новый математический шрифт (344).
  Глава 18. Набор книги Concrete Mathematics (369).
  Глава 19. Из опыта преподавания программирования на METAFONT"e (381).
  Глава 20. Меташрифт Punk (393).
  Глава 21. Шрифты для дискретных полутонов (415).
  Глава 22. Оцифровка полутонов посредством диффузии точки (447).
  Глава 23. Заметки об оцифровке углов (469).
  Глава 24. TEXDR.AFT (477).
  Глава 25. TEX.ONE (506).
  Глава 26. TEX"овские инкунабулы (539).
  Глава 27. Пиктограммы для TEX"a и METAFONT"a (552).
  Глава 28. Компьютеры и книгоиздание (559).
  Глава 29. Новые версии TEX"a и METRFONT"a (567).
  Глава 30. Будущее TEX"a и METRFONT"a (576).
  Глава 31. Вопросы и ответы, I (578).
  Глава 32. Вопросы и ответы, II (604).
  Глава 33. Вопросы и ответы, III (625).
  Глава 34. Последние ошибки TEX"а (651).
  Предметный указатель (659).

Аннотация издательства: Сборник работ Д. Кнута, написанных им за время работы над созданием всемирно известных систем TEX и metafont, в который вошли также статьи последних лет по этой тематике. Книга состоит из 34 глав, разделенных условно на три части: TEX и относящиеся к нему темы; metafont и родственные вопросы; TEX и metafont в историческом аспекте. Представлен богатый иллюстративный материал и приводятся листинги программ.
Как и во всех книгах Д. Кнута, весьма серьезные вопросы излагаются просто и увлекательно, что, учитывая междисциплинарную направленность книги, делает ее доступной для специалистов в разных областях науки.
Книга представляет интерес для научных работников всех специальностей, самостоятельно готовящих свои работы к публикации, для специалистов в области информатики и издательских систем, а также для математиков, интересующихся нестандартными приложениями.

Дональд Эрвин Кнут - американский учёный, почётный профессор Стэнфордского университета и нескольких других университетов в разных странах, преподаватель и идеолог программирования, автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для набора и вёрстки книг, посвящённых технической тематике (в первую очередь - физико-математических).

Дональд Кнут родился 10 января 1938 года в Милуоки (штат Висконсин)-Его отец преподавал бухгалтерский учет в университете и занимался также дома, в подвале, печатным делом. Ребенком Кнут с удовольствием играл с калькулятором отца, который мог перемножать десятизначные числа, но у него уходило от десяти до двадцати секунд, чтобы напечатать ответ.

Кнут вспоминает, как он пытался извлечь квадратный корень из десяти, пытался и ошибся. Открыв, что ответ находится между 3,16 и 3,17, он сделал заключение, что число должно иметь истинное значение п, а не 3,14, как говорилось в его учебнике. Вскоре он понял, что его заключение было ошибочным.

Любовь Кнута к математике усилилась на первом году учебы в университете. Он был захвачен графикой алгебраических функций - областью нескончаемых возможностей.

Физика также ему нравилась, и он разрывается между ней и музыкой - он серьезно обучался игре на пианино, сам написал несколько произведений. Кнут признает, что у него комплекс неполноценности. Это объясняет, говорит он, то, что он всегда много работал. В старших классах Милуокской лютеранской высшей школы он беспокоился, что низкие оценки по математике могут помешать его поступлению в колледж, но это была непонятная озабоченность, поскольку он закончил школу с самым высоким коэффици-ентом за все времена - 97,5%.

В 1956 году он поступил в Кейский Технологический институт в Кливленде. На первом году обучения он занялся высшей математикой. Снова из-за страха, что не справится, Кнут в дополнительное время с рвением изучал дифференциальное и интегральное исчисление и аналитическую геометрию.

Во время каникул после первого курса Кнут впервые занялся работой с компьютером. У него было задание на лето - построить графики для статистиков Кейса. В соседней комнате находилась новая машина IBM 650. Кнут так загорелся ею, что посвятил «Искусство программирования» компьютеру IBM 650, установленному в Кэйском технологическом институте, в память о многих приятных вечерах. Некоторые из его преподавателей советовали ему держаться в стороне от компьютеров, утверждая, что это ни к чему хорошему не приведет. Но любопытство взяло верх, он проводил ночи напролет с компьютером.

Кнут с легкостью оставил физику. Его лабораторные работы, казалось, не приносили удовлетворения, он ронял детали на пол и часто оказывался последним. Сварка оказалась катастрофой: при росте 6 футов и 4 дюйма он был слишком высоким для сварочных столов, и ему невозможно было наблюдать за работой, кроме того, очки ему не подходили.

Кнут добился успехов, используя компьютер для оценки игры баскетбольной команды, менеджером которой он являлся. Он выработал сложную формулу для ранжирования игроков, рассчитывая вклад каждого в игру, не только по количеству очков, которые он принес команде. Кнут обычно сидел за компьютером IBM 650 и подводил статистику игры, в то время, когда тренер стоял рядом. Используя программу Д. Кнута, тренер мог определить Истинный вклад каждого в игру и в соответствии с этим использовать игроков. Оказалось также, что данная программа стимулировала игроков работать с большей отдачей. В 1960 году Кэйский институт выиграл чемпионат лиги, а магическая формула Кнута неожиданно была опубликована в «Walter Cronkite"s Sunday» и в «Newsweek».

В 1960 году Кнут получил звание бакалавра по математике, причем студенты даже проголосовали за присуждение ему степени доктора. Летом этого года в Пассадене Кнут занялся работой по системному программированию, результатом которой было создание компилятора для ALGOL. За эту работу он получил 5,5 тысячи долларов. Осенью того же года он поступает в Калифорнийский технологический институт для получения степени доктора философии по математике.

В январе 1962 года издательство «Addison-Wesley» предложило Кнуту написать книгу по компиляторам. Он принял это предложение.

В июне 1963 года в Калифорнийском технологическом институте Кнуту присуждается степень доктора философии по математике и он становится ассистентом профессора. Вскоре он начинает работу над главами своей книги.

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

Цель Кнута в этой монументальной работе состояла в том, чтобы обобщить технику программирования и найти ей соответствующее применение. Его основным вкладом было обобщение материала и анализ методов. Он пытался развить наиболее используемые теории для разных методов и заполнить пробелы в этих теориях, он был первым, кто находил эти пробелы и собрал все эти разбросанные теории. Вначале Кнут думал, что напишет толь" одну книгу о компиляторах. Набросав несколько глав, тем не менее, он почувствовал, что книга должна быть гораздо большей и основополагающей. Получив зеленый свет от издателя, он писал, писал и писал. К июню 1965 года он завершил первый проект из двенадцати глав, который размещался на трех тысячах страниц рукописного текста. В октябре он отослал первую главу издателю. Издательство «Addison-Wesley» предложило, что двенадцать частей будут опубликованы как семь отдельных томов, каждый которых будет содержать один или два раздела. Кнута устраивало такое предложение.

Проведя напряженные дни и ночи над реализацией семитомного проекта, Кнут испытал несколько приступов язвы летом 1967 года. Как вспоминает он, это случилось на середине «алгоритма Евклида», на 333 странице второго тома.

Данные издания, как оказалось, имели наибольший спрос из всех книг, продаваемых «Addison-Wesley». В середине 80-х годов две тысячи экземпляров каждого из трех томов расходились в течение месяца, и эта цифра не менялась с середины 70-х годов. Работа была переведена на китайский, румынский, японский, испанский и русский, планировалось издание на португальском и венгерском. Кнут становится все более знаменитым: в 1979 г. в возрасте 41 года он получает из рук президента Дж. Картера Национальную медаль в области науки за свою работу по алгоритмам.

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

Может показаться неправдоподобным, но Д. Кнут также пишет фантастические вещи. Его новелла «Сюрреалистические числа: как два бывших студента занялись чистой математикой и нашли полное счастье» была опубликована в издательстве «Addison-Wesley» в 1974 году. В книге рассказывается об исследовании новой системы чисел, открытой в Кэмбриджском университете Дж. Конвэем. Кнут узнал о данной системе от самого Конвэя в 1972 году. Один журналист отметил, что впервые значимое открытие в математике описывается сначала в научной фантастике. Кнут написал данную книгу не для того, чтобы проповедовать теорию Конвэя, а чтобы объяснить, как человек может создать такую теорию.

Весной 1977 года Дональд Кнут резко изменил род своих занятий. Просматривая гранки проверенного издания второго тома, он неожиданно почувствовал, что полиграфия нуждается в кардинальном изменении. Он хотел уничтожить эти гранки, поскольку они выглядели ужасно. Пространственное расположение знаков было плохим, и особенно острой проблемой в издании был стандартный шрифт и вид математических уравнений. Кнут хотел понять, почему печатная работа, в которой использовался фоторепродукционный шрифт, была такой непривлекательной. Он решил посвятить несколько месяцев тому, чтобы попытаться совместить математику и компьютерную науку с задачей улучшения внешнего вида книг. Проект длился Девять лет!

Кнут изобрел ТеХ, первую издательскую систему, а также METAFONT, систему, которая использует классическую математику для придания внешнего вида шрифтам. ТеХ был назван одним из наиболее важных изобретений в истории печатания книг. Некоторые сравнивали его по значению с Библией Иоганна Гуттенберга, что смутило Кнута.

ТеХ позволяет наборной машине размещать буквы и знаки на странице со значительной гибкостью и эстетичным качеством.

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

Кнут ввел обе программы в открытое пользование: ни он, ни Стэнфордский университет не заработали на них ни гроша. Он написал программы, как он говорит, из любви к книгам и для достижения необходимой эстетики.

Когда Кнут сверстал второй том «Искусства программирования», используя METAFONT и ТеХ, результат был лучше, но не идеальным. Плохо получались числа. Так он потратил еще пять лет, работая с лучшими дизайнерами по графике, для того, чтобы создать новые системы и наиболее полно использовать их потенциал. Летом 1986 года разработки Кнута по типографии были завершены, и вышел пятитомник «Компьютеры и набор знаков». Первый том посвящен ТеХ; второй содержит полный источник кодов ТеХ; третий и четвертый, соответственно, посвящены METAFONT и полному источнику кодов для него; пятый том содержит 500 с лишним примеров программирования по METAFONT.

В 1986 году на приеме в издательстве «Addison-Wesley», устроенном в его честь, ему задали вопрос: «Будет ли завершен его семитомник, будут ли дописаны четыре недостающих тома?» Он ответил, что их написание заняло бы еще двадцать лет.

Прошло тринадцать лет. В 1999 году профессор Кнут заявил, что к существующим трем томам он намерен добавить еще два тома. Кроме того, он решил заменить виртуальную модель компьютера MIX 1009 (модель, похожую на реальные компьютеры конца 60-х - начала 70-х годов), на языке которого написаны большинство алгоритмов первых трех томов, на новую модель - 64-разрядный процессор MMIX 2009 с RISC-архитектурой. В следующих изданиях «Искусство программирования» примеры будут приводиться на языке ассемблера MMIX.

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

Номер 2009 является средним арифметическим номеров четырнадцати процессоров. В их числе - CRAY I, IBM 701, Alpha 21264, MIPS 4000, StrongArm 110, Sparc 64 и др. Логическая модель MMIX довольно подробно описывает поведение настоящего процессора. Например, для каждой команду указано число тактов, требующихся для выполнения, определено поведение процессора в таких ситуациях, как неверное предсказание ветвления или промах кэша. В модели имеется набор изменяемых параметров, поэтому на самом деле MMIX - это целое семейство совместимых процессоров. Профессор Кнут намерен реализовать метасимулятор для всего семейства, чтобы можно было менять параметры модели и исследовать поведение программ.

Дональд Кнут уже разработал архитектуру процессора, простой симулятор и ассемблер. Первая редакция описания набора команд была опубликована в феврале, а четвертая редакция введения в MMIX вышла в конце июня. Теперь предстоит перенос всего накопленного программного фонда старого MIX на новый RISC-процессор MMIX. Дональд Кнут приглашает к сотрудничеству добровольцев со всего мира, прежде всего студентов.

«Сейчас предельно ясно, что с той скоростью с которой я пишу, я не закончу весь проект до своего девяностолетия.»

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

Поддержка публикации - компания 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 футов материала в длину.

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

Люди писали мне, сообщая об ошибках в первом, втором и третьем томах. У меня были письма с 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-х, из которой я могу взять предложения и фразы, чтобы омолодить книгу.

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

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

Автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики , а также создатель настольных издательских систем T E X и METAFONT , предназначенных для набора и вёрстки книг научно-технической тематики (в первую очередь - физико-математических).

Биография

Родился в семье преподавателя. Его отец преподавал бухгалтерский учёт, а также занимался печатным делом на дому как любитель (этим можно объяснить последующий интерес Дональда к этому делу и такие разработки как T E X). С юных лет в нём наблюдалась склонность к математике, физике и музыке.

Окончил с отличием отделение математики (бакалавр, 1960). Одновременно за значительные достижения в программировании был удостоен степени магистра. Спустя три года получил докторскую степень в . Преподавал там же математику и одновременно консультировал по проблемам разработки программного обеспечения в компании Burroughs Corporation.

В 1968 году перешел в Стэнфордский университет. В 1968-69 годах также работал в Институте оборонных исследований. Приглашенный профессор математики в университете Осло, Норвегия (1972, 1973). В Стэнфорде под его руководством защищено 28 докторских диссертаций.

Большое влияние на юного Дональда Кнута оказали работы Андрея Петровича Ершова , впоследствии его друга.

Это началось ещё когда я был студентом последнего курса. Тогда только появилась книга Андрея «Программирование для БЭСМ », и мы, группа студентов, смогли убедить преподавателя русского языка включить её в курс в качестве одного из двух сборников текстов для изучения научной лексики .

Поскольку Кнут всегда считал монографию «Искусство программирования » основным проектом своей жизни, в 1990(3?) году он вышел в отставку, с намерением полностью сконцентрироваться на написании недостающих частей и приведении в порядок существующих.

Признание

Член редакционных коллегий многих научных журналов.

Действительный член Американской академии искусств и наук, Национальной академии наук, Национальной академии инженерных наук. Член Американской гильдии органистов (с 1965 года), Американского математического общества (1961), Ассоциации компьютерной техники (ACM) (1959), Математической ассоциации Америки (1959), Общества промышленной и прикладной математики (1965), действительный член Британского компьютерного общества (1980), почетный член IEEE (1982). Иностранный член Российской академии наук (29.05.2008) . Почётный доктор многих университетов. Почётный доктор СПбГУ (1992).

Профессор Кнут удостоен многочисленных премий и наград в области программирования и вычислительной математики, среди которых

Гарнитуры операционных систем Другие гарнитуры Программное обеспечение Лицензии Группы и люди

Отрывок, характеризующий Кнут, Дональд Эрвин

На листочке бумаги у него было записано то, что нужно было в Смоленске, и он, ходя по комнате мимо дожидавшегося у двери Алпатыча, стал отдавать приказания.
– Первое, бумаги почтовой, слышишь, восемь дестей, вот по образцу; золотообрезной… образчик, чтобы непременно по нем была; лаку, сургучу – по записке Михаила Иваныча.
Он походил по комнате и заглянул в памятную записку.
– Потом губернатору лично письмо отдать о записи.
Потом были нужны задвижки к дверям новой постройки, непременно такого фасона, которые выдумал сам князь. Потом ящик переплетный надо было заказать для укладки завещания.
Отдача приказаний Алпатычу продолжалась более двух часов. Князь все не отпускал его. Он сел, задумался и, закрыв глаза, задремал. Алпатыч пошевелился.
– Ну, ступай, ступай; ежели что нужно, я пришлю.
Алпатыч вышел. Князь подошел опять к бюро, заглянув в него, потрогал рукою свои бумаги, опять запер и сел к столу писать письмо губернатору.
Уже было поздно, когда он встал, запечатав письмо. Ему хотелось спать, но он знал, что не заснет и что самые дурные мысли приходят ему в постели. Он кликнул Тихона и пошел с ним по комнатам, чтобы сказать ему, где стлать постель на нынешнюю ночь. Он ходил, примеривая каждый уголок.
Везде ему казалось нехорошо, но хуже всего был привычный диван в кабинете. Диван этот был страшен ему, вероятно по тяжелым мыслям, которые он передумал, лежа на нем. Нигде не было хорошо, но все таки лучше всех был уголок в диванной за фортепиано: он никогда еще не спал тут.
Тихон принес с официантом постель и стал уставлять.
– Не так, не так! – закричал князь и сам подвинул на четверть подальше от угла, и потом опять поближе.
«Ну, наконец все переделал, теперь отдохну», – подумал князь и предоставил Тихону раздевать себя.
Досадливо морщась от усилий, которые нужно было делать, чтобы снять кафтан и панталоны, князь разделся, тяжело опустился на кровать и как будто задумался, презрительно глядя на свои желтые, иссохшие ноги. Он не задумался, а он медлил перед предстоявшим ему трудом поднять эти ноги и передвинуться на кровати. «Ох, как тяжело! Ох, хоть бы поскорее, поскорее кончились эти труды, и вы бы отпустили меня! – думал он. Он сделал, поджав губы, в двадцатый раз это усилие и лег. Но едва он лег, как вдруг вся постель равномерно заходила под ним вперед и назад, как будто тяжело дыша и толкаясь. Это бывало с ним почти каждую ночь. Он открыл закрывшиеся было глаза.
– Нет спокоя, проклятые! – проворчал он с гневом на кого то. «Да, да, еще что то важное было, очень что то важное я приберег себе на ночь в постели. Задвижки? Нет, про это сказал. Нет, что то такое, что то в гостиной было. Княжна Марья что то врала. Десаль что то – дурак этот – говорил. В кармане что то – не вспомню».
– Тишка! Об чем за обедом говорили?
– Об князе, Михайле…
– Молчи, молчи. – Князь захлопал рукой по столу. – Да! Знаю, письмо князя Андрея. Княжна Марья читала. Десаль что то про Витебск говорил. Теперь прочту.
Он велел достать письмо из кармана и придвинуть к кровати столик с лимонадом и витушкой – восковой свечкой и, надев очки, стал читать. Тут только в тишине ночи, при слабом свете из под зеленого колпака, он, прочтя письмо, в первый раз на мгновение понял его значение.
«Французы в Витебске, через четыре перехода они могут быть у Смоленска; может, они уже там».
– Тишка! – Тихон вскочил. – Нет, не надо, не надо! – прокричал он.
Он спрятал письмо под подсвечник и закрыл глаза. И ему представился Дунай, светлый полдень, камыши, русский лагерь, и он входит, он, молодой генерал, без одной морщины на лице, бодрый, веселый, румяный, в расписной шатер Потемкина, и жгучее чувство зависти к любимцу, столь же сильное, как и тогда, волнует его. И он вспоминает все те слова, которые сказаны были тогда при первом Свидании с Потемкиным. И ему представляется с желтизною в жирном лице невысокая, толстая женщина – матушка императрица, ее улыбки, слова, когда она в первый раз, обласкав, приняла его, и вспоминается ее же лицо на катафалке и то столкновение с Зубовым, которое было тогда при ее гробе за право подходить к ее руке.
«Ах, скорее, скорее вернуться к тому времени, и чтобы теперешнее все кончилось поскорее, поскорее, чтобы оставили они меня в покое!»

Лысые Горы, именье князя Николая Андреича Болконского, находились в шестидесяти верстах от Смоленска, позади его, и в трех верстах от Московской дороги.
В тот же вечер, как князь отдавал приказания Алпатычу, Десаль, потребовав у княжны Марьи свидания, сообщил ей, что так как князь не совсем здоров и не принимает никаких мер для своей безопасности, а по письму князя Андрея видно, что пребывание в Лысых Горах небезопасно, то он почтительно советует ей самой написать с Алпатычем письмо к начальнику губернии в Смоленск с просьбой уведомить ее о положении дел и о мере опасности, которой подвергаются Лысые Горы. Десаль написал для княжны Марьи письмо к губернатору, которое она подписала, и письмо это было отдано Алпатычу с приказанием подать его губернатору и, в случае опасности, возвратиться как можно скорее.
Получив все приказания, Алпатыч, провожаемый домашними, в белой пуховой шляпе (княжеский подарок), с палкой, так же как князь, вышел садиться в кожаную кибиточку, заложенную тройкой сытых саврасых.
Колокольчик был подвязан, и бубенчики заложены бумажками. Князь никому не позволял в Лысых Горах ездить с колокольчиком. Но Алпатыч любил колокольчики и бубенчики в дальней дороге. Придворные Алпатыча, земский, конторщик, кухарка – черная, белая, две старухи, мальчик казачок, кучера и разные дворовые провожали его.
Дочь укладывала за спину и под него ситцевые пуховые подушки. Свояченица старушка тайком сунула узелок. Один из кучеров подсадил его под руку.
– Ну, ну, бабьи сборы! Бабы, бабы! – пыхтя, проговорил скороговоркой Алпатыч точно так, как говорил князь, и сел в кибиточку. Отдав последние приказания о работах земскому и в этом уж не подражая князю, Алпатыч снял с лысой головы шляпу и перекрестился троекратно.
– Вы, ежели что… вы вернитесь, Яков Алпатыч; ради Христа, нас пожалей, – прокричала ему жена, намекавшая на слухи о войне и неприятеле.
– Бабы, бабы, бабьи сборы, – проговорил Алпатыч про себя и поехал, оглядывая вокруг себя поля, где с пожелтевшей рожью, где с густым, еще зеленым овсом, где еще черные, которые только начинали двоить. Алпатыч ехал, любуясь на редкостный урожай ярового в нынешнем году, приглядываясь к полоскам ржаных пелей, на которых кое где начинали зажинать, и делал свои хозяйственные соображения о посеве и уборке и о том, не забыто ли какое княжеское приказание.
Два раза покормив дорогой, к вечеру 4 го августа Алпатыч приехал в город.
По дороге Алпатыч встречал и обгонял обозы и войска. Подъезжая к Смоленску, он слышал дальние выстрелы, но звуки эти не поразили его. Сильнее всего поразило его то, что, приближаясь к Смоленску, он видел прекрасное поле овса, которое какие то солдаты косили, очевидно, на корм и по которому стояли лагерем; это обстоятельство поразило Алпатыча, но он скоро забыл его, думая о своем деле.
Все интересы жизни Алпатыча уже более тридцати лет были ограничены одной волей князя, и он никогда не выходил из этого круга. Все, что не касалось до исполнения приказаний князя, не только не интересовало его, но не существовало для Алпатыча.
Алпатыч, приехав вечером 4 го августа в Смоленск, остановился за Днепром, в Гаченском предместье, на постоялом дворе, у дворника Ферапонтова, у которого он уже тридцать лет имел привычку останавливаться. Ферапонтов двенадцать лет тому назад, с легкой руки Алпатыча, купив рощу у князя, начал торговать и теперь имел дом, постоялый двор и мучную лавку в губернии. Ферапонтов был толстый, черный, красный сорокалетний мужик, с толстыми губами, с толстой шишкой носом, такими же шишками над черными, нахмуренными бровями и толстым брюхом.
Ферапонтов, в жилете, в ситцевой рубахе, стоял у лавки, выходившей на улицу. Увидав Алпатыча, он подошел к нему.
– Добро пожаловать, Яков Алпатыч. Народ из города, а ты в город, – сказал хозяин.
– Что ж так, из города? – сказал Алпатыч.
– И я говорю, – народ глуп. Всё француза боятся.
– Бабьи толки, бабьи толки! – проговорил Алпатыч.
– Так то и я сужу, Яков Алпатыч. Я говорю, приказ есть, что не пустят его, – значит, верно. Да и мужики по три рубля с подводы просят – креста на них нет!
Яков Алпатыч невнимательно слушал. Он потребовал самовар и сена лошадям и, напившись чаю, лег спать.
Всю ночь мимо постоялого двора двигались на улице войска. На другой день Алпатыч надел камзол, который он надевал только в городе, и пошел по делам. Утро было солнечное, и с восьми часов было уже жарко. Дорогой день для уборки хлеба, как думал Алпатыч. За городом с раннего утра слышались выстрелы.
С восьми часов к ружейным выстрелам присоединилась пушечная пальба. На улицах было много народу, куда то спешащего, много солдат, но так же, как и всегда, ездили извозчики, купцы стояли у лавок и в церквах шла служба. Алпатыч прошел в лавки, в присутственные места, на почту и к губернатору. В присутственных местах, в лавках, на почте все говорили о войске, о неприятеле, который уже напал на город; все спрашивали друг друга, что делать, и все старались успокоивать друг друга.
У дома губернатора Алпатыч нашел большое количество народа, казаков и дорожный экипаж, принадлежавший губернатору. На крыльце Яков Алпатыч встретил двух господ дворян, из которых одного он знал. Знакомый ему дворянин, бывший исправник, говорил с жаром.
– Ведь это не шутки шутить, – говорил он. – Хорошо, кто один. Одна голова и бедна – так одна, а то ведь тринадцать человек семьи, да все имущество… Довели, что пропадать всем, что ж это за начальство после этого?.. Эх, перевешал бы разбойников…
– Да ну, будет, – говорил другой.
– А мне что за дело, пускай слышит! Что ж, мы не собаки, – сказал бывший исправник и, оглянувшись, увидал Алпатыча.
– А, Яков Алпатыч, ты зачем?
– По приказанию его сиятельства, к господину губернатору, – отвечал Алпатыч, гордо поднимая голову и закладывая руку за пазуху, что он делал всегда, когда упоминал о князе… – Изволили приказать осведомиться о положении дел, – сказал он.
– Да вот и узнавай, – прокричал помещик, – довели, что ни подвод, ничего!.. Вот она, слышишь? – сказал он, указывая на ту сторону, откуда слышались выстрелы.
– Довели, что погибать всем… разбойники! – опять проговорил он и сошел с крыльца.
Алпатыч покачал головой и пошел на лестницу. В приемной были купцы, женщины, чиновники, молча переглядывавшиеся между собой. Дверь кабинета отворилась, все встали с мест и подвинулись вперед. Из двери выбежал чиновник, поговорил что то с купцом, кликнул за собой толстого чиновника с крестом на шее и скрылся опять в дверь, видимо, избегая всех обращенных к нему взглядов и вопросов. Алпатыч продвинулся вперед и при следующем выходе чиновника, заложив руку зазастегнутый сюртук, обратился к чиновнику, подавая ему два письма.

Никто не может «владеть» математической формулой. Математика принадлежит Богу.

Дональд Кнут
о недопустимости патентов на программное обеспечение

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

Так что же - пользоваться компьютерными учебниками или программами, написанными пять лет назад, бесполезно: всё равно они безнадёжно устарели? Обычно это так, но бывают исключения. Например, один из самых популярных учебников по компьютерным наукам начал печататься аж в 1968 году - это многотомник американского учёного Дональда Кнута «Искусство программирования для ЭВМ» («The Art of Computer Programming»). А бо льшая часть физико-математической и технической литературы по сей день верстается на компьютерах с помощью системы (обычно пишут: ТеХ), которая практически не изменялась с 1989 года. Кстати, ТеХ создал тот же Дональд Кнут. Что же это за уникальный человек?

Дональд Эрвин Кнут родился в 1938 году в американском городе Милуоки. В детстве он был очарован печатными изданиями и уже в пятилетнем возрасте отметил все «засечки» у букв в своей азбуке. В юности Дональд увлёкся игрой на саксофоне и трубе и думал, что станет профессиональным музыкантом. Однако поступил Кнут в Западный университет Кейза, где активно занялся физикой. На первых курсах он считал чистую математику весьма скучной, но после встречи с Полом Гюнтером, математиком с незаурядным чувством юмора, Кнут заинтересовался ею.

В 1956 году Дональд впервые познакомился с компьютером. Он внимательно анализировал примеры программ из руководства для пользователя и многие из них существенно улучшил. Через два года Кнут написал программу, подсчитывающую рейтинг игроков университетской баскетбольной команды по статистике бросков, передач и т. п.; программа имела неожиданный успех, и о ней написали в газетах.

По окончании университета Кейза в 1960 году Кнут поступил в аспирантуру Калифорнийского технологического университета, где продолжил свои изыскания в области компьютерных наук (Computer Science). В 1963 году он защитил диссертацию. Ещё будучи аспирантом, в 1962 году Кнут задумал свой многотомник, «библию для программистов», где хотел изложить фундаментальные алгоритмы, применяющиеся при написании программ. Выходившие с 1968 года тома пользовались большим успехом, и через несколько лет их решили переиздать. Но случилась весьма необычная история.

Все уже вышедшие тома «Искусства программирования» были напечатаны в типографии на монотипе 1 . Но в 1974–75 годах монотипы вытеснила намного более дешёвая технология фотонаборной печати 2 , при которой сложные формулы получались уродливо. Кнут был крайне разочарован тем, как будет выглядеть его книга после фотонабора. С большим трудом он нашёл монотип и добился перевёрстки на нём. Однако после полного исчезновения монотипов было непонятно, как добиваться красиво изданных книг.

13 мая 1977 года Кнут составил план создания компьютерной системы вёрстки ТеХ. Он рассчитывал осуществить этот план месяцев за восемь, но сильно недооценил объём работ, затянувшихся более чем на 10 лет. В итоге помимо самой системы ТеХ были созданы: язык программирования METAFONT для рисования шрифтов; специальный язык программирования, на котором была написана система ТеХ; а также концепция «грамотного программирования» (англ. literate programming ). Эта концепция позволяет писать программу на понятном человеку, «литературном» языке; позже «слова» из этой программы обрабатываются специальной программой, выдающей код на языке, понятном компьютеру.

Я не могу прийти в ресторан и просто заказать еду, потому что начинаю изучать шрифты в меню.

Дональд Кнут

В 1982 году системой ТеХ уже можно было пользоваться для набора текстов, и новое издание «Искусства программирования» было подготовлено в ТеХ"е. Особенностью ТеХ"а стала отточенная вёрстка сложных формул, отвечающая классическим канонам. Есть даже высказывание: «ТеХ - стандарт для набора формул, к которому стремятся приблизиться все остальные издательские системы». Кроме того, Кнут выложил эту систему в свободный доступ, она бесплатна. В результате ТеХ как бы объединил всех математиков: не обязательно переписываться, вставляя в текст формулы «от руки», - каждый может легко освоить ТеХ и набирать тексты с формулами любой сложности. ТеХ стал стандартным форматом научных публикаций, и сейчас большая часть физико-математической литературы верстается в программах, основанных на ТеХ"е. Для набора формул в Википедии и на некоторых других сайтах также применяется ТеХ.

В 1989 году была выпущена версия ТеХ 3.0, оказавшаяся исключительно стабильной. С тех пор исправляются только небольшие ошибки, а очередные версии ТеХ"a нумеруются десятичными знаками числа π. На 2014 год актуальна версия 3.1415926. Кнут завещал, когда он покинет этот мир, присвоить текущей на тот момент версии номер π, а все ошибки, которые останутся, считать особенностями системы.

В этом коде могут быть ошибки. Я лишь доказал, что он работает, но не проверял на компьютере.

Дональд Кнут

Первым не латинским шрифтом, появившимся в ТеХ"е, была кириллица. Кстати, Кнут знает русский язык - он выучил его, чтобы читать работы русских математиков в подлиннике. Одним из друзей Кнута был советский программист Андрей Петрович Ершов, чьи книги автор ТеХ"а очень ценит.

Кнут всегда чрезвычайно беспокоится о точности и правильности того, что он пишет. Чтобы избавиться от ошибок в ТеХ"е и в книге «Искусство программирования», он придумал оригинальную систему: за каждую найденную ошибку выплачивалось небольшое денежное вознаграждение. Например, в первый год после выхода «Искусства программирования» каждый нашедший ошибку получал от автора чек на $2,56. Получение подобного чека - дело очень редкое и почётное, поскольку даже первоначальные версии были практически безошибочны. Большинство обладателей этих чеков не отнесли их в банк, а оставили на память. Сейчас Кнут вместо чеков высылает шуточные сертификаты.

Кнут работает над «Искусством программирования» по сей день. В 1990 году он вышел на пенсию, чтобы целиком посвятить себя написанию этого труда. В 2011 году была выпущена первая часть 4 тома, а на сайте автора можно скачать несколько фрагментов второй части.

В свободное время Кнут занимается музыкой. В 1977 году он опубликовал шутливую статью «Оценка сложности песен», в которой постарался дать математическое описание популярных песен.