Abstract FR:

L'arbre sert a la fois comme support d'algorithmes (systemes de fichiers, compression d'images) mais aussi pour le calcul de fonctions (systemes d'attributs en theorie de la compilation). Ce memoire est consacre a l'etude d'une classe particuliere de fonctions sur les arbres: les fonctions inductives (ou fonction dont la valeur en un sommet de l'arbre depand de la valeur de la fonctions en ses fils). Elles sont definis sur les arbres et sur les prearbres (arbre dont on oublie l'orientation et la racine), un algorithme calculant en temps 2. A. N les fonctions inductives sur les prearbres est presente. Le test du mineur est une etape clef dans la construction d'obstruction (ensemble de graphes permettant de caracteriser une famille particuliere). Nous montrons que le test du mineur sur les arbres se resoud a l'aide d'un couple de fonctions inductives. Ce probleme etant np-complet (que ce soit dans le cas general des graphes mais aussi pour le cas plus restreint des arbres), une implementation sequentielle de l'algorithme propose montre vite ses limites (on ne peut esperer depasser la centaine de sommets pour les arbres), nous proposons une methode de parallelisation du calcul des fonctions inductives sur les arbres et prearbres. Cette methode nous permettra d'apporter une solution utilisable au probleme du mineur sur les prearbres