Джон Луис Бентли (родился 20 февраля 1953 г.) - американский учёный-компьютерщик , известный своим вкладом в компьютерное программирование, алгоритмы и исследования структур данных.
Бентли получил степень бакалавра математических наук в Стэнфордском университете в 1974 году. В это время он разработал свою наиболее цитируемую работу — эвристический алгоритм разделения дерева kd , опубликованный в 1975 году. [2]
Он получил степень магистра и доктора философии в 1976 году в Университете Северной Каролины в Чапел-Хилл . Будучи студентом, он также проходил стажировку в Исследовательском центре Xerox в Пало-Альто и Стэнфордском центре линейных ускорителей . [1]
После получения докторской степени он в течение шести лет преподавал программирование и компьютерную архитектуру в качестве преподавателя в Университете Карнеги-Меллон в качестве доцента кафедры информатики и математики . [1] В CMU среди его студентов были Брайан Рид , Джон Оустерхаут , Джефф Эппингер , Джошуа Блох и Джеймс Гослинг , и он был одним из советников Чарльза Лейзерсона . [3] В 1982 году он опубликовал книгу «Написание эффективных программ». [4]
В 1982 году [5] Бентли перешёл в Исследовательский центр компьютерных наук в Bell Laboratories , где он был почётным членом технического персонала. В этот период он разработал различные языки, продолжил исследования алгоритмов и разработал различное программное обеспечение и продукты для систем связи. [6] Вместе с Дугом Макилроем он является соавтором оптимизированного алгоритма быстрой сортировки . [7]
Он покинул Bell Labs в 2001 году и до 2013 года работал в Avaya Labs Research. В этот период он занимался разработкой корпоративных коммуникационных систем. [5]
Он нашел оптимальное решение для двумерного случая задачи Клее о мере : по заданному набору из n прямоугольников найти площадь их объединения. Он и Томас Оттманн изобрели алгоритм Бентли-Оттмана , эффективный алгоритм для поиска всех пересекающихся пар среди набора отрезков прямой.
Он вел колонку «Жемчужины программирования» в журнале Communications of the ACM , а позже собрал статьи в две одноименные книги в 1986 и 1988 годах. [8] [9]
Bentley получил награду доктора Добба за выдающиеся достижения в области программирования в 2004 году.
Он альпинист , поднявшийся на более чем сто пиков высотой 4000 футов в северо-восточной части США. [6]