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