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

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

.128013nco0m/gS-.d;fw,7F2qy+à)e[é]h43vblr_:p96kT5 i=8a(sP1tu050l0y0!0V0S0H0X0R0c0H0V0X0X0T010!0S0L010406050X0#0f0f0V0I0u040i0d0H0#0_0d0b050g101214160~0L04051m1f1p0g1m0~0l0S0F0.0:0=0@0:0b0h0#0V0h0y0j0L0u0!0C1d0R0C0S0h0C0H1R0C0!0|050)0G0H0y1y0;0?011Q1S1U1S0!1!1$1Y0!0I1n1M0.190X0L0V0b0@0s011(1A010n0+0y0b0V0f0y1Y1}1 241*271$2a2c0|0a0R0Y0I0d0L0d0X0S1c0b0R0%1{0I0I0y0c2x1f2f0b1n0g1M2K1@1_1^1Z0l2h1B0S0b292u1Y1v1x0/1)2U2W0b0d2!1Y0L2D1n2I2K2;0 1~2y2$252*0I130H1Y0V1P2D0n0@030J0J0c2+0y1U2)0d0j0Z3f0|0R0Z1f0V2=2^0}2@2g2`1*2|2~30320y340136383a3c2X3f0j22040R0s3l3n1 3p2I2T013u0V2 1n310C333537390%3E2*3G0E3i0E3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0D3i0D3.1g3:3q2_1z3t0d2}3U3w3Y3y3!3C3%403)3g0Q3i0Q462;3;2^3R3^4g3|3B3$3b4m3e3g0N3i0N4s483=4b3@4d3v3W3x3z4A3 3d3G0q3i0q4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0U3i0U4!2J4$4a2%4)4e3_3{4i3}4k4C4;0j0M3i0M4_3P4v3?4~4P3`4R4j4B3(4E3f0e0|0Z0e5b4{4w4*505i535k4D3G0Z0Z5p3k0g3m3/3O1q2/1f2!2N0l1_2S5e4B2Z1w1n2.0y2:3o5I2J054B5Z2g0S0l0@372I5B3w5+5-545l5:0R2l0y5?5z565D2K5H4L4}0O0|0%0n5#5)4|250o3i69494w0n0|2D0c0C0y0I6l0y6f63250{040W6r5d4(0b0|0,0!6x4%4}6u0p690R6g5e6A042*0f0G2D6E6b1*6H6J6L6z666T3R6W473O6K6s3t0|686(5$6+0@6u0x0K690~6/6a0R5=015.2^3G3I5h6~4/55413H235{5}4U78735G6|5e6d3J0R7l6#5e0X0l0|020t0#0d0!0m7s7u7w7y7v0m6_6#750J5/3g3+4Q7G5~783+5`2b5|6 5@5A7J1Y7g6Y4}7p3i7l2p0I0A390b1v2x0R0K0R6C0R0y0X0!0R0#2W7;0S7^1%0w0R2.0S4d0S5`1O1@0S0A0y0p876Q2D7?7^7`2y0A0H0A2c0b7_6p6o0C0A2z1 0-0:7}7 6K6{6`2?3Q7G7I0j437L5,7T7N4n8I7a7R7c4:788J3.6;017#7k7l2S7@7_1$0R0I1 0h2z0#2z0A0G1b2z1%8y6k6m8s8c7?7_0n7;1%8+1D8@7;31272y2A8_2E8{6p8v0b8x7^7E6{6g8G714o5;8L765^9o7Q2c8S778O4p617h4(8Z7%822u0!7+7-842y7:8y0n1d2F9K8*290F0d0S1%0l8/0G0d198b9L8B4t7F9q7H9n0j4G8K9w9s9/8Q9v8M7d8O9:8W6y7!7q8!0R0P0I0#1%2v8e6R1%8%9f8x311U7 8d0(0R0r3U0Xa72V1d0k9j8E4v9m1 4W9p9=7V0j4X9u7S9raA4X9A7Z259D7%7B7A7t7CaN7D8C9+5?8H4?9;9`8T8O4?aDaz56aX3M9EaJ1*65040S6.2;6*9 2{6!6{a@6F250d0|0T0T6X8X6Na=5!8X6u6^aT9k8F9,8H58aYaF5658a%aZ9x5mbga+9E7%a-0@a/2D0!0#0I1ea{bt3S6B9ibca^6V0|0z7n6Z040lbL6G0|0Bb3bH0@a 04b1bTa}6,6O0d8f6qbbat5*be9.5qaybm9?b/blbi78b/9Aa,b40|0fbZ6UbVb0c06$0|6wbGb!3@a`a?bCbW0vc46M6-bP6t0|0xcg4(bW0g0gcn4}0f0S0|3Lb*b7aub-aw3g5Cb:b^8OcEb@7U5 60bq7m8Xbv0(bybAccb}048`6n6pcjbI6vc!ca046Cc%016%cUbUbDb$b(c+c-3oa|c1c:bOc8c`c@6)bC6Nb c}c504cmbB8X0d7j4dcsa_cW9ccY6mc?c6c+6Nc*d45ec 2Jc_4w0|6Paadj046Id8c/d2dd1*cedD0@cu5pdxdzc.c9c:b65Jb8clas5!0g5(5K5Y5M5V1f0!5Pd#2Q2L0V1#dY0g5N6`0%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 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 pour ré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

.128013nco0m/gS-d;fw,72qy+)e[é]h43vblr_:p9C6k5 ix=8a(sP1tu050k0v0Y0T0P0E0V0O0c0E0T0V0V0R010Y0P0I010406050V0Z0f0f0T0F0s040i0d0E0Z0@0d0b050g0~1012140|0I04051k1d1n0g1k0|0k0P0C0,0.0:0=0.0b0h0Z0T0h0v0j0I0s0Y0z1b0O0z0P0h0z0E1P0z0Y0`050%0D0E0v1w0/0;011O1Q1S1Q0Y1Y1!1W0Y0F1l1K0,170V0I0T0b0=0q011$1y010m0)0v0b0T0f0v1W1{1}221(251!282a0`0a0O0W0F0d0I0d0V0P1a0b0O0#1_0F0F0v0c2v1d2d0b1l0g1K2I1=1@1?1X0k2f1z0P0b272s1W1t1v0-1%2S2U0b0d2Y1W0I2B1l2G2I2/0}1|2w2!232(0F110E1W0T1N2B0m0=030G0G0c2)0v1S2%0d0j0q0j0X0`0O0X1d0T2:2?0{2=2e2^1(2`2|2~300v32013436383a2V3d3d3h0q3k3m1}3o2G2R013t0T2}1l2 0z313335370#3D2(3F0B3h0B3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0A3h0A3+1e3-3p2@1x3s0d2{3R3v3V3x3X3B3!3}3$3e0N3h0N432/3.2?3O3=4d3_3A3Z394j3c3e0L3h0L4p453/483;4a3u3T3w3y4x3|3b3F0p3h0p4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0S3h0S4X2H4Z472#4$4b3?3^4f3`4h4z4.0j0J3h0J4?3M4s3:4{4M3@4O4g4y3#4B3f0e0`0X0e584^4t4%4}5f505h4A3F0X3g045z5p465r4|4v4 4Q4-3~3f205B3I0g3l3,4Y5E5b4u4)4w4,525L0X3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530X4D5B4F692;1q2-1d2Y2L0k1@2Q5b4y2X1u1l2,0v2.3n5|1l4y6E2e0P0k0=352G5y3v6L6N635x3e3g0O2j0v6T6h5#1W5{6c1(0M0`0#0m6G5-4`0n3h6:6*3;0m0`110Q0P0f0 0G2B0c0Z0F2t6/6a2H6;230_040U6^5a5.0`1Y7g4!4`7d0o6G0O7b3s6-0v0D197l4_7c0`7p79047r6_3P0`251c7D7s0=7d0u0H6G0|7L3N6S016O2?3F5N5e7V5Z643e206Y296!7W6U537!6)7h6=3h0O7_7y3O0V0k0`020r0Z0d0Y0l80828486830l7R7{7$0G6P3e5%7#6M7.6$4k0j3(7+2a6#5?8n8i7=7m237}7^7_2o0x370b1t2v0+0H0O1Y0O0v0V0Y0O0Z2U0O1S8O0v0o2x7v198M8O8T02030B0J0l2T1t0c1#0k0Z2x0x7w8P2y0.0O730z0v0F0c8~8X8c7T4s8e8g0j5^8j8s5K8n408q7-7%6V996(5R7G8z7E7_8M8P7J8%8)8+8-0P8/8Y8T2 9t8`2 8}8 910v942;7U8k7X1}3F669b8l8t5j4m9g9c5!8n9R8w7z1(9o9q2n2s0Y8E8G0P1M8J8{0m1b2D9:2w2B0b0C0d0P1#1!0O6}6 0 9A8{8U0Y1#7k7D7S9L969N8f7Y4C6Rah8m5j4D9X9T9dao9l6J9%0=9)9q8988818aaA8bad8dah984U4N8ean4T216Z9Y7(0jaK3J9*7M016,040P782/7F7?2_7u8^7qaX0d0`0R0Ra-7G0b7I2Ta?a)1(7d7Q7Da(8x1(0c5A030O0K0/9A0D0/1#8R0O0V0v0Z0E0O0x0E0x2a0b0Y9K6F9M6T984:aLam9U3F4:aq9i53bwaV9*9qaXaZ2B0Y757Ka%aXa^04acafb27N0`0w7{5Va+7x95bV017d0ybr3L5E97aj54alaR9j55bC7/5L552I3laW7GaZ39bgbZ4#a~b,7abt7.985nb=ar9Z5jccb_aN6W5lb}9pbHb1aw7H040f0)a00Za{b(a/04a=b0aX7d7fb%cqbR0#a,cC7Gcz0tcxcHa_bObsa|bW040ucP3Ocz0g0gcY5bct0`5P4qaHbub:5zcdbD5#6XaQceaSc:cmco7`a@0`0Qc%4#czcBbPc cs0T6~700f722C7577c47n0`cFbUcQbS0T0Ddh7A047Cd6cUcrcJb$dl3O7od25 6|cubhdqa}0`cXaGcG0Ob/9P6W7!2 aMbzdQaP7,b?6i7;b~c}bQ0`0sdC23d4d*7td8da7173dfa#dHcVdkcTb(bRbTd{cqdBcLdvbRct1SdGe2cy0`cOe8cqc)5Bd^b)7Bd-3;cReg7Oc7avdNaIc/8idSbyas5y8pc^c=8n5$auc}cp3OaZd@ec4td0ej01cz020E84d53neFb!04d)dM5bc6dLdzdO0b5y9aeudY5@dW8rc_9j0X9a5*eEb dvbK0$bNeMbReXc,dMe%65c;b`eB9Wezf6cg9#d#cobJ0`c29JeYc50`a f1e$erdP3f6k9SeAcgapf9cjfreDe^c~e`0`bLe}eJeVd1e#6F0g6I1o6q0g6s1d0Y6ufS2O2Jdo1!2I6s7S0#0%0)0V04.

À vous de jouer 3 :

Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013nco0m/gS-d;fw,72qy+)e[é]h43vblr_:p96k5 ix=8a(sP1tNu050k0v0X0S0O0E0U0N0c0E0S0U0U0Q010X0O0I010406050U0Z0f0f0S0F0s040i0d0E0Z0@0d0b050g0~1012140|0I04051k1d1n0g1k0|0k0O0C0,0.0:0=0.0b0h0Z0S0h0v0j0I0s0X0z1b0N0z0O0h0z0E1P0z0X0`050%0D0E0v1w0/0;011O1Q1S1Q0X1Y1!1W0X0F1l1K0,170U0I0S0b0=0q011$1y010m0)0v0b0S0f0v1W1{1}221(251!282a0`0a0N0V0F0d0I0d0U0O1a0b0N0#1_0F0F0v0c2v1d2d0b1l0g1K2I1=1@1?1X0k2f1z0O0b272s1W1t1v0-1%2S2U0b0d2Y1W0I2B1l2G2I2/0}1|2w2!232(0F110E1W0S1N2B0m0=030G0G0c2)0v1S2%0d0j0B0j0W0`0N0W1d0S2:2?0{2=2e2^1(2`2|2~300v32013436383a2V3d0j20040N0q3k3m1}3o2G2R013t0S2}1l2 0z313335370#3D2(3F0B3h0B3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0A3h0A3-1e3/3p2@1x3s0d2{3T3v3X3x3Z3B3$3 3(3e0M3h0M452/3:2?3Q3@4f3{3A3#394l3c3e0K3h0K4r473;4a3?4c3u3V3w3y4z3~3b3F0p3h0p4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0R3h0R4Z2H4#492#4(4d3^3`4h3|4j4B4:0j0J3h0J4^3O4u3=4}4O3_4Q4i4A3%4D3f0e0`0W0e5a4`4v4)4 5h525j4C3F0W3g045B5r485t4~4x514S4/403f3H0W3K0g3l3.4!5G5d4w4+4y4.545N0W3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550W4F5D4H6b4s5/616g5Z5K5#663e0W4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3f575D596Q5 6S6f6U6I6v6K550q5n046:5a1o2-1d2Y2L0k1@2Q5d4A2X1u1l2,0v2.3n5~1l4A772e0O0k0=352G5A3v7e7g6.5%212j0v7m6j7o2I5T6e1(0L0`0#0m796r230n3h7D7x3?0m0`110P0O0f0 0G2B0c0Z0F2t0m0G0C5R2;7J010_040T7I6)3s0`1Y7,4$4|7)0o790N7E7.040#0D197_7{0=0d0`0Q817%0L0c0`0Y1b0v7;4{237@877-3?0`251c6c2H7`7%8404868p3I8201898b8d8f3Q7)0u0H790|8w5G7l017h2?3F3H5g8M6w6L3G7p297r8N7n6Y8R5}7%7G3I0N8,8D5d0U0k0`020r0Z0d0X0l8?8^8`8|8_0l8I8D8T0G7i3e5)8S7f8!7t6Y3*0N7q7s6X5l988(8k018:3h8,2n0F0x370b1t2v0+0H0N1Y0N0v0U0X0N0Z2U0N1S9E0v0o2x0v7 9F9D9F0E02030B0J0l2T1t0c1#0k0Z2x0x9Q9O9J2 7T0z0v0F0c9;9N928K3P94960j5`999h5M6Y429f8Ya25$a41W9l7=239o8+8,0$0N8n9J9V9X9Z9v0O9$9-0.aj2Tas9/2C9;9?9;9`7$4u9}8P4n7k9a8U554oa62aa86x0j683-7%af9q2n2s0X9u9w0O1M9zat0m1b2Da$2w2B0b0C0d0O1#1!0N7N7P0 aw9J0O9L9A0S0DaC789|aJ95aG0j6ma19b9i3F4FaN8ZaK5Nbbac8g1(aV9q8 8~8@90br918w8JaD7db79~6Abcbj6Y4WbhaP8VbD5,aW8y7z040O7C8w8r9m0b7A9P80bT8y8t0Q8v2/bUad7y8a048c2U8.4%7)8Hbx93bBb96NbE8#5l4=bIbda3b ab3laWbN7%bW7}bY0X8jb+8385cebn0=0f0O0`5qb^9{aEb`1}3F6!b}9c5l57c1bFcyc5agb*cj8z0`bRci4v8m2TcK5db$b(3ncF3Q8Ab.8Ccqcf7(0`b@6qcY2waFct6y6;cwbec,8XaOc2a95l5pcDc79q8yca8ncO4%b$d0610D0`2ib;7?0`7+c(cL047:dc5d8Fd8238t0jdj1(cl5ob43N8Lcs0b5A5Cc.c3dwc;bib~dA7vcEbOcIbSb)c}bX9Qd3dk85cR3NcT5XcM8odK7%b?dr2Hdt7m9~5QaIbJ6k20cAdD6y8%c6c{dT4%bP2B0X7VdWcSdLdeb2dn0=7)0we23RdMbZbzcG7)0yd!7cc)du5A982 94cxeidBd+5%9kd=8-880`390U8edgb=c#eed$8!d(a0ekb7em6ya59gc?aQ0Wa0bMd?d cl1S0v0ZdO1(d2b!dYdae6ca7~e9d~8s0`0teY8l04c ezd9040ue:018t0g0ge{dp6=eCb6d%b90WaSeHep6Yf7eoeN8VfcdFd?d@610`0Pe{e!dXbV7M0S7O7Q0f7S2C7V7X7Z7#b59m7)dbeadddffGdh0`7^e#fqcbdNe@8hfLe{caeUa?eXfR1(dicpfGc*dv6ybbf9fe6kbgeMcB5Ablesc7d 0sfnchfNcZfVfsa{fv7TfybRfAe6fEe(7/e1fZe3fTf}cGfV0)fXf{04e/gf3Qf13jgcc!04fMfpf~dVg70`e`f$fCbAf5c+3fbDf,f;6ybHf:d/gGc`eSeubQdJe,fOfmgncP8=0E8`dR8qf_gy04c$47dcf(5Ab|gIgN0Wc0gMeJ3fb|eRfiet9md_0$d|fU0`f`gBdsf4eEf6cvg;g_0Wczg^c/6ZgPc{dH04eweyfJeAg*f3crgEf)3Gc-hchh6:fdgJhwhjg}hld`h2gX5:fleC0g7b6^766`731d0X6}hT2O2Jb21!2I6{8J0#0%0)0U04.

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 interdit d'utiliser ** ou pow.

1. Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013nco0m/gS-d;fw,72qy)*eéh43vblr_:p96k5 ix=8a(sP1tu050k0v0V0Q0M0C0S0L0c0C0Q0S0S0O010V0M0G010406050S0W0f0f0Q0D0s040i0d0C0W0;0d0b050g0{0}0 110_0G04051h1a1k0g1h0_0k0M0A0)0+0-0/0+0b0h0W0Q0h0v0j0G0s0V0x180L0x0M0h0x0C1M0x0V0@050!0B0C0v1t0,0.011L1N1P1N0V1V1X1T0V0D1i1H0)140S0G0Q0b0/0q011Z1v010m0$0v0b0Q0f0v1T1^1`1 1#221X25270@0a0L0T0D0d0G0d0S0M170b0L0Y1?0D0D0v0c2s1a2a0b1i0g1H2F1/1;1:1U0k2c1w0M0b242p1T1q1s0*1!2P2R0b0d2V1T0G2y1i2D2F2,0`1_2t2X202#0D0~0C1T0Q1K2y0m0/030E0E0c2$0v1P2!0d0j0y0j0U0@0U1a0Q2-2:0^2/2b2=1#2@2_2{2}0v2 01313335372S3a0j1}040q3g3i1`3k2D2O013p0Q2`1i2|0x2~3032340Y3z2#3B0z0@0z3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0y0@0y3(1b3*3l2;1u3o0d2^3O3r3S3t3U3x3X3`3Z3b0K0@0K402,3+2:3L3/4a3?3w3W364g393b0I0@0I4m423,453.473q3Q3s3u4u3_383B0p0@0p4D3I4o3m4G3M4I494K4b4M3^4f4P3b0P0@0P4U2E4W442Y4Z483:3=4c3@4e4w4+0j0H0@0H4:2F2)0v2F2V2I0k1;2N3-014v2U1r1i572+3j3)3I054v5m2b0M0k0/322D3B3d4K5u5w4~3Y4y3c1~2g0v5D4v5F5z1T0g3h433L0J0@0Y0m5o2E5S5f0n0@0L5Y5s4?2?0m0@0v0N2o0E2y0c5)5!4Y0?040R5^4F4@0b0@0N5~4p5f5{0o5)5(5 2?0@19415p6b1#5{0t0F5)0_6f5Z3K5C015x2:3B3D3;0L6r4)4 3{3C5I265K6s5E4x6v5P5R6h0/5$040L6R5(6o5*3L0S0k0@020r0W0d0V0l6!6$6(6*6%0l6m645t5v6H5y3b3#5B6?6A5N6_6E275L4O6C6`3(6N016X5%6S2l0w340b1q2s0L0F0L0N0L0Z0L2t0S180V2u0v0(240;0v0D0S6:6U5S6z0E6^3a3r7E5M6J3|706G6}7L7H2F6M654Y796Q7b2p0V7e7g0M1J7j0+0L0m182A7%2t2y0b0A0d0M1Y0N0u0u6e4n6;2t7E7G4j6{724*6C4j7o6F856B4h0j83767U4@7W6S0L6-6,6#6.8m6/6U6n2.6q6|7F6u4z7I8w7K504A89716H8C6C4A7S7X6R5_4@5U040M5X6U6a8h6c047}3j8V4X4@0d0@0O0O698O200f0M0@0e7 3L5{6l8s8?818y0j4R848H738d4R8F7O6I508 3G8k8k8-1#8Q2y0V0W0D8Z3I8#5+1#8/3e7B8u4p8|1`3B4-907P504-958b6~0j9x9a6S9d0/8Q360S0v8,778^9r5n8v5D7G529y976C529C91868d9X9H9b9m5T0@9g9i9k2E9-5f6104638U9J018(040u9P8W3o5.5:0d5=2z8?660@5}7C779_9{9s8$2067a2aja48Yam9n0/9 0jaq3L9p043faea30/6j9S5p0g5r1l2*1a5a1a0V5caM2L2G0Q1W58aK5j6n0Y0!0$0S04.

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.

4. Exponentiation rapide⚓︎

On peut définir $x^{n}$ d'une autre façon :

$x^0$ = 1
Si $n$ est pair : $x^{n}$ = $(x^{\frac{n}{2}})^{2}$
Si $n$ est impair : $x^{n}$ = $x \times (x^{\frac{n-1}{2}})^{2}$

Remarque :
Que $n$ soit pair ou impair, on divise le problème par 2 puis on recombine les résultats avec le carré.

🌵 💡 Autre remarque :

Si $n$ est pair on a vu que $x^{n}$ = $(x^{\frac{n}{2}})^{2}$ .
Il ne faut évidemment pas faire deux appels récursifs différent pour calculer $x^{\frac{n}{2}}$, puis encore $x^{\frac{n}{2}}$, pour enfin réaliser le calcul de $x^{\frac{n}{2}} \times x^{\frac{n}{2}}$.
On ne fait cet appel qu'une fois, puis on utilise une variable a à laquelle on aura affecté le résultat de $x^{\frac{n}{2}}$
Si n est impair, il faut procéder de façon analogue.

À vous de jouer 5

Vous ne devez pas utiliser ** pour la puissance. Le but est de programmer vous-même cette fonction. Cela peut à la rigueur être utilisé dans un assert.

Évaluations restantes : 5/5

.128013nco0m/gS-d;fw,72qy)*eéh43vblr_:p96k5 %ix=8a(sP1tu050k0v0W0R0N0C0T0L0c0C0R0T0T0P010W0N0G010406050T0X0f0f0R0D0s040i0d0C0X0=0d0b050g0|0~10120`0G04051i1b1l0g1i0`0k0N0A0*0,0.0:0,0b0h0X0R0h0v0j0G0s0W0x190L0x0N0h0x0C1N0x0W0^050#0B0C0v1u0-0/011M1O1Q1O0W1W1Y1U0W0D1j1I0*150T0G0R0b0:0q011!1w010m0%0v0b0R0f0v1U1_1{201$231Y26280^0a0L0U0D0d0G0d0T0N180b0L0Z1@0D0D0v0c2t1b2b0b1j0g1I2G1:1=1;1V0k2d1x0N0b252q1U1r1t0+1#2Q2S0b0d2W1U0G2z1j2E2G2-0{1`2u2Y212$0D0 0C1U0R1L2z0m0:030E0E0c2%0v1Q2#0d0j0K0j0V0^0L0V1b0R2.2;0_2:2c2?1$2^2`2|2~0v3001323436382T3b0j1~040L0q3i3k1{3m2E2P013r0R2{1j2}0x2 3133350Z3B2$3D0z3f0z3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0y3f0y3+1c3-3n2=1v3q0d2_3R3t3V3v3X3z3!3}3$3c0K3f0K432-3.2;3O3=4d3_3y3Z374j3a3c0I3f0I4p453/483;4a3s3T3u3w4x3|393D0p3f0p4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0Q3f0Q4X2F4Z472Z4$4b3?3^4f3`4h4z4.0j0H3f0H4?3M4s3:4{4M3@4O4g4y3#4B3d0e0^0V0e584^4t4%4}5f505h4A3D0V3e045z5p465r4|4v4 4Q4-3~3d3F0V3I0g3j3,4Y5E5b4u4)4w4,525L0V3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{443L1m2+1b2W2J0k1=2O5b4y2V1s1j2*0v2,3l5|1j4y6r2c0N0k0:332E5y3t6y6A635x3c3e0L2h0v6G5w535A3+5~210J0^0Z0m6t5-4`0n3f6Z6T3q0m0^0v0O2p0E0k0D6(5a4#0@040S6?4!5 0^0O6|4_216_0o6t0L6!2@0^1a6a2F781$6_0t0F6t0`7c6w2u6F016B2;3D3F5e7o5Z643c1~6L276N7p6H537t5{6)0:6$3G0L7M713O0T0k0^020r0X0d0W0l7T7V7X7Z7W0l7j7O7v0E6C3c5%7u6z7D6P5L3(7A286O5?4k0j7/7H6@4`7Q3f7M2l0D0w350b1r2t0)0F0L0O0L0!6L0L0T190W2v0v0)250=0v0D0T7)7l5E7+7-0j5^7:7{5K7}407_7C7w6I8B1U806}21837L7M0U2q0W898b0N1K8e0,0L0m192B8Z2u2z0b0A0d0N1Z0O0u0u7b4q7*7;7q1{3D668D7=7|5j4m8I8E5!7}908O721$8R850L7$7#7U7%9h7(7l7k2/3N8z7r4C6E8|7E5L4D96928F5j4D2G3j9f7e0:6V040N6Y7l777I3P7a769H010d0^0P0P9S9P0f0N0^5o8x9P6_7i9n8{6G8A4U4N7+7?7}4U9z8K539;3J9f9G9P9J2z0W0X0D8_3l9O81219#5m8w9p4s9r8~4/9u977x0j4:9`9w7}4:9E3m9)ag9v8A559=9v9@5j55apaC3Daz9~859T9J4z9M2-a98P3q9R9N9T9V040M9Zaa1$ac045PaPaV9W9YaU9!9$049(afaR0:9+ae6s9qax9s5kak9A985j5n1 6Mal8Lb3at9 aK9P0b0^0RaZa?9U9Wbg9c3;6,6.0d6:6=avbh6_6{bsbl9Q0470bw3O74bk4taTa)9PaW0g0gbE5ba$a(a`a!a@0^0ta_6ba{9/a}5za 9{5#6Kb5b0amb!b9baaQbxa20!a5a73Lb/bF04bfa-bRbi040ubM5.bebV7dbX7D8A5Ob#aqb27zb)b$7}caat9obQ6xa|ai3d7/2}9?935y7^cfcccu8N9Fbbb~aM1QaOa89Tbd04b@2Fb_5baWaYb}bhbOc24`aW9XcTaba/3hbB5ba^9-bBah0b5y8CcraBct6J8HcwaGc;cz8S9 cHc4cQbxcVcXaS046-6/6;7Oc$0^bva=bxcIbAdbbC0^75c~dg6`d7c3cJdmcU0^0jdpcYadc#6^bTd10:bJbLdjbNa/bPbWb~7gc57m0Lc*65cbc@3d95c?c:dRc_b.cM4#b;a4a6dzbydecGbI0^c1dDdnb|bHb~aWd-d;bhcId:458x0g6v6c6q6e6n1b0W6he42M2H0R1Xe10g6f7k0Z0#0%0T04.

Temps de calcul avec l'exponentiation récursive rapide

Votre figure

Votre tracé sera ici

😀 Enfin on voit de façon évidente et éclatante l'intérêt de la méthode "diviser pour régner!"
Comparons les temps mis pour calculer $2^{800}$

😀 Le temps d'exécution est environ multiplié par 60 par la méthode récursive, par rapport à la méthode diviser pour régner, pour le calcul de $2^{800}$

Complexité de l'exponentiation rapide

On peut montrer que la complexité (en regardant le nombre de multiplication) de cet algorithme est en $O(\text{log}_2(N))$ (se prononce "grand O" de $\text{log}_2(N)$) .

Nous allons voir cela, mais essayons d'approcher la réponse.

Combien de multplications ferons nous pour évaluer expo_dr(2,128) ?

Solution

réponse : 7

$2^{128} = (2^{64})^2 = ((2^{32})^2)^2 = (((2^{16})^2)^2)^2 = (((2^{8})^2)^2)^2)^2 = ((((2^{4})^2)^2)^2)^2)^2 = (((2^{2})^2)^2)^2)^2)^2$

et finalement :
$2^{128} = ((((((2^{1})^2)^2)^2)^2)^2)^2)^2$

Chaque élévation au carré coûte une multiplication. On élève 7 fois au carré, et donc on élève ici à la puissance $2^7$

Ceci parce qu'on effectue des divisions successives par 2, d'une part, et que $2^7=128$

Or, $2^7=128$ est equivalent à $\text{log}_2(128)=7$. Il faudra donc faire 7 multiplications pour calculer $x^{128}$ .

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 :

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

.128013nco0m/gS-.d;fw,72qy+à)e[é]h43vblr_:Ep96k5 ix=8a(sP1tu050l0x0!0V0R0G0X0Q0c0G0V0X0X0T010!0R0L010406050X0#0f0f0V0H0t040i0d0G0#0_0d0b050g101214160~0L04051m1f1p0g1m0~0l0R0E0.0:0=0@0:0b0h0#0V0h0x0j0L0t0!0B1d0Q0B0R0h0B0G1R0B0!0|050)0F0G0x1y0;0?011Q1S1U1S0!1!1$1Y0!0H1n1M0.190X0L0V0b0@0r011(1A010n0+0x0b0V0f0x1Y1}1 241*271$2a2c0|0a0Q0Y0H0d0L0d0X0R1c0b0Q0%1{0H0H0x0c2x1f2f0b1n0g1M2K1@1_1^1Z0l2h1B0R0b292u1Y1v1x0/1)2U2W0b0d2!1Y0L2D1n2I2K2;0 1~2y2$252*0H130G1Y0V1P2D0n0@030I0I0c2+0x1U2)0d0j0q0j0Z0|0Q0Z1f0V2=2^0}2@2g2`1*2|2~30320x340136383a3c2X3f0j22040Q0r3m3o1 3q2I2T013v0V2 1n310B333537390%3F2*3H0D3j0D3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0C3j0C3/1g3;3r2_1z3u0d2}3V3x3Z3z3#3D3(413*3g0P3j0P472;3=2^3S3_4h3}3C3%3b4n3e3g0N3j0N4t493?4c3^4e3w3X3y3A4B403d3H0q3j0q4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0U3j0U4#2J4%4b2%4*4f3`3|4j3~4l4D4=0j0M3j0M4`3Q4w3@4 4Q3{4S4k4C3)4F3h0e0|0Z0e5c4|4x4+515j545l4E3H0Z3i045D5t4a5v504z534U4;423h3J0Z3M0g3n3:4$5I5f4y4-4A4:565P0Z3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570Z4H5F4J6d4u5;636i5#5M5%683g0Z4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570r5p046=5H6g4d6-655_5O6!0r5E716_6+6{5h6}5z6Z5n0r3J7c744(6V775y5N5(705+0r5-5V6e6*7g6,7i5^796 7b5|0r5~7q6s6`4O6|7j6y6N3I6a0r6c7D3p1q2/1f2!2N0l1_2S5f4C2Z1w1n2.0x2:7Q7r1n4C7*2g0R0l0@372I5C3x7;7?6:5)232l0x7|6l7~2K5V7F010O0|0%0n607/4}250o3j8d6t2{0n0|0n0#2v1d8j870{040W8s753^0|0G3l7,8k1*8u0p8d0Q8E8z040G5T2?8t0|0w0J8d0~8D3R7{017@2^3H3J5i8Y7J6;7 2b818Z7}701Y5 878h3K0Q8`8x7t1*0X0l0|020s0#0d0!0m92949698950m8U8|2y8)0I7^3g5+8(7=8/836!3,0Q80827a3+8=868y018 3j8`2p0H0z390b1v2x0Q0J0Q8B0Q0(9N0r0Q0X1d0!2z0x0#0S9N0R0X0!0x0-1@0R0z9)9e8W4w9h9j0j5|9m9u7y3H449s8-9`7l5n9^8?9z9B8_8`0Y2u0!9H9J0R1O9M0:0Q0n1d2Fae2y2D0b0E0d0R1%0#2W9#9%1%9+9-1{0b9%2w0#aA2Aah8o8q2y9/8P9;9n8!1 3H6a9_9o9v4p8,2ca06z0jaTa48}0@a69D9X9N0Z9P9W8NaM7Q8XaP9i8#4G7`a_9p5n4H9~aZaV9{a|858e3Sa+9D0K0S0x0f0L1$9La?3P5I9=a{3fa}a!7K4Yb28.8*5P6C3/87ba8`aJam0W0y0r0p0Q0DbH0PbH0U0A0p0y0ZbH0C0A0w0Qaoaqas0QbQbHbGbIbKbM0Abj2Jbla_9?6PaUbv6!4@btbq57b;a(8f8~90a70Q9b9a939cc39d7,8VaN7:b/bn6$b=8:5n59b_b4a13Hcf5.caa@aO7|9?5rbpcla#cvckb?5ncvb7a,8K3T0|0b8C2;8J870d0|0T8IcG0b0F8A299f3S8u8w9:a)cH8McKcrc$8u0wb,b8bmaR6A5Ecga 5C3icAchc_9xc1cScI8O3pcM9zcO04cQ7,d4c$cTcV1ec#b~0@cZcX5Z8Ad2bk8Q04c-c9cXc:0b5C8%319hc^6A22c{dz5Qc~cF870b8A9%cRcNcPdL9z8u0yb+d9cG0c5E030Q2V2w0R3V9$0V9KaH31bC1OaHa/9Q8N8JdrdfdYcdc;3h9ldxa~aWd{aYbuc|6A9l5.dG9zdI040Rc)3Pdadg01d6d8cLcG0f0R0|5sdT87dV0|dX2V1v0c1%930R9T0x0H9W0v0Q1~0H390#0H0R0Ha.c.b.ctbn0Z9^d}b`5{e1eV6!eSdF9Dd0eadm2Jee3SehdOc$elene.efer04et9I0Rew0QeyeAeC0QeEeGeIeKeMa=d?cb9gd_du6AaTeUcx7K0Z4qdCd fie#8{8789040o1Q1$e=4x0|ebfv5fd6020G96fz5=cIece*cG0d8^1 0lfF63fxe)3KfK91fDc8ejdHd1fP258u8Tf8c*faeQd`6ncwcB5Cb19tfg6m6o3Na,e7c$fq0R8cepe88AfIb85fdQdjfGeag4cG8udSfYd5fVfEg1dbdlg84~g7d@dke(gmf$0|0Af(6sd@dt5Cbxfff:6Absf?gD3hbxe6f{gLe%0,0!gs1*d60kgQ8L0V0L0L29fOgp4)dig#fQc(gU01gof9fwgag+gddqgxg.gz6Of/e33hb^gGg|0Zb|3ngLgMfZg:gjefe-h8g/fyhbfA0|0uf#1*e:5FeOa^f,fc6#g{dD0Zcjg hscoh3h4cGfq3b0X0xhidh0|gw49gyfb8$6?c@d 6=eXf@5PhQcEh4f|efe9gOg+gSg+e9gWgY9Ig;0|c!g.gqf7h/g$0|0yh%fRh,04bUhmcs8/9?71hrhPc`hvi4fnhWe+gq0RfSia4)hagfgkgrheifhghF01hkg4cqdnh aQhp7ci3b53IdBi6iyiwhVfo9zf~g0ihhYfxg4ie4~eheid3e%cJh{hI5XhKho8$d|d^eY7b9riBcm3g7oi8hX3Sfq2D0!eJdeiJg/h!ikiOimi{2{glg(gt04h^j13uh`j5hG040JgehJg^hLi+eTi#hS709}i)a#7Bi8hAfxiIiRh6iciniPine90bfSgchHh~cciYi+fejigH7NhRjKa%hyh5iG0|i;i?jydJgPi~gRi}i^h:gbdoj4h=g)hdj*j2jbeO0g7.7R7)7T7$1f0!7Wj`2Q2L0V1#j@0g7U8V0%0)0+0X04.

😥 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

.128013nco0m/gS-.d;fw,72qy+à)e[é]h43vblr_:Ep96k5 ix=8a(sP1tu050l0x0!0V0R0G0X0Q0c0G0V0X0X0T010!0R0L010406050X0#0f0f0V0H0t040i0d0G0#0_0d0b050g101214160~0L04051m1f1p0g1m0~0l0R0E0.0:0=0@0:0b0h0#0V0h0x0j0L0t0!0B1d0Q0B0R0h0B0G1R0B0!0|050)0F0G0x1y0;0?011Q1S1U1S0!1!1$1Y0!0H1n1M0.190X0L0V0b0@0r011(1A010n0+0x0b0V0f0x1Y1}1 241*271$2a2c0|0a0Q0Y0H0d0L0d0X0R1c0b0Q0%1{0H0H0x0c2x1f2f0b1n0g1M2K1@1_1^1Z0l2h1B0R0b292u1Y1v1x0/1)2U2W0b0d2!1Y0L2D1n2I2K2;0 1~2y2$252*0H130G1Y0V1P2D0n0@030I0I0c2+0x1U2)0d0j0U0j0Z0|0Q0Z1f0V2=2^0}2@2g2`1*2|2~30320x340136383a3c2X3f0j22040Q0r3m3o1 3q2I2T013v0V2 1n310B333537390%3F2*3H0D3j0D3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0C3j0C3/1g3;3r2_1z3u0d2}3V3x3Z3z3#3D3(413*3g0P3j0P472;3=2^3S3_4h3}3C3%3b4n3e3g0N3j0N4t493?4c3^4e3w3X3y3A4B403d3H0q3j0q4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0U3j0U4#2J4%4b2%4*4f3`3|4j3~4l4D4=0j0M3j0M4`3Q4w3@4 4Q3{4S4k4C3)4F3h0e0|0Z0e5c4|4x4+515j545l4E3H0Z3i045D5t4a5v504z534U4;423h3J0Z3M0g3n3:4$5I5f4y4-4A4:565P0Z3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570Z4H5F4J6d4u5;636i5#5M5%683g0Z4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570r5p046=5H6g4d6-655_5O6!0r5E716_6+6{5h6}5z6Z5n0r3J7c744(6V775y5N5(705+0r5-5V6e6*7g6,7i5^796 7b5|0r5~7q6s6`4O6|7j6y6N3I6a0r6c7D6G7t764,6.6Y7y3H0r6o7Y7f4}7u7T787k6z3I6C0r6E7P6T7R7G7v6L6l5P0r6P7{5c1q2/1f2!2N0l1_2S5f4C2Z1w1n2.0x2:3p601n4C8e2g0R0l0@372I5C3x8l8n6:5)232l0x8t7_6!5E3/7F010O0|0%0n8g6t250o3j8K8E0b0n0|0n0#2v1d5T2?8E0{040W8P753^0|0G3l7r8j7$1*8#0p8(7=3T8+8Y8f8!0|0w0J8g0~8.5I8s018o2^7X8r8m968u708w2b8y9c8A7b1Y5 8E8N3K0Q9q8@8:0@0X0l0|020s0#0d0!0m9y9A9C9E9B0m919s0Q95971 3+9a8z7a9Q0Q8x9S7W3g5+8D8)019v3j9q2p0H0z390b1v2x0Q0J0Q8,0Q0(9@0r0Q0X1d0!2z0x0#0S9@0R0X0!0x0-1@0R0za99K933R9N0I8p439R9i9Tal9V9g9X7l5n5|9#8^9(9p9q0Y2u0!9.9:0R1O9?0:0Q0n1d2FaG2y2D0b0E0d0R1%0#2Wa5a71%abad1{0ba72w0#a$2AaJ8U8W2yaf8Z4waiak0j6a5iai9j3H4qaq2cas7+a{9m9$ay9*a19@0Z9_a00G8{5Xaga@9b9O0b3H6oa|bk9d5n4Hb19h7J57bob6ax9waz0Q0K0S0x0f0L1$9=a=8|bj8ta_6Cbpb37K4YbubS57bQbz9t9%bBb9a/aO0W0y0r0p0Q0Db-0Pb-0U0Ab-0y0Zb-0C0A0w0QaQaSaU0Qb_b-b,b.b:b=0AbL3P94bqa_6PbRan9Y3f9fb2ciat3HcgbZ3Sb89*9H9G9z9Icv9J8.92a?8kce983g6$chbw5P59bVcn7+cI5.b98L3u0|0b8-2;0QcT0@0d0|0T8gcZ8Q0F8+299L5f8#8%bi8^0b8+cXbM8^8#0wcb2JcdbOcG5oamcK8B5pcNd65n5r9l3ncS8QcVbg2Jc*9$c$04c(8.dkc@c,042kc/4)c;dv638`dy25c}c 8/9McF9P6A8C31a}ao3h3id9br5C8CcR9*c!8_dta7c)dWdmdocYdW8#0ycadpdW0c5E039M0b2w0R3Va60V9;a-31b(1Oa-bc9`bfcZcB9La^d35Sd5dR6A22dQa~edddbCdWc^040Rc`3Pdqb!d$d!8E0f0R0|5sd-8Ed/0|d;2V1v0c1%9z0R9}0x0Ha00v0Q1~0H390#0H0R0HbbdEd19ca_5*ebeg3h3,efdNe$2KdedVdgemdi3Kd#c%et9$evexe`8^eB04eD9/0ReG0QeIeKeM0QeOeQeSeUeWbfeYahdHbm6AavdLbqe(0Z44e+cjfqeidf9$8G040o1Q1$e~b!elenfD3Sdm020G9CfH5ZcVeodjd#9o1 0lfN5=0|0Re?eqfI9xfLcAd(e;0bf!d)0|90e6c?2ye8dI3ha{fnbW5)b09WcO7K0Zb5e/b99r8Efy0R8Jez9$el8,dB8;0|0ygf8*emfQdFc:0|d,f*dlf%fMgbc@dAf=3Sd*gjdXfZgB8#0Af:6sgyf@fk3hbof{g06mbtf da5Cbyg4g5fwgwdY0!gBdm0kgBel0V0L0L29fVgygo8$g)c_gEghg?glg^04b}fhbNe!e9bQgOgT6AbUgSec3hbYgWgXg6gcfYgmf#5fesgvfEhgfW4~dm0uho25e|5Fg cEd2f^0Zcgh4h9hAclbvhDcqhce:fx0|3b0X0xhsgg04gH49gJfj5CcIhCfpcMh8h!fvhdgYhmg!g$0|g(g:fX04g+g-9/g|c=cDh+fgh:4~gAh~2{fYe?f.g}c~f;h{dGhygL6=e%dNidfsco3gide.bCh)eki3hQc#e_hl4xipithj0|hriw4)hugmcCc{f?hWijdKiagP7`dPh$ifdTgWdWg8gagrgZfGiAhpc%d%3phih;cWg|hTbhi9gK7X3JcJh97chFf|70i:dUgXiS8T4eiqgCj00d9o2Vj00bds0H1 1Hh_g`gDi1hR8?iYi204f,g|8 hwiGib7X9!hZife*iOcj7oh(h)hegZ0,g#jfir04h/i9fOh=g,g.jcjFdXh}jJdwg_jPfFg|g~i8iFiKbl7Xfmj#i=frjwii3Iavi{g5i}042D0!eT1ejicUh,dpiEccfijqijf`j)e(7Ni@iL70g3ejg7fYiUi$ioe=j2i!j6dhi*joj)a_7YiejxgRark97bgVimhK8^fyaL0Hklemj2j4j`iVfEj8jahPjPdxjVhnkP0|jhkKiujkgmi5jnjZk0h0j$ijh3k5ifh7kvh57,jzjAkhjDh-jHg`h?jNkTg=kRdtkZ8}04gil00RjXi7gIi-iH3IhBk,jx4@ih7+7{k=h*3Sfyj@j_kFk^k$d00g8i7 8d818a1f0!84lB2Q2L0V1#ly0g82920%0)0+0X04.

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.
Etudier la page "Tri fusion".

⏳ 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

.128013nco0m/gS-d;fw,72qy)e[é]h43vblr_:p96k5 i=8a(sP1tu050k0u0V0Q0N0D0S0M0c0D0Q0S0S0O010V0N0H010406050S0W0f0f0Q0E0s040i0d0D0W0;0d0b050g0{0}0 110_0H04051h1a1k0g1h0_0k0N0B0)0+0-0/0+0b0h0W0Q0h0u0j0H0s0V0y180M0y0N0h0y0D1M0y0V0@050!0C0D0u1t0,0.011L1N1P1N0V1V1X1T0V0E1i1H0)140S0H0Q0b0/0q011Z1v010m0$0u0b0Q0f0u1T1^1`1 1#221X25270@0a0M0T0E0d0H0d0S0N170b0M0Y1?0E0E0u0c2s1a2a0b1i0g1H2F1/1;1:1U0k2c1w0N0b242p1T1q1s0*1!2P2R0b0d2V1T0H2y1i2D2F2,0`1_2t2X202#0E0~0D1T0Q1K2y0m0/030F0F0c2$0u1P2!0d0j0I0j0U0@0M0U1a0Q2-2:0^2/2b2=1#2@2_2{2}0u2 01313335372S3a0j1}040M0q3h3j1`3l2D2O013q0Q2`1i2|0y2~3032340Y3A2#3C0A3e0A3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0z3e0z3*1b3,3m2;1u3p0d2^3Q3s3U3u3W3y3Z3|3#3b0L3e0L422,3-2:3N3;4c3^3x3Y364i393b0J3e0J4o443.473:493r3S3t3v4w3{383C0p3e0p4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0P3e0P4W2E4Y462Y4#4a3=3@4e3_4g4y4-3a3e0I4=3L4r3/4`4L3?4N4f4x3!4A3c0e0@0U0e564@4s4$4|5d4 5f4z3C0U3d045x5n455p4{4u4~4P4,3}3c3E0U3H0g3i3+3K1l2*1a2V2I0k1;2N594x2U1r1i2)0u2+3k5Q2E054x5+2b0N0k0/322D5w3s5?5^505g5{0M2g0u5~5u525y3*4H4_0K0@0Y0m5-5;4^200n3e6g5C590b0m0@1/0N0F0m0W2q186m6a200?040R6z584!0b0@0%0V6F4Z4_6C0t0G6g0_435R3M5}015_2:3C3E5c6X4+515J1}6226646Y5 5v3b6$5O6h3N6k3F0M6}6M6i1#0S0k0@020r0W0d0V0l7577797b780l6S6 0M6(0F5`3b3%4M7k665J3%6-27654Q7s1T6^6n4!723e6}2k0E0w340b1q2s0M0G0M6K0M0u0S0V0M0W2R7P0N7T0u7h6U5.6W5@6:7m0j3 7p7*6)603~1~637w5I4j7-7z5P6A71736|6}0T2p0V7J7L0N1J7O0+0M0m182A892t2y0b0B0d0N1Y7W1Y1P7!0M760N7R7T7P2|8r0V1Y6s0w7#7%3l8G5C7k7,4l7/7_6*7{4l7u6/7;6=0j8M3I6T2.7)5~7,4C8N6:7r7{4C8S8O7=0j8(696G4_7D820M7e7d767f8|7g8G8Z5,8#7+6!3b4T8)8U524T8.8*7x7{993I7F0M7B4_6I04198G9l7 0/0d0@0O6g9s8@2?0C6J247i596C6E8I9t3O6J7T9F4!6P7$8!4r8K970j4/9a6;524/9e9b5J9X9j7F9m206c040N6f9r9,3p0@9q2,9z6N209v04020D799x9=9K0f0N5k9O6O0@6R927i9U1`3C0I5|7:9Z5Jai9$al7{ai2F3i9k9k9?0/9.2y0V0W0E9_3k9{703:9M6Lad9J9Tak7,5laj8/8VaPao8+5haPas8`aw019.360S8F9`a!6Cac4paeaN9V5xaQ9f7`aW3daU9ga_7}8`av9K9o0f9ya!9~a3a*b19^b49K9~0g0gbb9A1#a60@5Na.aL5=a:ag3b5Ma?9%7{bsa{a^5w6@atau6~9Kay0ZaBaD3KaF4s0@6v6xbI7(bh0/9Ha92?6r0E6tbN8hbU1#bTbnaG9L046Kb#bS0@0va-94bRb*b3b(3N6C0x0t0obg9|9@046s6u6wb!b_9G0@9I9Sc0aHb+9Nc79Pb/b-b@cja,b|0t9y935R0g5:5S5*5U5%1a0V5Xcy2L2G0Q1Wcv0g5V6T0Y0!0$0S04.

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

.128013jnco0m/!gS-.d;fw,72qy+Là)e[]h43vblr_:Ep9C6k5 i=8a(sP1tu050n0A0$0X0U0I0Z0T0d0I0X0Z0Z0V010$0U0N010406050Z0%0g0g0X0J0v040k0e0I0%0{0e0c050h12141618100N04051o1h1r0h1o100n0U0G0:0=0@0_0=0c0j0%0X0j0A0l0N0v0$0D1f0T0D0U0j0D0I1T0D0$0~050+0H0I0A1A0?0^011S1U1W1U0$1$1(1!0$0J1p1O0:1b0Z0N0X0c0_0t011*1C010p0-0A0c0X0g0A1!1 21261,291(2c2e0~0a0T0!0J0e0N0e0Z0U1e0c0T0)1}0J0J0A0d2z1h2h0c1p0h1O2M1_1{1`1#0n2j1D0U0c2b2w1!1x1z0;1+2W2Y0c0e2$1!0N2F1p2K2M2?11202A2(272,0J150I1!0X1R2F0p0_030K0K0d2-0A1W2+0e0l0#0f3h0~0T0#1h0X2@2`0 2_2i2|1,2~3032340A3601383a3c3e2Z3h3j24040T0t3o3q213s2K2V013x0X311p330D3537393b0)3H2,3J0l0F3l0F3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0l0E3l0E3=1i3@3t2{1B3w0e2 3X3z3#3B3%3F3*443,460S3l0S4b2?3^2`3U3|4l403E3)3d4r3g460Q3l0Q4x4d3_4g3{4i3y3Z3A3C4F433f3-0s3l0s4O3R4z3u4R3V4T4k4V4m4X424q4!460W3l0W4)2L4+4f2)4.4j3}3 4n414p4H4_3j0O3l0O4~3S4A3`534U3~4W4o4G3+4J3j3i0~3i5g504B4/555n585p4I3-0#0#5u3n0h3p3?4*4e5y544D574Y4^455s3L0#3O5K3Q4 5O5j4C4;4E4@5a5V3h3/040#3;5!5M5$4Q525)5m4=5o4Z5.0#485;4a5@4c5N5`2}5z5R4?595q5F4u5;4w662^1u2;1h2$2P0n1{2U5j4G2#1y1p2:0A2=3r5^1p4G6B2i0U0n0_392K5F3z6I6K6e5E465H0T2n0A6Q5D5b3k2M5L691,0R0~0)0p6D5%4-0q3l6.6(3{0p0~1_0U0K0Z3d2G2I672L6/520}040Y6?5i4-0c0~1W0Z0$0A794,750~0z0L6D10726G2A6P016L2`3-3L5m7t5,6f46246V2d6X7u6R6!7y5@6@016;3M0T7R7i51270Z0n0~020u0%0e0$0o7Z7#7%7)7$0o7o7T0T7A6}7w465:7z6J7I6Z5.3/7F2e6Y604s3j7_7M7a527W3l7R0T7e7g0T0A7f2B1)0$0v0N1)8e7h7q7p2^3T7=6M46637`825U8447256W8A5-8C8y877j7V7X7Q7R0x330p1f2H0U1Q2F0c0G0e0U8o338p0T6{0A1)200J0T4i0n2F0:2t0U0@210$0m7/7q5O8v7@3j6h8z7|835r0l4u807H7B6S921!8K7U1,8a8O0T0M0I1(0T1d0-8^8o02030F0O0o3X0j4i2y0D2e8j8)0J0U0T8-0T6~1(8U1f0m0T0P9u9w0o8h0$9p2A6{0T7,7%2b9J0=0d0A9$7.8r7:90213-4L4V7=7}8C4L9a8G7C3j9@3=7N9j8c9#7!7-9-9-8}8t4A9;0c4#6O7{9c6!4$9}958B974$6$9k74276*048S0J6D0Tat3w0~0UazaB0_0e7P2XaF7N0c0H0~0J211J7:5j76788~aMaO042maT4-aVa$5{7d8^7ga)27760zaL88270e0~0la=8L1,0g0U5ua.1,a:7n9/aXadai7?9=4`ah9~9d0l4{amaj5.4{ara5a5aG3VaD0c1x9+0Ka~1g7qaA7Na^040Va{9h3{aDab6C8ub88w5cbcan8H975dbh7J5.5dblbm7S7NavaxbD4B0~0bb$5jaIbqb*7baZaQ1F8qaca|0_a(b6b^bp04aEbxbobA0wb.52a~b0b{bE01760rc42}aZa#c83Ub`b@c97ca!a,b?bIa?b27l7mcd1,0d5H04030T2F0d0D0A0JcD1)2C0I9T9x2XbscI0%0Tbv0U0g13bH3R8 bK913JbNbi8C5tbS9`975tbWbXc/c:c;c:bocx0~cA0n210/9o2F7fcI8$8dco0Y0y2B8@7ga;b5ck7;cZba5scy94c%c,6U8FbO9 3hdh5!c=bYcr0_av0U6-c0aMa+d0b1b_0~0BdDb}b)chaU0~0CcvaH7Y0I7%dOb}8pdH76dGdK7bbqcObuaKdZ7k040Cb44y9:deaf6T7y339_965F7Edmdjd`9f3pdsbmbocmcN0UbtbvdTbAbCdzdudIcW73bJ6QbL5/c$bTc(7 d|emc,86e0c/bodwdy2?byede4bre60Ad%bweyc10~0iebeHdAb~dW0~d-3rezb|c^cz8gcDaR1)0ZcL0o0-0T0v0T330%2Y9)0%0/8n0{8f0G3X0A0%8.c{0c0Zef7rddeic!62elc+5F48c*d_6T8Jete1e1c@cycA0=9J160{cId8d18d8%cof0cYf3df3h93d@b8f76T99epfC5s93drdse3dBa-d)a/dFdHe4ePd+ccecb|cmdVfOcs04dYdc5(d#eDeFfTdNfWc9eadTfYftf!dEf$fRf*e7d(f(a%dMfVeMeAfMcpcX7NdXf{eOf^cadMfu0h6F1s6n0h6p1h0$6rgm2S2N0X1%6A6o6x7p0)0+0-0Z04.

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

.128013nco0m/gS-.d;fw,72qyL)e[é]h43vblr_:Ep9C6k5 i=8a(sP1tu050l0w0Z0U0R0F0W0Q0c0F0U0W0W0S010Z0R0K010406050W0!0f0f0U0G0t040i0d0F0!0^0d0b050g0 1113150}0K04051l1e1o0g1l0}0l0R0D0-0/0;0?0/0b0h0!0U0h0w0j0K0t0Z0A1c0Q0A0R0h0A0F1Q0A0Z0{050(0E0F0w1x0:0=011P1R1T1R0Z1Z1#1X0Z0G1m1L0-180W0K0U0b0?0r011%1z010n0*0w0b0U0f0w1X1|1~231)261#292b0{0a0Q0X0G0d0K0d0W0R1b0b0Q0$1`0G0G0w0c2w1e2e0b1m0g1L2J1?1^1@1Y0l2g1A0R0b282t1X1u1w0.1(2T2V0b0d2Z1X0K2C1m2H2J2:0~1}2x2#242)0G120F1X0U1O2C0n0?030H0H0c2*0w1T2(0d0j0Y0Y3e0{0Q0Y1e0U2;2@0|2?2f2_1)2{2}2 310w33013537393b2W3e3g21040Q0r3l3n1~3p2H2S013u0U2~1m300A323436380$3E2)3G0j0C3i0C3M2G3o0}3Q3s0?3T3V053X3Z3A3#3D2U3F3f0j0B3i0B3/1f3;3q2^1y3t0d2|3U3w3Y3y3!3C3%413)430P3i0P482:3=2@3R3_4i3}3B3$3a4o3d430N3i0N4u4a3?4d3^4f3v3W3x3z4C403c3*0q3i0q4L3O4w3r4O3S4Q4h4S4j4U3 4n4X430T3i0T4$2I4(4c2$4+4g3`3|4k3~4m4E4?3g0L3i0L4{3P4x3@504R3{4T4l4D3(4G3g0Y0e0{5q5d4}4y4,525k555m4F3*3f5s3k0g3m3:4%4b5w514A544V4=425p3I0Y3L5H3N4|5L5g4z4.4B4;575S3e3,040Y3.5X5J2I1p2.1e2Z2M0l1^2R5g4D2Y1v1m2-0w2/3o5=1m4D662f0R0l0?362H5D3w6d6f565n6i0Q2k0w6l5B583h2J5I4N4 0O0{0$0n685!4*0o3i6E6y2`0n0{1?0R0H2U0W0w0G2F493O6F4 0`040V6J5f4*0b6N0U0E6%4)6Z0{0I680Q6Y2`0E0{1T0W0Z6.4~246!0v6?6^1)0d0{0j020h0Z0m746K3t6`046|6~6W5?7f0?6!6=7l3p7r5L6k016g2@3*3I5j7v5)6n43216p2a6r7w6m5C7F1X5;7n016H3J0Q7U6 3R0W0l0{020s0!0d7c7#7%7)7$7(7d7r0}7t3Q7C0H6h435-7B6e7K6t5+3,7H2b6s4W807O6x6(4 7Y3i7U0Q1Z0Q0w6}2y1$0Z0t0K1$7j0w687;2=7?7}7x1~3*454S7@7 4p3g45827J7D7M8E876b701)8b7T7U0u300n1c2E0R1N2C0b0D0d0R8o308p8e0G0R0y1$1}0G0Q4f0l2C0-2q0R0;1~0Z0k8r7W7@7_3g4r8A8v7L6u4r8G845R8D0j953/7Q8P8d0Q0J0F1#0Q1a0*8{8o02030C0L0m3U0h4f2v0A2b8j8+0R0Q8:0Q6R6T2w0k0Q0M9u9w0m8h0Z9p2x6O8g2x0K0/0c0w8 7:9197930j4I969c5*9e4I9b7~859?8L750?9j8d7*7.a17,7+7/4v9+6l9-4Z9:9_9d5o0j4Z9^8I6uab3M9k9}016A048U0G7e892`0{2U1u9%au6/240d7S2UaB8N3^7h0G1~1G7W5g6!6$7=av1)0f0R5saO4*6!0paH4y7h2jaY6:6#a*aw041Za-1)720v7qa7aS6c9,7y4@6j978Caf4^ai985+4^6w8Q9k6@7Q6*043a0w2b0b7k2:bbaT0?77040Sa$5#6+6-a`aI016!0xa;3^ax0baz8qbv3R6!0z90bG92a}59a 9;7EbOb4b13*5ab8ba8daobd0Rbr4*bobq7rblaC3tbCbEbK8t4xbM8x435qbPad9=afb`bT9`b~5rbXbYb,bwaq0o1P1#b%4 b#ccaD7!7ba63oc63RaV0{0ecf767S1~0lcqbBa/6,bAbx0{bzbGbs04b$b+aobo0jcv01cn5.czbIcLbo7a7ccLbdbfbhbj677Q7pb;c!b?a|b^5p0Yb{aj5+5Ec0ae5Dc-c4c5bZbcbtcPcBczcecDaZ0{bJcH7Qb)cVc}d2a+cCb=b-cwcGbkcI78cLcN5GdebwcQ9*bLc*0b5D7A308Bc1dv226qbQ8J3e7A5Xc`anc|cFcR0{b*didKdhckdj04cKd6bmcMaWcOdrdo9Kdt5D7{dxb0dzb_81dCb|bR5,8Lc`b!dad$aPc dba.dR6Xc#d4dMbpd9be1#cYc%6X0g6a5@655_621e0Z5|ei2P2K6,1#2J5`7;0$0(0*0W04.

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

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