Algorithmique : recherche dichotomique, fin + debut / 2 [Résolu/Fermé]

Signaler
Messages postés
3
Date d'inscription
mardi 26 novembre 2013
Statut
Membre
Dernière intervention
27 novembre 2013
-
Messages postés
3
Date d'inscription
mardi 26 novembre 2013
Statut
Membre
Dernière intervention
27 novembre 2013
-
Hello tout le monde,

J'aurais besoin de précision au sujet de la recherche dichotomique, et plus exactement dans la logique utilisé pour concevoir son algorithme.

Le principe de dichotomie comprit, j'ai fais un exercice et vu sa résolution dans mon support de cours ; un passage m'interpelle :

Variables
...

Initialisation
...

Traitement
Tantque
mil ? partie entière( (début + fin) / 2)
...
FTantque

Sortie
...



On est d'accord que l'instruction
mil ? partie entière( (début + fin) / 2)
a pour but d'obtenir le MILIEU d'une échelle allant de DEBUT à FIN.

Cependant, à ce titre, ce qui me vient plus logiquement (selon moi uniquement peut-être), c'est
mil ? partie entière( (fin - début) / 2 + debut)
Je procède de manière à obtenir le milieu de la "taille" de la partie à analyser (fin - debut/2) puis j'y ajouter le début de l'échelle qu'on a auparavant déterminé(+ début) de manière à " positionner " le curseur au bon endroit.

Le résultat escompté est le même - mais la solution proposé par mon support de cours est plus courte, donc avec une meilleur scalabilité, et est donc à privilégié..

Y'a t'il donc une notion de mathématique qui m'échappe et qui m'empêche de parvenir à cette optimisation ? (Une sorte de vérité général tel que (A+B)/2 = (B-A)/2+A qui m'aurait complètement échappé). Si oui, comment pourrais-je acquérir ces notions sensées optimiser mes algorithmes ?
Vous comprendrez que c'est davantage un problème de conception à long terme qu'un souci de compréhension de cet algorithme en particulier. En conditions réelles je sais que ça peut ralentir l'expérience utilisateur, surcharger des serveurs, ralentir le développement en équipe (" pourquoi il a fait ça ? ") etc.

Bref, si quelqu'un pouvait m'aider je lui en serai reconnaissant :)

Bonne navigation !

Pour vous renseigner sur mon niveau, dans l'optique de me construire de solides connaissant en algorithmique (mon parcours a débuté par l'intégration web) j'aborde en ce moment les bases : qu'est-ce que les mathématique sont, comment les logiciens forment une branche des mathématique, qu'est-ce qu'un algorithme et enfin les principaux algorithmes (dont la dichotomie).

2 réponses

Messages postés
16142
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
8 avril 2020
2 571
mil ← partie entière( (début + fin) / 2)
Ici c'est la moyenne de début et fin qui est utilisé, donc ça donne bien le milieu.

mil ← partie entière( (fin - début) / 2 + debut)
Là tu réfléchis un peu différemment (et tu n'es pas le seul), mais c'est aussi le milieu.

À la partie entière près, les deux calculs sont mathématiquement équivalents.
(x+y)/2 = x/2 + y/2 = (x - x/2) + y/2 = x + y/2 - x/2 = x + (y-x)/2
En terme d'optimisation,
(début+fin)/2
fait deux opérations (une addition, une division), alors que
(fin-début)/2+début
en fait trois (une soustraction, une division, une addition), donc le premier calcul est moins lourd.

Attention :
(début+fin)
étant plus grand que début et fin, il peut y avoir un dépassement numérique (c'est à dire qu'on peut obtenir un nombre qui est trop grand pour être représenté dans le type de donnée qu'on a attribué à début et fin), du coup le résultat peut devenir faux.
En faisant
(fin-début)/2+debut
on est sûr de rester dans l'intervalle de valeurs debut → fin, et donc d'avoir des résultats numériques corrects. Mais c'est un cas assez particulier vu que ce problème ne peux se poser que pour des données extrêmes et uniquement à la première itération de ton algorithme de dichotomie.La confiance n'exclut pas le contrôle
2
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 81396 internautes nous ont dit merci ce mois-ci

Messages postés
3
Date d'inscription
mardi 26 novembre 2013
Statut
Membre
Dernière intervention
27 novembre 2013

(x+y)/2 = x/2 + y/2 = (x - x/2) + y/2 = x + y/2 - x/2 = x + (y-x)/2
Après décortication, ça parait en effet évident.

Je ferais plus attention à ce type de structure dorénavant.

Je te remercie de ton aide KX.
Concernant un moyen de m'améliorer, j'imagine que me remettre à niveau en mathématique m'aiderait pas mal à trouver des optimisations naturellement (en retrouvant des schéma de bases) et puis qu'avec l'expérience...

Bonne continuation !
Messages postés
3
Date d'inscription
mardi 26 novembre 2013
Statut
Membre
Dernière intervention
27 novembre 2013

EDIT : A la place du " mil ? partie entière (...) ", il s'agit de " mil = partie entière (...) "