Diviser/régner

Diviser pour régner

I. Présentation⚓︎

Vidéo Lumni

Diviser

👉 Découper un problème initial en sous problèmes.

Régner

👉 Résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits)

Combiner

👉 Trouver une solution au problème initial à partir des solutions des sous-problèmes.

II. Premiers exemples :⚓︎

Quelques exemples d'utilisation de "diviser pour régner" :

La correction est arrivée 😊

III. Une approche de la complexité⚓︎

Vidéo de Cédric Gerland

https://youtube.com/watch?v=UcT_4cWfnAs&si=EnSIkaIECMiOmarE

IV. Le tri fusion⚓︎

🤔 Comment fusionner deux listes triées pour obtenir une liste triée ?⚓︎

Nous donnons l1 = [2, 3, 5, 8] et l2 = [1, 4]

✏️ A vos crayons 1 :⚓︎

Voici un script Python :

🐍 Script Python

def mystere(l1, l2):
    n1 = len(l1)
    n2 = len(l2)
    lst = [] # initialisation de la fusion de l1 et l2 
    i1 = 0 # indice qui sert à parcourir l1
    i2 = 0 # indice qui sert à parcourir l2
    while i1 < n1 and i2 < n2 :
        if l1[i1] < l2[i2]:
            lst.append(l1[i1])
            i1 = i1 + 1
        else :
            lst.append(l2[i2])
            i2 = i2 + 1
    return lst

mystere([2, 3, 5, 8], [1, 4])

Recopier sur votre cahier le tableau suivant qui décrit le déroulement de l'exécution de :
mystere([2, 3, 5, 8],[1, 4]) et le compléter.

Il y a une ligne par tour de boucle.
Pour vous aider, nous avons rajouté une colonne pour l1 et une pour l2. Vous pourrez entourer à chaque étape, dans une de ces colonnes, l'élément qui sera ajouté à lst (en gras ici)

`i1`	`i2`	`l1`	`l2`	`lst`
0	0	[2, 3, 5, 8]	[1, 4]	[1]
0	1	[2, 3, 5, 8]	[1, 4]	[1, 2]
...	...	...	...	...
...

Solution

`i1`	`i2`	`l1`	`l2`	`lst`
0	0	[2, 3, 5, 8]	[1, 4]	[1]
0	1	[2, 3, 5, 8]	[1, 4]	[1, 2]
1	1	[2, 3, 5, 8]	[1, 4]	[1, 2, 3]
2	1	[2, 3, 5, 8]	[1, 4]	[1, 2, 3, 4]
2	2

😥 Nous observons que les deux listes n'ont pas été complètement fusionnées, car nous avons "épuisé" tous les éléments de l2.
👉 Par contre, il est certain que les éléments restants de l1 qui n'ont pas été fusionnés, sont triés, et plus grands que tous les éléments déjà présents dans lst.
🤗 Pour obtenir la liste complètement fusionnée, il suffit donc d'exécuter :
lst + [5, 8] c'est à dire lst + l1[i1:]

💻 A vous de jouer 1

Compléter le script suivant :

###

# Testsbksl-nlassert fusion([2, 3, 5, 8], [1, 4]) == [1, 2, 3, 4, 5, 8]bksl-nlassert fusion([2, 3, 5, 8], [1, 2, 9, 10, 11]) == [1, 2, 2, 3, 5, 8, 9, 10, 11]bksl-nlbksl-nl# Autres testsbksl-nlassert fusion([2, 3, 5, 8], []) == [2, 3, 5, 8]bksl-nlassert fusion([], [2, 3, 5, 8]) == [2, 3, 5, 8]bksl-nlassert fusion([5, 8, 10, 12], [1, 2, 3, 13, 14, 15]) == [1, 2, 3, 5, 8, 10, 12, 13, 14, 15]bksl-nlassert fusion([5, 8, 10, 12], [3, 4, 5, 10, 11, 13]) == [3, 4, 5, 5, 8, 10, 10, 11, 12, 13]bksl-nlbksl-nl 5/5

def fusion(l1, l2):bksl-nl """bksl-nl Précondition : l1 et l2 sont deux listes triéesbksl-nl Postcondition : la fonction renvoie une liste triée constituée de la fusion bksl-nl de l1 et l2bksl-nl Exemple :bksl-nl fusion([2, 3, 5, 8], [1, 4]) renvoie [1, 2, 3, 4, 5, 8]bksl-nl """bksl-nl n1 = len(l1)bksl-nl n2 = len(l2)bksl-nl lst = [] # initialisation de la fusion de l1 et l2 bksl-nl i1 = 0 # indice qui sert à parcourir l1bksl-nl i2 = 0 # indice qui sert à parcourir l2bksl-nl while i1 < n1 and i2 < n2 :bksl-nl if l1[i1] < l2[i2]:bksl-nl lst.append(l1[i1])bksl-nl i1 = i1 + 1bksl-nl else :bksl-nl lst.append(l2[i2])bksl-nl i2 = i2 + 1bksl-nl if i1 == n1:bksl-nl ...bksl-nl else :bksl-nl ...bksl-nl return lstbksl-nlbksl-nl# Testsbksl-nlassert fusion([2, 3, 5, 8], [1, 4]) == [1, 2, 3, 4, 5, 8]bksl-nlassert fusion([2, 3, 5, 8], [1, 2, 9, 10, 11]) == [1, 2, 2, 3, 5, 8, 9, 10, 11]bksl-nlbksl-nldef fusion(l1, l2):bksl-nl """bksl-nl Précondition : l1 et l2 sont deux listes triéesbksl-nl Postcondition : la fonction renvoie une liste triée constituée de la fusion bksl-nl de l1 et l2bksl-nl Exemple :bksl-nl fusion([2, 3, 5, 8],[1, 4]) renvoie [1, 2, 3, 5, 8]bksl-nl """bksl-nl bksl-nl n1 = len(l1)bksl-nl n2 = len(l2)bksl-nl lst = [] # initialisation de la fusion de l1 et l2 bksl-nl i1 = 0 # indice qui sert à parcourir l1bksl-nl i2 = 0 # indice qui sert à parcourir l2bksl-nl while i1 < n1 and i2 < n2 :bksl-nl if l1[i1] < l2[i2]:bksl-nl lst.append(l1[i1])bksl-nl i1 = i1 + 1bksl-nl else :bksl-nl lst.append(l2[i2])bksl-nl i2 = i2 + 1bksl-nl if i1 == n1:bksl-nl return lst + l2[i2:]bksl-nl if i2 == n2:bksl-nl return lst + l1[i1:]bksl-nl bksl-nl

😥 Le problème, c'est que les "slices" ne sont pas vraiment au programme de NSI, et que leur utilisation n'est pas toujours efficace. Essayons une version qui n'utilise pas de "slices".

💻 A vous de jouer 2

Compléter le script suivant :

###

# Testsbksl-nlassert fusion2([2, 3, 5, 8], [1, 4]) == [1, 2, 3, 4, 5, 8]bksl-nlassert fusion2([2, 3, 5, 8], [1, 2, 9, 10, 11]) == [1, 2, 2, 3, 5, 8, 9, 10, 11]bksl-nlbksl-nl# Autres testsbksl-nlassert fusion2([2, 3, 5, 8], []) == [2, 3, 5, 8]bksl-nlassert fusion2([], [2, 3, 5, 8]) == [2, 3, 5, 8]bksl-nlassert fusion2([5, 8, 10, 12], [1, 2, 3, 13, 14, 15]) == [1, 2, 3, 5, 8, 10, 12, 13, 14, 15]bksl-nlassert fusion2([5, 8, 10, 12], [3, 4, 5, 10, 11, 13]) == [3, 4, 5, 5, 8, 10, 10, 11, 12, 13]bksl-nlbksl-nl 5/5

def fusion2(l1, l2):bksl-nl """bksl-nl Précondition : l1 et l2 sont deux listes triéesbksl-nl Postcondition : la fonction renvoie une liste triée constituée de la fusion bksl-nl de l1 et l2bksl-nl Exemple :bksl-nl fusion([2, 3, 5, 8], [1, 4]) renvoie [1, 2, 3, 4, 5, 8]bksl-nl """bksl-nl n1 = len(l1)bksl-nl n2 = len(l2)bksl-nl lst = [] # initialisation de la fusion de l1 et l2 bksl-nl i1 = 0 # indice qui sert à parcourir l1bksl-nl i2 = 0 # indice qui sert à parcourir l2bksl-nl while i1 < n1 and i2 < n2 :bksl-nl if l1[i1] < l2[i2]:bksl-nl lst.append(l1[i1])bksl-nl i1 = i1 + 1bksl-nl else :bksl-nl lst.append(l2[i2])bksl-nl i2 = i2 + 1bksl-nl if i1 == n1:bksl-nl for i in range(...):bksl-nl lst.append(l2[i])bksl-nl return lst bksl-nl if i2 == n2:bksl-nl for i in range(...):bksl-nl lst.append(l1[i])bksl-nl return lst bksl-nlbksl-nl# Testsbksl-nlassert fusion2([2, 3, 5, 8], [1, 4]) == [1, 2, 3, 4, 5, 8]bksl-nlassert fusion2([2, 3, 5, 8], [1, 2, 9, 10, 11]) == [1, 2, 2, 3, 5, 8, 9, 10, 11]bksl-nlbksl-nldef fusion2(l1,l2):bksl-nl """bksl-nl Précondition : l1 et l2 sont deux listes triéesbksl-nl Postcondition : la fonction renvoie une liste triée constituée de la fusion bksl-nl de l1 et l2bksl-nl Exemple :bksl-nl fusion([2, 3, 5, 8], [1, 4]) renvoie [1, 2, 3, 5, 8]bksl-nl """bksl-nl n1 = len(l1)bksl-nl n2 = len(l2)bksl-nl lst = [] # initialisation de la fusion de l1 et l2 bksl-nl i1 = 0 # indice qui sert à parcourir l1bksl-nl i2 = 0 # indice qui sert à parcourir l2bksl-nl while i1 < n1 and i2 < n2 :bksl-nl if l1[i1] < l2[i2]:bksl-nl lst.append(l1[i1])bksl-nl i1 = i1 + 1bksl-nl else :bksl-nl lst.append(l2[i2])bksl-nl i2 = i2 + 1bksl-nl if i1 == n1:bksl-nl for i in range(i2, n2):bksl-nl lst.append(l2[i])bksl-nl return lst bksl-nl if i2 == n2:bksl-nl for i in range(i1, n1):bksl-nl lst.append(l1[i])bksl-nl return lst bksl-nlbksl-nl

Cours détaillé⚓︎

Cours de Nicolas Revéret

Dans ce cours les tableaux sont des tableaux de taille fixe. La syntaxe .append n'est donc jamais utilisée.

⏳ Nous étudierons une autre présentation de ce tri avec le type list Python dans un second temps

Cours de Nicolas Revéret

➗ Diviser Pour Régner : le tri fusion 🤴⚓︎

😊 Nous allons maintenant implémenter une méthode de tri basée sur "diviser pour régner" : le tri fusion.

Observons cette animation :

Illustration animée (source wikipédia)

Nous disposons d'un tableau (type list de Python) de taille n.
Son premier rang est donc 0 et son dernier rang n-1.
On notera t[a -> b] la liste constituée des éléments de rang compris entre a et b (compris) de la liste t.
La fonction tri_fusion fait appel à la fonction fusion qui permet de fusionner deux listes triées en une liste triée.


fonction tri_fusion(t)
      """
      entrée ː un tableau t
      sortie ː renvoie un autre tableau qui correspond au tableau t trié
      """
      n = longueur(t)
      si n ≤ 1
              renvoyer t
      sinon 
              m = n//2
              renvoyer fusion(tri_fusion(t[0 -> m-1]), tri_fusion(t[m -> n-1]))

La terminaison est justifiée par la décroissance stricte de n à chaque appel récursif.

💻 A vous de jouer 3

Compléter le script suivant :

###

from random import shufflebksl-nl# Testsbksl-nlassert tripy-undfusion([1, 2, 3, 4]) == [1, 2, 3, 4]bksl-nlassert tripy-undfusion([4, 3, 2, 1]) == [1, 2, 3, 4]bksl-nlassert tripy-undfusion([4, 2, 3, 1]) == [1, 2, 3, 4]bksl-nlbksl-nl# Autres testsbksl-nlassert tripy-undfusion([]) == []bksl-nlmapy-undliste = [i for i in range(20)]bksl-nlshuffle(mapy-undliste)bksl-nlassert tripy-undfusion(mapy-undliste) == [i for i in range(20)]bksl-nlbksl-nl 5/5

def tripy-undfusion(lst):bksl-nl """bksl-nl Précondition : lst est une listebksl-nl Postcondition : la fonction renvoie une liste qui est la liste triéebksl-nlbksl-nl """bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert tripy-undfusion([1, 2, 3, 4]) == [1, 2, 3, 4]bksl-nlassert tripy-undfusion([4, 3, 2, 1]) == [1, 2, 3, 4]bksl-nlassert tripy-undfusion([4, 2, 3, 1]) == [1, 2, 3, 4]bksl-nlbksl-nldef tripy-undfusion(lst):bksl-nl """bksl-nl Précondition : lst est une listebksl-nl Postcondition : la fonction renvoie une liste qui est la liste triéebksl-nlbksl-nl """bksl-nl n = len(lst)bksl-nl if n <= 1:bksl-nl return lstbksl-nl else :bksl-nl m = n // 2bksl-nl return fusion(tripy-undfusion(lst[:m]), tripy-undfusion(lst[m:])) bksl-nlbksl-nl

Une approche de la complexité du tri fusion⚓︎

⏳ La correction viendra bientôt ...

Une vidéo de Cédric Gerland sur le tri fusion et sa complexité⚓︎

Complexité

Le tri fusion a un coût en \(n \log_2 n\)

Bilan⚓︎

Le tri fusion en entier

🐍 Script Python

def fusion(l1, l2):
    """
    Précondition : l1 et l2 sont deux listes triées
    Postcondition : la fonction renvoie une liste triée constituée de la fusion 
    de l1 et l2
    Exemple :
    fusion([2, 3, 5, 8],[1, 4]) renvoie [1, 2, 3, 4, 5, 8]
    """
    n1 = len(l1)
    n2 = len(l2)
    lst = [] # initialisation de la fusion de l1 et l2 
    i1 = 0 # indice qui sert à parcourir l1
    i2 = 0 # indice qui sert à parcourir l2
    while i1 < n1 and i2 < n2 :
        if l1[i1] < l2[i2]:
            lst.append(l1[i1])
            i1 = i1 + 1
        else :
            lst.append(l2[i2])
            i2 = i2 + 1
    if i1 == n1:
        return lst + l2[i2:]
    if i2 == n2:
        return lst + l1[i1:]

def tri_fusion(lst):
    """
    Précondition : lst est une liste
    Postcondition : la fonction renvoie une liste qui est la liste triée
    """
    n = len(lst)
    if n <= 1:
        return lst
    else :
        m = n // 2
        return fusion(tri_fusion(lst[:m]), tri_fusion(lst[m:]))