Mikkel Thorup- Mikkel Thorup

Mikkel Thorup (* 1965) ist ein dänischer Informatiker, der an der Universität Kopenhagen arbeitet . Er absolvierte 1993 sein Bachelorstudium an der Technischen Universität Dänemark und sein Doktoratsstudium an der Oxford University . Von 1993 bis 1998 war er an der Universität Kopenhagen und von 1998 bis 2013 bei AT&T Labs-Research in New Jersey. Seit 2013 ist er als Professor und Leiter des Center for Efficient Algorithms and Data Structures (EADS) an der Universität Kopenhagen.

Thorups Hauptarbeit liegt in Algorithmen und Datenstrukturen . Eines seiner bekanntesten Ergebnisse ist ein Algorithmus mit linearer Zeit für das Single-Source-Kürzeste-Wege-Problem in ungerichteten Graphen (Thorup, 1999). Mit Mihai Pătraşcu hat er gezeigt, dass einfache tabellarische Hashing- Schemata die gleichen oder ähnliche Leistungskriterien wie Hash-Familien erreichen, die im schlimmsten Fall eine höhere Unabhängigkeit aufweisen und gleichzeitig schnellere Implementierungen ermöglichen.

Thorup war Redakteur des Bereichs Algorithmen und Datenstrukturen für das Journal of the ACM und war auch in den Editorial Boards des SIAM Journal on Computing , ACM Transactions on Algorithms und Theory of Computing tätig. Er hat gewesen Mitglied der Association for Computing Machinery für seine Beiträge zur Algorithmen seit 2005 und Datenstrukturen. Er ist seit 2006 Mitglied der Königlich Dänischen Akademie der Wissenschaften und Literatur .

2011 war er Co-Gewinner des David P. Robbins Prize der Mathematical Association of America für die Lösung des klassischen Problems des Stapelns von Blöcken auf einem Tisch, um den größtmöglichen Überhang zu erreichen , d am weitesten horizontaler Abstand von der Tischkante. „Die Arbeiten beschreiben ein beeindruckendes Ergebnis in der diskreten Mathematik; das Problem ist leicht verständlich und die Argumente sind trotz ihrer Tiefe für jeden motivierten Studenten leicht zugänglich.“ 2021 war er Co-Gewinner des Fulkerson Prize für seine Arbeit mit Ken-Ichi Kawarabayashi über schnelle deterministische Algorithmen für Edge Connectivity.

Ausgewählte Publikationen

• Thorup, Mikkel (1999). „Ungerichtete Single Source Shortest Paths mit positiven ganzzahligen Gewichtungen in linearer Zeit“. Zeitschrift der ACM . 46 (3): 362–394. doi : 10.1145/316542.316548 . S2CID  207654795 . Angekündigt bei FOCS 1997.
• Pătraşcu, Mihai; Thorup, Mikkel (2010). „Höhere untere Schranken für nahe Nachbarn und weitere reiche Probleme“. SIAM Journal für Computer . 39 (2): 730–741. doi : 10.1137/070684859 . S2CID  8324376 .Vorläufige Version veröffentlicht in FOCS 2006, doi : 10.1109/FOCS.2006.35 .
• Pătraşcu, Mihai ; Thorup, Mikkel (2011). „Die Macht des einfachen tabellarischen Hashing“. Proceedings of the 43. Annual ACM Symposium on Theory of Computing (STOC '11) . S. 1–10. arXiv : 1011.5200 . doi : 10.1145/1993636.1993638 ..
• Paterson, Mike ; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri (2009). "Maximaler Überhang". The American Mathematical Monthly . 116 (9): 763–787. arXiv : 0707.0093 . doi : 10.4169/000298909x474855 . S2CID  1713091 . 2011 MAA Robbins-Preis.

Verweise