mé triqu e ( lo ng ue ur, la rg ue ur .. . ) es t
importante a lo rs.
Il y a bie n de ux concepts de complex ité
à ne pas co nfo ndre : la « co mplex ité
a léato ire » et la « complex ité o rgani sée
(ou structure lle) » . Po ur l' illu stre r plus
préc iséme nt, cons idérons le pro bl è me
de la description au millimètre près d ' une
ma ison dont les murs sont couverts de
c ré pi . Le pl a n de la ma ison correspo nd
à la complex ité o rgani sée de la ma ison .
Ce plan ne préc ise pas les dess ins du
c rép i sur les murs. La descripti o n complète de la ma ison , qui contie nt to us les
détails du crépi , compo rte bien plus d' informa ti o ns que celle du pl an . La ma ison
possède une complexité organisée de
ta ill e moyenne (un pl an n 'est pas très
compliqué comparée pa r exemple à un
être viva nt ) et une complexité aléatoire
assez grande.
Programmes courts et temps de calcul
Le concept mathé matique de complex ité
a léato ire a été ide ntifié da ns les a nnées
1960, g râce a ux travaux pré limina ires
de Ray S o lo mo no ff , e t à ce ux d ' A nd reï Ko lmogorov, de Gregory C ha it in
et de Leonid Lev in . Cette complex ité
se no mme complexité de Kolmogorov.
Elle est dé fini e co mme la ta ille du plus
peti t progra mme po ur un o rdinate ur de
référe nce - a ppe lé machine universelle - capable de produire l'objet numérique auque l o n s' inté resse e t que l'on
a s upposé éc rit so us la fo rme d ' une
sui te de O et de 1 (image numérique, son
numé rique ... ). Une suite d ' un milli a rd
de O a une fa ibl e co mpl ex ité de Ko lmogorov, de mê me qu ' un milli a rd de
c hi ffres bin a ires d e n (ca r d es p rogra mmes courts pe rme tte nt de les ca lcul er). Une suite a léato ire d ' un milli ard
de O e t de 1, à l ' in verse, possède une
co mpl ex ité de Ko lmogorov d 'enviro n
un milli ard .
POUR L'INFORMATIQUE
Raymond Solomonoff
(1926-2009).
La dé finiti o n de la profo nde ur log ique
de Be nne tt s'appuie sur la théori e de la
calc ul a bilité e t es t assez tec hnique à
é no ncer ; e ll e fa it e n partic ulie r inte rvenir les no ti o ns de machine de Turing
uni versell e e t de fo nc ti o ns récurs ives .
Mais cela n'empêche pas de comprendre
assez bie n intuiti vement de quo i il s'agit.
Po ur tro uver le« bo n » concept mathématique assoc ié à la complex ité structure lle, C harles Bennett a mené un trava il
d 'ana lyse. Po ur lui , un o bje t fo rte me nt
organisé contie nt nécessaire me nt e n lui
la trace d ' un lo ng process us d 'élaborati o n , de ré fl ex io n o u d 'évo luti o n qui
correspo nd à une fo rme de calcul . Dé fi -
nir la co mplex ité o rgani sée d ' un o bje t
se ramè ne do nc au problè me de la dé fi -
niti o n d ' une no ti o n de contenu en calcul. E n in fo rm a tiqu e th éor iqu e, les
trava ux s ur les a lgo rithmes pre nne nt
bi e n e n co mpte les te mp s de ca lcul
(classes P, NP, EXP ... ), ma is ces é tudes
s ' attache nt surto ut a ux compo rte me nts
asy mpto tiques des a lgorithmes, a lo rs
qu ' ic i o n n 'a à fa ire qu 'à des o bj e ts
numé riques fini s, o u que l 'on ra mè ne à
des o bje ts fini s e n fi xant un ni veau de
préc is io n cons idé ré comme s u ffisant
po ur la numé ri sati o n . Po ur dé finir le
conte nu e n ca lc ul d ' un o bje t numé rique
(c'est-à-dire sa complex ité o rgani sée),
Be nnett propose de considé re r le te mps
de calcul que pre nd le programme minima l (celui do nt la ta ille définit la complex ité de Ko lmogorov) po ur produire
l'objet a uque l on s' inté resse . C'est une
Hors-série n° 52. Mathématiques & informatique Tangente
importante a lo rs.
Il y a bie n de ux concepts de complex ité
à ne pas co nfo ndre : la « co mplex ité
a léato ire » et la « complex ité o rgani sée
(ou structure lle) » . Po ur l' illu stre r plus
préc iséme nt, cons idérons le pro bl è me
de la description au millimètre près d ' une
ma ison dont les murs sont couverts de
c ré pi . Le pl a n de la ma ison correspo nd
à la complex ité o rgani sée de la ma ison .
Ce plan ne préc ise pas les dess ins du
c rép i sur les murs. La descripti o n complète de la ma ison , qui contie nt to us les
détails du crépi , compo rte bien plus d' informa ti o ns que celle du pl an . La ma ison
possède une complexité organisée de
ta ill e moyenne (un pl an n 'est pas très
compliqué comparée pa r exemple à un
être viva nt ) et une complexité aléatoire
assez grande.
Programmes courts et temps de calcul
Le concept mathé matique de complex ité
a léato ire a été ide ntifié da ns les a nnées
1960, g râce a ux travaux pré limina ires
de Ray S o lo mo no ff , e t à ce ux d ' A nd reï Ko lmogorov, de Gregory C ha it in
et de Leonid Lev in . Cette complex ité
se no mme complexité de Kolmogorov.
Elle est dé fini e co mme la ta ille du plus
peti t progra mme po ur un o rdinate ur de
référe nce - a ppe lé machine universelle - capable de produire l'objet numérique auque l o n s' inté resse e t que l'on
a s upposé éc rit so us la fo rme d ' une
sui te de O et de 1 (image numérique, son
numé rique ... ). Une suite d ' un milli a rd
de O a une fa ibl e co mpl ex ité de Ko lmogorov, de mê me qu ' un milli a rd de
c hi ffres bin a ires d e n (ca r d es p rogra mmes courts pe rme tte nt de les ca lcul er). Une suite a léato ire d ' un milli ard
de O e t de 1, à l ' in verse, possède une
co mpl ex ité de Ko lmogorov d 'enviro n
un milli ard .
POUR L'INFORMATIQUE
Raymond Solomonoff
(1926-2009).
La dé finiti o n de la profo nde ur log ique
de Be nne tt s'appuie sur la théori e de la
calc ul a bilité e t es t assez tec hnique à
é no ncer ; e ll e fa it e n partic ulie r inte rvenir les no ti o ns de machine de Turing
uni versell e e t de fo nc ti o ns récurs ives .
Mais cela n'empêche pas de comprendre
assez bie n intuiti vement de quo i il s'agit.
Po ur tro uver le« bo n » concept mathématique assoc ié à la complex ité structure lle, C harles Bennett a mené un trava il
d 'ana lyse. Po ur lui , un o bje t fo rte me nt
organisé contie nt nécessaire me nt e n lui
la trace d ' un lo ng process us d 'élaborati o n , de ré fl ex io n o u d 'évo luti o n qui
correspo nd à une fo rme de calcul . Dé fi -
nir la co mplex ité o rgani sée d ' un o bje t
se ramè ne do nc au problè me de la dé fi -
niti o n d ' une no ti o n de contenu en calcul. E n in fo rm a tiqu e th éor iqu e, les
trava ux s ur les a lgo rithmes pre nne nt
bi e n e n co mpte les te mp s de ca lcul
(classes P, NP, EXP ... ), ma is ces é tudes
s ' attache nt surto ut a ux compo rte me nts
asy mpto tiques des a lgorithmes, a lo rs
qu ' ic i o n n 'a à fa ire qu 'à des o bj e ts
numé riques fini s, o u que l 'on ra mè ne à
des o bje ts fini s e n fi xant un ni veau de
préc is io n cons idé ré comme s u ffisant
po ur la numé ri sati o n . Po ur dé finir le
conte nu e n ca lc ul d ' un o bje t numé rique
(c'est-à-dire sa complex ité o rgani sée),
Be nnett propose de considé re r le te mps
de calcul que pre nd le programme minima l (celui do nt la ta ille définit la complex ité de Ko lmogorov) po ur produire
l'objet a uque l on s' inté resse . C'est une
Hors-série n° 52. Mathématiques & informatique Tangente