Philippe Flajolet

Philippe Flajolet Beschreibung dieses Bildes, auch unten kommentiert Philippe Flajolet, 2006, auf der Konferenz zur Analyse von Algorithmen . Schlüsseldaten
Geburtsname Philippe Patrick Michel Flajolet
Geburt 1 st Dezember 1948
Lyon 6 th ( Frankreich )
Tod 22. März 2011
Suresnes ( Frankreich )
Staatsangehörigkeit  Französisch
Bereiche Mathematik , Informatik
Institutionen INRIA
Diplom Paris 7
Universität Paris 11 Universität
Supervisor Maurice Nivat , Jean Vuillemin
Bekannt für Analytische Kombinatorik
Algorithmusanalyse
Auszeichnungen Wissenschaftlicher Hauptpreis der Pariser Versicherungsunion 1986
Michel-Monpetit-Preis der Akademie der Wissenschaften 1994
Silbermedaille des CNRS 2004

Philippe Flajolet , geboren am1 st Dezember 1948in Lyon und starb am22. März 2011bei Suresnes ist ein französischer Forscher in Informatik und Mathematik .

Nach seinem Studium am Lycée Ampère in Lyon trat er 1968 in die École Polytechnique ein, promovierte 1972 an der Universität Paris 7 und promovierte 1979 an der Universität Paris 11. Anschließend wurde er Forschungsdirektor am Nationalen Institut für Forschung in Informatik und Automatisierung und Mitglied der Akademie der Wissenschaften .

Seine Hauptarbeiten in der Informatik liegen in der Kombinatorik und widmen sich der Algorithmusik , insbesondere der Analyse und dem Entwurf von Algorithmen, und allgemeiner der Untersuchung diskreter Strukturen (einschließlich grundlegender Datenstrukturen der Informatik) durch die Festlegung komplexer Theoreme Analyse und Wahrscheinlichkeitstheorie , wodurch im Gegenzug die Leistung vieler Algorithmen verbessert wird.

Funktioniert

Philippe Flajolet wurde hauptsächlich durch die Lektüre der Werke von Leonhard Euler , Srinivasa Ramanujan , Louis Comtet und Donald Knuth inspiriert und interessierte sich gleichzeitig für Linguistik. Anfang der 1970er Jahre wurde er von Maurice Nivat für die Arbeit in Sprachtheorie und Komplexität rekrutiert . Sehr schnell, in Kontakt mit Marcel-Paul Schützenberger und Jean Vuillemin , nimmt seine Arbeit eine Wendung, die er zum Programm seiner gesamten Forschungskarriere machen wird: eine glückliche Verbindung zwischen formalen Methoden (symbolisch kombinatorisch) und analytischen Methoden (komplexe Analyse) angewendet auf Informatik und diskrete Mathematik. Diese Arbeit gipfelt in der Schaffung eines neuen Feldes mit Robert Sedgewick : der analytischen Kombinatorik .

Analytische Kombinatorik

Die analytische Kombinatorik besteht darin, ein Problem in kombinatorischen Begriffen auszudrücken und dann über die Erzeugungsfunktionen, die bestimmte Parameter dieser kombinatorischen Objekte zählen , zu einer analytischen Darstellung kombinatorischer Objekte überzugehen (dieser erste Schritt wird von Flajolet der symbolischen Methode qualifiziert ). Die Werkzeuge der komplexen Analyse ( Berechnung von Rest , Punkt col , Lokalisierung der Singularitäten ) ermöglichen es dann, Ergebnisse über das Verhalten der Erzeugungsreihen (insbesondere über ihre Koeffizienten) zu erhalten. Dieser Ansatz kann daher als Cousin der analytischen Zahlentheorie angesehen werden , was sich insbesondere in der Pionierarbeit von Mathematikern wie Godfrey Harold Hardy , Srinivasa Ramanujan , Gaston Darboux , George Pólya , Paul Erdős ... widerspiegelt.

Die analytische Kombinatorik ist das gemeinsame Merkmal aller Artikel von Flajolet, deren Verdienst darin besteht, die Stärke dieser Idee zu identifizieren und sie so zu verallgemeinern, dass sie zu einer Methode wird, die auf a priori sehr unterschiedliche Universen angewendet wird.

Analyse von Algorithmen im Durchschnitt

Analytische Kombinatorik findet eine natürliche Brutstätte für Anwendungen in der Analyse der Mittelungsalgorithmen , weil es oft auf der Untersuchung von einigen wichtigen Parametern von diskreten Strukturen bei der Berechnung basiert ( Bäume , Graphen , Hash - Tabellen , usw. Worte , Permutationen ...).

Flajolet untersuchte daher die Effizienz zahlreicher Varianten von Sortieralgorithmen, das Auftreten von Mustern in Text oder in Bäumen. Er arbeitete an den typischen Eigenschaften digitaler Bäume, planaren Karten (Anwendung auf Konnektivität), Graphen, funktionalen Anwendungen (Anwendung auf Pollards Rho-Algorithmus zur Faktorisierung von ganzen Zahlen), der Faktorisierung von Polynomen auf einem endlichen Körper und Modellen von Urnen (einschließlich dieser) von Ehrenfest , einem Bereich, der nach einem Artikel von Flajolet im Jahr 2004 eine starke Wiederbelebung erlebte und das Problem durch eine Neuformulierung in Form von Differentialgleichungen ausruhte und löste ). Er interessiert sich auch für das Paradoxon von Geburtstagen (Anwendung auf Hashing ), für die Theorie der Warteschlangen , für die Ermittlung der Identität von Polylogarithmen und Polyzetafunktionen , für die Diskretion von Sequenzen auf Kosten von Algorithmen. Euklidisch (was sich als verknüpft herausstellt) zur Riemannschen Hypothese  !) ...

Er arbeitete an der probabilistischen und effizienten Zählung großer Datenmengen zur zufälligen Erzeugung kombinatorischer Objekte (nach rekursiven Methoden und Boltzmann ) sowie zu Themen im Zusammenhang mit Algebra und Wahrscheinlichkeit . Er etablierte Phasenübergangsphänomene auf Zufallsgraphen ( Erdős - Rényi Modell ), kombinatorische Karten , legte die Grundlagen der Online-Algorithmen (probabilistische Zählung über log Zählung Algorithmen ), generali die Verwendung von Transformationen Integralen ( Mellin - Transformation ) für die Analyse von divide und Eroberungsalgorithmen, die "analytische" Verschlusseigenschaften verwendeten, um die Nichtalgebraizität bestimmter Sprachen oder die Nicht-D-Endlichkeit bestimmter Strukturen zu zeigen, führten eine kombinatorische Synthese der Verbindung zwischen fortgesetzten Brüchen , orthogonalen Polynomen und zufälligen Spaziergängen durch die Analyse von Singularitäten mit Andrew Odlyzko .

Diese Arbeiten haben Phänomene des universellen asymptotischen Verhaltens hervorgehoben, insbesondere für die durchschnittliche Höhe zufälliger Bäume (Frage nach der Größe des Stapels bei rekursiven Aufrufen und auch nach einem verwandten Problem in der Informatik: der Registerfunktion, die ebenfalls entspricht die Horton-Strahler-Zahl in der Hydrographie).

Er hatte eine besondere Vorliebe für spezielle Funktionen (wie die Airy-Funktion , die Bessel-Funktionen , die Jacobi-Ellipsenfunktionen ) und mathematische Konstanten und gab verschiedene Algorithmen an, um diese mit hoher Genauigkeit zu berechnen (Spielen zwischen Leistungsreihen / Integral, Konvergenzbeschleunigungsdiagrammen). .

Formale Berechnung

Philippe Flajolet trug zur Entwicklung mehrerer Algorithmen für die Automatisierung bei, darunter über die Computeralgebra mathematische Berechnungen (Gesetz über asymptotische Aufzählungsgrenzen, erschöpfende Erzeugung, zufällige Erzeugung).

Sehr früh hatte Flajolet mit seinem Kollegen Jean-Marc Steyaert, mit dem er seine Doktorarbeit zusammen schrieb, die Vision von Software, die es ermöglichen sollte, viele ihrer Berechnungen zu automatisieren. Dies führte in den 1980er Jahren, als Computeralgebra-Systeme aufkamen , zum Luo-System und zur „ Combstruct  “ -Bibliothek  der Maple- Software , die von ihren Doktoranden Bruno Salvy und Paul Zimmermann  (en) entwickelt wurde .

Flajolet hat dazu beigetragen, in der Kombinatorik und im formalen Kalkül den Begriff der Holonomie in seiner Neuformulierung in Bezug auf die D-Endlichkeit zu fördern , dh in Reihen, die Differentialgleichungen verifizieren, ein Feld, das hauptsächlich von Ira Gessel , Richard Peter Stanley und Doron Zeilberger entwickelt wurde . Er gab verschiedene Kriterien der Nicht-Holonomie an und etablierte auch die Holonomie vieler kombinatorischer Probleme.

Wir schulden ihm auch den "Flajolet-Salvy" -Algorithmus, der feststellt, dass die Verzweigungsverfolgung für eine algebraische Funktion entscheidbar ist, oder den "Platypus" -Algorithmus, der symmetrische Funktionen manipuliert, um das minimale Polynom bestimmter algebraischer Funktionen zu berechnen. Im Allgemeinen war Flajolet stets bemüht, die Automatisierung der von ihm entwickelten symbolischen und analytischen Methoden sicherzustellen, und präsentierte seine Methoden daher in seinen Artikeln häufig als Algorithmus.

Phasenübergang: zwischen Analyse und Wahrscheinlichkeitstheorie

Data Flow Mining-Algorithmus

Flajolet ist der Autor eines Data Flow Mining- Algorithmus  : des Flajolet-Martin-Algorithmus .

Zufällige Generierung

Er entwickelte auch das Konzept von Buffons Maschinen , das auf einem einfachen und effizienten Mittel basiert, um verschiedene Gesetze (auch mit transzendenten Parametern) mit wenigen Bits zu simulieren.

Bunte Terminologien

Wir schulden ihm mehrere Terminologien, die aus der Community stammen, um die zentralen Ideen seiner Forschung hervorzuheben oder gelegentlich mit Humor mit verschiedenen kulturellen Referenzen zu flirten: analytische Kombinatorik , Analyse von Singularitäten , symbolische Methode , Kernel-Methode , probabilistisches Zählen , Pumpmomente , Satz Drmota-Lalley Woods , Satz Quasi-Kräfte Hwang , Satz Borges , Gas / Flüssig / Fest-Phasen (für Diagramme), Umriss Camembert Modell Urnen mabinogiennes oder OK Corral , Rices Methode , magische Dualität , Boltzmanns Methode , Buffons Maschinen ...

Forschungsstrukturierung

Philippe Flajolet hat eine führende Rolle bei der Strukturierung der nationalen und internationalen Forschung in der mathematischen Informatik gespielt und verschiedene Forscher zu gemeinsamen Themen zusammengebracht, insbesondere zu diskreter Mathematik, komplexer Analyse, Wahrscheinlichkeiten, Algorithmen, Computeralgebra, statistischer Physik und Bioinformatik.

Er hatte verschiedene administrative Aufgaben (Team- und Projektmanagement), wissenschaftliche Komitees, die Ausarbeitung eines Strategieplans für INRIA, AERES-Experten ... inne, jedoch seine Abneigung gegen gemeinsame Sprache und Verwaltungsreden, die durch ein einstimmig angesehenes Gespenst und unbestreitbare menschliche Qualitäten ausgeglichen wurden machte ihn zu einem besonderen Charakter, von dem man manchmal darum bat, Vermittler in einem solchen oder einem solchen Kirchturmstreit zu sein, oder ganz einfach, öfter, um Rat zu holen.

Auszeichnungen

Philippe Flajolet wurde 1993 zum korrespondierenden Mitglied der Académie des Sciences gewählt, danach zum Mitglied18. November 2003(im Bereich Mechanik und Informatik). Er wurde 1995 auch zum Mitglied der Academia Europaea und dann zum Mitglied der Europäischen Akademie der Wissenschaften gewählt . Er erhielt 1986 den wissenschaftlichen Hauptpreis der Union des Assurances de Paris und 1994 den Michel-Monpetit-Preis der Académie des Sciences. Im selben Jahr wurde er an der Université libre de Bruxelles mit der Ehrendoktorwürde ausgezeichnet . 2004 erhielt er die CNRS-Silbermedaille .

Philippe Flajolet wird zum Ritter der Ehrenlegion ernanntJuli 2010.

1998 wurde ihm anlässlich seines fünfzigsten Geburtstages eine Sonderausgabe der Zeitschrift Algorithmica gewidmet, die insbesondere eine Zusammenfassung seiner Forschungsergebnisse enthält. Die Zeitschrift Discrete Mathematics widmete sich in ihrem Band 306 von 2006 den einflussreichsten Artikeln seit ihrer Gründung im Jahr 1971 und überarbeitete insbesondere Philippe Flajolets Artikel „Combinatorial Aspects of Continued Fractions“ , der ursprünglich 1980 veröffentlicht wurde.

Zum 60-jährigen Jubiläum wurde ein Kolloquium organisiert Dezember 2008und ein Band der Zeitschrift Discrete Mathematics & Theoretical Computer Science war dieser Veranstaltung gewidmet. Viele Magazine haben in seinem Gedächtnis einen Nachruf veröffentlicht, darunter die Gazette des mathématiciens de la Société mathatique de France , die in ihrer Nummer 129 verschiedene Zeugnisse von Verwandten gab und so die Karriere von Philippe Flajolet erzählte. ImJuni 2011Die Konferenzen Formal Power Series und Algebraic Combinatorics and Analysis of Algorithms waren ihm gewidmet. Ein Kombinationsseminar in Ile-de-France trägt jetzt seinen Namen. Eine Konferenz, die seine wissenschaftliche Karriere nachzeichnet, fand in Paris stattDezember 2011.

Philippe Flajolet war sehr interessiert in der Linguistik, insbesondere in Sanskrit , in Verbindung mit Gérard Huet , seinem Kollegen von INRIA und der Akademie der Wissenschaften. In seiner Erinnerung wurde von seiner Frau ein Stipendium für die Doktorarbeit über Sanskrit ins Leben gerufen.

Seine Sammlung von Büchern über Linguistik und Mathematik (2.000 Werke) wurde der Linguistikbibliothek von Paris 7, der neuen Universitätsbibliothek der Universität Versailles (die ihm gewidmet ist) und der Bibliothek des International Mathematical Encounters Center gespendet .

Philippe Flajolet (posthum) und Robert Sedgewick sind die Gewinner des Leroy P. Steele-Preises 2019 im Abschnitt „Mathematische Popularisierung“ für ihr Buch Analytic Combinatorics .

Funktioniert

Anmerkungen und Referenzen

  1. "  Philippe Flajolet: Algorithmix ist verstorben  " , INRIA Alumni ,23. März 2011.
  2. "  Philippe Flajolet 1948–2011, von Dick Lipton  " .
  3. Zivilstand in der Akte von Personen, die seit 1970 in Frankreich gestorben sind
  4. Siehe das Foto von Philippe Flajolet an der Polytechnique
  5. Philippe Flajolet (1948 - 2011). Nachruf von Bruno Salvy, Bob Sedgewick, Michèle Soria, Wojciech Szpankowski, Brigitte Vallée . Rückblick auf das Lotharingian Combinatorial Seminar. Juni 2011.
  6. "  Einige Meinungen von Philippe Flajolet zur Verwaltung der Forschung  "
  7. "  Plötzliches Verschwinden einer wissenschaftlichen Figur. Tributbuch  "
  8. http://www.eurasc.org/members/members.asp?Cognome=f Liste der Mitglieder der Europäischen Akademie der Wissenschaften
  9. CNRS , „  Silbermedaillen - Die Preisträger 2004  “ , auf http://www.cnrs.fr (abgerufen am 21. Februar 2014 )
  10. Dekret vom 13. Juli 2010, veröffentlicht im JORF vom 14. Juli 2010.
  11. "Philippe Flajolets Forschung in der Kombinatorik und Analyse von Algorithmen" , H. Prodinger & W. Szpankowski, Algorithmica , 1998
  12. Kolloquium zum 60. Geburtstag von Philippe Flajolet
  13. Sonderausgabe von DMTCS zu Ehren von Philippe Flajolet
  14. http://smf4.emath.fr/Publications/Gazette/2011/129/
  15. "Philippe Flajolet Combinatorics Seminar"
  16. Konferenz "Philippe Flajolet and Analytic Combinatorics", Paris, Dezember 2011.
  17. "  Die UFR des Sciences möchte Philippe Flajolet ehren  " , in der Universitätsbibliothek der Wissenschaften von Versailles ,5. Dezember 2011
  18. Steele-Preis 2019 für mathematische Exposition geht an Philippe Flajolet und Robert Sedgewick .

Externe Links