recherche de l'algorithme et l'organigramme de la methode de dichotomie

[fati21]

bonjour,
le prof nous a demander de resoudre un exo qui sera noté par la suite sur la methode de dichotomie.
en effet, il nous a demander de rediger l'algorithme et faire l'organigramme de la methode de dichotomie ; pour cela je demande de l'aide y a t 'il quelqu'un qui maitrise cette methode et qui pourra m'aider ou m'orienter vers des sites important.
je vous remercie d'avance

[Pacorabanix]

le problème c'est qu'il y a plusieurs "dichotomie".

Il y a la "recherche par dichotomie", faisable sur des listes *triées* au départ.

En fait tu connais la taille du tableau, donc tu peux regarder au milieu.

Si ce que tu vois au milieu du tableau est ce que tu cherches, alors c'est bon.

Si ce que tu vois est plus grand que ce que tu cherches, alors il fallait aller avant -> tu iras à la moitié de la partie précédente (c'est à dire au quart du tableau...).

Si ce que tu vois est plus petit que ce que tu cherches, il fallait aller après -> tu iras à la moitié de la partie suivante (donc aux 3/4 du tableau)

Un bon exemple avec un annuaire -> Tu l'ouvres au milieu pour chercher le nom d'un ami. Tu as séparé l'annuaire en 2 -> la première moitié et la deuxième moitié. Si ton ami s'appelle "M. Fred" et que tu es arrivé dans les M, tu iras maintenant faire ta recherche (prendre le milieu) sur la première moitié. Si ton ami dont tu cherches le numéro s'appelle M. X, tu iras sur la deuxième moitié



Sinon il y a aussi la méthode de dichotomie pour trouver les racines d'une fonction mathématique continue. Il y a aussi ce principe de "couper en 2" a chaque fois la zone de recherche.

sur un intervale [a;b] où f(a) et f(b) n'ont pas le même signe, et où f est continue , on sait qu'il existe une valeur entre a et b qui passe par "0" (c-à-d un certain nombre c où f(c)=0 ).

On la cherche "au bol" en prenant au milieu de a et b : m=(a+b)/2


Ensuite on continue la recherche sur un interval deux-fois plus petit : [a; m] ou [m;b], selon le signe de f(m) (c-à-d si on constate que la racine de la fonction est entre a et m ou entre b et m).

On continue ainsi en boucle, en vérifiant que m n'est pas deja la bonne solution bien sur .

Par contre on ne peut pas etre sur de tomber ainsi sur la vraie solution, car elle peut etre irrationelle. Il faut donc se fixer une "marge d'erreur" e telle que si |f(m)| < e alors on considère qu'on a trouvé la bonne solution.

[ToTo13]

Bonjour,

Envoyé par fati21

le prof nous a demander de resoudre un exo qui sera noté par la suite sur la methode de dichotomie.
en effet, il nous a demander de rediger l'algorithme et faire l'organigramme de la methode de dichotomie ; pour cela je demande de l'aide y a t 'il quelqu'un qui maitrise cette methode et qui pourra m'aider ou m'orienter vers des sites important.
je vous remercie d'avance

Cet algorothme est extrêmement connu et le web regorge de renseignements la concernant => Fais une recherche sur avant de poser la question.
Dis nous alors si tu ne comprends pas quelques chose et nous t'orienterons.

[fati21]

merci paco d'avoir repondu à mon message, en fait je cherche a faire un algorithme et un organigramme de la methode de dichotomie pour chercher un maximum, vous savez j'ai pas pas fait d'algorithme auparavant et la meilleur c'est que notre prof nous a encore demander de faire un programme en fortran , je suis vraiment perdue.

[nabil]

Une recherche sur google te donnera plein de chose

Mais bon regarde ce lien:

http://fr.wikipedia.org/wiki/Dichotomie

De plus le fichier joint

[fati21]

salut nabil
Tout d'abord je vous remercie pour votre réponse mais sincèrement ce n'est pas ce que je cherche
Vous savez j'ai cherché sur internet et je n'ai pas trouvé ; en fait je cherche a faire un algorithme et un organigramme avec la méthode de dichotomie mais en cherchant l'optimum c'est à dire optimisation (chercher le Xmax).
Voici les étapes données par le prof

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
On effectue par itération 2 expériences x1 et x2 tel que::
a≤ x1≤x2≤b
ε: L'intervalle minimum de séparation entre x1 et x2 pour pouvoir détecter une différence significative entre f(x1) et f(x2))
on situe x1 et x2 à une distance ε/2 du centre de [a ,b] 
x1= (a+b)/2 – ε/2
x2= (a+b)/2 – ε/2
si f(x2)< f(x1) le max se trouve dans le nouveau intervalle est [a=x1,b]
si f(x1)> f(x2) le max se trouve dans [a ,b=x2]
i= 1,....n
1ere iteration: delta x= (b-a)/2 + ε 
.
.
.
.
.
.Jusqu'a delta x = (bi-ai)/2ⁿ + 2ε (1-1/2ⁿ)
On trouve f(x)max
Arrivant à une précision ∆ de 0.1%

Aider moi je suis perdue

[pseudocode]

Moi je dirais plutot:

Code :

1
2
3
4
5
6
7
8
9
10
11
        x1     x2
----|----+--|--+----|---->
    a       m       b

m = (a+b)/2
x1 = m – ε/2
x2 = m + ε/2

si f(x1) < f(x2) le max se trouve dans l'intervalle [m,b]
si f(x1) > f(x2) le max se trouve dans l'intervalle [a,m]

[nabil]

je pense que ton algorithme sera comme suit :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ai=a
bi=b

// j'ai oublié comment convertir do whlile en algorithmique c'est faire tantque ??//

do  
m=(ai+bi)/2
x1=m-(e/2)
x2=m+(e/2)

si f(x1)<f(x2) alors ai=m
si f(x1)>f(x2) alrs bi=m

x= (bi-ai)/2 + e 
while x>0.1

max=f(x)

[fati21]

je te remercie nabil pour ta reponse