stringtranslate.com

Дональд Б. Джонсон

Дональд Брюс Джонсон (16 декабря 1933 г. – 10 сентября 1994 г.) [1] [2] [3] был американским ученым-компьютерщиком, исследователем в области разработки и анализа алгоритмов , а также основателем кафедры компьютерных наук в Дартмутском колледже . [4]

Джонсон получил степень доктора философии в Корнеллском университете в 1973 году под руководством Дэвида Грайса . [5] Он занял должность преподавателя на кафедре компьютерных наук в Университете штата Пенсильвания , а затем перешел на кафедру математики в Дартмуте. [5] Когда в 1994 году была основана кафедра компьютерных наук в Дартмуте, [6] он стал ее первым заведующим. [4]

Джонсон изобрел структуру данных d -арной кучи [7] [ 8] , а также известен своим алгоритмом для задачи поиска кратчайшего пути для всех пар элементов [9] [10] .

Ссылки

  1. ^ дата из биографии автора диссертации Джонсон, Дональд Б., Алгоритмы поиска кратчайших путей
  2. ↑ Дата смерти из списка авторов Армена, Криса; Джонсон, Дональд Б. (1996), «Детерминированные выборы лидера на асинхронном QRQW PRAM», Parallel Processing Letters , 6 (2): 247–250, doi :10.1142/S0129626496000248.
  3. ^ "Домашняя страница Джонсона в Дартмуте по состоянию на 1997 год". Архивировано из оригинала 5 июня 1997 года . Получено 23 апреля 2017 года .{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ), получено 04.01.2011.
  4. ^ ab Gloor, PA (1997), "Благодарности", Элементы дизайна гипермедиа: методы навигации и визуализации в киберпространстве , Birkhäuser, стр. xvii.
  5. ^ Дональд Брюс Джонсон в проекте «Генеалогия математики» .
  6. ↑ История компьютерных наук в Дартмутском колледже. Архивировано 31 октября 2010 г. на Wayback Machine , получено 04.01.2011.
  7. ^ Джонсон, ДБ (1975), «Приоритетные очереди с обновлением и поиском минимальных остовных деревьев», Information Processing Letters , 4 (3): 53–57, doi :10.1016/0020-0190(75)90001-0.
  8. ^ Tarjan, RE (1983), "3.2. d -heaps", Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS-NSF по прикладной математике, т. 44, Общество промышленной и прикладной математики , стр. 34–38.
  9. ^ Джонсон, Дональд Б. (1977), «Эффективные алгоритмы для кратчайших путей в разреженных сетях», Журнал ACM , 24 (1): 1–13, doi : 10.1145/321992.321993 , S2CID  207678246.
  10. ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), Введение в алгоритмы , MIT Press и McGraw-Hill, ISBN 978-0-262-03293-3. Раздел 25.3, «Алгоритм Джонсона для разреженных графов», стр. 636–640.