Algorithmique : recherche dichotomique, fin + debut / 2

Résolu/Fermé
Rollover Messages postés 3 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 27 novembre 2013 - Modifié par Rollover le 26/11/2013 à 16:57
Rollover Messages postés 3 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 27 novembre 2013 - 27 nov. 2013 à 10:04
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

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
Modifié par KX le 26/11/2013 à 19:31
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
Rollover Messages postés 3 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 27 novembre 2013
27 nov. 2013 à 10:04
(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 !
0
Rollover Messages postés 3 Date d'inscription mardi 26 novembre 2013 Statut Membre Dernière intervention 27 novembre 2013
26 nov. 2013 à 18:28
EDIT : A la place du " mil ? partie entière (...) ", il s'agit de " mil = partie entière (...) "
0