Наука — это то, что мы понимаем достаточно хорошо, чтобы объяснить это компьютеру; искусство — это всё остальное.
Donald Ervin Knuth — американский учёный в области компьютерных наук, математик и профессор-эмерит Стэнфордского университета. Он — лауреат премии ACM Turing Award 1974 года, неофициально считающейся Нобелевской премией в области информатики. Knuth называют «отцом анализа алгоритмов».
Он — автор многотомного труда «Искусство программирования на ЭВМ». Он внёс вклад в развитие строгого анализа вычислительной сложности алгоритмов и систематизировал формальные математические методы для этого. При этом он также популяризировал асимптотическую нотацию. Помимо фундаментальных вкладов в несколько областей теоретической информатики, Knuth — создатель системы компьютерного набора TeX, связанного с ней языка определения шрифтов METAFONT и системы визуализации, а также семейства гарнитур Computer Modern.
Как писатель и учёный, Knuth создал системы программирования WEB и CWEB, предназначенные для поощрения и облегчения грамотного программирования, а также спроектировал архитектуры наборов команд MIX/MMIX. Knuth решительно противостоит выдаче патентов на программное обеспечение, высказав своё мнение Ведомству по патентам и торговым маркам Соединённых Штатов и Европейской патентной организации.
Биография
Ранняя жизнь
Knuth родился в Milwaukee, Wisconsin, в семье американцев немецкого происхождения Ervin Henry Knuth и Louise Marie Bohning. Его отец владел небольшой типографией и преподавал бухгалтерию. Donald, ученик школы Milwaukee Lutheran High School, придумывал остроумные способы решения задач. Например, в восьмом классе он участвовал в конкурсе на поиск количества слов, которые можно составить, переставляя буквы в фразе «Ziegler's Giant Bar»; жюри выявило 2500 таких слов. Использовав время, полученное благодаря притворной боли в животе, и решая задачу в обратном направлении, Knuth с помощью полного словаря проверил, можно ли составить каждую словарную статью из букв этой фразы. Используя этот алгоритм, он выявил более 4500 слов и выиграл конкурс. Школа получила в награду новый телевизор и столько конфет, чтобы все его одноклассники могли их съесть.
Образование
Knuth получил стипендию по физике в Технологический институт Case, ныне входящий в состав Case Western Reserve University в Cleveland, Ohio, и поступил туда в 1956 году. Он также присоединился к Beta Nu Chapter братства Theta Chi. Во время учёбы физике в Case, Knuth познакомился с IBM 650, ранним коммерческим компьютером. После прочтения руководства компьютера Knuth решил переписать код ассемблера и компилятора для машины, используемой в его школе, так как считал, что сможет это сделать лучше.
В 1958 году Knuth создал программу, которая помогла баскетбольной команде его школы выигрывать игры. Он присваивал «значения» игрокам, чтобы оценить вероятность забивания ими очков — новый подход, о котором позже сообщали Newsweek и CBS Evening News.
Knuth был одним из основных редакторов Engineering and Science Review Технологического института Case, который в 1959 году выиграл национальный приз как лучший технический журнал. Затем он переключился с физики на математику и получил две степени от Case в 1960 году: степень бакалавра наук и одновременно степень магистра наук по особому решению факультета, который считал его работу исключительно выдающейся.
В 1963 году, под руководством математика Marshall Hall, он получил докторскую степень по математике в Калифорнийском технологическом институте.
Ранняя работа
После получения докторской степени, Knuth присоединился к факультету Caltech в качестве ассистента профессора.
Он принял заказ на написание книги о компиляторах языков компьютерного программирования. Работая над этим проектом, Knuth решил, что не может адекватно рассмотреть эту тему без предварительной разработки фундаментальной теории компьютерного программирования, которая стала «Искусством программирования на ЭВМ». Первоначально он планировал опубликовать это как одну книгу. По мере разработки плана книги, Knuth пришёл к выводу, что ему требуется шесть томов, а затем семь, чтобы полностью охватить тему. Он опубликовал первый том в 1968 году.
Непосредственно перед публикацией первого тома «Искусства программирования на ЭВМ» Knuth уехал из Caltech, чтобы работать в Communications Research Division Института анализа обороны, который находился на территории кампуса Принстонского университета и занимался математическими исследованиями в криптографии в поддержку Агентства национальной безопасности.
В 1967 году Knuth присутствовал на конференции Society for Industrial and Applied Mathematics и кто-то спросил его, чем он занимается. В то время информатика была разделена на численный анализ, искусственный интеллект и языки программирования. На основе своих исследований и книги «Искусство программирования на ЭВМ» Knuth решил, что в следующий раз, когда его спросят, он ответит: «Analysis of algorithms».
Затем Knuth покинул эту должность и присоединился к факультету Стэнфордского университета в 1969 году, где сейчас является профессором информатики Fletcher Jones, эмеритом.
Сочинения
Knuth — писатель, а также учёный в области информатики.
The Art of Computer Programming TAOCP
В 1970-х годах Knuth описывал информатику как «совершенно новую область без реальной идентичности. И стандарт доступных публикаций был не столь высок. Много вышедших статей были просто ошибочными. ... Таким образом, одна из моих мотиваций заключалась в том, чтобы выправить историю, которая была очень плохо рассказана». К 2011 году были опубликованы первые три тома и первая часть четвёртого тома его серии. Также опубликована книга «Concrete Mathematics: A Foundation for Computer Science» второе издание, которое возникло в результате расширения раздела математических основ тома 1 TAoCP. В апреле 2020 года Knuth сказал, что он интенсивно работает над частью B тома 4, и он предполагает, что книга будет иметь по крайней мере части с A по F.
Другие произведения
Knuth также автор книги «Surreal Numbers», математической новеллы о конструкции теории множеств John Conway альтернативной системы чисел. Вместо простого объяснения темы, книга стремится показать развитие математики. Knuth хотел, чтобы книга подготовила студентов к проведению оригинальных, творческих исследований.
В 1995 году Knuth написал предисловие к книге «A=B» авторов Marko Petkovšek, Herbert Wilf и Doron Zeilberger. Knuth также время от времени вносит вклад в языковые головоломки в журнал «Word Ways: The Journal of Recreational Linguistics».
Knuth также погружался в развлекательную математику. Он публиковал статьи в журнале «Journal of Recreational Mathematics» начиная с 1960-х годов и признавался в качестве основного участника в работе «Mathematics on Vacation» Joseph Madachy.
Knuth также появлялся в ряде видео на YouTube каналов Numberphile и Computerphile, где он обсуждал темы от написания «Surreal Numbers» до того, почему он не пользуется электронной почтой.
Произведения, касающиеся религиозных убеждений Knuth
Помимо своих сочинений об информатике, Knuth, лютеранин, также автор книги «3:16 Bible Texts Illuminated», в которой он исследует Библию путём систематической выборки, а именно анализа главы 3, стиха 16 каждой книги. Каждый стих сопровождается каллиграфическим искусством, созданным группой каллиграфов под руководством Hermann Zapf. Впоследствии его пригласили прочитать серию лекций в MIT о своих взглядах на религию и информатику, стоящие за его проектом 3:16, что привело к появлению ещё одной книги «Things a Computer Scientist Rarely Talks About», в которой он опубликовал лекции «God and Computer Science».
Мнение о патентах на программное обеспечение
Как член академического и научного сообщества, Knuth категорически противостоит политике выдачи патентов на программное обеспечение за тривиальные решения, которые должны быть очевидными, но выразил более обоснованные взгляды на нетривиальные решения, такие как метод внутренней точки линейного программирования. Он выразил своё несогласие непосредственно как Ведомству по патентам и торговым маркам Соединённых Штатов, так и Европейской патентной организации.
Computer Musings
Knuth несколько раз в год читает неформальные лекции в Стэнфордском университете, которые он назвал «Computer Musings». Он был приглашённым профессором на факультете информатики Оксфордского университета в Соединённом Королевстве до 2017 года и почётным членом колледжа Magdalen.
Программирование
Цифровой набор
В 1970-х годах издатели TAOCP отказались от Monotype в пользу фотонабора. Knuth так разочаровался неспособностью последней системы приблизиться к качеству предыдущих томов, которые были набраны с использованием более старой системы, что нашёл время для работы над цифровым набором и создал TeX и Metafont.
Грамотное программирование
Во время разработки TeX Knuth создал новую методику программирования, которую он назвал грамотным программированием, потому что считал, что программисты должны думать о программах как о произведениях литературы. «Вместо того, чтобы воображать, что наша основная задача — указать компьютеру, что делать, давайте сосредоточимся скорее на объяснении людям, что мы хотим, чтобы компьютер сделал.»
Knuth воплотил идею грамотного программирования в системе WEB. Один и тот же исходный код WEB используется для создания файла TeX и для получения исходного файла Pascal. Они, в свою очередь, создают читаемое описание программы и исполняемый бинарный файл соответственно. Более поздняя итерация системы, CWEB, заменяет Pascal на C.
Knuth использовал WEB для программирования TeX и METAFONT и опубликовал обе программы в виде книг: «The TeXbook», первоначально опубликованный в 1984 году, и «The METAFONTbook», первоначально опубликованный в 1986 году. Примерно в то же время Leslie Lamport разработал LaTeX, широко распространённый теперь пакет макросов на основе TeX и позже опубликовал его первое руководство пользователя в 1986 году.
Музыка
Knuth — органист и композитор. В 2016 году он завершил музыкальное произведение для органа под названием «Fantasia Apocalyptica», которое он описывает как «перевод греческого текста Откровения святого Иоанна Богослова в музыку». Его премьера состоялась в Sweden 10 января 2018 года.
Личная жизнь
Donald Knuth женился на Nancy Jill Carter 24 июня 1961 года, когда он был аспирантом Калифорнийского технологического института. У них два детей: John Martin Knuth и Jennifer Sierra Knuth.
Китайское имя
Китайское имя Knuth — Gao Dena. В 1977 году он получил это имя от Frances Yao, незадолго до трёхнедельной поездки в China. В своём томе 1980 года «Искусства программирования на ЭВМ» Knuth объясняет, что он принял своё китайское имя, потому что хотел быть известным растущему числу программистов в China в то время. В 1989 году его китайское имя было помещено в заголовок журнала «Journal of Computer Science and Technology», о чём Knuth говорит: «это заставляет меня чувствовать себя близко ко всем китайским людям, хотя я не могу говорить на вашем языке».
Проблемы со здоровьем
В 2006 году у Knuth было диагностировано раковое заболевание простаты. Он перенёс операцию в декабре того года и заявил: «немного лучевой терапии ... в качестве профилактики, но прогноз выглядит довольно хорошо», как он сообщил в своей видеоавтобиографии.
Юмор
Knuth раньше платил вознаграждение в размере $2,56 за любые опечатки или ошибки, обнаруженные в его книгах, потому что «256 пенни — это один шестнадцатеричный доллар», и $0,32 за «ценные предложения». По словам статьи в журнале «Technology Review» Массачусетского технологического института, эти чеки вознаграждения Knuth — «один из самых ценных трофеев в мире компьютеров». Knuth вынужден был прекратить отправку настоящих чеков в 2008 году из-за банковского мошенничества, вместо этого он теперь выдаёт каждому нашедшему ошибку «свидетельство о вкладе» из публично указанного баланса в своём вымышленном «Bank of San Serriffe».
Он однажды предупредил корреспондента: «Остерегайтесь ошибок в приведённом выше коде; я только доказал его корректность, но не пробовал его.»
Knuth опубликовал свою первую «научную» статью в школьном журнале в 1957 году под названием «The Potrzebie System of Weights and Measures». В ней он определил основную единицу длины как толщину журнала Mad No. 26 и назвал основную единицу силы «whatmeworry». Mad опубликовал статью в номере No. 33, июнь 1957.
Чтобы продемонстрировать концепцию рекурсии, Knuth намеренно перекрёстно ссылался на «Circular definition» и «Definition, circular» друг на друга в предметном указателе «Искусства программирования на ЭВМ», том 1.
Предисловие книги «Concrete Mathematics» содержит следующий абзац:
Когда DEK впервые преподавал Concrete Mathematics в Stanford, он объяснил несколько странный заголовок, сказав, что это была его попытка преподавать курс математики, который был сложным, а не лёгким. Он объявил, что, вопреки ожиданиям его коллег, он не собирался преподавать теорию совокупностей, теорему Стоуна об встраивании и даже компактификацию Стоуна–Čech. (Несколько студентов из отделения гражданского строительства тихо встали и вышли из комнаты.)
На конференции TUG 2010 Knuth объявил о сатирическом преемнике TeX на основе XML под названием «iTeX» произносимый , выполняемый звоном колокола, который поддерживал бы такие функции, как произвольно масштабируемые иррациональные единицы, трёхмерную печать, ввод от сейс
