Дональд Эрвин Кнут ( / kə ˈ n uː θ / [3] kə- NOOTH ; родился 10 января 1938 года) — американский учёный - компьютерщик , математик и почётный профессор Стэнфордского университета . Он является лауреатом Премии Тьюринга ACM 1974 года , неофициально считающейся Нобелевской премией в области информатики. [4] Кнута называли «отцом анализа алгоритмов ». [5]
Кнут — автор многотомного труда The Art of Computer Programming . Он способствовал развитию строгого анализа вычислительной сложности алгоритмов и систематизации формальных математических методов для него. При этом он также популяризировал асимптотические обозначения . Помимо фундаментального вклада в несколько областей теоретической информатики , Кнут является создателем компьютерной системы набора текста TeX , связанного с ней языка определения шрифтов и системы рендеринга METAFONT , а также семейства шрифтовComputer Modern .
Как писатель и ученый, Кнут создал системы компьютерного программирования WEB и CWEB , предназначенные для поощрения и облегчения грамотного программирования , а также разработал архитектуры набора команд MIX / MMIX . Он решительно выступает против выдачи патентов на программное обеспечение и выразил свое мнение в Ведомстве США по патентам и товарным знакам и Европейской патентной организации .
Дональд Кнут родился в Милуоки , штат Висконсин , в семье Эрвина Генри Кнута и Луизы Мари Бонинг. [6] Он описывает свое наследие как «лютеранского немца Среднего Запада». [7] : 66 Его отец владел небольшим типографским бизнесом и преподавал бухгалтерский учет. [8] Будучи учеником лютеранской средней школы Милуоки , Кнут придумал гениальные способы решения проблем. Например, в восьмом классе он принял участие в конкурсе на определение количества слов, которые можно было бы составить из букв в «Гигантском батончике Циглера»; судьи определили 2500 таких слов. Выиграв время вдали от школы из-за ложной боли в животе и решая задачу по-другому, Кнут использовал полный словарь и определил, можно ли составить каждую словарную статью с использованием букв во фразе. Используя этот алгоритм, он определил более 4500 слов и выиграл конкурс. [7] : 3 В качестве приза школа получила новый телевизор и достаточное количество шоколадных батончиков, чтобы их могли съесть все его одноклассники. [9]
Кнут получил стипендию по физике в Технологическом институте Кейса (ныне часть Университета Кейс Вестерн Резерв ) в Кливленде , штат Огайо, поступив в 1956 году . [10] Он также присоединился к отделению Бета Ну братства Тета Чи . Изучая физику в Кейсе, Кнут познакомился с IBM 650 , одним из первых коммерческих компьютеров . Прочитав руководство к компьютеру, Кнут решил переписать код ассемблера и компилятора для машины, используемой в его школе, потому что считал, что сможет сделать это лучше. [11]
В 1958 году Кнут создал программу, призванную помочь школьной баскетбольной команде побеждать в играх. [12] Он присваивал игрокам «ценности», чтобы оценить их вероятность набрать очки, - новый подход, о котором позже сообщили Newsweek и CBS Evening News . [11]