1. #1
    Invité de passage
    Inscrit en
    janvier 2008
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : janvier 2008
    Messages : 5
    Points : 0
    Points
    0

    Par défaut recherche de l'algorithme et l'organigramme de la methode de dichotomie

    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

  2. #2
    Membre confirmé
    Profil pro
    Inscrit en
    décembre 2007
    Messages
    191
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : décembre 2007
    Messages : 191
    Points : 207
    Points
    207

    Par défaut

    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.

  3. #3
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    janvier 2006
    Messages
    5 449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Santé

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 449
    Points : 9 262
    Points
    9 262

    Par défaut

    Bonjour,

    Citation Envoyé par fati21 Voir le message
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  4. #4
    Invité de passage
    Inscrit en
    janvier 2008
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : janvier 2008
    Messages : 5
    Points : 0
    Points
    0

    Par défaut algorithme de dichotomie

    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.

  5. #5
    Membre habitué
    Avatar de nabil
    Inscrit en
    avril 2002
    Messages
    219
    Détails du profil
    Informations forums :
    Inscription : avril 2002
    Messages : 219
    Points : 138
    Points
    138

    Par défaut

    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
    Images attachées Images attachées
    Il ne faut jamais désesperer, il y a toujours une solution.

  6. #6
    Invité de passage
    Inscrit en
    janvier 2008
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : janvier 2008
    Messages : 5
    Points : 0
    Points
    0

    Par défaut salut

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  7. #7
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 959
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 959
    Points : 15 767
    Points
    15 767

    Par défaut

    Moi je dirais plutot:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Membre habitué
    Avatar de nabil
    Inscrit en
    avril 2002
    Messages
    219
    Détails du profil
    Informations forums :
    Inscription : avril 2002
    Messages : 219
    Points : 138
    Points
    138

    Par défaut

    je pense que ton algorithme sera comme suit :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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)
    Il ne faut jamais désesperer, il y a toujours une solution.

  9. #9
    Invité de passage
    Inscrit en
    janvier 2008
    Messages
    5
    Détails du profil
    Informations forums :
    Inscription : janvier 2008
    Messages : 5
    Points : 0
    Points
    0

    Par défaut merci

    je te remercie nabil pour ta reponse

Discussions similaires

  1. Réponses: 6
    Dernier message: 05/11/2009, 20h28
  2. Recherche d'un algorithme de Stemming(Racinisation)
    Par samorra dans le forum Mathématiques
    Réponses: 0
    Dernier message: 08/10/2009, 18h20
  3. Recherche d'un algorithme
    Par shaenoide dans le forum Mathématiques
    Réponses: 12
    Dernier message: 07/10/2009, 10h24
  4. Recherche de deux algorithmes "conv2" et "filter2"
    Par The-msx dans le forum Traitement d'images
    Réponses: 10
    Dernier message: 21/07/2008, 13h46
  5. Recherche d'un algorithme pour calculer un Checksum
    Par noune40 dans le forum VB 6 et antérieur
    Réponses: 2
    Dernier message: 23/11/2006, 10h46

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo