Diviser pour régner.

Introduction.

Pour résoudre un problème sur un ensemble de données, le principe "diviser pour régner" consiste :

à diviser les données en deux (ou plus) parties.
résoudre le problème sur une ou plus des parties (de façon récursive).
utiliser les solutions sur les différentes parties pour trouver la (les) solution pour le problème.

Exemples

La dichotomie

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200

La méthode de la dichotomie pour trouver une valeur dans un tableau étudié en première (lien) est un exemple important d'algorithme "diviser pour régner". Voici une implémentation récursive (et fonctionnelle car les "variables" ne sont pas modifiées) :

Remarque

L'implémentation ci-dessus utilise le slicing (tranchage) (qui consiste à faire des copies d'un tableau et donc prend du temps) la version suivante n'a pas se problème mais à le désavantage de demander en paramètre les bornes de la recherche (ce qui en fait en réalité une meilleure fonction car plus polyvalente.). Si vous voulez juste donner la liste et la valeur en paramètre il faut ruser un peu (version 3).

Exercice

Faire une fonction qui va tester les fonctions de recherche dichotomique précédente.

Les fonctions de dichotomie présentées plus haut retourne dans le cas positif ( > -1) l'index d'une valeur du tableau qui marche mais pas forcément l'indexe le plus bas. Comment la modifier pour obtenir l'index le plus petit ? L'index le plus grand et enfin la plage où se trouve les valeurs.

Le tri fusion

Présentation

Le tri fusion est un autre classique de la méthode diviser pour régner, il est en O( nln(n) ) qui est la limite théorique des méthodes de tri par comparaison. Pour mémoire les tri par insertion et sélection sont en O( n² ) soit moins bien au bout d'une certaine taille.

Le tri par fusion a l'inconvénient de consommer beaucoup de mémoire (il faut doubler la liste) (mais on peut l'éviter voir l'exercice).

Algorithme

On partitionne le tableau en deux parties par son milieu.
Par récursion on ordonne les deux parties.
On fait la fusion des deux parties.

Faire la fusion des deux tableaux est rapide ( O (n) ) car les tableaux sont triés.

nombre de comparaisons = 0
nombre de copies = 0

Implémentation

Il existe de nombreuses manière d'implémenter le tri fusion, plus ou moins consommatrice en mémoire, avec plus ou moins de copies, avec ou sans récurrence. Une implémentation que je vous conseille car elle est simple (et finalement performante) du tri fusion est la suivante :

Exercice

Implémenter une fonction fusion(liste, taille1, taille2) sur une liste de taille égale à taille1 + taille2 où les taille1 premiers éléments de la liste sont rangés par ordre croissant ainsi que les éléments suivants. Il faut faire la fusion sans "doubler" la mémoire utilisée. Une méthode est celui de l'insertion on déplace d'une case après l'autre par inversion des variables.

Exemple avec la liste suivante, fusion(liste,3,2) doit donner la liste ordonnée.

Etape

Comparaison

Voci deux autres façons d'implémenter le tri_fusion, la première n'utilise pas de mémoires en plus (ou plutôt une mémoire indépendante de la taille) et la deuxième se fait en place. Les deux méthodes ne sont pas récursives mais on verra qu'elles ne sont pas forcément meilleures.

Comparer le temps des méthodes en utilisant le code suivant :

Exercice

Faire un algorithme de somme des éléments d'une liste via une stratégie diviser pour régner. Y-a-t'il une performance meilleure que la méthode classique ?
Faire un algorithme de recherche de maximum d'une liste via une stratégie diviser pour régner. Y-a-t'il une performance meilleure que la méthode classique ?
Faire un algorithme de recherche du nombre d’occurrences d'une valeur dans une liste via une stratégie diviser pour régner. Y-a-t'il une performance meilleure que la méthode classique ?
Tri paquet : On dispose un tableau tab de n doubles borné entre a et b :
1. On crée un tableau tab2 de n listes vides.
2. Pour chaque élément a de tab, il existe un k entier dans [0,n-1] tel que \( a \in \left [ a+\frac{k(b-a)}{n}, a+\frac{(k+1)(b-a)}{n} \right ] \), on le range dans tab[k] .
3. On effectue un tri dans chaque tab[i] avec i dans \(\left [ a+\frac{k(b-a)}{n}, a+\frac{(k+1)(b-a)}{n} \right ] \).
4. On reforme le tbaleau d'origine en rajoutant dans l'ordre les élèments des tab[i] succesifs.
Programmer le tri.
Pour un tableau tab on appelle inversion un couple (i,j) avec i < j tel que tab[i] > tab[j]. On veut compter le nombre d'inversions dans un tableau, par exemple [5,4,3,6] possède 3 inversions :
1. 5 et 4
2. 5 et 3
3. 4 et 3
Un tableau classé par ordre croissant n'a pas d'inversions, un classé par ordre décroissant de taille n à n(n-1)/2 inversions.
1. Construire un algorithme par force brute.
2. On considère deux tableaux tab1 et tab2 classés par ordre croissant, construire un algorithme qui permet de compter le nombre de couple (i , j) vérifiant tab1[i] > tab2[j], l’algorithme doit être O(len(tab1) + len(tab2)). Par exemple si tab1 = [1,1,3,5] et tab2 = [2,3,4,6] alors le nombre cherché est 4 ( 3 > 2, 5 > 2, 5 > 3, 5> 4).
4. On procède l'algorithme diviser pour régner suivant :
  1. On coupe tab en deux tableaux tab1 et tab2.
  2. On déterminer les nombres d'inversions n1 de tab1 et n2 de tab2.
  3. On trie par ordre croissant tab1 et tab2.
  4. On utilise l'algorithme précédent pour déterminer m.
  5. On retourne n1+n2+m
5. Programmer l’algorithme.
6. Estimer sa complexité, vérifier qu'il est meilleur que l'algorithme en force brute.
Peut être le meilleur algorithme de tri "pour une liste non particulière" est le tri-rapide. Il est récursif et basé comme pour le tri fusion sur la méthode diviser pour régner.
- On choisit un pivot, pour le besoin de l'exercice on prend le premier indice de la liste (il est conseillé de choisir le pivot de façon aléatoire pour éviter de prendre trop simplement le tri à défaut).
- On place tous les éléments de la liste plus petits que le pivot à gauche et tous les autres à droites.
- On place le pivot comme frontière des deux parties.
- Par récursion on ordonne les deux parties.
4 15 2 0 10 7 5 3 1 12 1 8 9 12 13 4

Echange : 0 Nombre de comparaisons : 0

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49
0	1	2	3	5	8	12	15	20	25	30	33	38	40	42	48	50	55	60	65	70	72	80	90	100	101	105	107	108	110	112	118	122	125	130	132	140	145	150	152	160	162	170	175	177	180	182	188	190	200