stringtranslate.com

Джозеф Ф. Трауб

Джозеф Фредерик Трауб (24 июня 1932 г. — 24 августа 2015 г.) — американский учёный-компьютерщик . Он был профессором компьютерных наук имени Эдвина Говарда Армстронга в Колумбийском университете и приглашенным профессором в Институте Санта-Фе . Он занимал должности в Bell Laboratories , Вашингтонском университете , Университете Карнеги — Меллона и Колумбийском университете, а также должности в академических отпусках в Стэнфорде , [3] Беркли , Принстоне , Калифорнийском технологическом институте и Техническом университете Мюнхена . [4]

Трауб был автором или редактором десяти монографий и около 120 статей по информатике, математике, физике, финансам и экономике. [4] В 1959 году он начал свою работу над оптимальной теорией итераций, завершившуюся его монографией 1964 года « Итеративные методы решения уравнений» . Впоследствии он стал пионером работы с Генриком Возняковским по вычислительной сложности, применяемой к непрерывным научным проблемам ( информационная сложность ). Он сотрудничал в создании важных новых алгоритмов, включая алгоритм Дженкинса-Трауба для полиномиальных нулей , а также алгоритмы Шоу-Трауба, [2] [5] Кунга-Трауба, [6] и Брента-Трауба. Одной из областей его исследований были непрерывные квантовые вычисления. [7] По состоянию на 10 ноября 2015 года его работы были процитированы 8500 раз, и его индекс Хирша составил 35. [8]

С 1971 по 1979 год Трауб возглавлял факультет компьютерных наук в Университете Карнеги-Меллона в критический период. С 1979 по 1989 год он был основателем факультета компьютерных наук в Колумбийском университете. С 1986 по 1992 год он был основателем и председателем Совета по компьютерным наукам и телекоммуникациям Национальной академии наук и снова занимал этот пост в 2005–2009 годах. [9] Трауб был основателем и редактором Annual Review of Computer Science (1986–1990) [10] и главным редактором Journal of Complexity (1985–2015). [11] Его исследовательская работа и работа по созданию институтов оказали большое влияние на область компьютерных наук . [4]

Ранняя карьера

Трауб учился в Bronx High School of Science , где он был капитаном и первым членом шахматной команды. После окончания City College of New York он поступил в Columbia в 1954 году, намереваясь получить докторскую степень по физике. В 1955 году по совету однокурсника Трауб посетил исследовательскую лабораторию IBM Watson в Columbia. В то время это было одно из немногих мест в стране, где студент мог получить доступ к компьютерам. Трауб обнаружил, что его навыки алгоритмического мышления идеально сочетаются с компьютерами. В 1957 году он стал стипендиатом Watson через Columbia. Его диссертация была посвящена вычислительной квантовой механике . Его докторская степень 1959 года посвящена прикладной математике , поскольку степени в области компьютерных наук еще не были доступны. (Действительно, в Columbia не было кафедры компьютерных наук, пока Трауба не пригласили туда в 1979 году, чтобы основать кафедру.) [12] [4]

Карьера

В 1959 году Трауб присоединился к Исследовательскому отделу Bell Laboratories в Мюррей-Хилл, штат Нью-Джерси. Однажды коллега спросил его, как вычислить решение определенной задачи. Трауб мог придумать несколько способов решения задачи. Какой был оптимальный алгоритм, то есть метод, который минимизировал бы требуемые вычислительные ресурсы? К его удивлению, не существовало теории оптимальных алгоритмов. (Фраза вычислительная сложность , которая является изучением минимальных ресурсов, требуемых для решения вычислительных задач, не была введена до 1965 года.) У Трауба было ключевое понимание того, что оптимальный алгоритм для решения непрерывной задачи зависит от доступной информации. Это в конечном итоге привело к области информационной сложности . Первой областью, в которой Трауб применил свое понимание, было решение нелинейных уравнений. Это исследование привело к монографии 1964 года Итеративные методы решения уравнений . [12] [6] которая все еще находится в печати. ​​[13]

В 1966 году Трауб провел годичный отпуск в Стэнфордском университете , где познакомился со студентом по имени Майкл Дженкинс. Вместе они разработали алгоритм Дженкинса-Трауба для полиномиальных нулей , который был опубликован в качестве докторской диссертации Дженкинса. Этот алгоритм до сих пор является одним из наиболее широко используемых методов для этой задачи и включен во многие учебники. [14] [1]

В 1970 году Трауб стал профессором в Университете Вашингтона , а в 1971 году он стал главой факультета компьютерных наук Карнеги-Меллона . [15] Факультет был довольно небольшим, но все еще включал в себя таких «гигантов», как Аллен Ньюэлл и Герберт А. Саймон . К 1978 году под руководством Трауба факультет вырос до примерно 50 преподавателей и исследователей. [16]

Одним из аспирантов Трауба был Х. Т. Кунг , ныне профессор Гарварда. Они создали алгоритм Кунга-Трауба для вычисления расширения алгебраической функции. Они показали, что вычисление первых членов не сложнее, чем умножение двух полиномов -й степени. [6] [17] [18]

В 1973 году Трауб пригласил Генрика Возняковского посетить CMU . [1] Они были пионерами в области сложности, основанной на информации , став соавторами трех монографий и многочисленных статей. Возняковский стал профессором как в Колумбийском университете , так и в Варшавском университете , Польша. [19]

В 1978 году, во время творческого отпуска в Беркли , он был нанят Питером Ликинсом, чтобы стать основателем и председателем кафедры компьютерных наук в Колумбийском университете и профессором компьютерных наук имени Эдвина Говарда Армстронга . Он занимал должность председателя в 1979–1989 годах. [20]

В 1980 году он стал соавтором A General Theory of Optimal Algorithms , совместно с Возняковским. Это была первая исследовательская монография по информационной сложности. [21] Грег Васильковский присоединился к Траубу и Возняковскому в двух других монографиях Information, Uncertainty, Complexity , Addison-Wesley, 1983, [22] и Information-Based Complexity , Academic Press, 1988. [23]

В 1985 году Трауб стал основателем и главным редактором журнала Journal of Complexity . [2] [24] Это был, вероятно, первый журнал, в названии которого слово «сложность» использовалось в смысле вычислительной сложности . [25]

В 1986 году Национальные академии попросили Трауба сформировать Совет по компьютерным наукам. Первоначальное название Совета было Совет по компьютерным наукам и технологиям (CSTB). Несколько лет спустя CSTB также было предложено отвечать за телекоммуникации, поэтому он был переименован в Совет по компьютерным наукам и телекоммуникациям, сохранив аббревиатуру CSTB. Совет занимается важнейшими национальными вопросами в области компьютерных наук и телекоммуникаций . Трауб был председателем-основателем в 1986–1992 годах и снова занимал этот пост в 2005–2009 годах. [12]

В 1990 году Трауб преподавал в летней школе Института Санта-Фе (SFI). С тех пор он играл различные роли в SFI. [2] В девяностых годах он организовал серию семинаров по пределам научного знания, финансируемых Фондом Альфреда П. Слоуна . Целью было обогатить науку таким же образом, как работа Гёделя и Тьюринга по пределам математики обогатила эту область. Была проведена серия семинаров по пределам в различных дисциплинах: физике, экономике и геофизике. [26]

Начиная с 1991 года Трауб был соорганизатором международного семинара по теме «Непрерывные алгоритмы и сложность» в замке Дагштуль, Германия. Многие доклады на семинаре посвящены сложности, основанной на информации, а в последнее время — непрерывному квантовому вычислению. [27]

Трауб был приглашен Национальной академией деи Линче в Риме, Италия, для представления Lezione Lincee 1993 года. [12] Он решил прочитать цикл из шести лекций в Scuola Normale в Пизе. Он пригласил Артура Вершульца присоединиться к нему в публикации лекций. Лекции появились в расширенном виде как Complexity and Information , Cambridge University Press , 1998. [28] [29]

В 1994 году он попросил аспиранта Спассимира Паскова сравнить метод Монте-Карло (MC) с методом квази-Монте-Карло (QMC) при расчете обеспеченного ипотечного обязательства (CMO), который Трауб получил от Goldman Sachs . Это включало численное приближение ряда интегралов в 360 измерениях. К удивлению исследовательской группы Пасков сообщил, что QMC всегда превосходил MC в этой задаче. Специалисты по финансам всегда использовали MC для таких задач, и эксперты по теории чисел считали, что QMC не следует использовать для интегралов размерности больше 12. Пасков и Трауб сообщили о своих результатах ряду фирм с Уолл-стрит , что вызвало значительный первоначальный скептицизм. Впервые они опубликовали результаты в 1995 году. [30] [31] [32] Теория и программное обеспечение были значительно улучшены Анаргиросом Папагеоргиу. Сегодня QMC широко используется в финансовом секторе для оценки финансовых деривативов . QMC не является панацеей для всех многомерных интегралов. [33] Продолжаются исследования по характеристике задач, для которых QMC превосходит MC.

В 1999 году Трауб получил медаль мэра за науку и технологии. Решения относительно этой награды принимаются Нью-Йоркской академией наук . Медаль была вручена мэром Руди Джулиани на церемонии в особняке Грейси . [4]

Трауб и его коллеги также работали над непрерывными квантовыми вычислениями. Закон Мура — это эмпирическое наблюдение, согласно которому количество функций на чипе удваивается примерно каждые 18 месяцев. Это правило действует с начала 60-х годов и ответственно за революцию в области компьютеров и телекоммуникаций. Широко распространено мнение, что закон Мура перестанет действовать через 10–15 лет при использовании кремниевой технологии. Поэтому существует интерес к созданию новых технологий. Одним из кандидатов являются квантовые вычисления . Это создание компьютера с использованием принципов квантовой механики . Мотивация заключается в том, что большинство проблем в физической науке, инженерии и математических финансах имеют непрерывные математические модели. [34]

В 2005 году Трауб передал архивные материалы в библиотеку Университета Карнеги-Меллона. Эта коллекция оцифровывается. [4]

Патенты на алгоритмы и программное обеспечение

Патенты США US5940810 и US0605837 были выданы Траубу и др. на систему программного обеспечения FinDer и были переданы Колумбийскому университету. Эти патенты охватывают применение хорошо известной техники (последовательности с низким расхождением) к хорошо известной проблеме (оценка ценных бумаг). [35]

Личная жизнь

У Трауба было две дочери, Клаудия Трауб-Купер и Хиллари Спектор. Он жил в Манхэттене и Санта-Фе со своей женой, автором Памелой МакКордак . Он часто высказывал свое мнение о текущих событиях, отправляя свои статьи в New York Times, которая часто публиковала его комментарии. [36] [37]

Избранные награды и отличия

Избранные публикации

Избранные монографии

Избранные статьи

Ссылки

  1. ^ abc Gelenbe, Erol (2011). «Интервью с Джозефом Ф. Траубом». Ubiquity . 2011 (февраль): 1–15. doi : 10.1145/1940721.1941856 . S2CID  34530233.
  2. ^ abcde Крейн, Линда (25 августа 2015 г.). "Памяти: Джозеф Ф. Трауб | Кафедра компьютерных наук, Колумбийский университет". Columbia Engineering . Получено 4 апреля 2023 г. .
  3. ^ "Биография | Коллекция Джозефа Ф. Трауба". Университет Карнеги-Меллона, Университетские библиотеки . Получено 4 апреля 2023 г.
  4. ^ abcdefg "Joseph Traub". Цифровые коллекции Университета Карнеги-Меллона . Получено 4 апреля 2023 г.
  5. ↑ Шоу, Мэри; Трауб, Дж. Ф. (1 января 1974 г.). «О числе умножений для вычисления многочлена и некоторых его производных». Журнал ACM . 21 : 161–167. doi : 10.1145/321796.321810 . S2CID  10595083.
  6. ^ abc Petković, Miodrag S.; Neta, Beny; Petković, Ljiljana D.; Džunić, Jovana (январь 2014 г.). "Многоточечные методы решения нелинейных уравнений: обзор" (PDF) . Прикладная математика и вычисления . 226 : 635–660. doi :10.1016/j.amc.2013.10.072. S2CID  2499424 . Получено 4 апреля 2023 г. .
  7. ^ Новак, Эрих (2009). "Генрик Возняковский и сложность непрерывных проблем". Очерки о сложности непрерывных проблем (PDF) . Цюрих, Швейцария: Европейское математическое общество. ISBN 978-3-03719-069-2. Получено 4 апреля 2023 г. .
  8. ^ "Статистика Google Scholar для JF Traub".
  9. ^ abc "Computer Pioneers - Joseph Frederick Traub". Институт инженеров по электротехнике и электронике . Получено 4 апреля 2023 г.
  10. ^ Кауфманн, Уильям (июнь 1986 г.). «Предисловие». Annual Review of Computer Science . 1 (1): annurev.cs.1.111406.100001. doi :10.1146/annurev.cs.1.111406.100001 . Получено 13 сентября 2021 г.
  11. ^ Лор, Стив (26 августа 2015 г.). «Джозеф Ф. Трауб, 83 года, умер; один из первых защитников компьютерных наук». The New York Times . Получено 4 апреля 2023 г.
  12. ^ abcde Национальная инженерная академия (2022). "Джозеф Ф. Трауб 1932–2015". Мемориальные почести. Том 24. Вашингтон, округ Колумбия: The National Academies Press. ISBN 978-0-309-28717-3. Получено 4 апреля 2023 г. .
  13. ^ "Итерационные методы решения уравнений". Американское математическое общество . Получено 15 ноября 2021 г.
  14. ^ Биннер, Дэвид (6 марта 2008 г.). «Поиск полиномиальных корней с помощью алгоритма Дженкинса-Трауба». Math ∞ Blog . Получено 4 апреля 2023 г. .
  15. ^ Лазовска, Эд (30 августа 2015 г.). «Вспоминая Джо Трауба, 1932-2015». Новости школы Аллена . Получено 4 апреля 2023 г.
  16. ↑ Spice, Byron (27 августа 2015 г.). «In Memoriam: Joseph F. Traub». Carnegie Mellon School of Computer Science . Получено 4 апреля 2023 г.
  17. ^ Мирсман, Роберт (1975). «Обзор методов прикладной вычислительной сложности c*)». Журнал вычислительной и прикладной математики . I (1): 39–46. doi : 10.1016/0771-050X(75)90005-4 .
  18. ^ Kung, HT; Traub, JF (1 апреля 1978 г.). «Все алгебраические функции можно вычислить быстро». Journal of the ACM . 25 (2): 245–260. doi :10.1145/322063.322068. S2CID  5933519. Получено 15 ноября 2021 г.
  19. ^ "Journal of Complexity". Elsevier . Получено 4 апреля 2023 г. .
  20. ^ МакКоги, Роберт А. (2014). Достаточно длинный рычаг: история Колумбийской школы инженерии и прикладных наук с 1864 года. Нью-Йорк: Columbia University Press. doi : 10.7312/columbia/9780231166881.003.0007. ISBN 9780231166881.
  21. ^ Парлетт, Бересфорд Н. (1992). «Некоторые основные сведения о теории сложности, основанной на информации» (PDF) . Бюллетень (Новая серия) Американского математического общества . 26 (1): 3–28. arXiv : math/9201266 . doi :10.1090/S0273-0979-1992-00239-2. S2CID  3077531.
  22. ^ Шуб, Майкл (сентябрь 1987 г.). «Информация, неопределенность, сложность (Дж. Ф. Трауб, Г. В. Васильковски и Х. Возняковски)». Обзор SIAM . 29 (3): 495–497. doi :10.1137/1029099. ISSN  0036-1445.
  23. ^ Kon, Mark A. (октябрь 1989 г.). «Обзор: JF Traub, GW Wasilkowski и H. Woźniakowski, Information-based difficulty». Bulletin (New Series) of the American Mathematical Society . 21 (2): 332–339. doi : 10.1090/S0273-0979-1989-15851-5 . ISSN  0273-0979 . Получено 4 апреля 2023 г.
  24. ^ "В честь покойного главного редактора-основателя журнала Journal of Complexity: учреждена стипендия имени Джозефа Ф. Трауба. - Новости - Journal of Complexity - Журнал - Elsevier". Elsevier . Получено 4 апреля 2023 г.
  25. ^ Трауб, Дж. Ф. (1985). «Сложность приближенно решенных проблем» (PDF) . Журнал сложности . 1 : 3–10. doi :10.1016/0885-064X(85)90019-6.
  26. ^ Хат, Пит; Рюэль, Дэвид; Трауб, Джозеф (1998). «Разновидности пределов научного знания | Институт Санта-Фе» (PDF) . Сложность . 3 (6). John Wiley & Sons. Inc. doi :10.1002/(SICI)1099-0526(199807/08)3:6<33::AID-CPLX5>3.0.CO;2-L . Получено 4 апреля 2023 г. .
  27. ^ Дагштуль-Отчет о семинаре; 11 15-19.4.1991 (9116) (PDF) . ИБФИ ГмбХ. 1991.
  28. ^ Kon, Mark A. (21 декабря 1999 г.). «Сложность и информация» JF Traub и AG Werschulz, Cambridge University Press, Кембридж, 1998, xii + 139 стр., $19.95, ISBN 0-521-48506-1 (мягкая обложка) (PDF) . Бюллетень (новая серия) Американского математического общества . 37 (2): 199–204. doi :10.1090/S0273-0979-99-00859-9 . Получено 4 апреля 2023 г. .
  29. ↑ Касти, Джон Л. (17 апреля 1999 г.). «Миссия невыполнима». New Scientist . Получено 4 апреля 2023 г.
  30. ^ «Искусные финансовые вычисления с помощью детерминированной выборки | Институт Санта-Фе». www.santafe.edu . 7 июля 2011 г. Получено 4 апреля 2023 г.
  31. ^ Хейс, Брайан (2011). «Квазислучайные бредни» (PDF) . American Scientist . 99 (4): 282–287. doi :10.1511/2011.91.282.
  32. ^ Пасков, Спасимир Г.; Трауб, Джозеф Ф. (31 октября 1995 г.). «Быстрая оценка производных финансовых инструментов». Журнал управления портфелем . 22 (1): 113–123. дои : 10.3905/jpm.1995.409541. ISSN  0095-4918. S2CID  17278384 . Проверено 4 апреля 2023 г.
  33. ^ Папагеоргиу, А.; Трауб, Дж. Ф. (1996). «Победа над Монте-Карло» (PDF) . Риск . 9 (6): 63–65.
  34. ^ Шандор, Джон (5 октября 2001 г.). «Убойные приложения для квантовых компьютеров». HPCwire . Получено 4 апреля 2023 г.
  35. ^ Папагеоргиу, А. "Патентная информация". www.cs.columbia.edu . Получено 22 марта 2018 г. .
  36. ↑ Трауб, Джозеф (3 августа 2004 г.). «Террористическая тревога: новое напряжение в нервной стране». The New York Times .
  37. ↑ Трауб, Джозеф (17 августа 2004 г.). «Флорида и гнев Чарли». The New York Times .
  38. ^ "IEEE Emanuel R. Piore Award Recipients" (PDF) . IEEE . Архивировано из оригинала (PDF) 24 ноября 2010 г. . Получено 20 марта 2021 г. .
  39. ^ "Почетные члены и члены Академии". Нью-Йоркская академия наук . Получено 4 апреля 2023 г.
  40. ^ "Исторические стипендиаты". Американская ассоциация содействия развитию науки (aaas.org) .(Поиск по last_name="Traub".)
  41. ↑ Список членов Американского математического общества, получен 27 августа 2013 г.

Внешние ссылки