SAVOIRS
par Alain Valette
Espaces de Banach
et informatique théorique
Un problème d'analyse difficile peut être reformulé en théorie
des graphes et se trouver lié à certains concepts de
l'informatique théorique. Ce phénomène fréquent est une
manifestation forte de l'unité des mathématiques !
Les termes suiv is
d'un astérisque sont
défin is en encadré.
clan s le glossaire.
L
' é me rge nce d e l ' o rdin a te ur ,
dans la seconde mo itié du XX
0
s iècl e, a induit le déve lo ppeme nt d ' une no uvelle branche des mathématiques , l' in fo rmatique théorique, e t
do nc auss i ! 'appariti o n d' une no uvelle
espèce de sc ie ntifiques , les « in fo rmati c ie ns théori c ie ns », qui o nt la parti c ularité d ' ê tre a uss i à l ' a ise d eva nt un
c lav ie r qu ' a u ta bl eau no ir. li y a d es
as pects de l' in fo rmatique théorique que
l'on im ag ine bi e n: théori e des g raphes,
algorithmique, théorie de la complexité ...
li est pe ut-être plus surpre nant de vo ir
des in fo rmati c ie ns se pass io nner po ur
des pro bl è mes d 'ana lyse fo ncti o nne ll e
li és à la géo m é tri e d es es paces de
Ba nac h* !
Une notion subtile : la distorsion
A u dé pa rt se tro uve la noti o n d ' espace
mé trique * fini (X, cl). U ne faço n de la
compre nd re est d 'essayer de plo nger X
dans un espace de Banach* B bien connu ,
pa r exe mpl e un es pace e uc lidi e n d e
grande dime ns io n. Le prix à payer est
qu ' une applicati o n injecti ve!: X -+ B
n 'a a uc une ra ison de préserver les d istances. Pour mesurer comme ntfdéforme
les di sta nces e ntre X et B , o n introduit
la dis lo rs io n d e f , un no m bre da ns
l l ; 001 dé fini par:
. .
11/(x)- f(_r)II
d(x. r)
th.\ï ( f } == ma x
II x max
·
.
·
'" '
d(x .y)
•· • llf
robu ste: il est in va ri ant par exemple par
les homothéti es de B. Po ur avoir un in vari ant ne dépe ndant que de X, on prend
la bo rne in fé ri e ure sur to utes les appli -
cati o ns injecti ves te lles quef, et on définit la dis10rsion de X à va le urs da ns B :
c,,( X) = in f dist (f).
J x---n
En 1986, da ns un a rticle qui fo nde la
th éo ri e no n lin éa ire des espaces de
Ba nac h , le mathé ma ti c ie n be lge Jea n
Bo urga in (né e n 1954, méda ille Fie lds
1994) mo ntre q ue, s i B es t l'es pace
L''([O; IJ) , avec 1 :Sp<+oo, il ex iste une
constante C(p) > 0 (ne dépe nd ant que de
p) te ll e que:
CL"IIOII) (X),, C(p) ln 1x1.
A utre me nt dit , il ex iste un e applicati o n
injecti ve X-+ L'' do nt la d istors io n est
a u plu s logarithmiqu e e n le no m bre de
po in ts de X .
Passons ma in te na nt à la t héor ie des
graphes: si X est un graphe fi ni, d'e n80 Tangente Hors-série n°52. Mathématiques & informatique
par Alain Valette
Espaces de Banach
et informatique théorique
Un problème d'analyse difficile peut être reformulé en théorie
des graphes et se trouver lié à certains concepts de
l'informatique théorique. Ce phénomène fréquent est une
manifestation forte de l'unité des mathématiques !
Les termes suiv is
d'un astérisque sont
défin is en encadré.
clan s le glossaire.
L
' é me rge nce d e l ' o rdin a te ur ,
dans la seconde mo itié du XX
0
s iècl e, a induit le déve lo ppeme nt d ' une no uvelle branche des mathématiques , l' in fo rmatique théorique, e t
do nc auss i ! 'appariti o n d' une no uvelle
espèce de sc ie ntifiques , les « in fo rmati c ie ns théori c ie ns », qui o nt la parti c ularité d ' ê tre a uss i à l ' a ise d eva nt un
c lav ie r qu ' a u ta bl eau no ir. li y a d es
as pects de l' in fo rmatique théorique que
l'on im ag ine bi e n: théori e des g raphes,
algorithmique, théorie de la complexité ...
li est pe ut-être plus surpre nant de vo ir
des in fo rmati c ie ns se pass io nner po ur
des pro bl è mes d 'ana lyse fo ncti o nne ll e
li és à la géo m é tri e d es es paces de
Ba nac h* !
Une notion subtile : la distorsion
A u dé pa rt se tro uve la noti o n d ' espace
mé trique * fini (X, cl). U ne faço n de la
compre nd re est d 'essayer de plo nger X
dans un espace de Banach* B bien connu ,
pa r exe mpl e un es pace e uc lidi e n d e
grande dime ns io n. Le prix à payer est
qu ' une applicati o n injecti ve!: X -+ B
n 'a a uc une ra ison de préserver les d istances. Pour mesurer comme ntfdéforme
les di sta nces e ntre X et B , o n introduit
la dis lo rs io n d e f , un no m bre da ns
l l ; 001 dé fini par:
. .
11/(x)- f(_r)II
d(x. r)
th.\ï ( f } == ma x
II x max
·
.
·
'" '
d(x .y)
•· • llf
robu ste: il est in va ri ant par exemple par
les homothéti es de B. Po ur avoir un in vari ant ne dépe ndant que de X, on prend
la bo rne in fé ri e ure sur to utes les appli -
cati o ns injecti ves te lles quef, et on définit la dis10rsion de X à va le urs da ns B :
c,,( X) = in f dist (f).
J x---n
En 1986, da ns un a rticle qui fo nde la
th éo ri e no n lin éa ire des espaces de
Ba nac h , le mathé ma ti c ie n be lge Jea n
Bo urga in (né e n 1954, méda ille Fie lds
1994) mo ntre q ue, s i B es t l'es pace
L''([O; IJ) , avec 1 :Sp<+oo, il ex iste une
constante C(p) > 0 (ne dépe nd ant que de
p) te ll e que:
CL"IIOII) (X),, C(p) ln 1x1.
A utre me nt dit , il ex iste un e applicati o n
injecti ve X-+ L'' do nt la d istors io n est
a u plu s logarithmiqu e e n le no m bre de
po in ts de X .
Passons ma in te na nt à la t héor ie des
graphes: si X est un graphe fi ni, d'e n80 Tangente Hors-série n°52. Mathématiques & informatique