Théorie de la complexité algorithmique

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

La Théorie de la complexité algorithmique, initiée par Kolmogorov, est à rapprocher de la théorie de l'information de Shannon. Attention ! Elle ne doit pas être confondue avec la théorie de la complexité (plus connue) qui concerne les temps de calculs d'algorithmes associès à des classes de problèmes. Toutefois, ces théories ont en commun la notion de codage de l'information. La longueur de ce codage sert alors de mesure de la complexité de information.

[modifier] Présentation informelle

L'idée principale de la théorie de la complexité algorithmique, est qu'une chose est d'autant plus complexe 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."

D3 : "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 D3 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 D3, les objets décrits sont identiques bien que D3 soit plus courte que D2. Ainsi la longueur 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 D3 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.