喬恩·本特利 (計算機科學家)
外观
喬恩·本特利 Jon Bentley | |
---|---|
出生 | Jon Louis Bentley 1953年2月20日 美国加利福尼亞州長灘[1] |
母校 | 史丹佛大學(BS) 北卡羅來納大學教堂山校區(MS、PhD) |
科学生涯 | |
机构 | 亞美亞 |
论文 | Divide and conquer algorithms for closest point problems in multidimensional space(1976) |
博士導師 | Donald Ford Stanat |
博士生 | 查爾斯·E·雷瑟爾森 凱瑟琳·麥姬奇 詹姆斯·B·薩克斯 |
喬恩·路易斯·本特利(英語:Jon Louis Bentley,1953年2月20日—)是一名美國計算機科學家,他提出了基於啟發式的分區演算法k-d樹。
生平
[编辑]本特利於1974年獲得史丹佛大學數學科學學士學位,1976年獲得北卡羅來納大學教堂山校區數學科學碩士和博士學位;在校期間,他還曾在施樂帕洛阿爾托研究中心和史丹佛直線加速器中心實習[1]。獲得博士學位後,他進入卡內基美隆大學任教,擔任電腦科學和數學助理教授[1]。在卡內基美隆大學,他的學生包括布萊恩·里德、約翰·奧斯特豪特、傑夫·埃平格、約書亞·布洛克和詹姆斯·高斯林,他也是查爾斯·E·雷瑟爾森的導師之一[2]。後來,本特利來到貝爾實驗室,與道格拉斯·麥克羅伊合著了一種優化的快速排序演算法[3]。
他找到克利度量問題二維情形的最適解:給定一組 n 個矩形,求它們的結合面積。他和托馬斯·奧特曼(Thomas Ottmann)發明本特利-奧特曼演算法,這是一種在線段集合中尋找所有相交線對的高效演算法。他為《ACM通訊》雜誌撰寫「程式設計珍珠」專欄,後來將這些文章匯集成兩本同名書籍。
2004年,本特利榮獲Dobb博士卓越程式設計獎。
參考書目
[编辑]- Programming Pearls (2nd edition), ISBN 0-201-65788-0.
- More Programming Pearls: Confessions of a Coder, ISBN 0-201-11889-0.
- Writing Efficient Programs, ISBN 0-13-970244-X.
- Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space, Ph.D. thesis.[4]
參考資料
[编辑]- ^ 1.0 1.1 1.2 Biography from Bentley, J. L.; Ottmann, T. A., Algorithms for reporting and counting geometric intersections (PDF), IEEE Transactions on Computers, 1979, C–28 (9): 643–647, S2CID 1618521, doi:10.1109/TC.1979.1675432, (原始内容存档于September 22, 2017).
- ^ Jon Louis Bentley在數學譜系計畫的資料。
- ^ Jon L. Bentley; M. Douglas McIlroy. Engineering a sort function. Software—Practice & Experience. November 1993, 23 (11).
- ^ Bentley, Jon L. Divide and conquer algorithms for closest point problems in multidimensional space.. 1976.
外部連結
[编辑]- www.cs.bell-labs.com/cm/cs/pearls/code.html on GitHub
- Lucent Technologies press release [失效連結]
- bug in Jon Bentley's binary search (页面存档备份,存于互联网档案馆) - google research
- The C Programming Language, both editions had shown the solution to the bug discussed in the above. In the second edition, it is in section 6.4 (Pointers to Structures).