De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

Mikkel Thorup (nacido en 1965) es un informático danés afiliado conjuntamente a AT&T Labs en Florham Park, Nueva Jersey , Estados Unidos y a 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. [1] 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). [2]

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). [3] 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. [4] [5]

Thorup es el editor del algoritmo de área y las estructuras de datos de Journal of the ACM . [6] También es miembro 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. [7] 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". [8]

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. [9] “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 ". [3]

Publicaciones seleccionadas [ editar ]

  • 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 . CS1 maint: discouraged parameter (link) Premio MAA Robbins 2011.

Referencias [ editar ]

  1. ^ Proyecto de genealogía matemática
  2. ^ Página de inicio personal de Thorup
  3. ^ a b Cita del premio Robbins
  4. ^ Pătraşcu y Thorup 2011 .
  5. ^ Regan, Hash de tabulación e independencia, Letra perdida de Gödel, 14 de abril de 2012 , Fortnow, Revisión del año de complejidad, 29 de diciembre de 2011.
  6. ^ Consejo editorial de JACM Archivado el 28 de abril de 2012 en la Wayback Machine.
  7. ^ Sitio web de ACM Fellows Archivado el 27 de mayo de 2012 en la Wayback Machine.
  8. ^ Página de perfil de AT&T para Mikkel Thorup
  9. ^ Paterson y col. 2009 .