Филип Н. Кляйн
Филип Н. Кляйн | |
|---|---|
 | |
| Национальность | американский |
| Образование | Гарвардский университет ( бакалавр ) Массачусетский технологический институт ( доктор философии ) |
| Профессии |
|
Филип Н. Кляйн — американский ученый-компьютерщик и профессор Университета Брауна . Его исследования сосредоточены на алгоритмах для задач оптимизации в графах.
Кляйн является членом Ассоциации вычислительной техники [1] и лауреатом Президентской премии для молодых исследователей Национального научного фонда (1991). [2] Он является лауреатом премии Филипа Дж. Брея за выдающиеся достижения в преподавании естественных наук от Университета Брауна (2007) и был стипендиатом Института перспективных исследований Рэдклиффа при Гарвардском университете (2015–2016). [2] Он с отличием окончил Гарвард, получив степень бакалавра наук по прикладной математике, и получил степень доктора философии по компьютерным наукам в Массачусетском технологическом институте . [3]
Ключевые вклады
- В 1991 году Кляйн и его тогдашние студенты Аджит Агравал и Р. Рави разработали алгоритм аппроксимации для проектирования сетей, который считается «первым высокосложным применением метода прямоугольных пар при проектировании алгоритмов аппроксимации». [4] В 2023 году это исследование получило 30-летнюю премию времени ежегодного симпозиума ACM по теории вычислений (STOC). [5] [6] [7] [4]
- В 1994 году Клейн и Роберт Э. Тарьян предложили рандомизированный линейный алгоритм для поиска минимальных остовных деревьев, основанный на методе выборки Дэвида Каргера. [8] [9] [10]
- В 2005 году Клейн предложил линейный алгоритм для поиска почти оптимального тура коммивояжера в плоском графе. [11] [12]
Книги
Кляйн опубликовал два учебника:
- Кляйн, Филип Н. (2014). Учебник криптографии: секреты и обещания. Нью-Йорк, США. ISBN 978-1-107-01788-7. OCLC 863632974.
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )[13] - Кляйн, Филип Н. (2013). Кодирование матрицы: линейная алгебра через приложения к информатике. [Ньютон, Массачусетс]: Newtonian Press. ISBN 978-0-615-85673-5. OCLC 855087626.[14]
Ссылки
- ^ "Philip N Klein". awards.acm.org . Получено 29.05.2022 .
- ^ ab "Philip N. Klein". cs.brown.edu . Архивировано из оригинала 2022-01-03 . Получено 2022-06-27 .
- ^ "Philip N. Klein". Radcliffe Institute for Advanced Study at Harvard University . Архивировано из оригинала 2022-04-19 . Получено 2022-06-27 .
- ^ аб Хохбаум, Дорит. Алгоритмы аппроксимации NP-трудных задач . п. 158.
- ^ «Выпускники Philip Klein и Brown CS получают премию STOC Test Of Time Award 2023».
- ^ Агравал, Аджит; Кляйн, Филипп; Рави, Р. (1995). «Когда деревья сталкиваются: алгоритм приближения для обобщенной проблемы Штейнера в сетях». SIAM Journal on Computing . 24 (3): 440– 456. doi :10.1137/S0097539792236237.
- ^ Агравал, Аджит; Кляйн, Филип; Рави, Р. (1991). "«Когда деревья сталкиваются: алгоритм приближения для обобщенной задачи Штейнера на сетях»". Труды 23-го ежегодного симпозиума ACM по теории вычислений : 134–144 .
- ^ Мотвани, Раджив; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы . Cambridge University Press. стр. Раздел 10.3.
- ^ Каргер, Дэвид Р.; Кляйн, Филип Н.; Тарьян, Роберт Э. (1995). «Рандомизированный линейный алгоритм поиска минимальных остовных деревьев». Журнал ACM . 42 (2): 321– 328. doi : 10.1145/201019.201022 . S2CID 832583.
- ^ Клейн, Филип Н.; Тарьян, Роберт Э. (1994). "Рандомизированный линейный алгоритм поиска минимальных остовных деревьев". Труды двадцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '94 . С. 9–15 . doi :10.1145/195058.195084. ISBN 0897916638. S2CID 15667728.
- ^ Кляйн, Филип Н. (2008). «Линейно-временная схема аппроксимации для TSP в неориентированных планарных графах с весами ребер». SIAM Journal on Computing . 37 (6): 1926–1952 . CiteSeerX 10.1.1.155.897 . doi :10.1137/060649562.
- ^ Кляйн, Филип Н. (2005). "Линейно-временная схема аппроксимации для плоской взвешенной задачи коммивояжера". 46-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS'05) . стр. 647–656 . doi :10.1109/SFCS.2005.7. ISBN 0-7695-2468-0. S2CID 16327107.
- ^ Кляйн, Филип Н. (2014). Учебник криптографии: секреты и обещания. Нью-Йорк, США. ISBN 978-1-107-01788-7. OCLC 863632974.
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) - ^ Клейн, Филип Н. (2013). Кодирование матрицы: линейная алгебра через приложения к информатике. [Ньютон, Массачусетс]: Newtonian Press. ISBN 978-0-615-85673-5. OCLC 855087626.
 | Эта биографическая статья, касающаяся специалиста по компьютерам в США, является заглушкой . Вы можете помочь Википедии, расширив ее. |
