Миккель Торуп

Миккель Торуп (родился в 1965 году) — датский учёный-компьютерщик, работающий в Копенгагенском университете . Он закончил бакалавриат в Техническом университете Дании и докторантуру в Оксфордском университете в 1993 году. ^[1] С 1993 по 1998 год он работал в Копенгагенском университете, а с 1998 по 2013 год — в AT&T Labs-Research в Нью-Джерси. С 2013 года он работает в Копенгагенском университете профессором и руководителем Центра эффективных алгоритмов и структур данных (EADS). ^[2]

Основная работа Торупа посвящена алгоритмам и структурам данных . Одним из его самых известных результатов является алгоритм линейного времени для задачи поиска кратчайших путей из одного источника в неориентированных графах (Торуп, 1999). ^[3] Совместно с Михаем Патрашку он показал, что простые схемы хеширования табуляцией достигают тех же или схожих критериев производительности, что и хеш-семейства, которые имеют большую независимость в худшем случае, при этом допуская более быстрые реализации. ^{[4] [5]}

Thorup был редактором области алгоритма и структур данных для Journal of the ACM , а также входил в редколлегии SIAM Journal on Computing , ACM Transactions on Algorithms и Theory of Computing. Он является членом Ассоциации вычислительной техники с 2005 года за его вклад в алгоритмы и структуры данных. ^[6] Он является членом Королевской датской академии наук и литературы с 2006 года. В 2010 году ему была присуждена награда AT&T Fellows Honor за «выдающиеся инновации в алгоритмах, включая передовые методы хеширования и выборки, применяемые к анализу интернет-трафика и речевым службам AT&T». ^[7]

В 2011 году он стал одним из лауреатов премии Дэвида П. Роббинса от Математической ассоциации Америки за решение с точностью до постоянного множителя классической задачи укладки блоков на столе для достижения максимально возможного выступа , т. е. достижения наибольшего горизонтального расстояния от края стола. ^[8] «В работах описывается впечатляющий результат в дискретной математике; проблема легко понятна, а аргументы, несмотря на их глубину, легко доступны любому мотивированному студенту». ^[3] В 2021 году он стал одним из лауреатов премии Фулкерсона за свою работу с Кен-Ичи Каварабаяши по быстрым детерминированным алгоритмам для связности ребер. ^[9]

У Схолии есть авторский профиль Миккеля Торупа .

• Торуп, Миккель (1999). «Ненаправленные кратчайшие пути из одного источника с положительными целыми весами за линейное время». Журнал ACM . 46 (3): 362–394. doi : 10.1145/316542.316548 . S2CID  207654795.Анонсировано на FOCS 1997.
• Патрашку, Михай; Торуп, Миккель (2010). «Более высокие нижние границы для задач с близким соседом и более богатыми задачами». SIAM Journal on Computing . 39 (2): 730–741. doi :10.1137/070684859. S2CID  8324376.Предварительная версия опубликована в FOCS 2006, doi :10.1109/FOCS.2006.35.
• Пэтрашку, Михай ; Торуп, Миккель (2011). «Мощь простого табуляционного хеширования». Труды 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11) . стр. 1–10. arXiv : 1011.5200 . doi : 10.1145/1993636.1993638..
• Патерсон, Майк ; Перес, Ювал; Торуп, Миккель; Винклер, Питер; Цвик, Ури (2009). «Максимальный навес». The American Mathematical Monthly . 116 (9): 763–787. arXiv : 0707.0093 . doi : 10.4169/000298909x474855. S2CID  1713091.Премия MAA Robbins 2011 года.