Миккель Торуп
Миккель Торуп | |
|---|---|
| Рожденный | 1965 (58–59 лет) Дания |
| Альма-матер | Оксфордский университет , Технический университет Дании |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Копенгагенский университет |
| Диссертация | Темы вычислений (1994) |
| Докторантура | Уильям Ф. «Билл» МакКолл Колин МакДиармид |
Миккель Торуп (1965 г.р.) — датский ученый-компьютерщик, работающий в Копенгагенском университете .Он закончил бакалавриат в Техническом университете Дании и докторантуру в Оксфордском университете в 1993 году. [1] С 1993 по 1998 год он работал в Копенгагенском университете, а с 1998 по 2013 год — в исследовательской лаборатории AT&T в Нью-Джерси. С 2013 года работает в Копенгагенском университете в должности профессора и руководителя Центра эффективных алгоритмов и структур данных (EADS). [2]
Основная работа Торупа связана с алгоритмами и структурами данных . Одним из его самых известных результатов является алгоритм с линейным временем для решения задачи о кратчайших путях с одним источником в неориентированных графах (Thorup, 1999). [3] Вместе с Михаем Патрашку он показал, что простые схемы табулированного хеширования достигают тех же или аналогичных критериев производительности, что и семейства хэшей, которые в худшем случае имеют более высокую независимость, но при этом позволяют более быструю реализацию. [4] [5]
Торуп был редактором отдела алгоритмов и структур данных в журнале Journal of the ACM , а также входил в редакционную коллегию журналов SIAM Journal on Computing , ACM Transactions on Algorithms и The Theory of Computing. С 2005 года он является членом Ассоциации вычислительной техники за вклад в разработку алгоритмов и структур данных. [6] С 2006 года он является членом Датской королевской академии наук и литературы. В 2010 году он был удостоен награды AT&T Fellows Honor за «выдающиеся инновации в алгоритмах, включая передовые методы хеширования и выборки, применяемые в анализе интернет-трафика и речевых услугах AT&T». [7]
В 2011 году он стал одним из лауреатов премии Дэвида П. Роббинса от Математической ассоциации Америки за решение с точностью до постоянного множителя классической задачи укладки блоков на столе для достижения максимально возможного выступа , т.е. максимальное расстояние по горизонтали от края стола. [8] «В статьях описан впечатляющий результат в области дискретной математики; проблема легко понятна, а аргументы, несмотря на их глубину, легко доступны любому мотивированному студенту». [3] В 2021 году он стал одним из лауреатов премии Фулкерсона за работу с Кен-Ичи Каварабаяши над быстрыми детерминированными алгоритмами для граничной связи. [9]
Избранные публикации
[ редактировать ]
- Торуп, Миккель (1999). «Ненаправленные кратчайшие пути из одного источника с положительными целочисленными весами в линейном времени» . Журнал АКМ . 46 (3): 362–394. дои : 10.1145/316542.316548 . S2CID 207654795 . Объявлено на FOCS 1997.
- Патрашку, Михай; Торуп, Миккель (2010). «Более высокие нижние границы для задач ближнего соседа и дальнейших богатых задач». SIAM Journal по вычислительной технике . 39 (2): 730–741. дои : 10.1137/070684859 . S2CID 8324376 . Предварительная версия опубликована в FOCS 2006 г. дои : 10.1109/FOCS.2006.35 .
- Патрашку, Михай ; Торуп, Миккель (2011). «Сила простого хеширования таблиц». Материалы 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11) . стр. 1–10. arXiv : 1011.5200 . дои : 10.1145/1993636.1993638 . .
- Патерсон, Майк ; Перес, Юваль; Торуп, Миккель; Винклер, Питер; Цвик, Ури (2009). «Максимальный вылет». Американский математический ежемесячник . 116 (9): 763–787. arXiv : 0707.0093 . дои : 10.4169/000298909x474855 . S2CID 1713091 . Премия MAA Роббинса 2011 года.
Ссылки
[ редактировать ]- ^ Проект математической генеалогии
- ^ Личная домашняя страница Торупа.
- ^ Jump up to: Перейти обратно: а б Цитирование премии Роббинса
- ^ Патрашку и Торуп 2011 .
- ↑ Риган, Хеширование и независимость табуляции, Утерянное письмо Гёделя, 14 апреля 2012 г. , Fortnow, Обзор сложности года, 29 декабря 2011 г.
- ^ Веб-сайт ACM Fellows. Архивировано 27 мая 2012 г. на Wayback Machine.
- ^ Страница профиля AT&T Миккеля Торупа
- ^ Патерсон и др. 2009 .
- ^ Объявление о премии Фулкерсона
