@jawbreaker read-only
Пользователь
28 июня 2009 в 12:53

Дональд Кнут

image

Дональд Эрвин Кнут — американский учёный, почётный профессор Стэнфордского университета и нескольких других университетов в разных странах, преподаватель и идеолог программирования, автор 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 года в Калифорнийском технологическом институте Кнуту присуждается степень доктора философии по математике и он становится ассистентом профессора. Вскоре он начинает работу над главами своей книги.
image
Находясь в зачаточном состоянии, компьютерная наука того времени страдала от недостатка специальной литературы, которая была к тому же неоднородной. Кнут обнаружил, что многие из опубликованных статей были неправильны. Тысячи программистов писали новые алгоритмы для мэйнфреймов. Но когда приходила хорошая мысль, она терялась в журнале или техническом докладе. Многие программы просто не читались. Результатом было то, что люди вновь открывали методы, которые уже были известны. Кнуту пришла в голову мысль, что будет полезным иметь общую картину всей этой ценной литературы. Он узнал, что те, кто раньше пытались суммировать технику программирования, были необъективны на основании их собственных теорий. Не развив ни одну из новых идей, но уже уверенный, что является хорошим писателем, Кнут почувствовал, что именно он подходит для этой работы.

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

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

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

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

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

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

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

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

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

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

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

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

imageПрошло тринадцать лет. В 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. Дональд Кнут приглашает к сотрудничеству добровольцев со всего мира, прежде всего студентов.
@jawbreaker
карма
76,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (49)

  • +50
    Думаю что все программисты глубоко признательны этому человеку
  • +11
    Спасибо за статью, было очень интересно почитать! Книги Д. Кнута из серии маст хэв.
    • +38
      Скорее Must Read. А то почти у всех программистов есть, но не все прочли, и почти никто не делал упражнений в конце глав.
      • +5
        Что да — то да, слишком уж их много и много времени займет их решение. Но в свободное время порешать их будет очень полезно.
        • +5
          На обложке какого-то из томов «Искусства программирования» есть цитата Гейтса, дословно не помню, но смысл в том, что если вы прочитали полностью этот труд, вам обязательно нужно отправить Гейтсу резюме. А вообще, что и говорить, трудно переоценить вклад Кнута в развитие ИТ и программирования в частности.
      • +6
        Я сколько не пытаюсь, все время упираюсь в проблемы с математикой :-(

        Вот с Корманом полегче.
      • 0
        Остановился на доказательстве Большой теоремы Ферма…
  • +1
    У меня есть 2 тома. Когда-то нашёл их на книжном рынке. Совершенно случайно, даже не думав, что такое возможно. Очень обрадовался и сразу купил (по очень смешной цене). Книги очень старые, страницы уже давно пожелтели и выцвели. Да уж… Но что-то в этом есть))
    • +1
      Здорово! :) А я на днях смотрел в книжном, при довольно посредственном издании(не самая хорошая бумага, мягкая обложка) цена у них порядочная. Вообще ИТ литература в России дорого стоит… :(
      • 0
        IT литература везде дорого стоит. Посмотрите цены на книги на английском и вам понравятся российские цены.
  • +24
    Хочу себе комплекс неполноценности!!!
    • +3
      такой вопрос уже подразумевает его наличие :)
      • +2
        рекурсия
    • 0
      У меня был такой по матану, чуть с универа не вылетел, пока меня на консультацию с пинками не затолкали… сдал довольно быстро.
  • +3
    Не только программисты, любой студент, который хочет чтоб его диплом выглядел именно так как ему хочется, а не так как получится, будет безмерно благодарен этому великому человеку за TeX.
    • 0
      TeX Live наше всё!
  • –10
    создатель настольных издательских систем TEX и METAFONT

    METAFONT — язык программирования, используемый для разработки векторных шрифтов. Также это название интерпретатора, выполняющего код METAFONT.

    TEΧ — система компьютерной вёрстки.
    • 0
      Привет, Кэп!
  • +3
    Великий дядька!
    • +5
      есть еще Боги на Земле!
  • +2
    Мне еще нравится книга «Конкретная Математика (КОНтинуальная и дисКРЕТНАЯ математика), где одним из 3х авторов является Д. Кнут, она написана по курсу, который припадает Кнут в Стендфорском университете
  • +4
    доктор философии по математики звучит коряво, может это доктор или кандидат по-русски?
    • +1
      «Несмотря на название, в настоящее время степень не имеет никакого практического отношения к философии (только историческое) и присуждается почти во всех научных областях, например: доктор философии по литературе или доктор философии по физике.» © wikipedia
      • +3
        «В связи с этим, ранее и в настоящее время в странах бывшего СССР по умолчанию степень доктора философии приравнивается к степени кандидата наук.» © wikipedia
      • 0
        за то звучит круто)
    • +2
  • +3
    Начал было читать первый том… тяжело идёт=(
  • +1
    а что это за теория Конвея? в русской вики только про игру Жизнь и теорию узлов есть?
    • +1
      Что-то из области теории игр и комбинаторики, честно говоря я не достаточно разбираюсь в математике чтобы ответить на этот вопрос :)
  • +3
    Легендарная личность. Неоценимый вклад. Не знал, что он увлекался многими вещами, например музыкой и писательством. Талантливый человек талантлив по всём.
  • +3
    Спасибо, очень интересно почитать о Жизни такого человека… Вдохновляет на прочтение его великих Трудов

    «источник кодов» — наверное всё же имелись ввиду исходные тексты…
  • 0
    Великий человек, эпоха, странно представить, как бы вся эта область развивалась без его трудов
  • 0
    Хорошая, интересная статья. Каждый раз, встретив такую на хабаре, радуюсь и горжусь: могут же русские люди писать хорошие тексты! (а не только переводить гуглом с аглийского популярные статьи) Однако, встретив фразу «на трех тысячах страницах», стал подозревать, что это снова аккуратный перевод.
    Автор, развейте мои сомнения! )
    • 0
      Я подозреваю, что это не перевод, а скан/распознавание печатной статьи.

      «Весной 1977 года Дональд Кнут резко изменил род своих занятий. Просматривая фанки проверенного издания второго тома, он неожиданно почувствовал,… » («ф» вместо «гр» — классическая ошибка распознавания).

      «а также METAFONT, систему, которая использует классическую математику для придания внешнего вИца шрифтам» (ещё одна классическая ошибка: «ц» вместо «д»).
      • 0
        Да, вы куда внимательнее меня, и да, вы, скорее всего, правы )
      • –2
        хары в коментах ошибки постить!
        все в личку

        заодно и знакомство заведете поближе!
  • 0
    Assistant professor это не «ассистент профессора», это просто «начальная ступень» профессора, присваиваемая сразу после получения Ph.D. Потом следует Associate professor, и, наконец, просто Professor. Дело в том, что профессор это скорее административная должность, чем учёная степень, отсюда и деление на «уровни».
    • –1
      И ещё — их доктор наук — приравнивается к нашему кандидату наук.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Долгих лет замечательному учёному.
    А на MMIX надо бы глянуть.
  • +1
    Эти «источникни кодов» меня убивают.
  • 0
    Кнут молоток!
    Но почему на хабре никто про Норберта Виннера не напишет, может мне набросать статейку?
  • 0
    «для лютеранской церкви в парке Менло в Калифорнии» — перевод не верен, «Menlo Park» — это город близ Сан Франциско (http://en.wikipedia.org/wiki/Menlo_Park,_California), а не парк

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.