Théorie de la complexité algorithmique

Théorie de la complexité algorithmique

Théorie algorithmique de l'information

La Théorie algorithmique de l'information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d'un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing.

Cette théorie permet également de formaliser la notion de complexité d'un objet, dans la mesure où l'on considère qu'un objet (au sens large) est d'autant plus complexe qu'il faut beaucoup d'informations pour le décrire, ou - à l'inverse -, qu'un objet contient d'autant plus d'informations que sa description est longue. La théorie algorithmique de l'information est fondée sur cette équivalence : la description d'un objet est formalisée par un algorithme d'une machine de Turing, et sa complexité, ou son contenu en information, est alors formalisé par certaines caractéristiques de l'algorithme : sa longueur ou son temps de calcul.

Ces fondements sont différents de ceux de la théorie de l'information de Shannon : cette dernière n'utilise pas la notion de calculabilité et n'a de sens que par rapport à un ensemble statistique de données. Cependant, les deux théories sont compatibles et des liens formels entre elles peuvent être établis.

Alors que la théorie de l'information de Shannon n'a eu que peu d'applications en dehors de l'informatique, la théorie algorithmique de l'information a été utilisée avec succès dans les domaines de la biologie, de la physique et même de la philosophie.

Sommaire

Présentation informelle

L'idée principale de la théorie algorithmique de l'information est qu'une chose est d'autant plus complexe, ou contient d'autant plus d'information, qu'elle est difficile à expliquer, c'est-à-dire fondamentalement longue à expliquer. Voici par exemple trois descriptions d'objets :

D1 : "un mur tout blanc de 1 m sur 1 m."

D2 : "un mur tout blanc de 1m sur 1m, avec une rayure rouge horizontale de 2 cm de large en bas, une autre 8 cm au dessus, encore une autre 8 cm au dessus, encore une autre 8 cm au dessus, encore une autre 8 cm au dessus, encore une autre 8 cm au dessus, encore une autre 8 cm au dessus, encore une autre 8 cm au dessus, encore une autre 8 cm au dessus, encore une autre 8 cm au dessus et une dernière encore 8 cm au dessus."

D2' : "un mur tout blanc de 1 m sur 1 m, avec des rayures rouges horizontales de 2 cm de large, de bas en haut tous les 10 cm."

En termes de longueur de description, D1 est plus courte que D2' qui est plus courte que D2. Que D1 soit la plus courte description semble normal, et est lié au fait que l'objet décrit est "plus simple". Mais en ce qui concerne D2 et D2', les objets décrits sont identiques bien que D2' soit plus courte que D2. Ainsi la longueur brute d'une description n'est pas une mesure parfaitement adapté.

L'idée "algorithmique" est alors de considérer, comme complexité de l'objet décrit, sa plus courte description possible. Idée "algorithmique" dans le sens où la description n'est pas forcément extensive, mais peut - comme D2' dans l'exemple ci-dessus - décrire un procédé d'obtention de l'objet (ici : tracer des bandes horizontales à intervalles réguliers).

Ainsi, un objet sera d'autant plus compliqué qu'on ne peut le décrire plus brièvement qu'une liste exhaustive de ses propriétés... ce dernier cas constituant le cas limite d'une complexité maximale.

Principes de la théorie

Première théorie algorithmique de l'information (Solomonov, Kolmogorov, Chaitin)

Voir l'article Complexité de Kolmogorov.


Deuxième théorie algorithmique de l'information (Levin, Chaitin, Schnorr)

Voir aussi

Articles connexes

Ce document provient de « Th%C3%A9orie algorithmique de l%27information ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorie de la complexité algorithmique de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Theorie de la complexite algorithmique — Théorie algorithmique de l information La Théorie algorithmique de l information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d un ensemble de données, en utilisant… …   Wikipédia en Français

  • Complexite algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Complexité Algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Theorie de la complexite — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Théorie de la complexité des algorithmes — Pour les articles homonymes, voir Théorie de la complexité. La théorie de la complexité des algorithmes étudie formellement la quantité de ressources (en temps et en espace) nécessitée par l exécution d un algorithme ainsi que la difficulté… …   Wikipédia en Français

  • Complexité algorithmique — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Complexité algorithmique en informatique théorique. Complexité de Kolmogorov, appelée aussi complexité algorithmique, en théorie algorithmique de l… …   Wikipédia en Français

  • Théorie de la complexité — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le terme théorie de la complexité peut désigner : L étude des systèmes complexes. La théorie de la complexité des algorithmes, un domaine de l… …   Wikipédia en Français

  • Complexite — Complexité Illustration métaphorique de la complexité. Les objets (tuyaux) intègrent de nombreux facteurs (taille, diamètre, situation, interconnexion, robinets, ...), ce qui rend la compréhension hardue. La complexité est une notion utilisée en… …   Wikipédia en Français

  • Complexité politique — Complexité Illustration métaphorique de la complexité. Les objets (tuyaux) intègrent de nombreux facteurs (taille, diamètre, situation, interconnexion, robinets, ...), ce qui rend la compréhension hardue. La complexité est une notion utilisée en… …   Wikipédia en Français

  • Complexité sociale — Complexité Illustration métaphorique de la complexité. Les objets (tuyaux) intègrent de nombreux facteurs (taille, diamètre, situation, interconnexion, robinets, ...), ce qui rend la compréhension hardue. La complexité est une notion utilisée en… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”