Diviser/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 :⚓︎

1. Exemple de recherche d'un élément dans une liste non triée⚓︎

Le problème est de rechercher la présence d’un élément dans une liste non triée.

En adoptant le paradigme "diviser pour régner", l’idée pour résoudre cette question est de rechercher récursivement l’élément dans la première moitié de la liste et dans la seconde, puis de combiner les résultats via l’opérateur logique or.

En effet, l’élément recherché sera dans la liste s’il est dans la première moitié ou dans la seconde. La condition d’arrêt à la récursivité sera l’obtention d’une liste à un seul élément,car il est alors immédiat de conclure si l’élément recherché appartient à une telle liste ou non.

Étapes

Voici donc les trois étapes de la résolution de ce problème via la méthode "diviser pour régner":

• Diviser la liste en deux sous-listes en la “coupant” par la moitié.

• Rechercher la présence de l’élément dans chacune de ces sous-listes. Arrêter la récursion lorsque les listes n’ont plus qu’un seul élément.

• Combiner avec l’opérateur logique or les résultats obtenus.

Algorithme proposé

👉 Voici l'algorithme proposé :

📋 Texte

fonction recherche(ma_liste, x, d, f):
"""
Précondition : ma_liste est une liste à priori non triée, x est un élément cherché dans la liste 
d est le rang du début de la recherche, et f le rang de la fin de la recherche dans ma_liste
postcondition : la fonction renvoie du booléen : 
`True` si x est dans la liste, et `False` sinon.
"""
Si d = f:
    renvoyer ma_liste[d] == x
m ← (d + f) // 2
renvoyer recherche(ma_liste, x, d, m) ou recherche(ma_liste, x, m + 1, f)

À vous de jouer 1 :

Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013f06S:d=F4yr./oTpg2mcb1w937ve[ l,8+P5)tài]kné;ua(shq050g0C0M0V0O0F0X0E0u0F0V0X0X0h010M0O0q010406050X0U0t0t0V0l0k040e0o0F0U0@0o0R050n0~1012140|0q04051k1d1n0n1k0|0g0O0B0,0.0:0=0Y0O0r0Y0F1B0Y0M0`050%0v0F0C1w0/0;011A1C1E1C0M1K1M1I0M0l1l0M0Y0,170X0q0V0R0=0s011O1y010b0)0C0R0V0t0C1I1+1-1=1Q1^1M1{1}0`0a0E0J0l0o0q0o0X0O1a0R0E0#1)0l0l0C0u2i1d200R1l0n1%2v1!1$1#1J0g220=1E0R1`2f1I1t1v0-1P2F0O2H0R0o2L1I0q2o1l2t2v2Z0}1,2j2N1?2S0l110F0`0E0w2s2%0{2$212)1Q2+2-2/0s2=1-2@2t2E012|0V2.040E0z302u0|332`0=36380E0j3c322%343i2/0K3m3e3o3g350o2,372/0d3t2^2(1x2{3y2}390A3D3f3G3h3I3A390H3M3v3O3x3z3j0y3U2_3W3q040w0c3#3F2O3X3J0w2;1e2?1o2X1d2L2y0g1$2D3w0u2T1~1l3{1m3_2#3?3105410#2Y3V3.0Q0`0#0b3m3E340x2/4l3N3.0R0b0`2o0u0Y0C0l4x0C4q4f1?0_040W4D3$4s0`0*0M4J3-4F0`0G3m0E4m3w0R0`2S0t0v2o4P344G4T492u4V4r2*4i4(3w4*4U4W3%0`4k4,4e4K4R040L0f3,4n2/0E574=3W0X0g0`020Z0U0o0M0T5e5g5i5k5h0T543w5b56572b0S410R1t2i0E0f0E4N0E0C0X0M0E0U2H5D0O5H1N0N0E2W0O3y0O0E2S2j1!0O0S0C0G5W0o4#2o5F5H5J2j0S0F0S1}0R5I4B4A0Y0S2k1-0+0.5M5O4V4}3u4 1Q5s39572k5,5I1M0E0l1-0r2k0U2k0S0v192k1N604w4y5`5$5F5I0b5D1N6g0R6i2l601^2j6E0V6f2p6t4B5}0R5 5H5q5a5c69572e5H5x5z5T2j5C6F1b2q6#6K0R0B0o0O1N0g6k0v0o175#6$632Z654Q676U6a0E0p0l0U1N2g5(5*1N5G5I0g5~5D6J1E5O5%0$0E0i370X772Q1b0m6S3.68725n5m5f5o7y5p64724_4g0`0O4|2Z4.4E2{4;4}7M660=0o0`0h0h4^4/7O047K3@7Z0=4G537E726a7G1?4h042o0M0U0l1c7Q7/7!4N593.4G0D7 4:040g831Q4G0P7Y7N7T7V7X7{7(354Z5)4$4C7,588h4Y040t8b7S017U048f7L7|7)0`4I4}8A8i858t6 8d040I8I3p4{878B518N3w8w0n0n8T3W0t0O0`2 8n7R8J017;7?7^7`8z8p4v6L4z4B8Q014G8D2#8;047~8E8h4@8g8c8G4!8l8_938:958q8691959a2?8)8O8r990`0L8Y3.0o4o043y9p846s8@4y9m4H8_8q908}9g4S9v7!974%9f8u9h319j4X0`8s948u8w8M9U8*8!0`3=9F9N9H9Y9k7$4a929n3D0n4c0C2v2W9?3`1u3|2y2B2w0V1L9_0n3{0|a30$0(0*04.

Comparaison avec la méthode de parcours séquentiel

On donne ici une méthode "naïve" par parcours de liste séquentiel.

Nous allons comparer ces deux méthodes dans le pire des cas (nous cherchons un élément x qui ne se trouve pas dans la liste):

Votre figure

Votre tracé sera ici

À lire

Ici, le parcours séquentiel est plus efficace. Une explication est que les appels de fonction (récursivement) ont un coût.
Utiliser la méthode diviser pour régner dans ce cas-là s'apparente à "écraser une mouche avec un marteau-pilon."

2. Recherche du maximum dans une liste non triée⚓︎

Avec le paradigme diviser pour régner

Le problème est de rechercher le maximum d’une liste de nombres.

En adoptant le paradigme "diviser pour régner", l’idée pour résoudre cette question est de rechercher récursivement le maximum de la première moitié de la liste et celui de la seconde, puis de les comparer. Le plus grand des deux sera le maximum de toute la liste.

La condition d’arrêt à la récursivité sera l’obtention d’une liste à un seul élément, son maximum étant bien sûr la valeur de cet élément.

Voici donc les trois étapes de la résolution de ce problème via la méthode "diviser pourrégner":

• Diviser la liste en deux sous-listes en la “coupant” par la moitié.

• Rechercher récursivement le maximum de chacune de ces sous-listes. Arrêter la récursion lorsque les listes n’ont plus qu’un seul élément.

• Combiner : Renvoyer le plus grand des deux maximums précédents.

Observons le schéma suivant :

maxis

À vous de jouer 2 :

Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013f06S:d=4yr/oxpg2mcb1w937Cve[ l,8+P5)ti]kné;ua(_shq050g0B0L0T0M0E0W0D0s0E0T0W0W0h010L0M0o010406050W0S0r0r0T0k0j040e0m0E0S0?0m0P050l0}0 11130{0o04051j1c1m0l1j0{0g0M0A0+0-0/0;0X0M0p0X0E1A0X0L0_050$0t0E0B1v0.0:011z1B1D1B0L1J1L1H0L0k1k0L0X0+160W0o0T0P0;0q011N1x010b0(0B0P0T0r0B1H1*1,1;1P1@1L1`1|0_0a0D0I0k0m0o0m0W0M190P0D0!1(0k0k0B0s2h1c1 0P1k0l1$2u1Z1#1!1I0g210;1D0P1_2e1H1s1u0,1O2E0M2G0P0m2K1H0o2n1k2s2u2Y0|1+2i2M1=2R0k100E0_0D0u2r2$0`2#202(1P2*2,2.0q2;1,2?2s2D012{0T2-040D0x2 2t0{322_0;35370D0i3b312$333h2.0J3l3d3n3f340m2+362.0d3s2@2%1w2`3x2|380y3C3e3F3g3H3z380G3L3u3N3w3y3i0w3T2^3V3p040u0c3!3E2N3W3I0u2:1d2=3t3#3-3%0u2~3=303@3,2)3P370u3a3}3c3D3o420_0u3k463m3^413X4b3r4e3 494i3(3B4e1n2W1c2K2x0g1#2C3v0s2S1}1k4v1l4t2!4r4B0!2X3U3-0O0_0!0b3l483v0v2.4T3M3_0b0_100n0M0r0~0V2n0s0S0k2f4S4r4Z1=0^040U4Y4N2)0_1J4|4g1P4_0F3l0D4U3$4Q0B0t185140530_554e574@2`0_1@1b4?4}5g040K0f3+334W380D5A5e330W0g0_020Y0S0m0L0R5H5J5L5N5K0R5w3v5E2.5A290k0Q4B0P1s2h0*0f0D1J0D0B0W0L0D0S2G0D1D5/0B0F2j5b185-5/5@02030x0w0R2P1s0s1M0g0S2j0Q5c5:2k0-0D4-0X0B0k0s6l5{5T3V5V5z5A0#0D5o616365670M695|5@0T6x2P6F6i6k6m6o0B6r3-6t5X292e0L5#5%0M1a0D5*6i0b1a2p6Z2i2n0P0A0m0M1M1L0D4%4)0~6K6H5^0L1M504l586R5F6u0D5Q5P5I5R775S4l6T721=4P040M4=2Y5k5r3g5a6f567f1P0m0_0h0h7r5l7o045o7y7n014_5v5j7s0;0s0u0_030D0z0.6F0t0.1M5=0D0W0B0S0E0D0Q0E0Q1|0P0L3s6T7e7z017h2n0L4/5p7l7J344 0T0t5C3v4_0C8059040!7q5q520;4_0N7-5X7{7h0B0)6P895f8b0_7H2Y067.8f7:0P4$0(6;0S7D8a017u047x7I7:4_4{8l3o7p5d8G7E8D0H8A8m7|7B2P843-4_0K8S338D0l0l8#3v0r0M0_3|8q8s5B8u0_0n8*3V8D8F7`8?046^4*0r4,2o4/4;8X4^0_8J2!8~709b7E548_3_8M7,8K815h9h4~8 8x7Z975s8!7d8;7{8v040j9o7t7v9C7A904+4-957j9t8n4`9M8U9d2=7{9g8O8B9z8,1D9s9V8T8Q9F018,4b9P9U8}7E9z7C9l3V8Z8e8s8g0_9L9#8L048^9}3v8D020E5L8|2=7m9W0_9B9=8Y8o9^8;8=7E7=0#7^9(9zac8:9x7:8h8j9,af9wahai8Bak7@0k7_a89y8@3C0l4K0B2u2VaL4u1t4w2x2A2v7~1L2u4v0{0l0!0$0(0W04.

À vous de jouer 3 :

Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013f06S:d=4-yr/Noxpg2mcb1w937ve[ l,8+P5)ti]kné;ua(_shq050g0C0M0U0N0F0X0E0u0F0U0X0X0h010M0N0q010406050X0T0t0t0U0l0k040e0o0F0T0@0o0Q050m0~1012140|0q04051k1d1n0m1k0|0g0N0B0,0.0:0=0Y0N0r0Y0F1B0Y0M0`050%0v0F0C1w0/0;011A1C1E1C0M1K1M1I0M0l1l0M0Y0,170X0q0U0Q0=0s011O1y010b0)0C0Q0U0t0C1I1+1-1=1Q1^1M1{1}0`0a0E0J0l0o0q0o0X0N1a0Q0E0#1)0l0l0C0u2i1d200Q1l0m1%2v1!1$1#1J0g220=1E0Q1`2f1I1t1v0-1P2F0N2H0Q0o2L1I0q2o1l2t2v2Z0}1,2j2N1?2S0l110F0`0E0w2s2%0{2$212)1Q2+2-2/0s2=1-2@2t2E012|0U2.040E0z302u0|332`0=36380E0i3c322%343i2/0K3m3e3o3g350o2,372/0d3t2^2(1x2{3y2}390A3D3f3G3h3I3A390H3M3v3O3x3z3j0y3U2_3W3q040w0c3#3F2O3X3J0w2;1e2?3u3$3.3(0w2 3?313^3-2*3Q380w3b3~3d3E3p430`0w3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0w3!4D4h3H4p0s3+4f1o2X1d2L2y0g1$2D3w0u2T1~1l4T1m4R2#4P4Z0#2Y4E1?0P0`0#0b3m4t3W0x2/4^4y2*0b0`110p0N0t0 0W2o0u0T0l2g0b0W0B3}2#4~1Q0_040V4}4/2{0`1K5n4K0=5k0G3m0E4_3`4=0C0v195x5z1?0o0`0h5F5i0=0P0u0`0n1b0C5s415j0`5w4f5y5M350`1^1c5Z5G1Q5I045K5*5#5O5Q5S5U345k0L0f3,344{390E615^3w0X0g0`020Z0T0o0M0S686a6c6e6b0S5}646660612b0R4Z0Q1t2i0+0f0E1K0E0C0X0M0E0T2H0E1E6B0C0G2k5C196z6B6G02030z0y0S2Q1t0u1N0g0T2k0R5D6C2l0.0E580Y0C0l0u6.6K6k3W652/616z6C5(6Q6S6U6W0N6Y6L6G0U0E6~6*776-6/6;5T4J5V0=6_6n2a2f0M6r6t0N1b0E6w6+0b1b2q7q2j2o0Q0B0o0N1N1M0E52540 756+6H0M1N5r7g347j6{0E6h6g696i7W6j4m7U5+5N0`0N4@5:5o3h5B6(5L7.015-0h5/2Z5!7?5=045R2H633W5k5|7$7U6{7(5$040#7;7-5t7@5J7=8f0t0N0`4O2Z067%5;7*7,7{890Q5%2Q8i7h8g5.7`2?7|8f7~807f5h7?843t87885#8w045(8z347^8U4u0v0`25823.5k5m4P8Q5q0U0v8$1?5`8/5,0`0j8=0=8k4c8N8P7}8s8X3%7:5E8e8A7^8D318F8A8R8T955_0`858o8O628r042o0M5a5)8u8+047Q8K8f5k0D8_8a8c949v8A5k0O8}9k8 040C0*8J2?898M868O8v510)7E0T913.8W9e3w8(9z8R9B0M9Y5H0`0I9,5p8S8y8*8L0`0L9:0=5-0m0m9{018{045g3@9j9a3p0`0pa09!9r7?8R7I550t572p5a5c5ea4319P0`8)9Da89t8-9z5va09)6M9+9@9w5Xaz9U1E0C9XaD9E9_9H879T040kab8h9#9204ag5658al7+anaxar9(8,8.aL9f045Yad8faf9VaJaT049/aV3.a23=at9$aFa|2*8x9q9O5#8;9RaP9l7+aG04aab38?04020F6c982ua74u0`aSa-b1049ha5a68~8G0`9n9pbebs9i9j894;9K9Ma(bvaOa6bIbB0$bDbh7/bf3D0m4,0C2v2Wb!4S1u4U2y2B2w8-1M2v4T0|0m0#0%0)0X04.

Comparaison avec la méthode de parcours séquentiel

On donne ici une méthode "naïve" par parcours de liste séquentiel.

Nous allons comparer ces deux méthodes :

Votre figure

Votre tracé sera ici

À lire

Ici, le parcours séquentiel est plus efficace. Une explication est que les appels de fonction (récursivement) ont un coût.
Utiliser la méthode diviser pour régner dans ce cas-là s'apparente à "écraser une mouche avec un marteau-pilon."

Remarque

😨 Mais pourquoi utiliser "diviser pour régner?"

3. Exponentiation récursive classique⚓︎

On peut définir $x^n$ de façon récursive

$x^0$ = 1
$x^n$ = $x$ * $x^{n-1}$

À vous de jouer 4 :

🤣 Le but étant de programmer la puissance "à la main", il est intedit d'utiliser ** ou pow.

1. Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013f:6S0d=4-yr/oxpg2mcb1w937ve l,8*P5)tikné;ua(_shq050g0B0K0R0L0D0U0C0t0D0R0U0U0h010K0L0p010406050U0Q0s0s0R0l0k040e0n0D0Q0;0n0N050m0{0}0 110_0p04051h1a1k0m1h0_0g0L0A0)0+0-0/0V0L0q0V0D1y0V0K0@050!0u0D0B1t0,0.011x1z1B1z0K1H1J1F0K0l1i0K0V0)140U0p0R0N0/0r011L1v010b0$0B0N0R0s0B1F1(1*1/1N1=1J1^1`0@0a0C0H0l0n0p0n0U0L170N0C0Y1$0l0l0B0t2f1a1}0N1i0m1!2s1X1Z1Y1G0g1 0/1B0N1@2c1F1q1s0*1M2C0L2E0N0n2I1F0p2l1i2q2s2W0`1)2g2K1:2P0l0~0D0@0v2p2!0^2Z1~2$1N2(2*0@0r2.1*2:2q2B012^0R2+040y2|2r0_2 2?0/32340i372~2!303d0@0I3g393i3b310n2)330@0d3n2;2#1u2@3s2_040z3x3a3A3c3C3u040F3G3p3I3r3t340x3g1l2U1a2I2v0g1Z2A3q0t2Q1{1i3Z1j3X2Y1b2/053)0Y2V3P2L010M0@0Y0b3V3H3{0w0@0C413`2%0b0@0B0o2b0T2l0t472=3Q0?040S4i3z3{0N0@0o4o304l0E3g46422%0@193;2}3y4v0@0J0c3O4j43450C4P4u3q0U0g0@020W0Q0n0K0P4W4Y4!4$4Z0P4L4p1:4T4O4P280O3)0N1q2f0C0c0C0o0C0Z0C2g0U180K2h0B0(1@0;0B0l0U4,304/044P4;2c0K4@4_0L184{0C0+0C0b182n5o2g2l0N0A0n0L1K0o0G0G4D2W3o4M4.4U5h5i4)4(4X4*5Q4+4E385i4z481N3}040L405W5h4G3q4r045I2/5Z5L1N0n0@0h0h4y5,3Q0s0L0@0f4R4k0@4K5*065Y5Y5}3{5$2l0K0Q0l5:2}5=4-1N5 2,3n6a4A5#4b0%0B5|6r0/4l665J695i6b1:6d0Z6g6i2r6k3j4s6w5!0/5^040G6O5?3c4b4d0n4f2m633{4l4n5*6E2@6N6*6x014w6U6l6W5/6=306R0j6_3q6n042-6.6P6:4I3x0m3@0B2s2T793Y1r3!2v2y2t0R1I7c0m3Z0_7m0Z0#0%04.

2. Utilisons la fonction précédente pour calculer $2^{1000}$

Que se passe-t-il?

Solution

Nous avons un message d'erreur expliquant qu'il y a eu un trop grand nombre d'appels de fonctions récursifs. Nous verrons plus tard que nous pouvons modifier cette limite dans Python.

😥 Il faudra faire 100 multiplications pour calculer $x^{100}$ .
On dit que la complexité (en regardant le nombre de multiplications) de cet algorithme est en $O(n)$,

Temps de calcul avec l'exponentiation récursive classique

Votre figure

Votre tracé sera ici

Solution

La complexité semble encore linéaire.

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

Diviser pour régner : exemples

La correction est arrivée 😊

Diviser pour régner : exemples - correction

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 :

Évaluations restantes : 5/5

.128013f06S:d=4yrE./oxpg2mcb1w937ve[ l,8+P5)tài]kné;ua(shq050g0C0M0V0O0F0X0E0u0F0V0X0X0h010M0O0q010406050X0U0t0t0V0k0j040e0o0F0U0@0o0R050n0~1012140|0q04051k1d1n0n1k0|0g0O0B0,0.0:0=0Y0O0r0Y0F1B0Y0M0`050%0v0F0C1w0/0;011A1C1E1C0M1K1M1I0M0k1l0M0Y0,170X0q0V0R0=0s011O1y010b0)0C0R0V0t0C1I1+1-1=1Q1^1M1{1}0`0a0E0J0k0o0q0o0X0O1a0R0E0#1)0k0k0C0u2i1d200R1l0n1%2v1!1$1#1J0g220=1E0R1`2f1I1t1v0-1P2F0O2H0R0o2L1I0q2o1l2t2v2Z0}1,2j2N1?2S0k110F0`0E0w2s2%0{2$212)1Q2+2-2/0s2=1-2@2t2E012|0V2.040E0z302u0|332`0=36380E0i3c322%343i2/0K3m3e3o3g350o2,372/0d3t2^2(1x2{3y2}390A3D3f3G3h3I3A390H3M3v3O3x3z3j0y3U2_3W3q040w0c3#3F2O3X3J0w2;1e2?3u3$3.3(0w2 3?313^3-2*3Q380w3b3~3d3E3p430`0w3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0w3!4D4h3H4p0s3+4J414L3J0s3=2Z4n4u4A0s3}4V4t3%4Y464#4y4i4S4e4*4E4,3R0s4l2#1q2X1d2L2y0g1$2D3w0u2T1~1l4|1m4`4^2#520#2Y4:1Q0Q0`0#0b3m4$3.0x2/5k4+2{0b0`0b0U2g1b5p5e0=0_040W5y4K3h0`0F4U2?5l1?5B0G3m0E5L2{5H4!5K5q5A0`0L0f3,345n390E5)5E4Q0=0X0g0`020Z0U0o0M0T5;5?5^5`5@0T5#3w5.2/5)2a0k0S520R1t2i0E0f0E5I0E0$6e0s0E0X1b0M2k0C0U0p6e0O0X0M0C0+1!0O0S6w603W625(5)0J2f0M686a0O1b6c6e0V0E0b1b2q6M2j2o0R0B0o0O1N0U2H6s6u1N6y6A1)0R6u2h0U6-2l0.6R5v6V5Q4P346E646o6e0w6g6n0F5U3 5R5-5/6F0E0l0p0C0t0q1M6c6C3.6 645u5w0R0W0D0s0G3a7v0K7v0H0P0G0D0w7v0i0P0L0E6X6Z6#0E7D7v7u7w0E7y0E7A7l1?7n5)5}5|5=5~7!5 4m067079350`0R5J315Q5W010o0`0h5P7-0R0v5H1`5+345B5D4f7}5H7;2u7-5B0L3t7,7@0R7/772u7?5z7^7`7|8g7 0425823w848u3%5T8x3.8c8e64878s6u8p8m7_047{4f8l5F015B0D0P8I8P0u0w0`030E2Q2h0O376t0V6b6@6Q7p6{6@736h766|4V8f8m8h040O89397-8K8M2Z8O5,010t0O0`4O937-8W8Y8!690O0u1N5=0O6k0C0k6n0N0E1,0k520U0k0O0k728D5*8g0`0O8j8 7@918U9597999J349d048Z2Q1t9i0E9k9m9o0E9q9s9u9w9y769A94345g040x1A1M9N4u9D8~9+3w8K020F5^9=8y047:9 3.0o5%1-0ga32*9D9F9_3W9{9}7)9b9Ca1ac8b0`5!4m708_8P9-0O5j8N8F5I8A5M0`0Daz5S8|8~am048Taw9H5:aga9aE9)867@8RaD5G8|9FaH0Pao8^aqa$ax8HaR8J0`0maU7.040V0q0q1`a8a*8P8wa_958{aya|83aBa.8{8}a.5B7H9*a$9B8`9@aO0=9IaKbcaFbe8n040Ibk9L3)b98E7@9-0C0*0Cbk5Ba!3@baaqa(0Ma.8Ka-b09?a:a=a@b60`852#ajaQbR8maTbJa09EbOaI8dapbCbsbibZbh8Pbgaib*alaLbmbo98bqb%bbas9Davb/8Pb49^907`922?ad3`7/aGaSanbrb{959-2o0M9v1cb,a}5Ha)b 958Kbncl3p8zbX8Bb2cwaaaWb!0faJa#ce9,b}bkb4b;a+8Lc57=8F0RaXcb04bA3 bC7-cg0$cjcJcnbFct9`0`cscpcu8scabVcybUc0bdcz1QbzcE3@1d5b0C2v2Wd04{1u4}2y2B2w0V1Ld30n4|0|dd0$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 :

Évaluations restantes : 5/5

.128013f06S:d=4yrE./oxpg2mcb1w937ve[ l,8+P5)tài]kné;ua(shq050g0C0M0V0O0F0X0E0u0F0V0X0X0h010M0O0q010406050X0U0t0t0V0k0j040e0o0F0U0@0o0R050n0~1012140|0q04051k1d1n0n1k0|0g0O0B0,0.0:0=0Y0O0r0Y0F1B0Y0M0`050%0v0F0C1w0/0;011A1C1E1C0M1K1M1I0M0k1l0M0Y0,170X0q0V0R0=0s011O1y010b0)0C0R0V0t0C1I1+1-1=1Q1^1M1{1}0`0a0E0J0k0o0q0o0X0O1a0R0E0#1)0k0k0C0u2i1d200R1l0n1%2v1!1$1#1J0g220=1E0R1`2f1I1t1v0-1P2F0O2H0R0o2L1I0q2o1l2t2v2Z0}1,2j2N1?2S0k110F0`0E0w2s2%0{2$212)1Q2+2-2/0s2=1-2@2t2E012|0V2.040E0z302u0|332`0=36380E0i3c322%343i2/0K3m3e3o3g350o2,372/0d3t2^2(1x2{3y2}390A3D3f3G3h3I3A390H3M3v3O3x3z3j0y3U2_3W3q040w0c3#3F2O3X3J0w2;1e2?3u3$3.3(0w2 3?313^3-2*3Q380w3b3~3d3E3p430`0w3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0w3!4D4h3H4p0s3+4J414L3J0s3=2Z4n4u4A0s3}4V4t3%4Y464#4y4i4S4e4*4E4,3R0s4l4/4K3P4M4r4^4Q4`4S4w4}4o4S4C2#1q2X1d2L2y0g1$2D3w0u2T1~1l5a1m58562#5g0#2Y4:1Q0Q0`0#0b3m4$3.0x2/5y4+2{0b0`0b0U2g1b4!2?5z1?0_040W5D5s3h0`0F4U5N5E0=5Q0G5T4_355W5M315O1Q5Q0L0f3,345B390E5`5(4~010X0g0`020Z0U0o0M0T62646668650T5?3w5 2/5`2a0k0S5g0R1t2i0E0f0E5X0E0$6s0s0E0X1b0M2k0C0U0p6s0O0X0M0C0+1!0O0S6K6e3W6g5_5`0J2f0M6m6o0O1b6q6s0V0E0b1b2q6!2j2o0R0B0o0O1N0U2H6G6I1N6M6O1)0R6I2h0U6~2l0.6)5J6-0E6Q3.6S6i6C6s0w6u6B0F5,485!5~606T0E0l0p0C0t0q1M6q7b1?7d6i5I5K0R0W0D0s0G3a7J0K7J0H0P7J0D0w7J0i0P0L0E6/6;6?0E7R7J7I7K0E7M0E7O7z1Q7B5`6b6a636c7=6d4m7e5.5V040R5Y317a7n0o0`0h3m835U350v5W1`5|345Q5S4f7}5*045X8f3w5:3t7|7n0R0`0R7l398k8504874f895)0R8c8m8e8j7n8h8o3%5+8N3.8q7{6i8k8u8m6I888z868Z8L0`0D0P8$8a0u0w0`030E2Q2h0O376H0V6p756(7D79757h6v7k7a8T5{8t0`0O812u8E5}8A8C2Z9c340t0O0`4O9g8k8-8/8;6n0O0u1N630O6y0C0k6B0N0E1,0k5g0U0k0O0k7g8r8U97040O8x9h3w9e8+5)9j9l9V5}9p048:2Q1t9u0E9w9y9A0E9C9E9G9I9K7k9M968a5u040x1A1M9Z3p989a8y84610F66a14u8va49S3W0o5^1-0gaa8O9P9R8!0402a87`9n9O8wak8R0`5=957eae3.9|0O5x8D8V5Wa48k5Q0D8Q2*a3aO5/0`8*aHa6aparawaP8m8xaL8(aR7~9Qa)015Q0Paz4VaBa=aCa!0*0Ma,8A0ma,8W0V0q0q1`aj8K8a8Mb58FaJa,aMa~aQb85}a.0L9_a?9`b99Padao9f2?a@2{beat8a8A0IaZ1Q9X3)bj8s9{0`0C0*0Cbz5#aybDa?aI8Xa`bf34a|bd04b0b26nbb0`8i2#9O9^bS8pa(b*ala+b-ax047VbNa=bPb/bv5)9UaV8a8Wb`braobyb~9W9kbCaA8kaEaGb{5}c0boaW0hbq82bP80b!04a:3@bkca5H3ybK8l0Ocvag981cc5ce8H0k1-0rbJb:5Pb#bVc15-8%045%cCa27 a$cP5;b@aBbPa_a{0`a}cJbtbWb1b3cnb$5Zb 8Pc)bL04aNc?cwcnb?aAbE5)9|2o0M9HcBcdcTc#8D06c 5}cbcvc0anchcj9bclcVb6bMc~9NbF046*0kde98cy5^2QdecEcGcIb%dm5RcMaKcPcRd6ab7 dHdEcXdob^b(8Yc`bUc`a c,bZc`b7dDbm8nd!b,d$cedvd)b=bidQbs0=d10$d4dubQ3D0n5p0C2v2Wd 591u5b2y2B2w0V1Le20n5a0|ec0$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 :

La fonction fusion est écrite dans le code caché.

Évaluations restantes : 5/5

.128013f06S:d=4yr/opg2mcb1w937ve[ l,8P5)ti]kné;ua(_shq050g0z0I0Q0J0C0T0B0r0C0Q0T0T0h010I0J0n010406050T0P0q0q0Q0k0j040e0m0C0P0:0m0M050l0`0|0~100^0n04051g191j0l1g0^0g0J0y0(0*0,0.0U0J0o0U0C1x0U0I0?050Z0s0C0z1s0+0-011w1y1A1y0I1G1I1E0I0k1h0I0U0(130T0n0Q0M0.0p011K1u010b0#0z0M0Q0q0z1E1%1)1.1M1;1I1@1_0?0a0B0F0k0m0n0m0T0J160M0B0X1#0k0k0z0r2e191|0M1h0l1Z2r1W1Y1X1F0g1~0.1A0M1?2b1E1p1r0)1L2B0J2D0M0m2H1E0n2k1h2p2r2V0_1(2f2J1/2O0k0}0C0?0B0t2o2Z0@2Y1}2#1M2%2)2+0p2.1)2:2p2A012^0Q2*040B0w2|2q0^2 2?0.32340B0i382~2Z303e2+0G3i3a3k3c310m2(332+0d3p2;2!1t2@3u2_350x3z3b3C3d3E3w350E3I3r3K3t3v3f0v3Q2=3S3m040t0c3X3B2K3T3F0t2-1a2/3q3Y3*3!0t2{3/2}1k2T192H2u0g1Y2z3s0r2P1`1h3 1i3}2X3`2q05450X2U3R3*0L0?0X0b3i3A300u2+4p3J3?0b0?1W0J0S0b0P2c174u4j1/0=040R4G3=2$0?0$0I4M3)4I0?0H0f3(4r2+0B4#4S300T0g0?020V0P0m0I0O4,4.4:4=4/0O4Y3s4)4!4#270N450M1p2e0B0f0B4Q0B0z0T0I0B0P2D580J5c0z4{3S4}354#262b0I52540J1756580Q0B0b172m5v2f2k0M0y0m0J1J5f1J1A5j0B4-0J5a5c5y5h5P4z0N5k4d0@3;4T1M5n5p0B4^4@4-4_5-4`5#065+4q3s0M0?185#0B5_3S0m0?0h3i5 4v2$0s4P1?4%3s4J4L5#603?4P5c6c3S4J0H3p5^671M4l040J4o5~6h4O045}2V664H1M6204020C4:646x6r0.0q0J0?3.2X6N014J4X5?5+6q6E0.6t2k0I0P0k6B2/6D4N2@6j4R6Y5p6y6s0?0z0$5!6C6^0.6W6p6Z4$6U5{040q656 016G6L6~755|796U6G0l0l7h6#016P0?3_2V5@736.5(6$0?6(6*6,2}7v3l0?4C4E7B4e6U6e6l6i044z4B4D5E7M4U4K7T6:044Q7W700?0A6X6T7n76786g7K0?0K0H0D7m6/3d4y0k4A7G7S7-7n7L7~7@316;7!6V7$857+856W7:6o5?194g0z2r2S8h3~1q402u2x2s0Q1H8k0l3 0^8u0Y0!0$04.

Une approche de la complexité du tri fusion⚓︎

Fonction tri_fusion

On redonne :

💻 A vous de jouer 4

Compléter le script suivant :

Évaluations restantes : 5/5

.128013f06S:d=4-yrE./opg2mcb1!w937Cvej[ l,8+P5)tài]kn;Lua(_shq050g0E0P0Y0R0I0#0H0u0I0Y0#0#0h010P0R0q010406050#0X0t0t0Y0l0k040e0p0I0X0{0p0U050o12141618100q04051o1h1r0o1o100g0R0D0:0=0@0_0$0R0r0$0I1F0$0P0~050+0v0I0E1A0?0^011E1G1I1G0P1O1Q1M0P0l1p0P0$0:1b0#0q0Y0U0_0s011S1C010b0-0E0U0Y0t0E1M1/1;1_1U1|1Q1 210~0a0H0M0l0p0q0p0#0R1e0U0H0)1-0l0l0E0u2m1h240U1p0o1+2z1(1*1)1N0g260_1I0U1~2j1M1x1z0;1T2J0R2L0U0p2P1M0q2s1p2x2z2%111:2n2R1`2W0l150I0~0H0w2w2+0 2*252-1U2/2;2?0s2_1;2{2x2I01300Y2=040H0A342y10372~0_3a3c0H0i3g362+383m2?0N3q3i3s3k390p2:3b2?0d3x2|2,1B2 3C313d0B3H3j3K3l3M3E3d0K3Q3z3S3B3D3n0z3Y2}3!3u040w0c3)3J2S3#3N0w2^1i2`3y3*3=3,0w333`353|3;2.3U3c0w3f423h3I3t470~0w3p4b3r3}463$4g3w4j1s2#1h2P2C0g1*2H3A0u2X221p4u1q4s2)4q4A0)2$3Z3=0T0~0)0b3q4d3A0y2?4S3R3~0b0~1(0R0!0#0E1Q2u0R1f4X4M1`0}040Z4/4l2 0~1I0#0P0E4^451U4=0O0f3:384V3d0H5a50380#0g0~020%0X0p0P0V5h5j5l5n5k0V563A5e2?5a0H4|4~0H0E4}2o1R0P0k0q1R5z4 4j445d5f595a0W0Y0H0b1f4,1f0H2s0U0D0p0R5J5T5K0H4$0E1R1:0l0H3C0g2s0:2g0R0@1;0P0n5t3!5v5Q0H0m0I1Q0H1d0-5{5J02030A0z0V3b0r3C2l0$215E5,0l0R0H5:0H4)4+2m0n0H0C6d6f0V5C0P682n4$0H5q5l1~6s0=0u0E6K5s5M4T615P5x6J5i5r6R6R3x6X6U4N0~5V0l3q0H6)2.0~0R6.6:1U0p582U6@4Y2.0v0~0l1;0r5L2)6~520~4@4q773l7004295c3A4=7a764:4`7f5{4~7h3!536}7m0_0p0~0j7u4_0_0t0R4g7r3=53555M6X6(7c396=0U1x6P0!7D1g4j6/7N7x040h7A513l6=6%7L5b7N4O046,7$3t0~0F7;3A6`7P7^3+7e720U747G4;79827n6?7W6^7w0~0L7|3=7D7F7b7v014=0J8d6 4{1~850_7j8q7O7o4}752`898j0~0O548m1U0u0w0~035Z2t0$0E0l0u8M6o0I6B6g2U7R1R0g0X0H7U0R0t137*7+8*8+8,8+8z8G8I2o1;0/672s8w8R5*7p0E0Z0Q2o5`4~0O8)8,8z7.0R4R887N0U4{8}8t4=0G8t9d047@8h7B8A040S8E8a04020I5l9s8u5K9g0~9i9n7%8u8V0R7S7U9B9q7J2%068-7+8z9k9H9J6|9b8i7Z7#9X9o9k9m9O8.7-6=9a2%7X8i9T7Q9I0E7T9W9.8z7Z0x9!9`9c7)9E384=9N2`9/9o8:048J8L731R0#8T0V0-0H0k0H5T0X2L6N0X0/5I0{5A0D3b0E0X5;0g8?959Q9Q8/8Haa5y5T5:0{8X928X5)5y9f7KaEa08v7qa27i9C9ja17l9o4=0S8l9#9F9k9AaX7saZa/3~7P8W9^7Va$9Fa(9y9Z9ya-aRa{a3a;b33A9;a^9Ka=839qa*9 9:9e8w9L9Db63+a#8y7Na}6T0o4J0E2z2!bu4t1y4v2C2F2A0Y1Pbx0o4u10bH0*0,0.04.

Temps de calcul pour le tri fusion et le tri par sélection

Votre figure

Votre tracé sera ici

Solution

Le tri fusion est bien plus efficace

💻 A vous de jouer 5

Compléter le script suivant :

Évaluations restantes : 5/5

.128013f06S:d=4-yrE./opg2mcb1w937Cve[ l,8P5)ti]kné;Lua(_shq050g0D0M0V0N0G0Y0F0u0G0V0Y0Y0h010M0N0q010406050Y0U0t0t0V0l0k040e0p0G0U0^0p0Q050o0 1113150}0q04051l1e1o0o1l0}0g0N0C0-0/0;0?0Z0N0r0Z0G1C0Z0M0{050(0v0G0D1x0:0=011B1D1F1D0M1L1N1J0M0l1m0M0Z0-180Y0q0V0Q0?0s011P1z010b0*0D0Q0V0t0D1J1,1.1?1R1_1N1|1~0{0a0F0J0l0p0q0p0Y0N1b0Q0F0$1*0l0l0D0u2j1e210Q1m0o1(2w1#1%1$1K0g230?1F0Q1{2g1J1u1w0.1Q2G0N2I0Q0p2M1J0q2p1m2u2w2!0~1-2k2O1@2T0l120G0{0F0w2t2(0|2%222*1R2,2.2:0s2?1.2^2u2F012}0V2/040F0z312v0}342{0?37390F0i3d332(353j2:0K3n3f3p3h360p2-382:0d3u2_2)1y2|3z2~3a0A3E3g3H3i3J3B3a0I3N3w3P3y3A3k0y3V2`3X3r040w0c3$3G2P3Y3K0w2=1f2@3v3%3/3)0w303@323_3.2+3R390w3c3 2v1p2Y1e2M2z0g1%2E3x0u2U1 1m4d1n4b2$481m4j0$2Z3W3/0P0{0$0b3n3F350x2:4C3O3{0b0{1#0N0X2R0Y0D0l2s4r4D3x0`040W4H4w2+4L0V0v4!3`1@4X0f3n0F4V3(0v0{1F0Y0M4*421R4X0L4/4;3/0p0{0j020r0M0S504I2+4?044^4`4U5b4}0{4.4r414E2:0F5q4{350Y0g0{020!0U0p585x5z5B5y5A595m511@5u5p5q1L0F0D4_2l1O0M0k0q1O5f0D3-5t5v3a5q0F0T0V0F0b1c2r0N1c0F2p0Q0C0p0N5X5+5Y0F4M0R1O1-0l0F3z0g2p0-2d0N0;1.0M0n5!3x5L5%5q0m0G1N0F1a0*6a5X02030z0y0S380r3z2i0Z1~5S5~0l0N0F620F4P4R2j0n0F0B6s6u0S5Q0M6n2k4M5P2k0q0/0u0D6e5I5i0?6h5(0F5C5G6/5E5D5H2!066-5J1R4y045-0l5a4#2|0{2R1u6$714+1R0p4F042R784|3i5d0l1.0r5Z5h720?4X4Z7n790?0t0N0{3?2$6*014X0H7f3q5d265s4W0{7r7z7o364%4)7s7g7B0{0L0L5l6^6-6`7A0Q0{0D1N1~0Q5g2!4:7A53040h7E3x7$041L7I3X4X0E7{3{740Q767m7M7t7T040O3u7Z5(6{3i747?3X7:7=4r7.7N7^750N775m8b5r7A6}0x1B1N8g807d8z1@7:56588C1R7v0{3,8k8d017b0{1.0g8H8e7_4(7 4,0{7~7R3q8f8M7/548T018J3*8X5j888+8E576@2@8l867^7(0D7*7,2@8N4-8a8s7!8m7P8/7p8Z997O8B8#7J8;8(7N8i8+7^7`9f7|9b9o8A0N8=8*9i868-7y917A4X898r958c7#8%7-8N9k9w7S8n9u040j8+9y948b8N9m8W9r8Y048!859N9I9A7N9C9P8j9J9H048}8 3E0o4t0D2w2X9`4c1v4e2z2C2x4(1N2w4d0}0o0$0(0*0Y04.

Temps de calcul pour le tri fusion et le tri par insertion

Votre figure

Votre tracé sera ici

Solution

Le tri fusion est bien plus efficace

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