唐納德·布魯斯·約翰遜

唐納德·布魯斯·約翰遜(英語:Donald Bruce Johnson,1933年12月16日—1994年11月10日[1][2][3]),美國計算機科學家,算法研究員,達特茅斯學院的計算機科學系主任[4]

個人經歷

編輯

1973年,約翰遜在康奈爾大學取得了他的博士學位[5]。之後他又先後擔任賓夕法尼亞州立大學計算機科學系教授和達特茅斯學院數學系教授職位[5]。1994年,達特茅斯學院計算機科學系成立[6] ,約翰遜任系主任[4]

學術貢獻

編輯

約翰遜發明了數據結構d叉堆英語D-ary heap[7][8],此外提出了計算最短路約翰遜算法英語Johnson's algorithm[9][10]

參考文獻

編輯
  1. ^ date from Author's thesis biographyJohnson, Donald B., Algorithms for shortest paths 
  2. ^ Death date from author listing of Armen, Chris; Johnson, Donald B., Deterministic leader election on the asynchronous QRQW PRAM, Parallel Processing Letters, 1996, 6 (2): 247–250, doi:10.1142/S0129626496000248 .
  3. ^ Johnson's home page at Dartmouth as of 1997. [2017-04-23]. (原始內容存檔於1997-06-05). , retrieved 2011-01-04.
  4. ^ 4.0 4.1 Gloor, P. A., Acknowledgements, Elements of hypermedia design: techniques for navigation & visualization in cyberspace, Birkhäuser: xvii, 1997 .
  5. ^ 5.0 5.1 Donald Bruce Johnson數學譜系計畫的資料。.
  6. ^ History of Computer Science at Dartmouth College頁面存檔備份,存於網際網路檔案館), retrieved 2011-01-04.
  7. ^ Johnson, D. B., Priority queues with update and finding minimum spanning trees, Information Processing Letters, 1975, 4: 53–57, doi:10.1016/0020-0190(75)90001-0 .
  8. ^ Tarjan, R. E., 3.2. d-heaps, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics 44, Society for Industrial and Applied Mathematics: 34–38, 1983 .
  9. ^ Johnson, Donald B., Efficient algorithms for shortest paths in sparse networks, ACM期刊, 1977, 24 (1): 1–13, doi:10.1145/321992.321993 .
  10. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, 算法导论, MIT Press and McGraw-Hill, 2001, ISBN 978-0-262-03293-3 . Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.