Ravindran Kannan

Ravi Kannan Descripción de esta imagen, también comentada a continuación Ravi Kannan en su página en la Universidad de Yale Llave de datos
Nacimiento 12 de marzo de 1953
Chennai ( India )
Casa Bangalore
Áreas Ciencias de la Computación
Diplomado Universidad de Cornell
Director de tesis Leslie Earl Trotter
Premios Premio Fulkerson (1991)
Premio Knuth (2011),

Ravindran Kannan , llamado Ravi , nacido el12 de marzo de 1953en Chennai es un científico informático y matemático. Es investigador principal de Microsoft Research India, donde dirige el Grupo de investigación de algoritmos. También es el primer asistente de la facultad de informática y del departamento de automatización del Instituto Indio de Ciencias en Bangalore .

Biografía

Kannan se educó en el Instituto Indio de Tecnología de Bombay y obtuvo un doctorado de la Universidad de Cornell en 1980 bajo la supervisión de Leslie Earl Trotter, titulado El tamaño de los números en el análisis de ciertos algoritmos . Enseñó en el Instituto de Tecnología de Massachusetts , luego fue profesor en la Universidad Carnegie-Mellon y luego profesor de Ciencias de la Computación y Matemáticas Aplicadas en la Universidad de Yale en la cátedra William K. Lanman Jr. y finalmente se unió a Microsoft .

Investigar

Áreas de investigación

Sus intereses de investigación incluyen algoritmos , informática teórica y matemáticas discretas , así como optimización . Su trabajo se centra en el desarrollo de algoritmos eficientes para problemas de naturaleza matemática, y muchas veces geométricos, que surgen en la informática. Trabajó en algoritmos de optimización lineal de números en enteros , la geometría de números , los paseos aleatorios en espacios de dimensión arbitraria, los algoritmos aleatorios para álgebra lineal y algoritmos de aprendizaje para conjuntos convexos .

Con Alan M. Frieze  (en) , Kannan desarrolló una versión algorítmica de la "  regularidad del lema de Szemerédi  ". Introducen un lema de regularidad débil que se convierte en una importante herramienta combinatoria para varios tipos de algoritmos ( algoritmo de minería de flujo de datos , límites de gráficos, algoritmos sublineales ).

En 1991, Kannan publicó un eficiente algoritmo (es decir en tiempo polinomial) para resolver el "  problema de la moneda  ", también llamado "problema de Frobenius  ": se trata de determinar el mayor entero (llamado número de Frobenius) que no se puede representar como la suma de números tomados de un conjunto dado. Por ejemplo, si tenemos monedas de valor unitario 3 y 5, el número de Frobenius es 7: cualquier entero n mayor se puede escribir como n = 3 i + 5 j (con i y j números naturales ). En este caso sencillo de dos números a y b , una fórmula explícita, a menudo erróneamente atribuida a Sylvester , es parte de folklore matemática  (en)  el número de Frobenius es ab - ab .

Contribuciones principales

Entre sus principales aportes que le han valido los premios de los que es galardonado se encuentran:

Otras publicaciones (selección)

Premios y reconocimientos

Notas y referencias

  1. Quién es quién en Frontiers in Science and Technology 1985
  2. (in) "  Ravindran Kannan  " en el sitio web del Proyecto de genealogía matemática .
  3. Investigador de Microsoft recibirá el premio ACM SIGACT Knuth "Copia archivada" (versión 29 de abril de 2011 en Internet Archive )

enlaces externos