Джон Бентли | |
---|---|
Родился | Джон Луи Бентли 20 февраля 1953 г. Лонг-Бич, Калифорния , [1] США |
Альма-матер | Университет Северной Каролины в Чапел-Хилл Стэнфордский университет |
Заголовок | Специалист в области информатики |
Научная карьера | |
Учреждения | Avaya |
Тезис | Алгоритмы разделяй и властвуй для решения ближайших точечных задач в многомерном пространстве (1976) |
Докторант | Дональд Форд Станат |
Докторанты |
Джон Луи Бентли (родился 20 февраля 1953 г.) - американский ученый-компьютерщик, которому приписывают основанный на эвристике алгоритм разбиения k -d tree .
Образование и карьера
Бентли получил степень бакалавра математических наук в Стэнфордском университете в 1974 году и степень магистра и доктора философии в 1976 году в Университете Северной Каролины в Чапел-Хилл ; Во время учебы он также проходил стажировку в Исследовательском центре Xerox в Пало-Альто и Стэнфордском центре линейных ускорителей . [1] После получения докторской степени он поступил на факультет Университета Карнеги-Меллона в качестве доцента компьютерных наук и математики . [1] В CMU среди его студентов были Брайан Рид , Джон Остерхаут , Джефф Эппингер , Джошуа Блох., и Джеймс Гослинг , и он был одним из советников Чарльза Лейзерсона . [2] Позже Бентли переехал в Bell Laboratories , где вместе с Дугом Макилроем он разработал оптимизированный алгоритм быстрой сортировки . [3]
Он нашел оптимальное решение для двумерного случая проблемы меры Кли : по заданному набору n прямоугольников найти площадь их объединения. Он и Томас Оттманн изобрели алгоритм Бентли – Оттмана , эффективный алгоритм для поиска всех пересекающихся пар среди набора отрезков прямых. Он написал колонку Programming Pearls для журнала ACM , а позже собрал статьи в две одноименные книги.
Bentley получил награду доктора Добба за выдающиеся достижения в программировании в 2004 году.
Библиография
- Жемчуг программирования (2-е издание), ISBN 0-201-65788-0 .
- Дополнительные жемчужины программирования: признания кодировщика , ISBN 0-201-11889-0 .
- Написание эффективных программ , ISBN 0-13-970244-X .
- Алгоритмы разделяй и властвуй в многомерном пространстве , доктор философии. Тезис.
Ссылки
- ^ 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 (Указатели на структуры).