Покупая сегодня компьютер, можно быть уверенным: через пять лет он будет считаться устаревшим, и многие новые программы даже не запустятся на нём. Срок жизни программ тоже обычно невелик: новые программы рассчитаны на большие вычислительные мощности и потому быстрее, удобнее, красивее старых. Так что же — пользоваться компьютерными учебниками или программами, написанными пять лет назад, бесполезно: всё равно они безнадёжно устарели? Обычно это так, но бывают исключения.
Например, один из самых популярных учебников по компьютерным наукам начал печататься аж в 1968 году — это многотомник американского учёного Дональда Кнута «Искусство программирования для ЭВМ» («The Art of Computer Programming»). А большая часть физико-математической и технической литературы по сей день верстается на компьютерах с помощью системы (обычно пишут: ТеХ), которая практически не изменялась с 1989 года. Кстати, ТеХ создал тот же Дональд Кнут. Что же это за уникальный человек?
Детство
Дональд Кнут родился 10 января 1938 года в Милуоки (штат Висконсин). Его отец преподавал бухгалтерский учет в университете и занимался также дома, в подвале, печатным делом, (этим можно объяснить последующий интерес Дональда к этому делу и такие разработки как ΤΕΧ). Ребенком Кнут с удовольствием играл с калькулятором отца, который мог перемножать десятизначные числа, но у него уходило от десяти до двадцати секунд, чтобы напечатать ответ. С юных лет в нём наблюдалась склонность к математике, физике и музыке. В старших классах Милуокской лютеранской высшей школы он беспокоился, что низкие оценки по математике могут помешать его поступлению в колледж, но это была непонятная озабоченность, поскольку он закончил школу с самым высоким коэффициентом за все времена — 97,5%.
Талант программиста впервые проявился у Кнута в тринадцатилетнем возрасте, то есть в середине прошлого века, когда искусство компьютерного программирования только зарождалось. Тогда одна из кондитерских фирм организовала для детей конкурс, в рамках которого им следовало определить, сколько слов можно получить, используя буквы, входящие в название фирменной плитки шоколада Ziegler’s Giant Bar. Это была чётко сформулированная проблема, состоящая из разных частей, — как раз такая, какие ему нравились. «У меня была обсессивно-компульсивная жилка, побуждавшая меня браться за решение цифровых, дискретных проблем. И я любил тщательно изучать большие коллекции информации», — вспоминает Кнут.
Кнут, сидя в подвале, методично пролистал все 2000 страниц полного стандартного словаря английского языка Funk & Wagnalls. Чтобы ничто не отвлекало от решения конкурсной проблемы, он даже сумел сказаться больным, и родители позволили ему две недели не ходить в школу. Пометив учётные карточки двумя буквами, которые могли быть начальными для слова, содержащего только буквы, входящие в название шоколадной плитки, — например «Aa», «Ab» и «Ba», — он скользил вниз по столбцам словаря, отмечая подходящие слова. Он обнаружил, что можно пропустить целые разделы словаря, например те, что посвящены словам, начинающимся с буквы «C», или словам, в которых первая буква «B», а вторая «U». По прикидкам организаторов конкурса, должно было получиться около 2000 слов, но Кнуту удалось найти более 4700. В награду за это его показали по телевидению и угостили шоколадом вместе со всеми его одноклассниками. А потом было много других наград, в том числе первая премия ACM (Ассоциации вычислительной техники) имени Грейс Мюррей Хоппер (Grace Murray Hopper), Национальная научная медаль (National Medal of Science) и премия A.M. Тьюринга (A.M. Turing Award). В 19 лет Кнут опубликовал свою первую техническую работу в журнале Mad. Он стал информатиком до того, как появилась эта дисциплина, еще когда изучал математику в Кейсовском технологическом институте. Он смотрел на программы для мейнфрейма IBM 650, и заметив некоторые недостатки, переписал ПО, а также учебник для курса.
В 1960 году окончил с отличием отделение математики Кейсовского технологического института (бакалавр, 1960). Одновременно за значительные достижения в программировании был удостоен степени магистра. Спустя три года получил докторскую степень в Калифорнийском технологическом институте. Преподавал там же математику и одновременно работал консультантом по проблемам разработки программного обеспечения в корпорации Burroughs.
Любовь Кнута к математике усилилась на первом году учебы в университете. Он был захвачен графикой алгебраических функций — областью нескончаемых возможностей.
Физика также ему нравилась, и он разрывается между ней и музыкой — он серьезно обучался игре на пианино, сам написал несколько произведений. Музыка представляет для Кнута большой энтузиазм.
Он стал дизайнером органа в стиле барокко, состоящего из 1000 труб, для лютеранской церкви в парке Менло в Калифорнии и выстроил уменьшенную версию для собственного дома. В 1977 году он опубликовал шутливую статью «Оценка сложности песен», в которой постарался дать математическое описание популярных песен.
Кнут признает, что у него комплекс неполноценности. Это объясняет, то, что он всегда много работал.
В 1956 году он поступил в Кейский Технологический институт в Кливленде. На первом году обучения он занялся высшей математикой. Снова из-за страха, что не справится, Кнут в дополнительное время с рвением изучал дифференциальное и интегральное исчисление и аналитическую геометрию.
Во время каникул после первого курса Кнут впервые занялся работой с компьютером. У него было задание на лето — построить графики для статистиков Кейса. В соседней комнате находилась новая машина IBM 650. Кнут так загорелся ею, что посвятил «Искусство программирования» компьютеру IBM 650, установленному в Кэйском технологическом институте, в память о многих приятных вечерах. Некоторые из его преподавателей советовали ему держаться в стороне от компьютеров, утверждая, что это ни к чему хорошему не приведет. Но любопытство взяло верх, он проводил ночи напролет с компьютером.
Кнут с легкостью оставил физику. Его лабораторные работы, казалось, не приносили удовлетворения, он ронял детали на пол и часто оказывался последним. Сварка оказалась катастрофой: при росте 6 футов и 4 дюйма он был слишком высоким для сварочных столов, и ему невозможно было наблюдать за работой, кроме того, очки ему не подходили.
Кнут добился успехов, используя компьютер для оценки игры баскетбольной команды, менеджером которой он являлся. Он выработал сложную формулу для ранжирования игроков, рассчитывая вклад каждого в игру, не только по количеству очков, которые он принес команде.
Кнут обычно сидел за компьютером IBM 650 и подводил статистику игры, в то время, когда тренер стоял рядом. Используя программу Д. Кнута, тренер мог определить истинный вклад каждого в игру и в соответствии с этим использовать игроков. Оказалось также, что данная программа стимулировала игроков работать с большей отдачей. В 1960 году Кэйский институт выиграл чемпионат лиги, а магическая формула Кнута неожиданно была опубликована в «Walter Cronkite's Sunday» и в «Newsweek».
В 1960 году Кнут получил звание бакалавра по математике, причем студенты даже проголосовали за присуждение ему степени доктора. Летом этого года в Пассадене Кнут занялся работой по системному программированию, результатом которой было создание компилятора для ALGOL. За эту работу он получил 5,5 тысячи долларов. Осенью того же года он поступает в Калифорнийский технологический институт для получения степени доктора философии по математике.
В январе 1962 года издательство «Addison-Wesley» предложило Кнуту написать книгу по компиляторам. Он принял это предложение.
В июне 1963 года в Калифорнийском технологическом институте Кнуту присуждается степень доктора философии по математике и он становится ассистентом профессора. За летние каникулы Кнут зарабатывал больше, чем профессора за год, тем, что писал компиляторы. Компилятор – что-то вроде переводчика; он переводит высокоуровневый язык программирования в низкоуровневый.
В итоге Кнут сам стал компилятором, случайно основав новую область наук под названием «Анализ алгоритмов». Он должен был написать книгу о компиляторах, но она превратилась в работу, в которой были собраны все его знания о написании кода для компьютеров – книгу об алгоритмах.
Выход нового тома планировался на Рождество, но его придется перенести, поскольку Кнут постоянно находит новые проблемы, которые хочет рассмотреть подробнее.
Чтобы побыстрее закончить труд, он освободил все свое время: в 55 лет он вышел на пенсию, ограничил все свои публичные обязательства и отказался от имейлов. Раньше Кнут принимал студентов по утрам в пятницу, пока не начал проводить ночи в лаборатории Джона Маккарти, где у него был доступ к компьютерам. Тогда он, ужаснувшись от того, как физически выглядела его книга, решил создать систему компьютерной верстки TeX, которая по сей день является золотым стандартом для всех форм научных коммуникаций и публикаций. Некоторые считают ее самым важным вкладом Кнута в типографию со времен Гутенберга.
Находясь в зачаточном состоянии, компьютерная наука того времени страдала от недостатка специальной литературы, которая была к тому же неоднородной. Кнут обнаружил, что многие из опубликованных статей были неправильны. Тысячи программистов писали новые алгоритмы для мэйнфреймов. Но когда приходила хорошая мысль, она терялась в журнале или техническом докладе. Многие программы просто не читались. Результатом было то, что люди вновь открывали методы, которые уже были известны. Кнуту пришла в голову мысль, что будет полезным иметь общую картину всей этой ценной литературы. Он узнал, что те, кто раньше пытались суммировать технику программирования, были необъективны на основании их собственных теорий. Не развив ни одну из новых идей, но уже уверенный, что является хорошим писателем, Кнут почувствовал, что именно он подходит для этой работы. Вскоре он начинает работу над главами своей книги.
Цель Кнута в этой монументальной работе состояла в том, чтобы обобщить технику программирования и найти ей соответствующее применение. Его основным вкладом было обобщение материала и анализ методов. Он пытался развить наиболее используемые теории для разных методов и заполнить пробелы в этих теориях, он был первым, кто находил эти пробелы и собрал все эти разбросанные теории. Вначале Кнут думал, что напишет только одну книгу о компиляторах. Набросав несколько глав, тем не менее, он почувствовал, что книга должна быть гораздо большей и основополагающей. Получив зеленый свет от издателя, он писал, писал и писал.
К июню 1965 года он завершил первый проект из двенадцати глав, который размещался на трех тысячах страниц рукописного текста. В октябре он отослал первую главу
издателю. Издательство «Addison-Wesley» предложило, что двенадцать частей будут опубликованы как семь отдельных томов, каждый которых будет содержать один или два раздела. Кнута устраивало такое предложение.
Проведя напряженные дни и ночи над реализацией семитомного проекта, Кнут испытал несколько приступов язвы летом 1967 года. Как вспоминает он, это случилось на середине «алгоритма Евклида», на 333 странице второго тома.
С 1968 года он член Совета факультета Стэнфордского университета как профессор в области компьютерной науки. В 1968—1969 годах также работал в Институте оборонных исследований. Приглашённый профессор математики в Университете Осло (1972, 1973). В Стэнфорде под его руководством защищено 28 докторских диссертаций.
Данные издания, как оказалось, имели наибольший спрос из всех книг, продаваемых «Addison-Wesley». В середине 80-х годов две тысячи экземпляров каждого из трех томов расходились в течение месяца, и эта цифра не менялась с середины 70-х годов. Работа была переведена на китайский, румынский, японский, испанский и русский язык, планировалось издание на португальском и венгерском. Кнут становится все более знаменитым: в 1979 г. в возрасте 41 года он получает из рук президента Дж. Картера Национальную медаль в области науки за свою работу по алгоритмам.
Весной 1977 года Дональд Кнут резко изменил род своих занятий. Просматривая гранки проверенного издания второго тома, он неожиданно почувствовал, что полиграфия нуждается в кардинальном изменении. Он хотел уничтожить эти гранки, поскольку они выглядели ужасно. Пространственное расположение знаков было плохим, и особенно острой проблемой в издании был стандартный шрифт и вид математических уравнений. Кнут хотел понять, почему печатная работа, в которой использовался фоторепродукционный шрифт, была такой непривлекательной. Он решил посвятить несколько месяцев тому, чтобы попытаться совместить математику и компьютерную науку с задачей улучшения внешнего вида книг. Проект длился девять лет!
Кнут изобрел ТеХ, первую издательскую систему, а также METAFONT, систему, которая использует классическую математику для придания внешнего вида шрифтам. ТеХ был назван одним из наиболее важных изобретений в истории печатания книг. Некоторые сравнивали его по значению с Библией Иоганна Гуттенберга, что смутило Кнута.
ТеХ позволяет наборной машине размещать буквы и знаки на странице со значительной гибкостью и эстетичным качеством.
METAFONT позволяет дизайнеру создавать шрифт или комплект шрифта, полный с буквами, числами и пунктуацией в специфичном стиле. Комплект шрифта может быть изображен на мониторе и может быть изменен любым способом.
Когда Кнут сверстал второй том «Искусства программирования», используя METAFONT и ТеХ, результат был лучше, но не идеальным. Плохо получались числа. Так он потратил еще пять лет, работая с лучшими дизайнерами по графике, для того, чтобы создать новые системы и наиболее полно использовать их потенциал. Летом 1986 года разработки Кнута по типографии были завершены, и вышел пятитомник «Компьютеры и набор знаков». Первый том посвящен ТеХ; второй содержит полный источник кодов ТеХ; третий и четвертый, соответственно, посвящены METAFONT и полному источнику кодов для него; пятый том содержит 500 с лишним примеров программирования по METAFONT.
В 1986 году на приеме в издательстве «Addison-Wesley», устроенном в его честь, ему задали вопрос: «Будет ли завершен его семитомник, будут ли дописаны четыре недостающих тома?» Он ответил, что их написание заняло бы еще двадцать лет.
Прошло тринадцать лет. В 1999 году профессор Кнут заявил, что к существующим трем томам он намерен добавить еще два тома. Кроме того, он решил заменить виртуальную модель компьютера MIX 1009 (модель, похожую на реальные компьютеры конца 60-х — начала 70-х годов), на языке которого написаны большинство алгоритмов первых трех томов, на новую модель — 64-разрядный процессор MMIX 2009 с RISC-архитектурой. В следующих изданиях «Искусство программирования» примеры будут приводиться на языке ассемблера MMIX.
В 2011 году была выпущена первая часть 4 тома.
Поскольку Кнут всегда считал монографию «Искусство программирования» основным проектом своей жизни, в 1993 году он вышел в отставку с намерением полностью сконцентрироваться на написании недостающих частей и приведении в порядок существующих. Сейчас ему 80 лет. В свое время он работал в непосредственной близости с машиной – писал в бинарном коде. Строгие стандарты ученого могут объяснить, почему труд всей его жизни еще не закончен. Он заключил пари с Сергеем Брином, сооснователем Google и его бывшим студентом, по поводу того, кто первым закончит свою научную работу – Брин диссертацию или Кнут книгу?
Дональд Кнут написал пару книг на богословские темы, в том числе «То, о чём редко говорит учёный-компьютерщик» (Things a Computer Scientist Rarely Talks About). Эти книги о том, что невозможно доказать, а не о проблемах математики или информатики.
Может показаться неправдоподобным, но Кнут также пишет фантастические вещи. Его новелла «Сюрреалистические числа: как два бывших студента занялись чистой математикой
и нашли полное счастье» была опубликована в издательстве «Addison-Wesley» в 1974 году. В книге рассказывается об исследовании новой системы чисел, открытой в Кэмбриджском университете Дж. Конвэем. Кнут узнал о данной системе от самого Конвэя в 1972 году. Один журналист отметил, что впервые значимое открытие в математике описывается сначала в научной фантастике. Кнут написал данную книгу не для того, чтобы проповедовать теорию Конвэя, а чтобы объяснить, как человек может создать такую теорию.
Первым не латинским шрифтом, появившимся в ТеХ'е, была кириллица. Кстати, Кнут знает русский язык — он выучил его, чтобы читать работы русских математиков в подлиннике. Одним из друзей Кнута был советский программист Андрей Петрович Ершов, чьи книги автор ТеХ'а очень ценит. Кнут всегда чрезвычайно беспокоится о точности и правильности того, что он пишет. Чтобы избавиться от ошибок в ТеХ'е и в книге «Искусство программирования», он придумал оригинальную систему: за каждую найденную ошибку
выплачивалось небольшое денежное вознаграждение. Например, в первый год после выхода «Искусства программирования» каждый нашедший ошибку получал от автора чек на $2,56. Получение подобного чека — дело очень редкое и почётное, поскольку даже первоначальные версии были практически безошибочны. Большинство обладателей этих чеков не отнесли их в банк, а оставили на память. Сейчас Кнут вместо чеков высылает шуточные сертификаты.
Профессор Кнут удостоен многочисленных премий и наград в области программирования и вычислительной математики, среди которых премия Тьюринга (1974), Национальная научная медаль США (1979) и AMS Steele Prize за серию научно-популярных статей, премия Харви (1995 год), премия Киото (1996) за достижения в области передовых технологий, премия имени Грейс Мюррей Хоппер (1971). В конце февраля 2009 года Кнут занимал 20 место в списке самых цитируемых авторов в проекте CiteSeer.
