Mikkel Thorup

Mikkel Thorup (geb. 1965) ist ein dänischer Informatiker an der Universität Kopenhagen . Er absolvierte sein Grundstudium an der Technischen Universität Dänemark und promovierte 1993 an der Universität Oxford . ^{[ 1 ]} Von 1993 bis 1998 war er an der Universität Kopenhagen tätig und von 1998 bis 2013 bei AT&T Labs-Research in New Jersey. Seit 2013 ist er Professor und Leiter des Zentrums für effiziente Algorithmen und Datenstrukturen (EADS) an der Universität Kopenhagen. ^{[ 2 ]}

Thorups Hauptarbeitsgebiet sind Algorithmen und Datenstrukturen . Eines seiner bekanntesten Ergebnisse ist ein Linearzeitalgorithmus für das Problem der kürzesten Wege von einem Startknoten in ungerichteten Graphen (Thorup, 1999). ^{[ 3 ]} Zusammen mit Mihai Pătraşcu zeigte er, dass einfache Tabellierungs-Hashing -Verfahren dieselben oder ähnliche Leistungskriterien wie Hash-Familien mit höherer Unabhängigkeit im ungünstigsten Fall erfüllen und gleichzeitig schnellere Implementierungen ermöglichen. ^{[ 4 ] [ 5 ]}

Thorup war Herausgeber des Bereichs Algorithmen und Datenstrukturen beim Journal of the ACM und Mitglied der Redaktionsausschüsse des SIAM Journal on Computing , der ACM Transactions on Algorithms und der Theory of Computing. Seit 2005 ist er Fellow der Association for Computing Machinery (ACM) für seine Beiträge zu Algorithmen und Datenstrukturen. ^{[ 6 ]} Seit 2006 gehört er der Königlich Dänischen Akademie der Wissenschaften an . 2010 wurde ihm die AT&T Fellows-Auszeichnung für „herausragende Innovationen im Bereich der Algorithmen, darunter fortschrittliche Hashing- und Sampling-Verfahren, die für die Internet-Traffic-Analyse und die Sprachdienste von AT&T eingesetzt wurden“, verliehen. ^{[ 7 ]}

2011 wurde er gemeinsam mit anderen Preisträgern des David P. Robbins Preises der Mathematical Association of America für die Lösung des klassischen Problems des Stapelns von Blöcken auf einem Tisch bis auf einen konstanten Faktor ausgezeichnet. Ziel war es, den größtmöglichen horizontalen Überhang vom Tischrand zu erreichen. ^{[ 8 ]} „Die Arbeiten beschreiben ein beeindruckendes Ergebnis der diskreten Mathematik; das Problem ist leicht verständlich, und die Argumente sind trotz ihrer Tiefe für jeden motivierten Studenten im Grundstudium gut nachvollziehbar.“ ^{[ 3 ]} 2021 wurde er gemeinsam mit Ken-Ichi Kawarabayashi mit dem Fulkerson Preis für seine Arbeit an schnellen deterministischen Algorithmen zur Kantenkonnektivität ausgezeichnet. ^{[ 9 ]}

• Thorup, Mikkel (1999). „Ungerichtete kürzeste Wege von einer Quelle mit positiven ganzzahligen Gewichten in linearer Zeit“ . Journal of the ACM . 46 (3): 362–394 . doi : 10.1145/316542.316548 . S2CID  207654795 .Angekündigt auf der FOCS 1997.
• Pătraşcu, Mihai; Thorup, Mikkel (2010). „Höhere untere Schranken für Near-Neighbor- und weitere Rich-Probleme“. SIAM Journal on Computing . 39 (2): 730–741 . doi : 10.1137/070684859 . S2CID  8324376 .Vorläufige Fassung veröffentlicht in FOCS 2006, doi : 10.1109/FOCS.2006.35 .
• Pătraşcu, Mihai ; Thorup, Mikkel (2011). „Die Leistungsfähigkeit von einfachem Tabulations-Hashing“. Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11) . S.  1–10 . arXiv : 1011.5200 . doi : 10.1145/1993636.1993638 .Die
• 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 .MAA Robbins Award 2011.