Введение

Американский учёный-компьютерщик и математик (род. 1938)

Donald Ervin Knuth (/k//ə/'/n//uː//θ/) – автор многотомного труда «Искусство компьютерного программирования». Он внес значительный вклад в развитие строгого анализа вычислительной сложности алгоритмов и систематизацию формальных математических методов в этой области. В процессе работы он также популяризировал асимптотическую нотацию. Помимо фундаментальных работ в различных областях теоретической информатики, Кнут является создателем компьютерной системы верстки TeX, связанного с ней языка описания шрифтов METAFONT и системы растеризации, а также семейства шрифтов Computer Modern. Как писатель и учёный, Кнут разработал системы компьютерного программирования WEB и CWEB, предназначенные для стимулирования и упрощения принципов литературного программирования, и спроектировал архитектуры наборов команд MIX/MMIX. Он категорически против патентования программного обеспечения и выразил свою позицию в Патентном ведомстве США и Европейской патентной организации.

Ранние годы

Дональд Кнут родился в Милуоки, штат Висконсин, в семье Эрвина Генри Кнута и Луизы Мари Бонинг. Он описывает свои корни как "лютеранское немецкое происхождение из Среднего Запада". Его отец владел небольшим типографским бизнесом и преподавал бухгалтерский учёт. Будучи учеником Лютеранской средней школы Милуоки, Кнут находил оригинальные способы решения задач. Например, в восьмом классе он участвовал в конкурсе, где нужно было найти, сколько слов можно составить, переставляя буквы в названии "Ziegler's Giant Bar"; судьи насчитали 2500 таких слов. Воспользовавшись временем, освободившимся от школы благодаря симуляции боли в животе, Кнут использовал толковый словарь и проверял, можно ли каждое слово в словаре составить из букв этой фразы. Применив этот алгоритм, он обнаружил более 4500 слов и выиграл конкурс. В качестве приза школа получила новый телевизор и достаточно шоколадных батончиков для всех его одноклассников.

Образование

Кнут получил стипендию по физике в Институт технологий Кейса (ныне часть Университета Кейс-Уэстерн-Резерв) в Кливленде, штат Огайо, и поступил туда в 1956 году. Он также вступил в братство Theta Chi, главу Beta Nu. Во время учебы на физическом факультете Кейса Кнут познакомился с IBM 650, одним из первых коммерческих компьютеров. Изучив руководство по эксплуатации компьютера, Кнут решил переписать код ассемблера и компилятора для машины, используемой в его учебном заведении, поскольку считал, что сможет сделать это лучше. В 1958 году Кнут разработал программу, призванную помочь баскетбольной команде его университета побеждать в матчах. Он присваивал игрокам "коэффициенты", чтобы оценить вероятность набора очков, что было новым подходом, о котором впоследствии сообщили Newsweek и CBS Evening News. После этого он перешел с физики на математику и в 1960 году получил две степени в Кейсе.

Ранние работы

В 1963 году, после получения степени доктора философии, Кнут присоединился к факультету Калтеха в качестве ассистент-профессора. Незадолго до публикации первого тома "Искусства программирования", Кнут покинул Калтех, чтобы принять предложение Института оборонного анализа, Отдела исследований в области связи, который в то время располагался на территории кампуса Принстона и занимался математическими исследованиями в области криптографии в поддержку Агентства национальной безопасности. В 1967 году Кнут посетил конференцию Общества промышленной и прикладной математики, где у него спросили о роде его деятельности. В то время компьютерная наука была разделена на численный анализ, искусственный интеллект и языки программирования. Основываясь на своих исследованиях и книге "Искусство программирования", Кнут решил, что в следующий раз, когда его об этом спросят, он ответит: "Анализ алгоритмов". В 1969 году Кнут покинул свою должность в Принстоне, чтобы присоединиться к факультету Стэнфордского университета, где в 1977 году стал профессором информатики имени Флетчера Джонса. В 1990 году он стал профессором по "Искусству программирования", а с 1993 года имеет статус профессора-эмеритуса.

Сочинения

Кнут — писатель и учёный-компьютерщик.

Работы о его религиозных убеждениях

Кроме своих работ по компьютерным наукам, лютеранин Кнут также является автором книги «3:16 Bible Texts Illuminated», в которой он исследует Библию, используя метод систематической выборки, а именно – анализ 3 главы, 16 стиха каждой книги. Каждый стих сопровождается художественным оформлением в каллиграфической технике, выполненным группой каллиграфов под руководством Германна Запфа. Кнута пригласили прочитать цикл лекций в MIT о взглядах на религию и компьютерные науки, лежащих в основе его проекта 3:16, что привело к публикации другой книги – «Things a Computer Scientist Rarely Talks About», где он представил лекции «Бог и компьютерные науки».

Мнение по патентам на программное обеспечение

Кнут решительно выступает против выдачи патентов на программное обеспечение для тривиальных решений, которые должны быть очевидны, но придерживается более взвешенной точки зрения в отношении нетривиальных решений, таких как метод внутренней точки в линейном программировании. Он выразил свое несогласие напрямую как в Патентному ведомству США, так и в Европейской патентной организации.

Цифровая набор

В 1970-х годах издатели TAOCP отказались от монотипа в пользу фотонабора. Кнут был настолько разочарован тем, что новая система не могла достичь качества предыдущих томов, набранных с использованием старой системы, что он посвятил время разработке цифрового набора и создал TeX и Metafont.

Личная жизнь

Дональд Кнут женился на Нэнси Джилл Картер 24 июня 1961 года, когда он был аспирантом Калифорнийского технологического института. У них двое детей: Джон Мартин Кнут и Дженнифер Сиерра Кнут. Кнут несколько раз в год читает неформальные лекции в Стэнфордском университете, которые он называет «Компьютерные размышления». Он был приглашенным профессором кафедры компьютерных наук Оксфордского университета в Великобритании до 2017 года и почетным членом Magdalen College. Кнут – органист и композитор. Он и его отец служили органистами в лютеранских приходах. У Кнута и его жены дома есть 16-регистровый орган. В 2016 году он завершил произведение для органа «Фантазия Апокалиптика», которое он называет «музыкальной интерпретацией греческого текста Откровения Иоанна Богослова». Премьера состоялась в Швеции 10 января 2018 года.

Китайское название

Китайское имя Кнута — Гао Дэна.

Проблемы со здоровьем

В 2006 году у Кнута диагностировали рак предстательной железы. В декабре того же года ему сделали операцию, и он сообщил в своей видеоавтобиографии: "немного лучевой терапии для подстраховки, но прогноз выглядит весьма благоприятным".

Юмор

Кнут платил вознаграждение в размере 2,56 доллара за обнаружение опечаток или ошибок в своих книгах, потому что "256 пенсов – это один шестнадцатеричный доллар", а за "ценные предложения" – 0,32 доллара. Согласно статье в Technology Review Массачусетского технологического института, эти награды от Кнута – "одни из самых желанных трофеев в мире компьютерных технологий". Кнуту пришлось прекратить отправлять настоящие чеки в 2008 году из-за банковского мошенничества, и теперь он выдает каждому, обнаружившему ошибку, "сертификат депозита" из публично зарегистрированного баланса в его вымышленном "Банке Сан-Серрифе". Однажды он предупредил корреспондента: "Остерегайтесь ошибок в приведенном выше коде; я доказал его корректность, но не проверял его работу". Чтобы продемонстрировать концепцию рекурсии, Кнут намеренно сделал перекрестные ссылки на "Круговое определение" и "Определение, круговое" в указателе к "Искусству программирования", тому 1. В предисловии к "Конкретной математике" есть следующий абзац: "Когда DEK впервые читал курс "Конкретная математика" в Стэнфорде, он объяснил несколько странное название, сказав, что это была его попытка преподавать сложный, а не легкий курс математики. Он объявил, что, вопреки ожиданиям коллег, он не будет преподавать теорию агрегатов, теорему вложения Стоуна и даже компактификацию Стоуна — Чеха. (Несколько студентов с факультета гражданского строительства встали и тихо покинули аудиторию.) На конференции TUG 2010 года Кнут представил сатирическую XML-реализацию, пришедшую на смену TeX, под названием "iTeX" (сопровождалось звоном колокола), которая должна поддерживать такие функции, как произвольно масштабируемые иррациональные единицы, 3D-печать, ввод данных с сейсмографов и кардиомониторов, анимацию и стереозвук."