IT имена: Donald Knuth (Дональд Кнут) - Искусство программирования

• Биография
• Признание
• Компьютерные размышления
• Музыка
• Личная жизнь
• Рассвет алгоритмов
• Творчество Дональд Кнут
• Библиография
• Цитаты

Биография

Дональд Эрвин Кнут (Donald Ervin Knuth). Родился 10 января 1938 года в Милуоки, штат Висконсин. Американский учёный, эмерит-профессор Стэнфордского университета и нескольких университетов в разных странах, преподаватель и идеолог программирования, автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для набора и вёрстки книг, посвящённых технической тематике (в первую очередь - физико-математических).

Родился в семье преподавателя. Отец Дональда преподавал бухгалтерский учёт, а также занимался печатным делом на дому как любитель (чем можно объяснить последующий интерес Дональда к выбранному профессиональному направлению и как следствие разработка TEX). С юных лет в Дональде наблюдалась склонность к математике, физике и музыке. Большее влияние на юного Дональда Кнута оказали работы Андрея Петровича Ершова, впоследствии его друга.

Увлечение программированием началось ещё со студенчества. Тогда только появилась книга Андрея Епшова «Программирование для БЭСМ», и группа студентов, смогли убедить преподавателя русского языка включить её в курс в качестве одного из двух сборников текстов для изучения научной лексики. Профессор Кнут удостоен многочисленных премий и наград в области программирования и вычислительной математики, среди которых премия Тьюринга (1974), Национальная научная медаль США (1979) и AMS Steele Prize за серию научно-популярных статей, премия Харви (1995 год), премия Киото (1996) за достижения в области передовых технологий, премия имени Грейс Мюррей Хоппер (1971). В конце февраля 2009 года Кнут занимал 20 место в списке самых цитируемых авторов в проекте CiteSeer.

Образование

Кнут получил стипендию по физике от Кейсовского технологического института (теперь часть Кейс Вестерн Резервный университет) в Кливленд, Огайо, поступил в 1956 г. Он также присоединился к главе Beta Nu Братство Тета Чи. Тогда только выпускались прототипы современных компьютеров - Прочитав руководство к компьютеру, Кнут решил переписать код сборки и компилятора для машины, используемой в его школе, потому что он считал, что может сделать это лучше.

В 1958 году Кнут создал программу, чтобы помочь школьной баскетбольной команде выиграть матчи в своей лиге. Он присвоил игрокам «ценности», чтобы оценить их вероятность получения очков, - новый подход, о котором сообщили в Newsweek и CBS Evening News.

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

В 1963 г. с математиком Маршалл Холл в качестве его советника, он получил степень доктора математики в Калифорнийском технологическом институте.

Ранняя работа

После получения докторской степени Кнут поступил на факультет Калифорнийского технологического института в качестве доцента.

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

Незадолго до публикации первого тома "Искусство программирования" Кнут покинул Калифорнийский технологический институт, чтобы устроиться на работу в Отдел исследований связи Института оборонного анализа, затем расположенный на Университет Принстона кампуса, который проводил математические исследования в криптография для поддержки Национальное Агенство Безопасности.

В 1968 году перешел в Стэнфордский университет. В 1968-69 годах также работал в Институте оборонных исследований. Приглашенный профессор математики в университете Осло, Норвегия (1972, 1973). В Стэнфорде под его руководством защищено 28 докторских диссертаций.

Признание

На январь 2013 года Кнут занимает 37-е место в списке самых цитируемых авторов в области информатики согласно проекту CiteSeer.

Член редакционных коллегий многих научных журналов.

Действительный член Американской академии искусств и наук (1973), Национальной академии наук США (1975), Национальной инженерной академии США (1981). Член Американской гильдии органистов (с 1965 года), Американского математического общества (1961), Ассоциации компьютерной техники (ACM) (1959), Математической ассоциации Америки (1959), Общества промышленной и прикладной математики (1965), действительный член Британского компьютерного общества (1980), почётный член IEEE (1982). Иностранный член Лондонского королевского общества (2003), Российской академии наук (29 мая 2008).

Почётный доктор многих университетов. Почётный доктор СПбГУ (1992).

Удостоен многочисленных премий и наград в области программирования и вычислительной математики, среди которых:

• 1971 — Премия имени Грейс Мюррей Хоппер
• 1972 — Стипендия Гуггенхайма
• 1974 — Премия Тьюринга
• 1978 — Гиббсовская лекция
• 1979 — Национальная научная медаль США
• 1980 — Премия Уоллеса Макдауэлла
• 1986 — Премия Стила за серию научно-популярных статей
• 1988 — Медаль Франклина
• 1992 — Мемориальные лекции Вейцмана
• 1995 — Премия Харви
• 1995 — Медаль Джона фон Неймана
• 1996 — Премия Киото за достижения в области передовых технологий
• 1998 — Fellow Awards
• 2010 — BBVA Foundation Frontiers of Knowledge Awards
• 2011 — Медаль Фарадея
• 2011 — Лекция Тьюринга
• 2016 — Лекция Джона фон Неймана

Существует премия его имени за вклад в основы информатики.

Компьютерные размышления

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

Музыка

Дональд Кнут органист и композитор. В 2016 году закончил музыкальное произведение для органа названное как "Fantasia Apocalyptica", который он описывает как "перевод греческого текста откровения св. Иоанна в музыку". Премьера состоялась в Швеции 10 января 2018 г.

Личная жизнь

Дональд Кнут женился на Нэнси Джилл Картер 24 июня 1961 года, когда он был аспирантом Калифорнийского технологического института. У них двое детей: Джон Мартин Кнут и Дженнифер Сьерра Кнут.

Китайское имя

А вы знали, что у Дональда Кнута есть китайское имя Гао Дена (упрощенный китайский: 高 德纳; традиционный китайский: 高 德納; пиньинь: Гао де на). В 1977 году это имя ему дал Фрэнсис Яо, незадолго до трехнедельной поездки в Китай. В его выпуске 1980 г. Искусство программирования (упрощенный китайский: 计算机 程序 设计 艺术; традиционный китайский: 電腦 程式 設計 藝術; пиньинь: Jìsuànjī chéngxù shèjì yìshù), Кнут объясняет, что он принял свое китайское имя, потому что хотел, чтобы его знали все увеличивающееся в то время число программистов в Китае. В 1989 году его китайское имя было помещено в Журнал компьютерных наук и технологий с заголовоком, который, по словам Кнута, «заставляет меня чувствовать себя ближе ко всем китайцам, хотя я не говорю на вашем языке».

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

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

Юмор

Кнут платил "гонорар искателя" в размере 2,56 доллара за любые опечатки или ошибки, обнаруженные в его книгах, потому что «256 пенни - это один шестнадцатеричный доллар» и 0,32 доллара за «ценные предложения». Согласно статье в Массачусетском Технологическом Институте эти Наградные чеки Кнута являются «одними из самых ценных трофеев компьютерного мира». Кнут был вынужден прекратить посылать настоящие чеки в 2008 году из-за безудержного мошенничества. Теперь он рассылает «личные депозитные сертификаты» в банке Сан-Серрифф (BoSS). Он говорит, что готов выслать реальные деньги в случае необходимости, но, похоже, это слишком хлопотно.

Однажды он предупредил корреспондента: «Остерегайтесь ошибок в приведенном выше коде; я только доказал его правильность, а не пробовал».

Рассвет алгоритмов

В 19 лет Кнут опубликовал свою первую техническую работу в журнале Mad. Он стал информатиком до того, как появилась эта дисциплина, еще когда изучал математику в Кейсовском технологическом институте. Он смотрел на программы для мейнфрейма IBM 650, и заметив некоторые недостатки, переписал ПО, а также учебник для курса.

За летние каникулы Кнут зарабатывал больше, чем профессора за год, тем, что писал компиляторы. Компилятор – что-то вроде переводчика; он переводит высокоуровневый язык программирования в низкоуровневый.

В итоге Кнут сам стал компилятором, случайно основав новую область наук под названием «Анализ алгоритмов». Он должен был написать книгу о компиляторах, но она превратилась в работу, в которой были собраны все его знания о написании кода для компьютеров – книгу об алгоритмах.

Выход нового тома планировался на Рождество, но его придется перенести, поскольку Кнут постоянно находит новые проблемы, которые хочет рассмотреть подробнее.

Чтобы побыстрее закончить труд, он освободил все свое время: в 55 лет он вышел на пенсию, ограничил все свои публичные обязательства и отказался от имейлов.

Раньше Кнут принимал студентов по утрам в пятницу, пока не начал проводить ночи в лаборатории Джона Маккарти, где у него был доступ к компьютерам. Тогда он, ужаснувшись от того, как физически выглядела его книга, решил создать систему компьютерной верстки TeX, которая по сей день является золотым стандартом для всех форм научных коммуникаций и публикаций. Некоторые считают ее самым важным вкладом Кнута в типографию со времен Гутенберга.

«Я никогда не буду знать всего. Моя жизнь была бы намного хуже, если бы я знал ответы на все и если бы я не мог ответить ни на один вопрос».

Пазлы и игры – вещи, которые очень нравятся ученому. Один из разделов его книги называется «Пазлы против реального мира». Он отправил по электронной почте выдержку из своей работы художнику Мартину Демейну и его сыну и информатику Эрику Демейну, поскольку написал об их алгоритмических шрифтах-головоломках.

«Для меня большая честь быть упомянутым в его книге», – поделился Эрик Демейн.

Конечно, вся эта алгоритмическая суета также вызывает и реальные проблемы. Алгоритмы, написанные людьми, которые с каждым разом решают все более сложные проблемы, но производят код с багами и предвзятостью, довольно проблематичны. Возможно, еще большую тревогу вызывают алгоритмы, написанные не людьми, а машинами.

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

Фото: Джилл Кнут

«Сегодня программисты используют то, что создали Кнут и другие, в качестве компонентов своих алгоритмов, а затем добавляют другие необходимые им вещи и объединяют это все в одно целое», – сказал Норвиг.

«С ИИ все то же самое. Просто часть, где все объединяется в одно целое, делается автоматически на основе данных, а не работы программиста. ИИ должен объединять компоненты для получения хорошего ответа, основываясь на данных. Но вам решать, какими будут эти компоненты. Возможно, это будет страница или глава из книг Кнута, потому что это лучший способ выполнить работу», – продолжил он.

А пока Кнут предполагает, что до завершения книги еще примерно 25 лет, хотя это прогнозируемое число не менялось с 1980 года. Получат ли алгоритмы, пишущие алгоритмы, собственную главу или страницу в его эпилоге? «Определенно, нет», – сказал Кнут.

«Я переживаю, что алгоритмы сейчас играют слишком заметную роль в мире, – добавил он. – Сначала информатики переживали, что их никто не слушает. Теперь я переживаю, что нас слушают слишком много людей».

Творчество Дональд Кнут

На нашем ресурсе представлены описания 15 книг автора Дональда Кнута. Самая популярная по мнению читателей "Искусство программирования. Том 1. Основные алгоритмы".

Первый том серии книг Искусство программирования начинается с описания основных понятий и методов программирования. Затем автор сосредотачивается на рассмотрении информационных структур - представлении информации внутри компьютера, структурных связях между элементами данных и о способах эффективной работы с ними.

Эта книга представляет собой один из выпусков очередных томов всемирно известного труда "Искусство программирования", не нуждающейся ни в представлении, ни в рекламе. В данный выпуск вошли разделы первого тома, посвященные RISC-компьютеру MMIX, который заменит прежний компьютер MIX, и языка ассемблера MMIX.

Дональд Кнут Конкретная математика. Основание информатики

Название этой оригинальной как по содержанию, так и по форме книги знаменитых американских математиков можно расшифровать как КОНтинуальная и дисКРЕТНАЯ математика. Прообразом книги послужил раздел „Математическое введение" первого тома фундаментальной монографии Д. Кнута „Искусство программирования для ЭВМ" (М.: Мир, 1976).

Дональд Кнут Искусство программирования. Том 2. Получисленные алгоритмы

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

Дональд Кнут Искусство программирования. Том 3. Сортировка и поиск. 2-е издание

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

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

Захватывающая приключенческо-математическая история от известного и блестящего автора Дональда Кнута. Двое героев случайно находят камень с древними письменами и открывают для себя новые математические структуры. Для студентов, преподавателей и всех любителей математики.

Эта книга представляет собой том 4А, поскольку сам том 4 является многотомником. Комбинаторный поиск - богатая и важная тема, и Кнут приводит слишком много нового, интересного и полезного материала, чтобы его можно было разместить в одном или двух (а может быть, даже в трех) томах.

Этот выпуск представляет собой продолжение главы о комбинаторных алгоритмах, которая будет включена в четвертый том "Искусства программирования". Поскольку часть этого тома составит большая глава о комбинаторном поиске, то этот выпуск начинается с рассмотрения генерации всех возможных объектов. Особое внимание уделяется генерации всех n-кортежей, которые расширяют эти идеи для всех перестановок.

Эта книга представляет собой один из выпусков очередных томов всемирно известной работы "Искусство программирования", не нуждающейся ни в представлении, ни в рекламе. В данный выпуск вошли разделы четвертного тома, посвященные вопросам генерации всех сочетаний и разбиений. Материалы выпуска в будущем войдут в четвертый том серии, посвященный комбинаторным алгоритмам.

Библиография

• 2003 - Всё про TEX
• 2003 - Всё про METAFONT Компьютеры и набор текста (Computers & Typesetting)
• 2006 - Конкретная математика. Основание информатики
• 2006 - Искусство программирования, том 1. Основные алгоритмы
• 2006 - Искусство программирования, том 1, выпуск 1. MMIX - RISC-компьютер для нового тысячелетия
• 2007 - Искусство программирования, том 2. Получисленные методы
• 2007 - Искусство программирования, том 3. Сортировка и поиск
• 2013 - Искусство программирования, том 4, A. Комбинаторные алгоритмы

Цитаты

• Лучший способ в чём-то разобраться до конца — это попробовать научить этому компьютер.
• Опасайтесь глюков в приведенном коде; я знаю что он правильный, но я его не проверял.
• Преждевременная оптимизация — корень всех (или большинства) проблем в программировании.
• Математические формулы не могут «принадлежать» кому-либо! Математика принадлежит Богу.
• Я не могу заказать блюдо в ресторане потому, что постоянно смотрю на шрифты в меню.
• Самая важная вещь в языке программирования — его имя. Язык не будет иметь успеха без хорошего имени. Я недавно придумал очень хорошее имя, теперь осталось изобрести подходящий язык.