Conseil de recherches en sciences naturelles et en génie du Canada
Symbol of the Government of Canada

Liens de la barre de menu commune

Ancien lauréat
Bourse commémorative E.W.R. Steacie de 1996

Ming Li

Informatique

University of Waterloo


Lorsque Ming Li, chercheur en informatique, était au doctorat à l'Université Cornell au début des années 1980, son directeur de thèse, Juris Hartmanis, lui a remis plusieurs documents à lire sur « la complexité de Kolmogorov ». Il les a mis de côté, pour y revenir un an plus tard. Le professeur Li s'était rendu compte que cette théorie du caractère aléatoire, élaborée pour la première fois il y a environ trente ans, pourrait lui permettre de trouver la solution à un problème qu'il tentait de résoudre. Il a réussi, et c'est à ce moment-là qu'a commencé sa profonde fascination envers cette théorie.

Actuellement professeur à l'Université de Waterloo, Ming Li joue un rôle clé dans la mise en valeur et la démonstration de la puissance de la complexité de Kolmogorov. Son livre ( écrit en collaboration avec Paul Vitányi), An Introduction to Kolmogorov Complexity and Its Applications, est le premier ouvrage complet à être publié dans ce domaine. On l'utilise dans le cadre de séminaires aux cycles supérieurs dans le monde entier et de nombreuses parties ont été traduites en chinois, en japonais et en russe. L'ouvrage de Li et de Vitányi ont projeté la complexité de Kolmogorov du statut de concept novateur à un outil souple permettant de réaliser des recherches concrètes.

La force de la complexité de Kolmogorov réside dans le fait qu'elle permet de quantifier le caractère aléatoire des objets individuels d'une manière objective et absolue. Cette opération est impossible à réaliser au moyen de la théorie des probabilités traditionnelle. Par exemple, en informatique, il est souvent nécessaire de déterminer la vitesse d'exécution de certains programmes. Ce processus s'avère très difficile avec les méthodes conventionnelles étant donné que l'exécution du programme exige de nombreuses entrées de données, que chaque résultat doit être analysé, et qu'un délai moyen doit être calculé. à l'aide de la complexité de Kolmogorov, seulement une entrée de données est nécessaire pour compléter l'analyse.

L'un des aspects des travaux actuels du professeur Li (qui comprennent également l'apprentissage automatique et l'étude de la biologie par modélisation numérique) consiste à étendre la portée de l'utilisation de la complexité de Kolmogorov à l'analyse des programmes informatiques, l'analyse de la séquence d'ADN, la physique et le calcul. D'autres chercheurs suivent ses traces. « Depuis la parution de mon ouvrage en 1993, j'entends parler de chercheurs qui ont été inspirés par la complexité de Kolmogorov - de philosophes travaillant sur l'inférence inductive à des chercheurs en océanographie qui essaient d'utiliser ce concept pour mesurer la complexité des cris des dauphins, affirme M. Li. Cette idée est puissante : je ne suis pas surpris de ses nombreuses applications. »