Abstract FR:

Cette these est consacree a trois problemes concernant ou mettant en uvre des structures arborescentes. 1) la generation aleatoire d'arbres: nous proposons des algorithmes lineaires pour generer les forets d'arbres decoupees en motifs et les arbres colores, deux pseudo-algorithmes pour construire des arbres unaire-binaires avec une complexite moyenne lineaire, deux algorithmes pour generer des arbres binaires de hauteur donnee qui ont complexite presque lineaire. Nous analysons et ameliorons l'algorithme de wilf de generation des arborescences. Nous etudions egalement comment construire sur une machine multiprocesseurs des mots (mots de dyck, mots de motzkine,. . . ) qui sont en bijection avec des structures arborescentes. 2) le probleme de l'inclusion: etant donne deux arbres s et t est-il possible d'obtenir l'arbre s en enlevant des nuds de t? recemment, p. Kilpelainen et h. Mannila ont fourni un algorithme qui resout ce probleme avec une complexite de o(|s|. |t|) (dans le pire cas et en moyenne) et un espace utilise du meme ordre. Nous proposons ici un nouvel algorithme qui ameliore cette complexite moyenne. 3) l'etude de relations de recurrence maximin multidimensionnelles: nous donnons des bornes superieures et inferieures pour les solutions de l'equation m(n)=max (m(a#i)+min(f(a#1),. . . ,f(a#p))), a#1+. . . +a#p=n, p2 i=1 lorsque la fonction f est croissante ou decroissante. Des bornes similaires sont obtenues lorsque nous remplacons la fonction min par la somme des k plus petits termes ou la somme de tous les termes sauf le maximum