SYSTEMES DYNAMIQUES et ALGORITHMIQUE

Iere partie 
Syst\`emes Dynamiques et Analyse  d'Algorithmes
(Brigitte Vallee).

 Analyser un algorithme consiste \`a en d\'ecrire le comportement
``moyen". Les m\'ethodes classiques d'analyse en moyenne sont
maintenant bien \'etablies, et beaucoup reposent sur l'outil essentiel
que sont les s\'eries g\'en\'eratrices.  Pourtant, dans le cas de
certains algorithmes, ces m\'ethodes ne peuvent s'appliquer, car la
distribution des donn\'ees \'evolue de mani\`ere trop complexe au
cours de l'algorithme pour pouvoir \^etre traduite dans le formalisme
des s\'eries g\'en\'eratrices. C'est ce qui se passe pour des
algorithmes \`a m\'emoire non born\'ee, o\`u le cours de l'algorithme
d\'epend de toute l'histoire pr\'ec\'edente. C'est alors une id\'ee
tr\`es naturelle de consid\'erer un algorithme et l'ensemble de ses
donn\'ees comme un syst\`eme dynamique. Le temps (discret) se confond
alors avec le nombre d'it\'erations de l'algorithme.

 Les principaux outils classiques des syst\`emes dynamiques, tel
l'op\'erateur de transfert, permettent alors de d\'ecrire
l'\'evolution du syst\`eme au cours du temps. De plus, l'op\'erateur
de transfert prend le relais des s\'eries g\'en\'eratrices; apr\`es
une g\'en\'eralisation naturelle et ad\'equate, il peut \^etre
d'ailleurs consid\'er\'e comme un op\'erateur g\'en\'erateur,
au-dessus des s\'eries g\'en\'eratrices.

L'analyse fine de l'algorithme repose alors sur les propri\'et\'es de
cet op\'erateur. Si cet op\'erateur poss\`ede, sur un espace
fonctionnel ad\'equat, de bonnes propri\'et\'es (par exemple
quasi-compacit\'e et existence d'une unique valeur propre dominante),
alors l'analyse de l'algorithme et de ses principaux param\`etres peut
\^etre men\'ee \`a bien.

Nous donnerons quelques exemples de r\'esultats tr\`es r\'ecents qui
peuvent \^etre obtenus gr\^ace \`a ce nouveau formalisme, dans deux
domaines algorithmiques particuliers: les algorithmes arithm\'etiques
et les algorithmes du texte. En arithm\'etique, nous d\'ecrirons
l'analyse d'une classe d'algorithmes de type Euclide, qui contient le
pgcd binaire et des algorithmes qui calculent le symbole de Jacobi.
Dans le contexte de l'algorithmique du texte, nous d\'ecrirons
l'analyse de la structure de trie qui sert \`a impl\'ementer les
dictionnaires et qui est fortement utilis\'ee dans les algorithmes de
compression.


IIe partie: 
"Quelques proprietes spectrales des operateurs de transfert"
Viviane Baladi

On se limitera au cas des syst\`emes dynamiques de l'intervalle.  Nous
expliquerons d'abord pourquoi, selon les propri\'et\'es de la
partition de l'intervalle en sous-intervalles de monotonie, nous
devrons travailler dans des espaces fonctionnels de nature
diff\'erente.
  
Nous consid\'ererons d'abord le cas le plus simple o\`u la partition
est finie et markovienne: (cas C^2 par morceaux, avec une br\`eve
mention du cas le plus simple analytique par morceaux); puis le cas ou
la partition est finie mais non markovienne (nous serons alors
oblig\'ees de travailler avec des fonctions \`a variation bornee); et
enfin le cas ou la partition est infinie (qui sera subdivis\'e en deux
cas: partition markovienne ou non markovienne).

Dans chacune de ces situations, nous \'enoncerons des resultats de
type Perron-Frobenius en dimension infinie:

(I) r\'esultats de quasi-compacite  qui permettent de controler 
le rayon spectral essentiel. (Lasota-Yorke-Doeblin-Fortet)
(II)  conditions r\'ealistes pour le m\'elange
topologique et l'ap\'eriodicit\'e qui permettent
d'assurer l'existence d'une  unique valeur propre  dominante reelle
et simple. 

Nous donnerons \'egalement  une idee des preuves.