Profondeur logique de Bennett
- Profondeur logique de Bennett
-
Profondeur de Bennett
La profondeur de Bennett (ou profondeur logique de Bennett) est un concept de logique informatique créé par le physicien et logicien américain Charles H. Bennett.
Il vient en complément du concept de complexité de Kolmogorov : si celle-ci mesure la longueur du plus petit programme écrit pour générer une suite binaire x, la profondeur de Bennett mesure, en nombre de pas, le temps de calcul de ce programme.
Comme son nom l'indique, ce concept ajoute une seconde dimension à la mesure en théorie de la complexité. 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.
Référence
- Conférence J.P. Delahaye, colloque Émergences, décembre 2008 (Programme)
Articles connexes
Portail de l’informatique
Catégories : Informatique théorique | Théorie algorithmique de l'information | Calculabilité
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Profondeur logique de Bennett de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Profondeur de Bennett — La profondeur de Bennett (ou profondeur logique de Bennett) est un concept de logique informatique créé par le physicien et logicien américain Charles H. Bennett. Il vient en complément du concept de complexité de Kolmogorov : si celle ci… … Wikipédia en Français
Charles H. Bennett — Pour les articles homonymes, voir Bennett et Charles H. Bennett (soldat). Charles H. Bennett (1943 ) est un physicien et cryptologue américain qui travaille dans les laboratoires de recherche d IBM Research. Les travaux récents de Bennett chez… … Wikipédia en Français
Orgueil et Préjugés — Orgueil et préjugés[N 1] … Wikipédia en Français
Adam Bede — Auteur George Eliot Genre Roman Version originale Titre original Adam Bede Éditeur original William Blackwood Sons Langue originale anglais Pays d or … Wikipédia en Français
ANGLAISE (LITTÉRATURE) — Toute histoire littéraire sous entend une perspective et la perspective a rapport au temps présent, le passé étant vu en fonction de problèmes contemporains; ainsi, maint écrivain dont le nom est consacré dans le panthéon des célébrités peut se… … Encyclopédie Universelle
Le naufrage du Titanic — Naufrage du Titanic Le Titanic à Southampton le 10 avril 1912. Le naufrage du Titanic a mis fin à la traversée inaugurale du RMS Titanic, qui devait relier Southampton à New York … Wikipédia en Français
Naufrage du Titanic — Le Titanic à Southampton le 10 avril 1912. Le naufrage du Titanic a mis fin à la traversée inaugurale du RMS Titanic, qui devait relier Southampton à New York[A 1 … Wikipédia en Français
Robert Browning — Pour les articles homonymes, voir Browning. Robert Browning … Wikipédia en Français
Dr House — Pour les articles homonymes, voir House. Dr House Logo original de la série Titre original … Wikipédia en Français
Elizabeth Bennet — Pour les articles homonymes, voir Bennet. Elizabeth Bennet Personnage de fiction apparaissant dans Orgu … Wikipédia en Français
