Личность род. 1938

Дональд Эрвин Кнут

Американский учёный в области информатики и математик, эмерит-профессор Стэнфордского университета, автор фундаментального труда «Искусство программирования», создатель систем TeX, METAFONT и концепции грамотного программирования

Краткая справка

Дональд Эрвин Кнут (род. 1938) — американский математик и классик теоретической информатики, прозванный «отцом анализа алгоритмов». Его многотомная монография «Искусство программирования», задуманная в 1962 году, превратила программирование из набора ремесленных приёмов в строгую математическую дисциплину. Столкнувшись с падением качества типографского набора своих книг, Кнут в конце 1970-х годов создал издательские системы TeX и METAFONT, семейство шрифтов Computer Modern и методологию грамотного программирования.

Портрет Дональда Эрвина Кнута в Музее компьютерной истории
Дональд Эрвин Кнут на открытии выставки Revolution в Музее компьютерной истории. Фото Алекса Хэнди Иллюстрация: Alex Handy, CC BY-SA 2.0

Происхождение, среда и становление

Дональд Эрвин Кнут родился 10 января 1938 года в Милуоки (штат Висконсин) в семье немецких лютеран Среднего Запада: Эрвина Генри Кнута и Луизы Мари Бонинг. Его отец преподавал бухгалтерский учёт, служил церковным органистом и держал дома небольшую печатню, привив сыну интерес к полиграфическому искусству и музыке. Ещё в восьмом классе Дональд выиграл национальный конкурс по составлению слов из букв названия батончика Ziegler’s Giant Bar, найдя со словарём свыше 4500 комбинаций против 2500 у жюри (в награду школа получила телевизор и партию сладостей), а в 1957 году опубликовал в журнале Mad сатирическую заметку «Система мер и весов Потржеби».

В 1956 году Кнут поступил по стипендии по физике в Кейсовский технологический институт в Кливленде, где встретился с компьютером IBM 650, переписал для него ассемблер и компилятор, а в 1958 году разработал программу количественной оценки баскетболистов, попавшую в репортажи Newsweek и CBS. Перейдя на математику и став одним из редакторов университетского технического журнала, в 1960 году он окончил институт сразу со степенями бакалавра и магистра и взялся за написание компилятора ALGOL для машины Burroughs B205 за 5500 долларов. Сильное влияние на молодого специалиста оказала книга советского программиста Андрея Ершова «Программирование для БЭСМ», по которой Кнут с сокурсниками изучал научную русскую лексику, а сам Ершов стал впоследствии его другом. Отклонив контракт на сто тысяч долларов в Green Tree и аспирантские стипендии, запрещавшие совместительство, Кнут в 1963 году защитил в Калтехе диссертацию по конечным полуполям и проективным плоскостям под руководством Маршалла Холла и до 1968 года консультировал Burroughs, предложив макромеханизм DEFINE и язык моделирования SOL.

Ключевые свершения, труды и историческая роль

В 1962 году издательство Addison-Wesley заказало Кнуту одну книгу о разработке компиляторов. Изучив литературу новой отрасли, он нашёл стандарты публикаций крайне низкими и решил «выправить историю, которая была очень плохо рассказана». Так замысел перерос в семитомное «Искусство программирования» (TAOCP): первый том вышел в 1968 году, второй — в 1969-м, а третий был подготовлен во время годичной стажировки в Университете Осло рядом с создателями языка Simula (1972–1973) и издан в 1973 году. Введя в 1967 году название «анализ алгоритмов» (позднее он предлагал и термин «алгоритмика»), Кнут систематизировал строгую математическую оценку сложности вычислений на модельных машинах MIX и MMIX и популяризовал асимптотическую нотацию.

В 1969 году после работы по криптографии в Институте оборонных исследований в Принстоне он перешёл в Стэнфордский университет, где воспитал 28 докторов наук и в 1970 году создал учебный курс дискретной математики, лёгший в основу учебника «Конкретная математика» (1988, совместно с Рональдом Грэмом и Ореном Паташником), а также внёс вклад в исследование задачи об устойчивых паросочетаниях и написал математическую новеллу «Сюрреальные числа» о конструкции Джона Конвея. Когда в 1970-е годы издатели заменили металлический набор Monotype фотонабором, ухудшив вёрстку формул в TAOCP, Кнут отложил четвёртый том и создал систему компьютерного набора TeX, язык описания шрифтов METAFONT и гарнитуру Computer Modern. Попутно он выдвинул методологию «грамотного программирования» (системы WEB и CWEB), заявив: «Вместо того чтобы представлять своей главной задачей объяснение компьютеру, что делать, сосредоточимся на том, чтобы объяснять людям, чего мы хотим от компьютера».

Переломные решения, конфликты и драма эпохи

Интеллектуальная независимость не раз приводила Кнута к спорам с коллегами и индустрией. Написав в 1962 году компилятор FORTRAN для Univac, он иронически замечал, что тогда «продал душу дьяволу», а внедрение макроподстановок DEFINE в Burroughs ALGOL отстаивал в полемике против Эдсгера Дейкстры, поначалу считавшего подобную возможность неприемлемой.

Решающий поворот произошёл в 1993 году: получив в Стэнфорде уникальное звание профессора «Искусства программирования», 55-летний учёный вышел на досрочную пенсию от регулярного преподавания и прекратил пользоваться электронной почтой, чтобы целиком посвятить остаток жизни завершению томов TAOCP (части 4A и 4B увидели свет в 2011 и 2022 годах). В общественно-правовой сфере Кнут стал последовательным критиком патентования программного обеспечения, направляя официальные возражения в Патентное ведомство США и Европейскую патентную организацию против выдачи монопольных патентов на очевидные программные решения. Его трезвую оценку границ формальной верификации выразила знаменитая фраза: «Остерегайтесь ошибок в приведённом выше коде: я только доказал его корректность, но не запускал его».

Наследие, влияние и оценки в историографии

Дональд Кнут преобразил одновременно теоретическую информатику и мировую научную полиграфию: на созданной им системе TeX (и надстройке LaTeX Лесли Лэмпорта) сегодня держится издание математических, физических и компьютерных журналов. Символом его перфекционизма стали чеки на 2,56 доллара («один шестнадцатеричный доллар») за каждую ошибку, найденную читателями в его книгах (с 2008 года из-за банковских мошенничеств — сертификаты вымышленного «Банка Сан-Серриффа»).

Помимо информатики, Кнут — верующий лютеранин и органист, имеющий дома шестнадцатирегистровый орган; он опубликовал книгу «3:16» о библейских стихах с каллиграфией Германа Цапфа, цикл лекций о религии и компьютерных науках в MIT и органную пьесу Fantasia Apocalyptica (премьера в 2018 году), а в Китае известен под именем Гао Дэна (高德纳), данным ему Фрэнсис Яо в 1977 году. Лауреат первой премии Хоппер (1971), Премии Тьюринга (1974), Национальной научной медали США (1979), медали фон Неймана (1995), премии Киото (1996), медали Фарадея (2011), иностранный член Лондонского королевского общества (2003) и РАН (2008), Кнут вошёл в историю как основатель анализа алгоритмов и эталон научной добросовестности.

Хронология ключевых этапов

Дата / этап Событие Историческое пояснение
1956–1960 Учёба в Кейсовском технологическом институте Поступил на физический факультет, освоил компьютер IBM 650, переписал для него ассемблер и компилятор и окончил вуз в 1960 году сразу со степенями бакалавра и магистра математики.
1960–1968 Калтех, консультации в Burroughs и замысел TAOCP Написал компилятор ALGOL для Burroughs B205, в 1963 году защитил PhD в Калтехе у Маршалла Холла и в 1962–1968 годах развернул курс о компиляторах в первый том «Искусства программирования».
1969 Переход в Стэнфордский университет После работы по криптографии в Институте оборонных исследований в Принстоне стал профессором информатики Стэнфордского университета.
1974 Премия Тьюринга Удостоен высшей награды ACM и выступил с программной лекцией «Программирование как искусство» (Computer Programming as an Art).
1977–1986 Создание систем TeX, METAFONT и WEB Взяв паузу в написании книг из-за недовольства фотонабором, изобрёл язык цифровой вёрстки TeX, систему описания шрифтов METAFONT, гарнитуру Computer Modern и методику грамотного программирования.
1988–1993 «Конкретная математика» и выход в отставку ради книг Опубликовал с Р. Грэмом и О. Паташником учебник «Конкретная математика» (1988) и в 1993 году вышел на почётную пенсию в Стэнфорде для завершения «Искусства программирования».
2011–2022 Выход томов 4A и 4B «Искусства программирования» Опубликовал очередные части четвёртого тома, посвящённого комбинаторным алгоритмам, продолжая работу над семитомным проектом жизни.

Жизнь и творчество на фоне истории

Сопоставление ключевых вех биографии (Дональд Эрвин Кнут) с мировыми и отечественными событиями, сражениями и технологическими переломами эпохи.

Личная веха Исторический фон эпохи
1938 г.рождение
Личная веха Рождение: Дональд Эрвин Кнут
август–декабрь 19435 лет
1953–1959 гг. (переворот — июнь 1954 г.)15 лет
1956–196018 лет
Веха жизни Учёба в Кейсовском технологическом институте — Поступил на физический факультет, освоил компьютер IBM 650, переписал для него ассемблер и компилятор и окончил вуз в 1960 году сразу со степенями бакалавра и магистра математики.
29 октября 1956 — март 195718 лет
Событие эпохи Суэцкий кризис
1960–196822 года
Веха жизни Калтех, консультации в Burroughs и замысел TAOCP — Написал компилятор ALGOL для Burroughs B205, в 1963 году защитил PhD в Калтехе у Маршалла Холла и в 1962–1968 годах развернул курс о компиляторах в первый том «Искусства программирования».
196931 год
Веха жизни Переход в Стэнфордский университет — После работы по криптографии в Институте оборонных исследований в Принстоне стал профессором информатики Стэнфордского университета.
197436 лет
Веха жизни Премия Тьюринга — Удостоен высшей награды ACM и выступил с программной лекцией «Программирование как искусство» (Computer Programming as an Art).
1977–198639 лет
Веха жизни Создание систем TeX, METAFONT и WEB — Взяв паузу в написании книг из-за недовольства фотонабором, изобрёл язык цифровой вёрстки TeX, систему описания шрифтов METAFONT, гарнитуру Computer Modern и методику грамотного программирования.
1988–199350 лет
Веха жизни «Конкретная математика» и выход в отставку ради книг — Опубликовал с Р. Грэмом и О. Паташником учебник «Конкретная математика» (1988) и в 1993 году вышел на почётную пенсию в Стэнфорде для завершения «Искусства программирования».
2011–202273 года
Веха жизни Выход томов 4A и 4B «Искусства программирования» — Опубликовал очередные части четвёртого тома, посвящённого комбинаторным алгоритмам, продолжая работу над семитомным проектом жизни.

Цепочка влияния: причины и последствия

Исторический «эффект домино» — какие предпосылки вызвали это событие или явление и к каким переменам оно привело.

К чему это привело дальше (последствия)

Личностьрод. 1947Формирующее влияние

Рональд Ривест

Во время учёбы в Стэнфорде Ривест работал под руководством Роберта Флойда и тесно сотрудничал с Дональдом Кнутом в области анализа алгоритмов.

Государства и ключевые связи в графе

Связанные личности, технологии, места и понятия

Личность Рональд Ривест род. 1947 — Формирующее влияние
Историческое место Киото (Хэйан-кё) с 794 г. — Исторический локус

Известные современники

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

1906–2002

Билли Уайлдер

режиссёр и сценарист («В джазе только девушки», «Сансет-бульвар»)

1911–2013

Во Нгуен Зяп

вьетнамский генерал, победитель при Дьенбьенфу

1915–1998

Фрэнк Синатра

американский певец и киноактёр («оскаровский» лауреат)

1913–2001

Малкольм Маклин

предприниматель, изобретатель стандартного морского контейнера 1956 г.

1907–2002

Астрид Линдгрен

шведская писательница, автор «Малыша и Карлсона» и «Пеппи»

Частые вопросы и ответы

Почему Дональд Кнут прервал написание «Искусства программирования» ради создания системы TeX?
В середине 1970-х годов издательство перевело печать его книг с металлического набора Monotype на ранний фотонабор, из-за чего качество формул и шрифтов резко ухудшилось. Чтобы вернуть книгам полиграфическое совершенство, Кнут в 1977 году взялся создать собственные программы цифровой вёрстки TeX и проектирования шрифтов METAFONT.
Что Дональд Кнут называет «грамотным программированием» (literate programming)?
Это предложенная Кнутом при разработке TeX и воплощённая в системах WEB и CWEB методология, при которой программа пишется как связный литературный текст для человека, а документация и исполняемый исходный код генерируются из единого первоисточника.
Какое влияние на становление Кнута оказала советская школа программирования?
Будучи студентом последнего курса, Кнут с товарищами включил книгу Андрея Ершова «Программирование для БЭСМ» в университетский курс русского языка для изучения научной лексики; впоследствии учёных связывала многолетняя личная дружба.
Почему Кнут выступает против патентования программного обеспечения?
Кнут убеждён, что тривиальные и очевидные программные решения не должны монополизироваться патентами, поскольку это тормозит творчество разработчиков и мешает свободному обмену знаниями в науке.

Научная литература и источники

  1. Donald Knuth's Home Page — Stanford University Computer Science Department [www-cs-faculty.stanford.edu]
  2. ACM A.M. Turing Award — Donald Ervin Knuth [amturing.acm.org]
  3. O'Connor J. J., Robertson E. F. Donald Ervin Knuth // MacTutor History of Mathematics Archive, University of St Andrews [mathshistory.st-andrews.ac.uk]
  4. Frana Ph. L., Computer History Museum — Oral History Interview with Donald Knuth (2007) [archive.computerhistory.org]
  5. INFORMS Biographical Profiles — Donald Ervin Knuth [www.informs.org]