Objectifs
- Comprendre la méthode algorithmique diviser pour régner
-
Implémenter en Python des algorithmes utilisant cette méthode :
- Recherche dichotomique
- Tri-fusion
Consignes
- Vous devez répondre aux questions indiquées en couleur bleue.
-
Vous devez m'envoyer (en dépôt sur le cahier de texte d'Ecole Directe ou si ce n'est pas possible par mail à thalesm@free.fr) un fichier nommé NOM1_NOM2_TP_diviser_pour_regner.zip avec NOM1,NOM2 les noms des élèves du groupe qui un document texte avec les réponses aux questions numérotées de Q1 à Q12 et les sources de toutes les fonctions Python demandées.
Chaque fonction doit être documentée en utilisant les
docstringet incluant plusieurs jeux de tests utilisant la bibliothèquedoctest.
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.
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.
Implémentation en python
On dispose d'une liste de nombres triés par ordre croissant.
Ecrire le corps des fonctions Python suivantes :
-
dichotomie(liste,x)Fonction (non récursive) qui détermine en utilisant une recherche dichotomique si le nombre
xpassé en paramètre est présent ou non dans la listelistetriée par ordre croissant passée en paramètre.La fonction renvoie :
-
False,nb_etapessi le nombre x n'est pas présent dans la listeliste,nb_etapesétant le nombre d'étapes effectuées.
True,nb_etapessi le nombre x est présent dans la listeliste,nb_etapesétant le nombre d'étapes effectuées pour identifier le nombre cherché; -
dichotomie_recursif(liste,x,g=0,d=-1)Fonction récursive qui détermine en utilisant une recherche dichotomique si le nombre
xpassé en paramètre est présent ou non dans la listelistetriée par ordre croissant passée en paramètre.Les paramètres
getdreprésentent les indices courants respectivement gauche et droite dans la liste étudiée lors des appels récursifs successifs.La fonction renvoie :
-
False,nb_etapessi le nombre x n'est pas présent dans la listeliste,nb_etapesétant le nombre d'étapes effectuées.
True,nb_etapessi le nombre x est présent dans la listeliste,nb_etapesétant le nombre d'étapes effectuées pour identifier le nombre cherché;
Représentation sous la forme d'un arbre binaire de recherche
On peut représenter une recherche dichotomique dans une liste triée à l'aide d'un arbre binaire de recherche.
Proposez l'arbre binaire de recherche pour une recherche dichotomique correspondant à la liste suivante :
L = (1,10,12,25,30,45,60)
Pour cette liste, combien d'étapes au maximum sont nécessaires pour retrouver un nombre ?
Complexité algorithmique d'un algorithme de recherche dichotomique
La taille de la liste triée étant n donnez le nombre d'étapes à effectuer dans le pire des cas pour trouver (ou pas) un nombre en fonction de n en utilisant une recherche dichotomique.
Algorithme de tri-fusion
Nous avons étudiez l'an dernier, plusieurs algorithmes de tri en place.
Citez plusieurs de ces algorithmes étudiés avec leur complexité algorithmique en fonction de la taille n des données à trier.
Un algorithme "efficace" basé sur le principe diviser pour régner est le Tri-fusion.
Principe de l'algorithme de tri-fusion
Activité débranchée de découverte
Vous disposez d'un jeu de cartes numérotées de 1 à 100 et mélangées.
Votre mission : trier ce jeu de cartes le plus rapidement possible (et surtout plus vite que les autres groupes ;))
Explications sur la méthode du tri-fusion
Si vous êtes seul(e), vous faites comment ? : vous pouvez faire comment vous le sentez ou bien vous pouvez utiliser un des algorithmes vus précédemment (par insertion sélection, à bulles)
Dans le pire des cas s'il vous faut 0,1 secondes pour placer une carte, il vous faudra 100x100x 0,1 = 1 000 sec = 17 minutes (environ)
Maintenant, si vous demandez à un camarade de vous aider, comment optimiser le tri ?
Une bonne solution, est de diviser le paquets en 2 paquets de 50 cartes, et demandez à chaque camarade de trier son paquet avec la méthode de son choix
Ensuite il suffit de rassembler ces deux paquets déjà triés, et là c'est déjà plus simple car il suffit de n'étudier que les fiches du haut de chaque paquet pour les fusionner.
Vous verrez qu'avec 2 élèves, vous mettez beaucoup moins de temps !
On peut utiliser plus d'élèves, en divisant le paquet initial en 4 ou bien plus encore.
Chaque élève mettra peu de temps à trier son paquet (puisque son nombre de cartes est faible)
Et la partie fusion des différents paquets triés sera aussi assez rapide de proche en proche.
Imaginons maintenant que vous disposez d'une liste de nombres à trier et un ordinateur.
En exploitant au maximum, ce double mécanisme de décomposition puis ensuite de fusion, on optimise ainsi notre procédure de tri.
Ce type d'algorithme est classé dans une catégorie nommée diviser pour mieux régner.
Voici une animation graphique illustrant les 2 opérations essentielles du Tri-Fusion : la décomposition et la fusion :
Une implémentation en Python de l'algorithme de Tri-fusion
L'algorithme de Tri-fusion est souvent implémenté de manière récursive aussi bien pour la partie décomposition que pour la partie fusion
Voici la fonction principale de l'algorithme de tri-fusion nommée triFusion(L).
Vous devez compléter les paramètres de la ligne du double appel récursif à la fonction triFusion().
Analyse de la partie fusion de l'algorithme
Une implémentation de la partie fusion de l'algorithme de tri fusion est donnée par la fonction fusion().
Est-ce une version récursive ou bien itérative ?
Codez une version différente de celle proposée (itérative ou récursive) de cette fonction de fusion nommée fusion_V2().
Complexité de l'algorithme de Tri-fusion
Recherchez sur Internet la complexité de l'algorithme de Tri-Fusion en fonction de la taille n des données à trier.
A l'aide d'un traceur de courbes (GeoGebra ou un tableur), tracez les courbes des complexités algorithmiques des deux catégories d'algorithmes de tri en fonction de la taille n des données à trier pour des valeurs de n comprises entre 10 et 500.
Quel est l'algorithme le plus efficace ?
Autres algorithmes basés sur la méthode diviser pour régner
Citez d'autres algorithmes connus utilisant la méthode diviser pour régner et détaillez un de ces algorithmes.
Auteur : Hugues Malherbe