Alan Michael Frieze (né le à LondresDates d'après American Men and Women of Science, Thomson Gale 2004) est un informaticien britannique.
Biographie Frieze étudie à l'Université d'Oxford (bachelor en 1966) et obtient son doctorat à l'université de Londres en 1975 avec Keith Wolfenden .. En 1968/69, il est « research officer » à British Rail et en 1969/70, il est programmeur à International Computers Limited (ICL). En 1970/71, il est lecturer à Polytechnic of North London (maintenant London Metropolitan University) et de 1972 à 1987, il enseigne à la Queen Mary University of London. Il est professeur à l'université Carnegie-Mellon depuis 1987. Il est marié avec Carol Mayfield, qui enseigne également l'informatique à l'Université Carnegie Mellon, depuis 1969. Ils ont deux enfants.
Recherche Avec Martin Dyer et Ravindran Kannan, il décrit en 1991 un algorithme en temps polynomial pour calculer les volumes des corps convexes en toutes les dimensions, algorithme pour lequel les trois ont reçu le prix Fulkerson en 1991. En outre, ce travail a été souligné comme l'un des développements les plus remarquables en matière d'algorithmique lors de l'attribution du prix Knuth à Ravindran Kannan. Le temps d'exécution de tous les algorithmes connus précédemment pour le calcul du volume augmente de façon exponentielle avec la dimension. Leur algorithme utilise la méthode de Monte-Carlo par chaînes de Markov (MCMC) et il est l'une des premières et des plus importantes applications de cette technique dans les algorithmes d'approximation.
Avec Ravindran Kannan, Frieze a élaboré une version algorithmique du lemme de régularité de Szemerédi... Dans leur article, ils ont introduit un lemme de régularité faible, qui est devenu un outil combinatoire important pour divers algorithmes (algorithmes de streaming, limites de graphes, algorithmes sous-linéaires).
Alan Frieze travaille en combinatoire probabiliste et ses applications en informatique théorique et en recherche opérationnelle. Il étudie en particulier les propriétés asymptotiques des graphes aléatoires, l'analyse du cas moyen des algorithmes et les algorithmes aléatoires. Ses travaux portent sur le comptage approximatif et le calcul de volume par le biais de marches aléatoires, la recherche de chemins disjoints dans les graphes expansifs, et l'exploration de la stabilité des algorithmes de routage.
Prix et distinctions
En 1991, il reçoit le prix Fulkerson avec Dyer et Kannan. En 1997, il a été boursier Guggenheim. En 2014, il est conférencier plénier au Congrès international des mathématiciens à Séoul ((Random structures and algorithms). Il est membre de l' American Mathematical SocietyList of Fellows of the American Mathematical Society, retrieved 29 December 2012.. Il est membre de la Society for Industrial and Applied Mathematics (SIAM) depuis 2011Siam Fellows Class of 2011.. En 2015, il est élu Simons Fellow. Un colloque en l'honneur de Frieze, appelé « Frieze Fest », a eu lieu à l'université Carnegie-Mellon en 2005« Carnegie Mellon Holds Workshop to Celebrate the Career of Influential Mathematician and Computer Scientist Alan Frieze » sur le site de CarnegieMellonToday
Publications (sélection) Alan Frieze a publié quelque 300 articles d'après DBLP, et un livre : . . .
Notes et références
Liens externes
Page d'accueil
Catégorie:Naissance en octobre 1945 Catégorie:Membre de l'American Mathematical Society Catégorie:Professeur à l'université Carnegie-Mellon Catégorie:Informaticien britannique Catégorie:Lauréat du prix Fulkerson