Andrzej Ehrenfeucht

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Andrzej Ehrenfeucht
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Voir et modifier les données sur Wikidata (87 ans)
VilniusVoir et modifier les données sur Wikidata
Nationalités
Formation
Activités
Autres informations
A travaillé pour
Domaine
Membre de
Directeur de thèse
Site web

Andrzej Ehrenfeucht (né le à Vilnius) est un mathématicien et informaticien théoricien américain d'origine polonaise. Il travaille principalement dans les domaines de logique mathématique, combinatoire et bio-informatique.

Biographie scientifique[modifier | modifier le code]

Ehrenfeucht étudie les mathématiques à l'université de Varsovie et soutient en 1961[1] une thèse sous la direction d'Andrzej Mostowski à l'institut de mathématiques de l'Académie polonaise des sciences[2],[3]. De 1961 à 1965 il est professeur assistant à Varsovie, avec un séjour à Berkeley; à partir de 1965, il est professeur assistant à Stanford puis à l'université de Californie à Los Angeles. Depuis 1971, il est d'abord professeur associé, puis professeur titulaire d'informatique à l'université du Colorado à Boulder et depuis 2006 « distinguished professor » de l’université[4],[1].

Ehrenfeucht travaille en logique mathématique, théorie des jeux et en théorie des modèles. Il est connu pour l'invention de la technique du jeu d'Ehrenfeucht-Fraïssé avec Roland Fraïssé qui permet de démontrer l'équivalence élémentaire ou la non-équivalence de structures en théorie des modèles[5].

La suite d'Ehrenfeucht-Mycielski nommée d'après lui et Jan Mycielski, est une suite binaire avec des propriétés pseudo-aléatoires[6].

Ehrenfeucht travaille en algorithmique, notamment en théorie des graphes, en combinatoire des mots, sur les algorithmes de pattern matching et d'apprentissage automatique, sur les langages formels et les théories des équations. Il est connu pour avoir formulé la conjecture, appelée « conjecture d'Ehrenfeucht » qui énoncé que tout sous-ensemble S d'un monoïde libre finiment engendré possède un sous-ensemble fini T avec la propriété que deux morphismes qui coïncident sur T coïncident sur S, conjecture qui a provoqué de nombreux travaux avant d'avoir été prouvée en 1985[7]. Maintenant, la conjecture s'appelle le « théorème de compacité ».

Il travaille aussi en bio-informatique et principalement sur le traitement de l’information par la cellule vivante, où il effectue ses recherches sur la base d'une vaste collaboration interdisciplinaire. Il s'intéresse par ailleurs aussi à la l'enseignement des mathématiques, et est actif dans la formation continue d'enseignants de mathématiques[8].

Parmi ses doctorants, on compte les bio-informaticiens Eugene Myers et David Haussler. Ehrenfeucht est marié avec Ina Tarski, la fille d'Alfred Tarski.

Honneurs et distinctions[modifier | modifier le code]

En 2002 Ehrenfeucht reçoit le « Faculty Research Award » de l'université du Colorado (College of Engineering and Applied Science) et en 2005 le « Boulder Faculty Assembly Award ».

Ehrenfeucht est membre de l'Academia Europaea.

Deux volumes d'hommages ont été publiés en son honneur, le premier pour son 65e anniversaire[1], le deuxième[9] à l'occasion de son 80e anniversaire.

Publications[modifier | modifier le code]

  • Andrzej Ehrenfeucht, « An application of games to the completeness problem for formalized theories », Fundamenta Mathematicae, vol. 49,‎ 1960/1961, p. 129–141.
  • Andrzej Ehrenfeucht et Jan Mycielski, « A pseudorandom sequence: how random is it? », American Mathematical Monthly, vol. 99,‎ , p. 373.
  • Patricia Baggett et Andrzej Ehrenfeucht, Breaking Away from the Math Book : Creative Projects for Grades K-6, Rowman & Littlefield Education, , 175 p. (ISBN 9781566762991).
  • Andrzej Ehrenfeucht, Tero Harju et Grzegorz Rozenberg, The Theory of 2-structures : A Framework for Decomposition and Transformation of Graphs, World Scientific, , 290 p. (ISBN 9789810240424).
  • Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott et Grzegorz Rozenberg, Computation in Living Cells : Gene Assembly in Ciliates, Springer Science & Business Media, , 202 p. (ISBN 9783540407959).
  • Andrzej Mostowski, Andrzej Ehrenfeucht, V. Wiktor Marek et Marian Srebrny, Andrzej Mostowski and Foundational Studies, IOS Press, , 447 p. (ISBN 9781586037826)

Bibliographie[modifier | modifier le code]

Volumes d'hommages
Conjecture d'Ehrenfeucht

Notes et références[modifier | modifier le code]

Liens externes[modifier | modifier le code]