Джон Луи Бентли (родился 20 февраля 1953 г.) - американский ученый-компьютерщик, которому приписывают основанный на эвристике алгоритм разбиения k -d tree .
Джон Бентли | |
---|---|
Родившийся | Джон Луи Бентли 20 февраля 1953 г. Лонг-Бич, Калифорния , [1] США |
Альма-матер | Университет Северной Каролины в Чапел-Хилл Стэнфордский университет |
Заголовок | Специалист в области информатики |
Научная карьера | |
Учреждения | Avaya |
Тезис | Алгоритмы разделяй и властвуй для решения ближайших точечных задач в многомерном пространстве (1976) |
Докторант | Дональд Форд Станат |
Докторанты |
Образование и карьера
Бентли получил степень бакалавра математических наук в Стэнфордском университете в 1974 году и степень магистра и доктора философии в 1976 году в Университете Северной Каролины в Чапел-Хилл ; Во время учебы он также проходил стажировку в Исследовательском центре Xerox в Пало-Альто и Стэнфордском центре линейных ускорителей . [1] После получения докторской степени он поступил на факультет Университета Карнеги-Меллона в качестве доцента компьютерных наук и математики . [1] В CMU среди его студентов были Брайан Рид , Джон Остерхаут , Джефф Эппингер , Джошуа Блох и Джеймс Гослинг , и он был одним из советников Чарльза Лейзерсона . [2] Позже Бентли переехал в Bell Laboratories , где вместе с Дугом Макилроем он разработал оптимизированный алгоритм быстрой сортировки . [3]
Он нашел оптимальное решение для двумерного случая проблемы меры Кли : по набору из n прямоугольников найти площадь их объединения. Он и Томас Оттманн изобрели алгоритм Бентли – Оттмана , эффективный алгоритм для поиска всех пересекающихся пар среди набора отрезков прямых. Он вел колонку Programming Pearls для журнала ACM , а позже собрал статьи в две одноименные книги.
Bentley получил награду доктора Добба за выдающиеся достижения в программировании в 2004 году.
Библиография
Рекомендации
- ^ a b c Биография от Bentley, JL; Ottmann, Т.А. (1979), "Алгоритмы для представления и подсчета геометрических пересечений" , IEEE Transactions на компьютерах , C-28 (9): 643-647, DOI : 10.1109 / TC.1979.1675432 , S2CID 1618521.
- ↑ Джон Луи Бентли в проекте « Математическая генеалогия»
- ^ Джон Л. Бентли; М. Дуглас Макилрой (ноябрь 1993 г.). «Разработка функции сортировки». Программное обеспечение - практика и опыт . 23 (11).
Внешние ссылки
- www.cs.bell-labs.com/cm/cs/pearls/code.html на GitHub
- Пресс-релиз Lucent Technologies (мертвая ссылка)
- ошибка в двоичном поиске Джона Бентли - исследование google
- Язык программирования C , обе редакции показали решение ошибки, описанной выше. Во втором издании он находится в разделе 6.4 (Указатели на структуры).