Дональд Кнут - Donald Knuth


Из Википедии, свободной энциклопедии

Дональд Кнут

KnuthAtOpenContentAlliance.jpg
Кнут в 2005 году
Родившийся
Дональд Эрвин Кнут

( 1938-01-10 )10 января 1938 (возраст 81)
Национальность американский
Альма матер
Известный
Награды
Научная карьера
поля
учреждения Стэндфордский Университет
Тезис Конечный Полутели и проективные плоскости  (1963)
Докторская советник Маршалл Холл, младший
Докторанты
Веб-сайт CS .stanford .edu / ~ Кнут

Дональд Эрвин Кнут ( / к ə п ˙U θ / kə- NOOTH , родился 10 января 1938) американский ученый , математик и почетный профессор в Стэнфордском университете .

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

Как писатель и ученый, Кнут создал WEB и CWEB компьютерных систем программирования , предназначенные для поощрения и облегчения грамотного программирования и разработал MIX / MMIX набор команд архитектуры . Кнут решительно выступает против предоставления патентов на программное обеспечение , выразив свое мнение в США по патентам и товарным знакам США и Европейской патентной организации .

биография

Ранний период жизни

Кнут родился в Милуоки , штат Висконсин , в германо-американцев Эрвин Кнут Генри и Луиза Мари Bohning. Его отец имел два рабочих места: бег небольшую типографию и преподавательскую бухгалтерию в Милуоки лютеранской средней школы . Дональд, студент Milwaukee лютеранской средней школы, получил академические награды там, особенно из-за хитроумными способами , которыми он думал о решении проблем. Например, в восьмом классе, он вошел в конкурс , чтобы найти количество слов , что буквы в «Giant Bar Циглера» можно переставить создать. Хотя судьи были только 2500 слов в их списке, Дональд нашел 4,500 слов, выиграв конкурс. Как призы, школа получила новый телевизор и достаточно конфет для всех своих однокашников , чтобы поесть.

образование

В 1956 году Кнут получил стипендию для случая технологического института (ныне часть Case Western Reserve University ) в Кливленде, штат Огайо. Он также присоединился к бета - Nu главы о братстве Theta Chi . При изучении физики в Case технологическом институте, Кнут был введен в IBM 650 , один из первых мэйнфреймов . После прочтения руководства пользователя компьютера, Кнут решил переписать сборку и код компилятора для машины , используемой в его школе, потому что он считал , что он мог бы сделать это лучше.

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

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

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

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

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

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

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

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

сочинения

Кнут является писателем, а также ученый. Кнут был назван «отцом анализа алгоритмов ».

Искусство программирования ( TAOCP )

В 1970 - х годах, Кнут описал компьютерную науку как «совершенно новое поле без реальной идентичности. И уровень имеющихся публикаций не был , что высоким. Многие из работ , выходящих были просто - напросто неправильно. ... Так что одна из моих мотиваций было поставить прямо в историю , которая была очень сильно сказано «. К 2011 году , первые три тома и части один из четырех объемов его серии были опубликованы. Конкретные математики: Фонд компьютерных наук . 2 - й изд, которая возникла с расширением раздела математического прелиминарии тома 1 TAOCP , также были опубликованы.

Билл Гейтс похвалил сложность предмета в Искусстве программирования , заявив: «Если вы думаете , что вы действительно хороший программист ... Вы обязательно должны прислать мне резюме , если вы можете прочитать все это.»

Другие работы

Кнут также автор Surreal чисел , математическая новелла на Джона Конвея «s теории множеств построения альтернативной системы чисел. Вместо того , чтобы просто объяснить эту тему, книга стремится показать развитие математики. Кнут хотел книгу , чтобы подготовить студентов к делать оригинальные, творческие исследования.

В 1995 году Кнут написал предисловие к книге A = B по Марко Петкавсек , Герберт Вильфа и Дорон Цейльбергер . Кнут также случайный вклад языковых головоломок в Word , Ways: The Journal Реабилитационной лингвистики .

Кнут также погрузились в рекреационных математике . Он внес статьи в журнале Recreational математики , начиная с 1960 года , и был признан в качестве одной из основных причин в Джозеф Мадчи «s математики на каникулы .

Кнут также появился в ряде Numberphile и Computerphile видео на YouTube , где он обсуждал темы от написания Surreal номера , почему он не использует электронную почту.

Работы, касающиеся религиозных убеждений Кнута

В дополнении к его трудам по информатике, Кнут, Лютеранский , является также автором 3:16 библейских тексты Горят , в которой он рассматривает Библию в процессе систематического отбора проб , а именно анализ главы 3, стих 16 каждого книга. Каждый стих сопровождается рендерингом в искусстве каллиграфии, внесенный группой каллиграфов под руководством Германа Цапф . Впоследствии он был приглашен дать ряд лекций по его 3:16 проекту, в результате чего в другой книге, вещи ученой редко высказывается , где он опубликовал лекцию «Бог и информатика» .

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

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

Компьютерные Musings

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

программирование

Цифровая верстка

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

Грамотное программирование

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

Кнут воплощал идею грамотного программирования в WEB системе. Тот же источник WEB используется для ткать файл TeX и запутаться в Pascal исходного файла. Это , в свою очередь , производит удобочитаемое описание программы и исполняемый файл соответственно. Поздняя итерация системы, CWEB , заменяет Pascal с C .

Кнут используется WEB программирования TeX и метафонта и опубликованы обе программы, как книги.

Личная жизнь

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

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

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

Забота о здоровье

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

Юмор

«Вложенные круглые скобки » -Donald Кнут (на Jacob Appelbaum рубашки «s в двух скобках), Джейкоб Аппельбаум, и Дональд Кнут

Кнут используется заплатить взнос находку в размере $ 2,56 за опечатки или ошибки , обнаруженные в его книгах, потому что «256 пенсов является один шестнадцатеричный доллар», и $ 0,32 за «ценные советы». Согласно статье , опубликованной в Массачусетском технологическом институте «s Technology Review , эти чеки награды Кнут являются„среди самых ценных трофеев computerdom в“. Кнуту пришлось прекратить отправку реальных проверок в 2008 году из - за банковское мошенничество, а вместо этого теперь дает каждому Finder об ошибке «депозитного сертификат» из публично перечисленного баланса в его фиктивном «Банке Сан - Serriffe ».

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

Кнут опубликовал свою первую «научную» статью в журнале школы в 1957 году под названием « Potrzebie система мер и весов». В ней он определил основную единицу из длины , как толщина Mad № 26, и назвал основной единицей силы «whatmeworry». Mad опубликовал статью в выпуске № 33 (июнь 1957).

Для того, чтобы продемонстрировать концепцию рекурсии , Кнут преднамеренно называют «Circular определение» и «определение», круговой друг с другом в индексе Искусство программирования , том 1 .

Предисловие Бетонных математик имеет следующий пункт:

Когда ДЭК учил Конкретную математику в Стэнфорд в первый раз, он объяснил несколько странного название, сказав , что это была его попытка научить курс математики , что было трудно , а не мягкие. Он сообщил , что, вопреки ожиданиям своих коллег, он не собирается преподавать теорию агрегатов, ни Стоуна теорему вложения , ни даже стоун-Чех . (Несколько студентов из гражданского инженерного отдела встал и тихо вышел из комнаты.)

На TUG 2010 конференции, Кнут объявил сатирический XML -На преемник TeX, под названием «Itex» ( произносится  [iː˨˩˦tɛks˧˥] , выполненный с колокольным звоном), который будет поддерживать такие функции, как произвольно масштабируемые иррациональные единицы , 3D печать , ввод от сейсмографов и сердечных мониторов, анимации и стереофонического звука.

Награды и почести

В 1971 году Кнут был удостоен первой ACM Грейс Мюррей Хоппер премии . Он получил множество других наград , включая премии Тьюринга , в Национальной медали науки , на Джоне фон Нейман медаль , и Киотской премию .

Кнут был избран почетным членом Британского компьютерного общества (DFBCS) в 1980 году в знак признания вклада Кнута в области информатики.

В 1990 годе он был удостоен единственным в своем роде ученого звания профессора Искусства программирования , который с тех пор был пересмотрен с профессором Заслуженным из Искусства программирования .

Кнут был избран в составе Национальной академии наук в 1975 г. В 1992 г. он стал ассоциированным членом Французской академии наук . Кроме того, в том же году он ушел из регулярных исследований и обучения в Стэнфордском университете , чтобы закончить Искусство программирования для ЭВМ . Он был избран иностранным членом Королевского общества (ForMemRS) в 2003 году .

Кнут был избран членом (первый класс Fellows) из Общества промышленной и прикладной математики в 2009 году за выдающийся вклад в математику. Он является членом Норвежской академии наук и литературы . В 2012 годе он стал членом в Американском математическом обществе . Другие награды и награды включают в себя:

Галерея

Публикации

Краткий список его публикаций включает:

Искусство программирования :

  1. --- (1997). Искусство программирования . 1: Основные алгоритмы (3 - е изд.). Addison-Wesley Professional. ISBN  978-0-201-89683-1 .
  2. --- (1997). Искусство программирования . 2: Получисленные алгоритмы (3 - е изд.). Addison-Wesley Professional. ISBN  978-0-201-89684-8 .
  3. --- (1998). Искусство программирования . 3: Сортировка и поиск (2 - е изд.). Addison-Wesley Professional. ISBN  978-0-201-89685-5 .
  4. --- (2011). Искусство программирования . 4A: Комбинаторные алгоритмы. Addison-Wesley Professional. ISBN  978-0-201-03804-0 .
  5. --- (2005). MMIX-A RISC Компьютер для нового тысячелетия . 1, пучки 1. ISBN  978-0-201-85392-6 .
  6. --- (2008). Искусство программирования . 4, пучки 0: Введение в комбинаторные алгоритмы и булевы функции. ISBN  978-0-321-53496-5 .
  7. --- (2009). Искусство программирования . 4, пучки 1: Битовые приемы и метода; Бинарные Решение диаграммы. ISBN  978-0-321-58050-4 .
  8. --- (2005). Искусство программирования . 4, пучки 2: Генерация всех кортежи и Перестановка. ISBN  978-0-201-85393-3 .
  9. --- (2005). Искусство программирования . 4, пучки 3: Генерация всех сочетания и Перегородка. ISBN  978-0-201-85394-0 .
  10. --- (2006). Искусство программирования . 4, пучки 4: Генерация всех дерев-История комбинаторной генерации. ISBN  978-0-321-33570-8 .
  11. --- (2018). Искусство программирования . 4, 5 пучков: Математическое Отборочные Перевождь; возврат; Танцевальные ссылки. ISBN  978-0-134-67179-6 .
  12. --- (2015). Искусство программирования . 4, 6 пучков: выполнимости. ISBN  978-0-134-39760-3 .

Компьютеры и Typesetting (все книги в твердом переплете , если не указано иное):

  1. --- (1984). Компьютеры и Typesetting . А, TeXbook. Чтение, MA : Addison-Wesley. ISBN  978-0-201-13447-6 ., Х + 483pp.
  2. --- (1984). Компьютеры и Typesetting . А, TeXbook. Чтение, MA : Addison-Wesley. ISBN  978-0-201-13448-3 . (мягкое покрытие).
  3. --- (1986). Компьютеры и Typesetting . B, TeX: Программа. Чтение, MA : Addison-Wesley. ISBN  978-0-201-13437-7 ., XVIII + 600pp.
  4. --- (1986). Компьютеры и Typesetting . С, METAFONTbook. Чтение, MA : Addison-Wesley. ISBN  978-0-201-13445-2 ., XII + 361pp.
  5. --- (1986). Компьютеры и Typesetting . С, METAFONTbook. Чтение, MA : Addison-Wesley. ISBN  978-0-201-13444-5 . (мягкое покрытие).
  6. --- (1986). Компьютеры и Typesetting . D, METAFONT: Программа. Чтение, MA : Addison-Wesley. ISBN  978-0-201-13438-4 ., XVIII + 566pp.
  7. --- (1986). Компьютеры и Typesetting . E, Компьютеры Современные Гарнитуры. Чтение, MA : Addison-Wesley. ISBN  978-0-201-13446-9 ., XVI + 588pp.
  8. --- (2000). Компьютеры и Typesetting . AE в штучной упаковке Набор. Чтение, MA : Addison-Wesley. ISBN  978-0-201-73416-4 .

Книги сборников:

  1. --- (1992). Грамотное программирование . Конспект лекций. Stanford, CA : Центр изучения языка и информации -CSLI. ISBN  978-0-937073-80-3 .
  2. --- (1996). Избранные труды по информатике . Конспект лекций. Stanford, CA : Центр по изучению языка и информационно-CSLi. ISBN  978-1-881526-91-9 .
  3. --- (1999). Digital Typography . Конспект лекций. Stanford, CA : Центр по изучению языка и информационно-CSLi. ISBN  978-1-57586-010-7 .
  4. --- (2000). Избранные труды по анализу алгоритмов . Конспект лекций. Stanford, CA : Центр по изучению языка и информационно-CSLi. ISBN  978-1-57586-212-5 .
  5. --- (2003). Избранные труды по Компьютерным Языкам (ткань) |format=требует |url=( помощи ) . Конспект лекций. Stanford, CA : Центр по изучению языка и информационно-CSLi. ISBN  978-1-57586-381-8 ., ISBN  1-57586-382-0 (мягкая обложка)
  6. --- (2003). Избранные труды по дискретной математике (ткань) |format=требует |url=( помощи ) . Конспект лекций. Stanford, CA : Центр по изучению языка и информационно-CSLi. ISBN  978-1-57586-249-1 ., ISBN  1-57586-248-4 (мягкая обложка)
  7. Дональд Е. Кнут, Избранные труды по проектированию алгоритмов (Стэнфорд, Калифорния:. Центр по изучению языка и информационно-CSLi Lecture Notes, не 191), 2010. ISBN  1-57586-583-1 (ткань), ISBN  1 -57586-582-3 (мягкая обложка)
  8. Дональд Е. Кнут, Избранные труды по развлечениям и играм (Стэнфорд, Калифорния:. Центр по изучению языка и информационно-CSLi Lecture Notes, не 192), 2011. ISBN  978-1-57586-585-0 (ткань), ISBN  978-1-57586-584-3 (мягкая обложка)
  9. Дональд Е. Кнут, Компаньон Документов Дональда Кнута (Стэнфорд, Калифорния: Центр по изучению языка и информационно-CSLi Lecture Notes, нет 202.), 2011. ISBN  978-1-57586-635-2 (ткань) , ISBN  978-1-57586-634-5 (мягкая обложка)

Другие книги:

  1. Грэм, Рональд L ; Кнут, Дональд Е .; Patashnik, Орен (1994). Конкретная математика: Основа для информатики (изд.). Reading, MA: Addison-Wesley. ISBN  978-0-201-55802-9 . MR  1397498 . XIV + 657 с.
  2. Кнут, Дональд Эрвин (1974). Surreal номер: как два бывших студенты свернули на чистую математику и нашли полное счастье: математическую повесть . Addison-Wesley. ISBN  978-0-201-03812-5 .
  3. Дональд Е. Кнут, Стэнфорд GraphBase: Платформа для комбинаторной Computing (Нью - Йорк, ACM Press) 1993 вторая книга в мягкой обложке печать 2009. ISBN  0-321-60632-9
  4. Дональд Е. Кнут, 3:16 Библия Тексты Освещенный (Мэдисон, Висконсин: AR Издание), 1990. ISBN  0-89579-252-4
  5. Дональд Е. Кнут, вещи Программист Редко говорят о (Центре по изучению языка и информационно-CSLi лекции не Примечания не 136), 2001. ISBN  1-57586-326-X
  6. Дональд Е. Кнут, MMIXware: A RISC Компьютер для третьего тысячелетия (Heidelberg: Springer-Verlag- Lecture Notes в области компьютерных наук, № 1750) . , 1999. VIII + 550pp. ISBN  978-3-540-66938-8
  7. Дональд Е. Кнут и Сильвио Леви, CWEB Система Structured документации (Reading, Массачусетс: Addison-Wesley), 1993. IV + 227pp. ISBN  0-201-57569-8 . В- третьих печати 2001 с поддержкой гипертекста, II + 237 с.
  8. Дональд Е. Кнут, Трейси Л. Larrabee, и Пол М. Робертс, Математическая написание (Вашингтон, округ Колумбия: Математическая ассоциация Америки), 1989. II + 115pp
  9. Дэниел Х. Грин и Дональд Е. Кнут, Математика для анализа алгоритмов (Бостон: Birkhäuser), 1990. VIII + 132pp.
  10. Дональд Е. Кнут, Конюшни Свадьбы: др Leurs отношения ауес d'Autres combinatoires задачи и их (Монреаль: Les Нажимает де l'Université де Монреаль), 1976. 106pp.
  11. Дональд Е. Кнут, Аксиомы и шелуха (Гейдельберг: Springer-Verlag-Lecture Notes в области компьютерных наук, № 606) . , 1992. IX + 109pp. ISBN  3-540-55611-7

Смотрите также

Рекомендации

Список используемой литературы

внешняя ссылка