Aller au contenu

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 :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280130ldy1,4]ké/weibmc:35qaPr+ 7=9o[f.gt28;6sSàh)(Epunxv050d0n0J0w0o0c0O0A0r0c0w0O0O0C010J0o0V010406050O0W0q0q0w0y0e040P0E0c0W0@0E0X050l0~1012140|0V04051k1d1n0l1k0|0d0o0Z0,0.0:0=0R0o0I0R0c1B0R0J0`050%0p0c0n1w0/0;011A1C1E1C0J1K1M1I0J0y1l0J0R0,170O0V0w0X0=0K011O1y010G0)0n0X0w0q0n1I1+1-1=1Q1^1M1{1}0`0a0A0x0y0E0V0E0O0o1a0X0A0#1)0y0y0n0r2i1d200X1l0l1%2v1!1$1#1J0d220=1E0X1`2f1I1t1v0-1P2F0o2H0X0E2L1I0V2o1l2t2v2Z0}1,2j2N1?2S0y110c0`0A0f2s2%0{2$212)1Q2+2-2/0K2=1-2@2t2E012|0w2.040A0t302u0|332`0=36380A0h3c322%343i2/0u3m3e3o3g350E2,372/0N3t2^2(1x2{3y2}390B3D3f3G3h3I3A390L3M3v3O3x3z3j0D3U2_3W3q040f0b3#3F2O3X3J0f2;1e2?3u3$3.3(0f2 3?313^3-2*3Q380f3b3~3d3E3p430`0f3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0f3!4D4h3H4p0K3+4J414L3J0K3=2Z4n4u4A0K3}4V4t3%4Y464#4y4i4S4e4*4E4,3R0K4l2#1q2X1d2L2y0d1$2D3w0r2T1~1l4|1m4`4^2#520#2Y4:1Q0j0`0#0G3m0A4$3`0G0`0G0W2g1b3m5m1?0_040T5u4+2{0`0c4U2?5v1Q5x0g5k5H3h5D4!5G5B0=5x0S0s3,340m2/0A5!5A5e0=0O0d0`020v0W0E0J0M5,5.5:5=5/0M5W3w5)5Z5!2b0k520X1t2i0A0s0A5E0A0$680K0A0O1b0J2k0n0W0Y680o0O0J0n0+1!0o0k6q5{3W5}395!2a2f0J62640o1b66680w0A0G1b2q6G2j2o0X0Z0E0o1N0W2H6m6o1N6s6u1)0X6o2h0W6%2l0.6L5r6P5l4P346y6A6i680f6a6h0c5P3 5M016_6A0U0Y0n0q0V1M666w3.755!5q5s0X0T0F0K0g3a7o0u7o0L0i0g0F0f7o0h0i0S0A6R6T6V0A7w7o7n7p0A7r0A7t7e1?7g0A5^5@5-5_7T5`4m066`730X0`0X5F315l5R010E0`0C5L7-0X0p5D1`5$4K5S0`5z4f7$5D7*2u735T3t7#7?7(712u7,5%7.7:7=8e7@7_1c807-5x7 2#8904707{4Q7}040S876A818s6o8h7|8f047;4f8d8F5x0F0i8E8v010r0f0`030A2Q2h0o376n0w656.6K7i6=6.6}6b706?4V888i0`0o8339737/8H8P340q0o0`4O2Z8K8Q8S8U8W630o0r1N5-0o6e0n0y6h0Q0A1,0y520W0y0o0y6|8z5#8r0o8b8`7-8|8I947390928~518T048V2Q1t9c0A9e9g9i0A9k9m9o9q9s8t4m8=8F5g040m1A1M9H3%8@8_95348|020c5:9,3`7(9/8{5Y041-0d9_2*8@9y9:3w9=9@7Y9D8r0Xa5850`5V9!6`8A7-9%0o5j8J8B5E8u348Mas4u9.av3W5x8Oap9A5+a9a25C8s9yaf040Fay9`049xaN5w0`0iah8;ajaXaq8D8m8e8|0HaRaH0w0V0V1`a1a#8L7~a)5N8s8_aKaMa:8Q7%aPa_8naT8yaiaX9#a}axaCa$8gb98Fa~8^aG0=8|0zbg019F3)9uaj739%0n0*0nbk5xaV3@b5bp8r0*0Ja?8Ga(a|3p0`a+a-63bE8obEa~9Z8q8eaubHawaPaJb1047Abobz8BaQbc8Q9BbkbeaeaD04bjb*8 91bnb4a63Wamaoab8?a bk9B9C2?b{aO7)bNagb$ak8e9%2o0J9p8lb bd5Da!cjb+0`b=cnbIaIc9aLbPa4cu0saBaW9vcd8@b~c5b(b/ba8Hc47+8BadcycbcC9$0`cfchb-clbDb?a7cpcWa^cua{bSckc1bVazagcA3@1d5b0n2v2Wc@4{1u4}2y2B2w0w1Lc`0l4|0|d40$0(0*04.

😥 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 :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280130ldy1,4]ké/weibmc:35qaPr+ 7=9o[f.gt28;6sSàh)(Epunxv050d0n0J0w0o0c0O0A0r0c0w0O0O0C010J0o0V010406050O0W0q0q0w0y0e040P0E0c0W0@0E0X050l0~1012140|0V04051k1d1n0l1k0|0d0o0Z0,0.0:0=0R0o0I0R0c1B0R0J0`050%0p0c0n1w0/0;011A1C1E1C0J1K1M1I0J0y1l0J0R0,170O0V0w0X0=0K011O1y010G0)0n0X0w0q0n1I1+1-1=1Q1^1M1{1}0`0a0A0x0y0E0V0E0O0o1a0X0A0#1)0y0y0n0r2i1d200X1l0l1%2v1!1$1#1J0d220=1E0X1`2f1I1t1v0-1P2F0o2H0X0E2L1I0V2o1l2t2v2Z0}1,2j2N1?2S0y110c0`0A0f2s2%0{2$212)1Q2+2-2/0K2=1-2@2t2E012|0w2.040A0t302u0|332`0=36380A0h3c322%343i2/0u3m3e3o3g350E2,372/0N3t2^2(1x2{3y2}390B3D3f3G3h3I3A390L3M3v3O3x3z3j0D3U2_3W3q040f0b3#3F2O3X3J0f2;1e2?3u3$3.3(0f2 3?313^3-2*3Q380f3b3~3d3E3p430`0f3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0f3!4D4h3H4p0K3+4J414L3J0K3=2Z4n4u4A0K3}4V4t3%4Y464#4y4i4S4e4*4E4,3R0K4l4/4K3P4M4r4^4Q4`4S4w4}4o4S4C2#1q2X1d2L2y0d1$2D3w0r2T1~1l5a1m58562#5g0#2Y4:1Q0j0`0#0G3m0A4$3`0G0`0G0W2g1b4!2?5A1?0_040T3m5K2{0`0c4U5J4+1Q5M0g5P5W3h5S5I315Q0=5M0S0s3,340m2/0A5?5!5s0=0O0d0`020v0W0E0J0M5~606264610M5/3w5{5=5?2b0k5g0X1t2i0A0s0A5T0A0$6n0K0A0O1b0J2k0n0W0Y6n0o0O0J0n0+1!0o0k6F6a3W6c395?2a2f0J6h6j0o1b6l6n0w0A0G1b2q6V2j2o0X0Z0E0o1N0W2H6B6D1N6H6J1)0X6D2h0W6_2l0.6!5F6(5z4P346N6P6x6n0f6p6w0c5(485#01786P0U0Y0n0q0V1M6l6L3.7k5?5E5G0X0T0F0K0g3a7D0u7D0L0i7D0F0f7D0h0i0S0A6*6,6.0A7L7D7C7E0A7G0A7I7t1?7v0A67665 687,694m795*350`0X5U315z7i0E0`0C5y7@0X0p5S1`5^4_015M5O4f835S7{2u7@5,3t7?7i0X7_7g397@7 04814f7}5_35850425884~8a0`8c2#8m5%8C348j7=6P8e8A6D827~808S8x5M0F0i8V890r0f0`030A2Q2h0o376C0w6k706Z7x74707c6q7f754V8l8x8n040o8g8q8T8t8!8D0q0o0`4O2Z8w8#8%048)2Q1t0r1N5 0o6t0n0y6w0Q0A1,0y5g0W0y0o0y7b8k8O8I928p9f8D8s8u9e7@9a9c98348$8(8*6i0o9m0A9o9q9s0A9u9w9y9A9C7f9E5@7i5u040m1A1M9R4u0`939_3W8s020c629}3`7_949J340E5;041-0da32*9{9I8r5}a17;9N9G0Xah7i5M5.8N799/8x9;0o5x8v8P5T8K3w8XaD3%9{948i0`8ZaA96a0a2aN908J8daq0`0FaGa49HaY5LaLas8~aua*aB8RaU8x8s0Ha#5Rab0V0V1`ada.898ba=5$8AaJaV04aXa|8D919|b68LaL0S9.a*9FaS92a6ai97aR89b8bj960zae1Q9P3)be8 899;0n0*0nbs5+0`a(3@bfaua,0Ja 01a:bM910wa^a`bMa~ba9`8A8paKb4bPagbUbcbwbf8P0oapa/8Ubmb7b%b;a80`brb@3wbu9406bx8Daxazambhb9c4899L9M2?a7bX7`b(04bG3 bI7@9;6#0ybD7^92coa99{1cb{3%8z0y1-0IbCbW3WbV8Hc5bZb35ZcvaZaocf5-b*a+9G0*bLcC3.bOcUafa@a_6icf8G5Vbh9-cX5XaWb$cqc+bE047PcPcc3W9;2o0J9zcuc7b=8QcT9eb bgby9{c3cbb,b.c880ca7|8PcMc:8Ecgc@ck5D3ycob8craa2QdpcxczcBcFa}8Fc.c6c(dz04cJc 3pa5cNch3dbIc0dId1bMcWdyd0bRc!a{dTbb5Nc.aCdiaFdidqd%b)atbJ9:0`c{c}dp5Sa-4#0l5p0n2v2Wd|591u5b2y2B2w0w1Ld 0l5a0|e90$0(0*04.

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 :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280130ldy1,4]ké/weibmc_:35qaPr 7=9o[fgt28;6sSh)(punv050d0n0I0x0o0c0N0A0r0c0x0N0N0C010I0o0S010406050N0T0q0q0x0z0e040O0E0c0T0:0E0U050l0`0|0~100^0S04051g191j0l1g0^0d0o0V0(0*0,0.0P0o0H0P0c1x0P0I0?050Z0p0c0n1s0+0-011w1y1A1y0I1G1I1E0I0z1h0I0P0(130N0S0x0U0.0J011K1u010G0#0n0U0x0q0n1E1%1)1.1M1;1I1@1_0?0a0A0y0z0E0S0E0N0o160U0A0X1#0z0z0n0r2e191|0U1h0l1Z2r1W1Y1X1F0d1~0.1A0U1?2b1E1p1r0)1L2B0o2D0U0E2H1E0S2k1h2p2r2V0_1(2f2J1/2O0z0}0c0?0A0f2o2Z0@2Y1}2#1M2%2)2+0J2.1)2:2p2A012^0x2*040A0u2|2q0^2 2?0.32340A0h382~2Z303e2+0v3i3a3k3c310E2(332+0M3p2;2!1t2@3u2_350B3z3b3C3d3E3w350K3I3r3K3t3v3f0D3Q2=3S3m040f0b3X3B2K3T3F0f2-1a2/3q3Y3*3!0f2{3/2}1k2T192H2u0d1Y2z3s0r2P1`1h3 1i3}2X3`2q05450X2U3R3*0j0?0X0G3i0A3A3l0G0?1W0o0s0G0T2c173i4r3s0=040R4C3J3?0?0$0I4I4j1/4F0Q0t3(300m2+0A4Y4O3=1/0N0d0?020w0T0E0I0L4*4,4.4:4-0L4U3s4%4X4Y270k450U1p2e0A0t0A4M0A0n0N0I0A0T2D560o5a0n4_3S4{354Y262b0I50520o1754560x0A0G172m5t2f2k0U0V0E0o1J5d1J1A5h0A4+0o585a5w5f5N4v0k5i4d0@3;3)4$4(5m4Y4?4=4+4@5+4^5Z065n4q4J2$0?185Z5@4P1M0E0?0C4p4D3Z0p4L1?4!5$1M4F4H5Z644K044M69304R3p5?6f1/4l040o4o5|6o2@5`635^5 4)0c4.626u6z0.0q0o0?3.2X6G014F4T5;5?6n6N6q2k0I0T0z5{2V5}4#6w6h5a6m5n6v0.6q0n0$5Y6#6-6O0?6Q2V5=6S4Z6N0U0?0q6y5~0.60046E6?6 6x6F7401760l0l736%6H6J043_6{6}6~7d6V0Y6Y6!2/6$6a3d0?4y4A7v3{6N6c6j3s70044v4x4z5C7H3S7G6e7a6)4N7S7d4F0F6`2/6@7J727W7j6^040i0Q0g7i7y314u0z4w7B7O7)7;7R6M7d7J6i7{6k0?0F7P6g7(7~7*6P7-0Q3z0l4g0n2r2S8h3~1q402u2x2s0x1H8k0l3 0^8u0Y0!0$04.

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:]))