NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

D
É
C
O
N
N
E
C
T
É

Diviser pour régner

1 - Introduction

Le diviser pour régner est une méthode algorithmique basée sur le principe suivant :

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)
FUSIONNER : les solutions des sous-problèmes sont fusionné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.

2 - Recherche dichotomique dans un tableau trié

Principe : L'élément rechercé est présent s'il est au milieu, sinon s'il est inférieur à l'élément du milieur, on regarde à gauche du tableau sinon à droitre.

Algorithme :

Fonction  est_present
paramètres :
    x : l'élément recherché
    T : le tableau trié
    g : indice gauche du tableau
    d : indice droit du tableau
retourne :
    vrai lorsque x dans le tableau s'il est présent, sinon retourne faux
    
Début:
    si g>d
        retourne faux
    sinon
        m ← entier correspondant au milieu de g et d 
        si x = T[m]
            retourne faux
        sinon
            si x<T[m]
                si est_present(x,T,g,m-1)
                    retourne vrai
                sinon
                    retourne faux
            sinon
                retourne est_present(x,T,m+1,d)
fin

Codez cet algorithme en langage python

Simulation

est_present(x=1,T,g=0,d=8)
m=4
x<25
retourne est_present(x=1,T,g=0,d=4-1)
    m=1
    x>-3
    retourne est_present(x=1,T,g=1+1,d=3)
        m=2
        x<2
        retourne est_present(x=1,T,g=2,d=2-1)
        g>d
        faux
    faux
faux

Complexité : Proportionnel à log(n)

2 - Tri-fusion

Nous avons déjà étudié des algorithmes de tri : le tri par insertion et le tri par sélection. Nous allons maintenant étudier une nouvelle méthode de tri, le tri-fusion. Comme pour les algorithmes déjà étudiés, cet algorithme de tri fusion prend en entrée un tableau non trié et donne en sortie, le même tableau, mais trié.

Le tri fusion d'un tableau consiste à :

découper le tableau en deux moitiés (diviser),
trier récursivement les deux moitiés,
fusionner les deux moitiés triées (combiner).

Remarque :

le tri fusion est une fonction de référence.

Principe:

2.1 - Exercice 1.

Écrire une fonction decoupe qui :

prend en paramètre un tableau tab,
découpe le tableau en deux moitiés de même taille (à un élément près),
retourne 2-uplets contenant la liste des deux moitiés.

Par exemple :

>>>decoupe([2,10,0,8,7,42,5])
([2, 10, 0, 8], [7, 42, 5])
>>>decoupe([2,10])
([2], [10])

2.2 - Exercice 2.

Écrire une fonction itérative fusionne qui :

prend en paramètres deux tableaux triés tab1 et tab2 dans l'ordre croissant,
fusionne les deux tableaux en un seul, trié dans l'ordre croissant,
retourne un tableau du résultat de la fusion.

Par exemple :

>>>fusionne([0,2,8,10], [5,7,42])
[0, 2, 5, 7, 8, 10, 42]
>>>fusionne([10],[5])
[5, 10]

Attention, cette fonction ne devra pas utiliser de tri.

2.3 - Exercice 3

Recopier les deux fonctions des exercices 1 et 2

Écrire une fonction récursive tri_fusion qui :

prend en paramètre un tableau tab d'entiers non triés,
retourne ce tableau trié dans l'ordre croissant grâce au tri fusion,
le cas de base retourne le tableau tab lorsqu'il ne reste plus qu'un élément dans tab,
2-uplets tab1 et tab2 mémorisent le retour du découpage de tableau tab en 2 en appelant la fonction decoupe,
on retourne recursivement la fusion du tri_fusion de tab1 et du tri_fusion de tab2.

Vérifier que :

>>> tri_fusion([2,10,0,8,7,42,5])
[0, 2, 5, 7, 8, 10, 42]
>>> tri_fusion([10,5])
[5, 10]

3 - Autre méthode pour le tri fusion.

Coder l'algorithme du tri_fusion récursif

Fonction tri_fusion
Paramètres 
    T : tableau à trier
    g : indice gauche du tableau
    d : indice droit du tableau

début
    si g<d
        m ← entier correspondant au milieu de g et d
        tri_fusion(T,g,m)
        tri_fusion(T,m+1,d)
        fusion(T,g,m,d)
fin

Fonction fusion
Paramètres 
    T : tableau à trier
    g : indice gauche du tableau
    m : milieu du tableau
    d : indice droit du tableau
        
début
    i ← g
    j ← m+1
    aux ← []
    tant que i ≤ m et j ≤ d
        si T[i] < T[j]
            ajouter à la table aux T[i]
            incrémenter i
        sinon
            ajouter à la table aux T[j]
            incrémenter j
    tant que i ≤ m
        ajouter à la table aux T[i]
        incrémenter i
    tant que j ≤ d
        ajouter à la table aux T[j]
        incrémenter j
    k ← 0
    l ← g
    tant que l ≤ d
        T[l] ← aux[k]
        incrémenter k
        incrémenter l
fin