Méthode diviser pour régner
Algorithmique
Plan
Introduction
La méthode diviser pour régner divide and conquer se décompose en 3 étapes.
- Diviser: découper le problème de départ en sous problèmes
- Régner: Résoudre les sous problèmes soit directement soit récursivement si la division nous place dans le même problème de départ mais en plus petit.
- Combiner: à partir des solutions trouvées au sous problème, former la réponse finale. Si la récursivité a été employée dans la résolution, elle le sera aussi ici.
Tri fusion
Objectif, ordonner une liste de valeurs
- Diviser: on partage le tableau en deux parties de même dimension
- Régner: On trie les tableaux récursivement (on repartage donc) ou on ne fait rien si la taille est 1(puisque un seul élément est forcément ordonné)
- Combiner: on ordonne les tableaux en fusionnant les sous tableaux qui sont donc ordonnés donc plus facile à ordonner!
Il faut effectuer environ nlog(n) comparaisons/ La complexité temporelle est O(nlog(n)), la complexité spatiale est O(n).
Tri rapide
Objectif, ordonner une liste de valeurs
- Diviser: on partage le tableau en deux parties. Ce partage ce fait autour d'une valeur du tableau choisie au hasard, c'est le pivot. Du coup, le pivot est à sa place! Il ne reste plus qu'à placer les autres!
- On trie les tableaux récursivement (on repartage donc) ou on ne fait rien si la taille est 1(puisque un seul élément est forcément ordonné)
- Combiner: rien à faire
Dans la pratique, pour aller plus vite, on décide de placer le pivot à la fin de la liste en échangeant avec le dernier élément. On place au début du tableau tous ceux qui lui sont inférieurs et on remet le pivot après ceux déplacés.
La complexité moyenne est en O(nlogn) mais O(n²) dans le pire des cas.
Plus proches voisins
Sur un ensemble de n points, on cherche les deux points les plus proches. La méthode qui consiste à tester toutes les possibilités a une complexité en temps de O(n²). En effet, on prend chaque point et pour chaque point on va chercher la distance avec ses n-1 voisins. Au total cela fait n(n-1)/2 comparaisons si l'on exclu de la comparaison les points utilisés comme départ.
Voici les étapes:
- Préparation: créer deux tableaux Tx et Ty qui contienent chacun les points triés en ordre croissant en fonction de x et de y. Cette étape réalisée en tri fusion aura une complexité en O(nlogn).
- Diviser: Si n>3, trouver une droite VERTICALE qui sépare les points de telle sorte qu'il y en ait la moitié (ou un de moins) à gauche et les autres à droite (donc la moitié ou la moitié+1). Si n=2, ou 3 on fait une recherche en testant toutes les possibilités.
- Régner: résoudre récursivement les deux sous problèmes obtenus (donc en redivisant...) et récupérer le minimum min des deux solutions.
- combiner: comparer le minimum obtenu par les sous problèmes et le minimum pour des paires dont chaque extrémité est issue d'un sous problème disitinct. (source wikipedia https://fr.wikipedia.org/wiki/Recherche_des_deux_points_les_plus_rapproch%C3%A9s ) Créer un tableau T'y ne contenant que les points de Ty compris dans la bande considérée triés selon les ordonnées croissantes. Pour chaque point P de la bande, calculer la distance qui sépare P aux 7 points qui le suivent dans le tableau T'y et noter le minimum δ′ de toutes les distances obtenues. Si δ′ < δ renvoyer δ′ sinon renvoyer δ. "a finir"
Rotation d'une image
Objectif, faire tourner une image de 90°
- Diviser: on considère que le bord du carré qui forme l'image
- Régner: si la taille du carré est supérieure à 1, on fait tourner ce bord puis on fait tourner le carré intérieur par récursivité en rappliquant Diviser
- Combiner: rien à faire
Cette méthode permet de faire la rotation sans occuper de place supplémentaire, la rotation des bords pouvant se faire, par 3 permutations. On a donc une compléxité spatiale en O(1).
Voici un autre algorithme, esthétiquement intéressant pour une image carrée.
- Diviser: Chaque image est compée en 4 (horizontalement et veritcalement en son milieu)
- Régner: recopier la rotation (récursivité !) de chaque sous image dans son nouvel emplacement
- Combiner: se fait au fur et à mesure de Régner.
La complexité de cet algorithme dépend de la complexité pour recopier un rectangle. Si l'on arrive à copier un carré de taille n en O(n²) alors la complexité est O(n²logn). Si la complexité de copie est de O(n) on a alors une complexité de O(nlogn), mais il faudrait alors une image 'simple' avec des répétitions pour atteindre ce O(n).
Un algorithme rapide en temps et simple est celui qui permute simplement les pixels un par un. On peut aussi considérer l'image comme une matrice. La rotation revient à transposer la matrice puis inverser les éléments des colonnes.
Exercices
- Fibonacci
- blabla
