Profondeur de Bennett

La profondeur de Bennett (ou profondeur logique de Bennett) est une mesure de la complexité en informatique, créée par le physicien et logicien américain Charles H. Bennett.

Elle vient en complément de la complexité de Kolmogorov : si celle-ci mesure la longueur du plus petit programme écrit pour créer une suite binaire, la profondeur de Bennett mesure, en nombre de pas, le temps de calcul de ce programme.

Comme son nom veut l'indiquer, cette mesure ajoute une seconde dimension à la théorie de la complexité ou, plus précisément, à la théorie algorithmique de l'information. Par exemple, une image entièrement blanche et une image entièrement aléatoire (en pixels noirs ou blancs) auront des valeurs de complexité de Kolmogorov très différentes (faible pour l'image blanche, forte pour l'image totalement aléatoire), mais auront toutes deux de faibles valeurs de profondeur de Bennett.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.