Kurt Mehlhorn

chercheur en informatique allemand

Kurt Mehlhorn (né le à Ingolstadt[1]) est un chercheur en informatique allemand, connu pour ses travaux en algorithmique, géométrie algorithmique, théorie de la complexité , complexité de la communication et algorithmique des graphes. Il a contribué considérablement au développement de l'informatique universitaire en Allemagne, notamment par la création de l'Institut Max-Planck d'informatique (MPII) à Sarrebruck dont il est l'un des directeurs, et par une activité de recherche et de direction de recherche soutenues.

Biographie

modifier

Après des études d'informatique et de mathématiques à l'université technique de Munich de 1968 à 1971, il part à l'université Cornell de 1971 à 1974 sur une bourse de la Studienstiftung des deutschen Volkes ; il obtient un Ph. D. en 1974 sous la direction de Robert L. Constable avec une thèse intitulée « Polynomial and Abstract Subrecursive Classes »[2]. Depuis 1975, il est à l'université de la Sarre à Sarrebruck en Allemagne. De 1976 à 1978 et à nouveau de 1987 à 1989, il dirige le département d'informatique. Depuis 1990, il est directeur de l'Institut Max-Planck d'informatique (MPII), aussi à Sarrebruck[3].

Travaux

modifier

Mehlhorn est l'auteur de plusieurs livres. Chercheur prolifique, et est de plus auteur ou coauteur de plus de 250 publications scientifiques avec plus de 250 coauteurs[4]. Il a apporté des contributions fondamentales sur les structures de données, la géométrie algorithmique, le calcul formel, le calcul parallèle, technologie VLSI, et théorie de la complexité, combinatorial optimization, et algorithmique des graphes[5]. Il est une figure importante dans le développement de la conception et l’analyse des algorithmes, leur implémentation et optimisation.
Il a aussi co-écrit l'un des articles fondateurs[6] sur la complexité de la communication[7].

Il est aussi connu pour la création avec Stefan Näher de LEDA (Library of Efficient Data types and Algorithms (en)), une librairie de structure de données et d'algorithmes. Cette bibliothèque est reconnue pour ses algorithmes très efficaces et robustes du point de vue théorique, et sa bonne implémentation[8]. Il a créé, avec Stefan Näher et Christian Uhrig, une entreprise appelée Algorithmic Solutions GmbH en 1995.

Mehlhorn a joué un rôle important dans la création de plusieurs centres de recherche en informatique en Allemagne. Il était la force motrice[5] dans la création de l'Institut Max-Planck d'informatique (MPII). Mehlhorn est l'un des initiateurs du centre d'informatique Leibniz-Zentrum für Informatik à Dagstuhl. Avec Max Fontet, il a initié la série de colloques Symposium on Theoretical Aspects in Computer Science (STACS) et il est à l'origine du European Symposium on Algorithms. Mehlhorn assume ou a assumé un nombre important dee resposabilités dans la gestion académique de la recherche, comme membre de conseils d'administration, conseils scientifiques et autres organes de direction, en Allemagne, en niveau européen et aux États-Unis. Ainsi, il est ou a été administrateur du International Computer Science Institute (en) à Berkeley, et membre du conseil d'administration de l'Université Jacobs de Brême, membre du sénat de la Deutsche Forschungsgemeinschaft[1], président du conseil scientifique de l'INRIA[9], où il succède à Martin Wirsing.

Mehlhorn a dirigé ou codirigé 84 thèses et a près de 230 descendants académiques[2]. Parmi ses élèves, il y a Susanne Albers, Helmut Alt, Hannah Bast, Rudolf Fleischer, Michael Kaufmann, Hans-Peter Lenhof, Athanasios Tsakalidis. Une Festschrift a été publiée en son honneur à l’occasion de son 60e anniversaire[10].

Prix et distinctions

modifier
Prix
Sociétés savantes
Docteur honoris causa

Publications

modifier
  • Kurt Mehlhorn, Effiziente Algorithmen, Stuttgart, Teubner, . Édition révisée et traduite en anglais sous le titre Data Structures and Algorithms, Springer-Verlag, 1984.
  • Kurt Mehlhorn, Data Structures and Algorithms II : Graph Algorithms and NP-completeness, Springer-Verlag, .
  • Kurt Mehlhorn, Data Structures and Algorithms III : Multidimensional Searching and Computational Geometry, Springer-Verlag, .
  • Jacques Loeckx, Kurt Mehlhorn et Reinhard Wilhelm, Foundations of Programming Languages, J. Wiley, , 426 p. (ISBN 0-471-92139-4).
  • (en) Kurt Mehlhorn et Stefan Näher, LEDA : a platform for combinatorial and geometric computing, Cambridge, Cambridge University Press, , 1018 p. (ISBN 978-0-521-56329-1, lire en ligne).
  • Kurt Mehlhorn et Peter Sanders, Algorithms and Data Structures : The Basic Toolbox, Springer, , 300 p. (ISBN 978-3-540-77977-3, lire en ligne).

Articles (sélection)

modifier
  • Kurt Mehlhorn et Erik M. Schmidt, « Las Vegas is better than determinism in VLSI and distributed computing », Proc. 14th ACM Symp. Theory of Computing (STOC),‎ , p. 330–337 (DOI 10.1145/800070.802208).
  • Kurt Mehlhorn et Uzi Vishkin, « Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories », Acta Informatica, vol. 21, no 4,‎ , p. 339–374 (DOI 10.1007/BF00264615).
  • Helmut Alt, Kurt Mehlhorn, Hubert Wagener et Emo Welzl, « Congruence, similarity, and symmetries of geometric objects », Discrete and Computational Geometry, vol. 3, no 1,‎ , p. 237–256 (DOI 10.1007/BF02187910).
  • Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin et Robert E. Tarjan, « Faster algorithms for the shortest path problem », Journal of the Association for Computing Machinery, vol. 37, no 2,‎ , p. 213–223 (DOI 10.1145/77600.77615).
  • Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert et Robert E. Tarjan, « Dynamic perfect hashing: upper and lower bounds », SIAM Journal on Computing, vol. 23, no 4,‎ , p. 738–761 (DOI 10.1137/S0097539791194094).
  • Michael Sagraloff et Kurt Mehlhorn, « Computing real roots of real polynomials », Journal of Symbolic Computation, vol. 73,‎ , p. 46-86 (DOI 10.1016/j.jsc.2015.03.004).

Notes et références

modifier
  1. a et b Curriculum Vitæ sur le site de l'Institut Max-Planck d'informatique.
  2. a et b (en) « Kurt Mehlhorn », sur le site du Mathematics Genealogy Project
  3. Page d'accueil du MPII
  4. Publications de Kurt Mehlhorn sur la DBLP.
  5. a b et c Bulletin of the EATCS, no 100, p. 7–8.
  6. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 13 (« Communication Complexity »).
  7. Mehlhorn, Schmidt 1982, « Las Vegas Is better than Determinism in {VLSI} and Distributed Computing ».
  8. Voir le Laudatio pour le prix EACTS.
  9. Conseil scientifique de l'INRIA.
  10. Susanne Albers, Helmut Alt et Stefan Näher (éditeurs), Efficient algorithms : essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday, Springer, , 439 p. (ISBN 978-3-642-03455-8, lire en ligne).
  11. Historique du département informatique
  12. Page du prix EATCS
  13. Page officielle du prix Kanellakis, sur le site de l'ACM
  14. 2014 Erasmus Medal awarded to Professor Dr Kurt Mehlhorn MAE, Academia Europaea, retrieved 2014-06-21.
  15. ACM Fellows Mehlhorn pour « important contributions in complexity theory and in the design, analysis, and practice of combinatorial and geometric algorithms »
  16. « National Academy of Sciences Elections », Notices of the American Mathematical Society, vol. 62, no 7,‎ , p. 826.

Liens externes

modifier