Diviser pour regner
Visionner la capsule vidéo proposée ci dessous et tirée du site lumni.f pour vous faire une idée de ces méthodes
1) Principe de la méthode algorithmique "Diviser pour régner"
On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes, l'idée étant que les "petits problèmes" seront plus simples à résoudre que le problème original. Une fois les petits problèmes résolus, on recombine les "petits problèmes résolus" afin d'obtenir la solution du problème de départ.
Le paradigme "diviser pour régner" repose donc sur 3 étapes :
- DIVISER : le problème d'origine est divisé en un certain nombre de sous-problèmes
- RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d'origine)
- COMBINER : les solutions des sous-problèmes sont combinées afin d'obtenir la solution du problème d'origine.
Les algorithmes basés sur le paradigme "diviser pour régner" sont très souvent des algorithmes récursifs. Faire le pdf juste à droite de la capsule vidéo et qui parle de cette méthode "diviser pour regner".
2) Algorithme de recherche par dichotomie
Principe de la méthode
La recherche dichotomique, ou recherche par dichotomie (en anglais : binary search), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Faire le pdf du milieu qui parle de " la dichotomie".
3) Algorithme de tri fusion
Principe de ce tri
Le tri fusion, est construit suivant la stratégie "diviser pour régner", en anglais "divide and conquer". La méthode "diviser pour régner" est tout à fait applicable au problème de tri : plutôt que de trier le tableau complet, il est préférable de trier deux sous tableaux de taille égale, puis de fusionner les résultats. L’algorithme proposé ici est récursif. En effet, les deux sous tableaux seront eux même triés à l’aide de l’algorithme de tri fusion. Un tableau ne comportant qu’un seul élément sera considéré comme trié : c’est la condition sine qua non sans laquelle l’algorithme n’aurais pas de conditions d’arrêt. Etapes de l’algorithme :
- DIVISION de l’ensemble de valeurs en deux parties
- TRI de chacun des deux ensembles
- FUSION des deux ensembles Faire le pdf de droite qui parle des " méthodes de tri".
