|
Ravindran KannanRavi Kannan
Ravi Kannan sur sa page à l'université Yale
Ravindran Kannan, appelé Ravi, né le à Chennai[1] est un informaticien et mathématicien. Il est chercheur principal (Principal Researcher) chez Microsoft Research Inde, où il dirige le groupe de recherche en algorithmique. Il est aussi premier adjoint de la faculté d'informatique et du département d'automation à l'Indian Institute of Science de Bangalore. BiographieKannan a fait ses études supérieures à l'Institut indien de technologie de Bombay et a obtenu un Ph.D. à l'université Cornell, en 1980, sous la direction de Leslie Earl Trotter, intitulée The size of numbers in the analysis of certain algorithms[2]. Il a enseigné au Massachusetts Institute of Technology, puis a été professeur à l'université Carnegie-Mellon, et ensuite professeur d'informatique et de mathématiques appliquées à l'université Yale sur la chaire William K. Lanman Jr. et il rejoint enfin Microsoft. RechercheDomaines de rechercheSes intérêts en recherche comprennent l'algorithmique, l'informatique théorique et les mathématiques discrètes ainsi que l'optimisation. Ses travaux se concentrent sur le développement d'algorithmes efficaces pour des problèmes de nature mathématique, et souvent géométriques, qui apparaissent en informatique. Il a travaillé sur des algorithmes d'optimisation linéaire en nombres entiers, la géométrie des nombres, les marches aléatoires dans des espaces de dimension arbitraire, les algorithmes randomisés pour l'algèbre linéaire et des algorithmes d'apprentissage pour des ensembles convexes. Avec Alan M. Frieze, Kannan développe une version algorithmique du « lemme de régularité de Szemerédi ». Ils introduisent un lemme de régularité faible qui devient un outil combinatoire important pour divers types d'algorithmes (algorithme de fouille de flots de données, limites de graphes, algorithmes sous-linéaires). En 1991, Kannan publie un algorithme efficace (c'est-à-dire en temps polynomial) pour résoudre le « problème des pièces de monnaie », aussi appelé « problème de Frobenius » : il s'agit de déterminer le plus grand entier (appelé nombre de Frobenius) qui ne peut pas être représenté comme somme de nombres pris dans un ensemble donné. Par exemple, si l'on possède des pièces de valeur unitaire 3 et 5, le nombre de Frobenius est 7 : tout entier n plus grand peut être écrit sous la forme n = 3i + 5j (avec i et j entiers naturels). Dans ce cas simple de deux nombres a et b, une formule explicite, souvent attribuée à tort à Sylvester, fait partie du folklore mathématique (en) : le nombre de Frobenius est ab – a – b. Contributions principalesParmi ses contributions principales qui lui ont valu les prix dont il est lauréat figurent :
Autres publications (sélection)
Prix et récompenses
Notes et références
Liens externes
|
