Algorithme et Dichotomie

Je ne comprends pas comment traduire cet exercice à laide de caml light...pouvez vous maider a "éclairer ma lanterne" svp??
merci davance

Ecrire une fonction:
dichtomie : (float->float)->float*float->float->float

telle que

dichtomie f (borne_inf, borne_sup) precision retourne la valeur approchée a dun reel r de lintervalle (borne_inf,borne_sup) tq f(r)=0 à la precision, c-a-d que la distance entre a et r ne doit pas depasser cette précision. On supposera que la fonction f est usuelle.
On rappelle que l'existence d'un tel r nest gearantie que si la fonction change de signe pr son eval aux bornes de l'intervalle. r est au moins dans un des demi intervalles dt une borne est le milieu et que le changement de signe se réalise à coup pour un des deux.

Bonjour et bienvenue sur le forum de developpez.com

Nous ne sommes pas ici pour te faire tes exercices, où se situent ton problème ? Au niveau de l'implémentation ou au niveau de l'algorithmique. D'après tes dire, c'est au niveau de la programmation en camL. Qu'as tu donc fait pour le moment ?

En calcul numérique, il y a plus d'une méthode de résolution d'une équation de la forme f(x) = 0. La méthode par dichotomie en est une. Elle est basée sur le théorème suivant:

Soit f une fonction numérique d'une variable réelle, continue et monotone sur un intervalle ]a, b[. Si f(a).f(b) < 0, alors il existe un et un seul réel c appartenant à ]a, b[ tel que f(c) = 0. (Cauchy)

L'algorithme:
On prend le milieu de ]a, b[ : m.
Si f(m) = 0, c = m :D .
Si f(a).f(m) < 0 alors c est compris entre a et m.
Sinon c est compris entre m et b.
On prend alors comme nouvel intervalle ]a, m[ (respectivement ]m, b[) dans le premier cas (respectivement dans le deuxième cas). Et ainsi de suite jusqu'à ce qu'on ait un intervalle assez petit pour permettre de connaître c avec une précision acceptable.

La méthode mathématique est là, juste quelques précisions d'ordre pratiques :

Citation:

---

Si f(m) = 0, c = m

---

Il faudra faire attention à ce niveau, et ne pas oublier que l'on ne peut pas (sauf cas très rares) tester l'égalité de deux réels. Il faudra alors le faire à un epsilon près. Cet epsilon pourra aussi servir de précision pour la valeur approchée du zéro de la fonction.

Citation:

---

Si f(a).f(m) < 0 alors c est compris entre a et m.
Sinon c est compris entre m et b.

---

Dans la pratique du fait des imprécisions et de la lenteur de certaines opérations on préfère souvent évaluer f(c) et la comparer avec 0 (en tenant compte de ma remarque précédente).

Citation:

---

Je ne comprends pas comment traduire cet exercice à laide de caml light...

---

Je pense que Melem à présenté l'algorithme de façon plutôt claire. Mais si ton problème se situe au niveau de l'implémentation c'est un autre problème. Quoique comme tu l'auras compris le procédé est hautement récursif ce qui correspond plutôt bien à la philosophie et aux pratiques de CAML. Dis-nous là où tu sèches et nous pourrons peut-être t'aider.

voila ce que jai essaye detablir:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

let rec dichotomie f(borne_inf,borne_sup)precision let f(borne_inf)=f(borne_inf) && f(borne_sup)=f(borne_sup)   if f(borne_inf)*f(borne_sup)>0 then "impossible" else borne_inf=mini && borne_sup=maxi in let milieu=(mini+maxi)/2 in if f(mini)*f(milieu)>0 then dichotomie (mini;milieu) else dichotomie (milieu;maxi)

---

je pense avoir un pb au niveau du typage et aussi au niveau de la redac' mais je ne coprends pas lesquels...si vous pouviez mexpliquer mes erreurs!
merci davance!

Je ne connais pas caml light mais j'image que la syntaxe ressemble à OCaml.

Code:

---

let f(borne_inf)=f(borne_inf) && f(borne_sup)=f(borne_sup)

---

Ceci j'a aucun sens, c'est comme si tu écraivais 1=1 ... Il faut stocker dans deux variables tes résultats :

Code:

---

let f_inf=f(borne_inf) && f_sup=f(borne_sup)

---

Ensuite, tu peux travailler sur les valeurs f_inf et f_sup.

Code:

---

1 2 3

if f(borne_inf)*f(borne_sup)>0 then "impossible" else borne_inf=mini && borne_sup=maxi

---

Ici tu as un problème de type, dans un cas, tu as un type vide (moi j'appèle ça unit dans un cas et de l'autre tu as une chaîne de caractère. Le mieux ici pour éviter ça, c'est de lancer une exception. (en OCaml c'est failwith, tu saura l'adapter je pense)

Code:

---

1 2 3 4

if f_min*f_max>0 failwith("impossible") else ...

---

Après ton else, tu effectues ton let milieu=...

Tu as également fait une erreur au niveau des paramètres de la fonction.

Il te faut également penser à utiliser la valeur de precision pour le cas d'arrêt, sinon tu peux te retrouver à avoir une récursion infinie.

Notament en ajoutant une condition du type :

Code:

---

1 2 3 4

if abs_float (borne_sup -. borne_inf) < precision then borne_inf (*ou borne_sup*) else ...

---