Mikkel Thorup - Mikkel Thorup

Mikkel Thorup (nacido en 1965) es un informático danés que trabaja en la Universidad de Copenhague . Completó su educación universitaria en la Universidad Técnica de Dinamarca y sus estudios de doctorado en la Universidad de Oxford en 1993. De 1993 a 1998, estuvo en la Universidad de Copenhague y de 1998 a 2013 estuvo en AT&T Labs-Research en Nueva Jersey. Desde 2013 ha estado en la Universidad de Copenhague como profesor y director del Centro de Estructuras de Datos y Algoritmos Eficientes (EADS).

El trabajo principal de Thorup está en algoritmos y estructuras de datos . Uno de sus resultados más conocidos es un algoritmo de tiempo lineal para el problema de las rutas más cortas de una sola fuente en gráficos no dirigidos (Thorup, 1999). Con Mihai Pătraşcu , ha demostrado que los esquemas de hash de tabulación simples logran los mismos o similares criterios de rendimiento que las familias de hash que tienen una mayor independencia en el peor de los casos, al tiempo que permiten implementaciones más rápidas.

Thorup ha sido editor del algoritmo de área y estructuras de datos para Journal of the ACM , y también ha formado parte de los consejos editoriales de SIAM Journal on Computing , ACM Transactions on Algorithms y Theory of Computing. Ha sido miembro de la Association for Computing Machinery desde 2005 por sus contribuciones a algoritmos y estructuras de datos. Pertenece a la Real Academia Danesa de Ciencias y Letras desde 2006. En 2010 recibió el premio AT&T Fellows Honor por "innovación sobresaliente en algoritmos, incluidas técnicas avanzadas de hash y muestreo aplicadas al análisis de tráfico de Internet y servicios de voz de AT&T".

En 2011 fue co-ganador del Premio David P. Robbins de la Asociación Matemática de América por resolver, hasta dentro de un factor constante, el clásico problema de apilar bloques sobre una mesa para lograr el máximo voladizo posible , es decir, alcanzar el distancia horizontal más lejana desde el borde de la mesa. “Los artículos describen un resultado impresionante en matemáticas discretas; el problema se comprende fácilmente y los argumentos, a pesar de su profundidad, son fácilmente accesibles para cualquier estudiante universitario motivado ". En 2021 fue co-ganador del Premio Fulkerson por su trabajo con Ken-Ichi Kawarabayashi en algoritmos deterministas rápidos para conectividad de borde.

Publicaciones Seleccionadas

• Thorup, Mikkel (1999). "Rutas más cortas no dirigidas de una sola fuente con pesos enteros positivos en tiempo lineal". Revista de la ACM . 46 (3): 362–394. doi : 10.1145 / 316542.316548 . S2CID  207654795 . Anunciado en FOCS 1997.
• Pătraşcu, Mihai; Thorup, Mikkel (2010). "Límites inferiores más altos para el vecino cercano y más problemas ricos". Revista SIAM de Computación . 39 (2): 730–741. doi : 10.1137 / 070684859 . S2CID  8324376 .Versión preliminar publicada en FOCS 2006, doi : 10.1109 / FOCS.2006.35 .
• Pătraşcu, Mihai ; Thorup, Mikkel (2011). "El poder del hash de tabulación simple". Actas del 43º Simposio anual de ACM sobre teoría de la computación (STOC '11) . págs. 1-10. arXiv : 1011.5200 . doi : 10.1145 / 1993636.1993638 ..
• Paterson, Mike ; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri (2009). "Voladizo máximo". The American Mathematical Monthly . 116 (9): 763–787. arXiv : 0707.0093 . doi : 10.4169 / 000298909x474855 . S2CID  1713091 . Premio MAA Robbins 2011.

Referencias