« KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE »

KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 563 mots

La théorie de la complexité de Kolmogorov d'une suite numérique S est définie comme la taille, K(S), du plus court programme P qui, confié à une machine universelle (tout ordinateur contemporain en est une), produit la suite S. Cette notion est séduisante car elle synthétise en un seul nombre plusieurs mesures de complexité dont celle que propose la […] Lire la suite

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 626 mots

Dans le chapitre "La complexité algorithmique" : …  Les difficultés mathématiques rencontrées sont peut-être liées aux résultats logiques d'incomplétude (démontrés par Gödel en 1930) et dont la compréhension n'a cessé de s'approfondir, en particulier grâce à la théorie de la complexité d'Andreï Kolmogorov (1903-1987), formulée simultanément en 1965 par Kolmogorov et Gregory Chaitin. Cette théorie dite de la complexité algorithmique développe math […] Lire la suite

INFORMATION THÉORIE DE L'

  • Écrit par 
  • Henri ATLAN, 
  • Jean-Paul DELAHAYE, 
  • Étienne KLEIN
  •  • 3 063 mots

Dans le chapitre "Théorie algorithmique de l'information" : …  Si l'on se fixe pour but de compresser la chaîne de caractères s et si l'on suppose qu'on dispose pour cela d'une machine M, alors la valeur de l'information de s est la longueur du plus petit programme (écrit en binaire) qui, lorsqu'il fonctionne dans M, reconstitue la chaîne s . La puissance des machines n'est pas sans limite. Dès qu'on a affaire à des machines d'une certaine puissance, leur p […] Lire la suite

Recevez les offres exclusives Universalis