Objectifs

Consignes

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 :

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 :

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