Inscription / Connexion Nouveau Sujet
Etude de complexité en Caml
bonjour,
je sais que c'est un forum de maths, mais je n'ai trouvé aucun forum réservé a Caml, et je sais que cet un programme très utilisé en prépa.
On définit le type: type int_arbre=Nil | Noeud of int*int_arbre*int_arbre ;;
Et j'ai la fonction:
let rec couper c=fun
Nil->(Nil,Nil)
|(Noeud(i,A,B))->let(Ga,Da)=(couper c A)
in let(Gb,Db)=(couper c B)
in if c<=1 then (Ga,(Noeud(i,Da,B)))
else ((Noeud(i,A,Gb)),Db);;
C'est un devoir maison sur les arbres bianire de recherche.
Je dois montrer que si n désigne la hauteur de l'arbre pris en argument, alors la complexité de la fonction couper est inférieure ou égale a n, en nombre d'appels récursifs.
J'avoue que je n'ai pas compris grand chose a l'etude de la complexité, donc si quelqu'un pouvait m'aider, merci beaucoup
oups désolé j'ai fait une erreur de frappe, c'est in if c<=i then (Ga,(Noeud(i,Da,B))) a la troisième ligne
J'en ai fait un peu à la fac mais on captait rien, sûrement à cause du prof parce que je vois pas pour quelle raison je ne pourrais pas comprendre un langage informatique.
Mais bon la complexité dépend de l'algorithme et non du langage non ? Alors si tu nous donnais l'algorithme "en clair" peut-être qu'on pourrait t'aider.
Ok je vais essayer d'expliquer clairement :
C'est a propos des arbres bianires de recherche(ABR).
C'est a dire qu'il y a une racine r, et deux sous arbres tel que tous les elements du sous arbres de gauche soient inférieur a la racine, et que tous les éléments du sous arbres de droite soient supérieur a la racine.
On appelle coupure d'un ABR A selon une valeur c, une partition de A en un couple de sous-arbres Ga et Da tel que:
-Ga et Ga sont des ABR
-l'ensemble des valeurs de A soit l'union des valeurs de Ga et Da
-Pour tous elements j de Ga, j<=c
-Pour tous elements j de Da, j>c
En gros l'algorithme permet de couper un arbre selon une valeur.C'est une fonction recursive.
Un arbre est noté Noeud(r,A,B) avec r la racine, A le sous arbre gauche et B le sous arbre droit.
-Si on prend l'arbre vide en argument, le programme rend deux arbres vides.
Si on prend Noeud(i,A,B) un arbre, on appelle Ga et Da les deux sous arbres de A qui proviennent de la fonction couper (qui est recursive). Pareil pour Gb et Db.
Si c (la valeur de coupure) est inférieur a i, alors on rend les deux sous arbre: Ga et Noeud(i,Da,B) (c'est a dire l'arbre de racine i, de sous arbre gauche Da, et de sous arbre droit B)
Sinon on rend les deux sous arbres Noeud(i,A,Gb) et Db.
Voilà, j'espère que j'ai été clair.
ben en gros un arbre c'est un truc du genre
Y'a pas grand chose de plus a expliquer, ici A est la racine, tout ce qui part a gauche est la sous arbre gauche, et ce qui part a droite est le sous arbre droit.
Et la hauteur, c'est le plus grand nombre de branches( représenter pas des traits) entre la racine et une feuille (c'est adire une extrmité)
Enfin bon, si tu connais pas, ca m'etonnerait que ca te suffise. Tant pis.
Merci quand meme
Oui ok mais tu compares les éléments de l'arbre à une valeur c, ça je ne suis pas sûr de comprendre.
Regarde si je ne sais pas ce que c'est un arbre : 
variables aléatoires discrètes 
Oui en effet, c'est un très joli arbre.
En fait, c'est parce que dans le lien que je t'ai donnée, ce sont des lettres, mais dans mons devoir, ce sont des chiffres.
Par exemple tu remplace:
A=13,B=11,C=15,D=8,E=12,F=14,G=16
Ok donc il y a un chiffre à chaque connection et ce que tu appelles les éléments d'un arbre ce sont les chiffres sur ses connections c'est bien ça ?
Annuler
connectez vous