Трауб, Джозеф Фредерик

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

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

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

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

Трауб учился в Высшей научной школе Бронкса, где был капитаном и первой доской шахматной команды. После окончания Городского колледжа Нью-Йорка он поступил в Колумбийский университет в 1954 году, намереваясь получить степень доктора философии по физике. В 1955 году по совету сокурсника Трауб посетил исследовательскую лабораторию IBM Watson в Колумбийском университете. В 1957 году он стал стипендиатом Уотсона в Колумбийском университете. Его диссертация была посвящена вычислительной квантовой механике. Его докторская степень 1959 года получена по прикладной математике, поскольку степеней по информатике тогда ещё не было.

В 1959 году Трауб присоединился к исследовательскому подразделению Bell Laboratories в Мюррей-Хилл, штат Нью-Джерси. Однажды коллега спросил его, как вычислить решение определённой задачи. Трауб мог придумать несколько способов решения. Теории оптимальных алгоритмов на тот момент не существовало. Термин вычислительная сложность, обозначающий изучение минимальных ресурсов, необходимых для решения вычислительных задач, был введён в 1965 году. Трауб понял, что оптимальный алгоритм решения непрерывной задачи зависит от доступной информации. Это привело к созданию области информационной сложности. Первой областью, к которой Трауб применил свою идею, было решение нелинейных уравнений. Это исследование привело к монографии 1964 года «Итерационные методы решения уравнений»^[4][7].

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

В 1970 году Трауб стал профессором Вашингтонского университета, а в 1971 году возглавил факультет информатики Университета Карнеги — Меллона^[9]. На нём работали учёные Аллен Ньюэлл и Герберт Саймон. К 1978 году под руководством Трауба факультет расширился до 50 преподавателей и исследователей^[10].

Одним из аспирантов Трауба был Х. Т. Кунг, ныне профессор Гарварда. Они создали алгоритм Кунга — Трауба для вычисления разложения алгебраической функции. Они показали, что вычисление первых ${\displaystyle N}$ членов не сложнее умножения двух полиномов ${\displaystyle N}$-й степени^[4].

В 1973 году Трауб пригласил Хенрика Возняковского посетить Университет Карнеги — Меллона. Они стали пионерами в области информационной сложности, написав в соавторстве три монографии и множество статей. Возняковский стал профессором Колумбийского университета и Варшавского университета в Польше.

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

В 1980 году он в соавторстве с Возняковским написал книгу «Общая теория оптимальных алгоритмов». Это была первая исследовательская монография по информационной сложности^[11]. Грег Василковский присоединился к Траубу и Возняковскому в работе над ещё двумя монографиями: Information, Uncertainty, Complexity (Addison-Wesley, 1983) и Information-Based Complexity (Academic Press, 1988)^[12].

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

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

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

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

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

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

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

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

В 2005 году Трауб передал архивные материалы в библиотеку Университета Карнеги — Меллона.

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

• Председатель-основатель Совета по информатике и телекоммуникациям Национальных академий, 1986—1992, 2005—2009^[5]
• Премия выдающемуся старшему учёному, Фонд Александра фон Гумбольдта, 1992, 1998^[5]
• 1993 Lezione Lincee, Национальная академия деи Линчеи, Рим, Италия
• Лекция, Президиум Академии наук, Москва, СССР, 1990
• Первая премия Министерства образования Польши за исследовательскую монографию Information-Based Complexity, 1989
• Премия Эмануэля Пиора (1991) «за новаторские исследования в области сложности алгоритмов, теории итераций и параллелизма, а также за лидерство в компьютерном образовании»^[23]
• Совет управляющих, Нью-Йоркская академия наук, 1986—1989 (Исполнительный комитет 1987—1989)^[24]
• Член: Американская ассоциация содействия развитию науки, 1971; ACM, 1994; Нью-Йоркская академия наук, 1999; Американское математическое общество, 2012^[25]
• Премия мэра Нью-Йорка за выдающиеся достижения в области науки и технологий, 1999
• Festschrift for Joseph F. Traub, Academic Press, 1993
• Festschrift for Joseph F. Traub, Elsevier, 2004
• Почётный доктор наук, Университет Центральной Флориды, 2001
• Главный редактор-основатель, Journal of Complexity, 1985^[1]