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

.128013vt4=8fw2pmuP(751,:cSsFré]k[63;0 dg)/+n9qiyelh_bàoaT.-050H0R0c0Y0P0S0v0G0t0S0Y0v0v0e010c0P0j010406050v0l0k0k0Y0x0Q040u0X0S0l0_0X0M050K101214160~0j04051m1f1p0K1m0~0H0P0b0.0:0=0@0:0M0I0l0Y0I0R0#0j0Q0c0T1d0G0T0P0I0T0S1R0T0c0|050)0V0S0R1y0;0?011Q1S1U1S0c1!1$1Y0c0x1n1M0.190v0j0Y0M0@0i011(1A010g0+0R0M0Y0k0R1Y1}1 241*271$2a2c0|0a0G0m0x0X0j0X0v0P1c0M0G0%1{0x0x0R0t2x1f2f0M1n0K1M2K1@1_1^1Z0H2h1B0P0M292u1Y1v1x0/1)2U2W0M0X2!1Y0j2D1n2I2K2;0 1~2y2$252*0x130S1Y0Y1P2D0g0@030U0U0t2+0R1U2)0X0#0q3f0|0G0q1f0Y2=2^0}2@2g2`1*2|2~30320R340136383a3c2X3f0#22040G0i3l3n1 3p2I2T013u0Y2 1n310T333537390%3E2*3G0D3i0D3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0d3i0d3.1g3:3q2_1z3t0X2}3U3w3Y3y3!3C3%403)3g0p3i0p462;3;2^3R3^4g3|3B3$3b4m3e3g0C3i0C4s483=4b3@4d3v3W3x3z4A3 3d3G0o3i0o4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0f3i0f4!2J4$4a2%4)4e3_3{4i3}4k4C4;0#0N3i0N4_3P4v3?4~4P3`4R4j4B3(4E3f0F0|0q0F5b4{4w4*505i535k4D3G0q0q5p3k0K3m3/3O1q2/1f2!2N0H1_2S5e4B2Z1w1n2.0R2:3o5I2J054B5Z2g0P0H0@372I5B3w5+5-545l5:0G2l0R5?5z565D2K5H4L4}0A0|0%0g5#5)4|250h3i69494w0g0|2D0t0T0R0x6l0R6f63250{040n6r5d4(0M0|0,0c6x4%4}6u0r690G6g5e6A042*0k0V2D6E6b1*6H6J6L6z666T3R6W473O6K6s3t0|686(5$6+0@6u0J0s690~6/6a0G5=015.2^3G3I5h6~4/55413H235{5}4U78735G6|5e6d3J0G7l6#5e0v0H0|020O0l0X0c0E7s7u7w7y7v0E6_6#750U5/3g3+4Q7G5~783+5`2b5|6 5@5A7J1Y7g6Y4}7p3i7l2p0x0y390M1v2x0G0s0G6C0G0R0v0c0G0l2W7;0P7^1%0W0G2.0P4d0P5`1O1@0P0y0R0r876Q2D7?7^7`2y0y0S0y2c0M7_6p6o0T0y2z1 0-0:7}7 6K6{6`2?3Q7G7I0#437L5,7T7N4n8I7a7R7c4:788J3.6;017#7k7l2S7@7_1$0G0x1 0I2z0l2z0y0V1b2z1%8y6k6m8s8c7?7_0g7;1%8+1D8@7;31272y2A8_2E8{6p8v0M8x7^7E6{6g8G714o5;8L765^9o7Q2c8S778O4p617h4(8Z7%822u0c7+7-842y7:8y0g1d2F9K8*290b0X0P1%0H8/0V0X198b9L8B4t7F9q7H9n0#4G8K9w9s9/8Q9v8M7d8O9:8W6y7!7q8!0G0Z0x0l1%2v8e6R1%8%9f8x311U7 8d0(0G0w3U0va72V1d0!9j8E4v9m1 4W9p9=7V0#4X9u7S9raA4X9A7Z259D7%7B7A7t7CaN7D8C9+5?8H4?9;9`8T8O4?aDaz56aX3M9EaJ1*65040P6.2;6*9 2{6!6{a@6F250X0|0e0e6X8X6Na=5!8X6u6^aT9k8F9,8H58aYaF5658a%aZ9x5mbga+9E7%a-0@a/2D0c0l0x1ea{bt3S6B9ibca^6V0|0B7n6Z040HbL6G0|0zb3bH0@a 04b1bTa}6,6O0X8f6qbbat5*be9.5qaybm9?b/blbi78b/9Aa,b40|0kbZ6UbVb0c06$0|6wbGb!3@a`a?bCbW0Lc46M6-bP6t0|0Jcg4(bW0K0Kcn4}0k0P0|3Lb*b7aub-aw3g5Cb:b^8OcEb@7U5 60bq7m8Xbv0(bybAccb}048`6n6pcjbI6vc!ca046Cc%016%cUbUbDb$b(c+c-3oa|c1c:bOc8c`c@6)bC6Nb c}c504cmbB8X0X7j4dcsa_cW9ccY6mc?c6c+6Nc*d45ec 2Jc_4w0|6Paadj046Id8c/d2dd1*cedD0@cu5pdxdzc.c9c:b65Jb8clas5!0K5(5K5Y5M5V1f0c5Pd#2Q2L0Y1#dY0K5N6`0%0)0+0v04.

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

.128013vt4=8fw2pmuP(751,:cSsré]k[63;0 dg)/+n9qiyelh_bCoax-050G0Q0c0X0O0R0v0F0t0R0X0v0v0e010c0O0j010406050v0l0k0k0X0w0P040u0W0R0l0@0W0L050J0~1012140|0j04051k1d1n0J1k0|0G0O0b0,0.0:0=0.0L0H0l0X0H0Q0Z0j0P0c0S1b0F0S0O0H0S0R1P0S0c0`050%0U0R0Q1w0/0;011O1Q1S1Q0c1Y1!1W0c0w1l1K0,170v0j0X0L0=0i011$1y010g0)0Q0L0X0k0Q1W1{1}221(251!282a0`0a0F0m0w0W0j0W0v0O1a0L0F0#1_0w0w0Q0t2v1d2d0L1l0J1K2I1=1@1?1X0G2f1z0O0L272s1W1t1v0-1%2S2U0L0W2Y1W0j2B1l2G2I2/0}1|2w2!232(0w110R1W0X1N2B0g0=030T0T0t2)0Q1S2%0W0Z0i0Z0q0`0F0q1d0X2:2?0{2=2e2^1(2`2|2~300Q32013436383a2V3d3d3h0i3k3m1}3o2G2R013t0X2}1l2 0S313335370#3D2(3F0C3h0C3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0d3h0d3+1e3-3p2@1x3s0W2{3R3v3V3x3X3B3!3}3$3e0p3h0p432/3.2?3O3=4d3_3A3Z394j3c3e0B3h0B4p453/483;4a3u3T3w3y4x3|3b3F0o3h0o4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0f3h0f4X2H4Z472#4$4b3?3^4f3`4h4z4.0Z0M3h0M4?3M4s3:4{4M3@4O4g4y3#4B3f0E0`0q0E584^4t4%4}5f505h4A3F0q3g045z5p465r4|4v4 4Q4-3~3f205B3I0J3l3,4Y5E5b4u4)4w4,525L0q3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530q4D5B4F692;1q2-1d2Y2L0G1@2Q5b4y2X1u1l2,0Q2.3n5|1l4y6E2e0O0G0=352G5y3v6L6N635x3e3g0F2j0Q6T6h5#1W5{6c1(0z0`0#0g6G5-4`0h3h6:6*3;0g0`110Y0O0k0 0T2B0t0l0w2t6/6a2H6;230_040n6^5a5.0`1Y7g4!4`7d0r6G0F7b3s6-0Q0U197l4_7c0`7p79047r6_3P0`251c7D7s0=7d0I0s6G0|7L3N6S016O2?3F5N5e7V5Z643e206Y296!7W6U537!6)7h6=3h0F7_7y3O0v0G0`020N0l0W0c0D80828486830D7R7{7$0T6P3e5%7#6M7.6$4k0Z3(7+2a6#5?8n8i7=7m237}7^7_2o0x370L1t2v0+0s0F1Y0F0Q0v0c0F0l2U0F1S8O0Q0r2x7v198M8O8T02030C0M0D2T1t0t1#0G0l2x0x7w8P2y0.0F730S0Q0w0t8~8X8c7T4s8e8g0Z5^8j8s5K8n408q7-7%6V996(5R7G8z7E7_8M8P7J8%8)8+8-0O8/8Y8T2 9t8`2 8}8 910Q942;7U8k7X1}3F669b8l8t5j4m9g9c5!8n9R8w7z1(9o9q2n2s0c8E8G0O1M8J8{0g1b2D9:2w2B0L0b0W0O1#1!0F6}6 0 9A8{8U0c1#7k7D7S9L969N8f7Y4C6Rah8m5j4D9X9T9dao9l6J9%0=9)9q8988818aaA8bad8dah984U4N8ean4T216Z9Y7(0ZaK3J9*7M016,040O782/7F7?2_7u8^7qaX0W0`0e0ea-7G0L7I2Ta?a)1(7d7Q7Da(8x1(0t5A030F0V0/9A0U0/1#8R0F0v0Q0l0R0F0x0R0x2a0L0c9K6F9M6T984:aLam9U3F4:aq9i53bwaV9*9qaXaZ2B0c757Ka%aXa^04acafb27N0`0A7{5Va+7x95bV017d0ybr3L5E97aj54alaR9j55bC7/5L552I3laW7GaZ39bgbZ4#a~b,7abt7.985nb=ar9Z5jccb_aN6W5lb}9pbHb1aw7H040k0)a00la{b(a/04a=b0aX7d7fb%cqbR0#a,cC7Gcz0KcxcHa_bObsa|bW040IcP3Ocz0J0JcY5bct0`5P4qaHbub:5zcdbD5#6XaQceaSc:cmco7`a@0`0Yc%4#czcBbPc cs0X6~700k722C7577c47n0`cFbUcQbS0X0Udh7A047Cd6cUcrcJb$dl3O7od25 6|cubhdqa}0`cXaGcG0Fb/9P6W7!2 aMbzdQaP7,b?6i7;b~c}bQ0`0PdC23d4d*7td8da7173dfa#dHcVdkcTb(bRbTd{cqdBcLdvbRct1SdGe2cy0`cOe8cqc)5Bd^b)7Bd-3;cReg7Oc7avdNaIc/8idSbyas5y8pc^c=8n5$auc}cp3OaZd@ec4td0ej01cz020R84d53neFb!04d)dM5bc6dLdzdO0L5y9aeudY5@dW8rc_9j0q9a5*eEb dvbK0$bNeMbReXc,dMe%65c;b`eB9Wezf6cg9#d#cobJ0`c29JeYc50`a f1e$erdP3f6k9SeAcgapf9cjfreDe^c~e`0`bLe}eJeVd1e#6F0J6I1o6q0J6s1d0c6ufS2O2Jdo1!2I6s7S0#0%0)0v04.

À vous de jouer 3 :

Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013vt4=8fw2pmuP(751,:cSsré]k[63;0 dg)/N+n9qiyelh_boax-050G0R0c0X0P0S0v0F0t0S0X0v0v0e010c0P0j010406050v0l0k0k0X0w0Q040u0W0S0l0@0W0M050J0~1012140|0j04051k1d1n0J1k0|0G0P0b0,0.0:0=0.0M0H0l0X0H0R0Z0j0Q0c0T1b0F0T0P0H0T0S1P0T0c0`050%0V0S0R1w0/0;011O1Q1S1Q0c1Y1!1W0c0w1l1K0,170v0j0X0M0=0i011$1y010g0)0R0M0X0k0R1W1{1}221(251!282a0`0a0F0m0w0W0j0W0v0P1a0M0F0#1_0w0w0R0t2v1d2d0M1l0J1K2I1=1@1?1X0G2f1z0P0M272s1W1t1v0-1%2S2U0M0W2Y1W0j2B1l2G2I2/0}1|2w2!232(0w110S1W0X1N2B0g0=030U0U0t2)0R1S2%0W0Z0C0Z0q0`0F0q1d0X2:2?0{2=2e2^1(2`2|2~300R32013436383a2V3d0Z20040F0i3k3m1}3o2G2R013t0X2}1l2 0T313335370#3D2(3F0C3h0C3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0d3h0d3-1e3/3p2@1x3s0W2{3T3v3X3x3Z3B3$3 3(3e0p3h0p452/3:2?3Q3@4f3{3A3#394l3c3e0B3h0B4r473;4a3?4c3u3V3w3y4z3~3b3F0o3h0o4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0f3h0f4Z2H4#492#4(4d3^3`4h3|4j4B4:0Z0N3h0N4^3O4u3=4}4O3_4Q4i4A3%4D3f0E0`0q0E5a4`4v4)4 5h525j4C3F0q3g045B5r485t4~4x514S4/403f3H0q3K0J3l3.4!5G5d4w4+4y4.545N0q3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550q4F5D4H6b4s5/616g5Z5K5#663e0q4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3f575D596Q5 6S6f6U6I6v6K550i5n046:5a1o2-1d2Y2L0G1@2Q5d4A2X1u1l2,0R2.3n5~1l4A772e0P0G0=352G5A3v7e7g6.5%212j0R7m6j7o2I5T6e1(0z0`0#0g796r230h3h7D7x3?0g0`110Y0P0k0 0U2B0t0l0w2t0g0U0b5R2;7J010_040n7I6)3s0`1Y7,4$4|7)0r790F7E7.040#0V197_7{0=0W0`0e817%0z0t0`0K1b0R7;4{237@877-3?0`251c6c2H7`7%8404868p3I8201898b8d8f3Q7)0I0s790|8w5G7l017h2?3F3H5g8M6w6L3G7p297r8N7n6Y8R5}7%7G3I0F8,8D5d0v0G0`020O0l0W0c0D8?8^8`8|8_0D8I8D8T0U7i3e5)8S7f8!7t6Y3*0F7q7s6X5l988(8k018:3h8,2n0w0x370M1t2v0+0s0F1Y0F0R0v0c0F0l2U0F1S9E0R0r2x0R7 9F9D9F0S02030C0N0D2T1t0t1#0G0l2x0x9Q9O9J2 7T0T0R0w0t9;9N928K3P94960Z5`999h5M6Y429f8Ya25$a41W9l7=239o8+8,0$0F8n9J9V9X9Z9v0P9$9-0.aj2Tas9/2C9;9?9;9`7$4u9}8P4n7k9a8U554oa62aa86x0Z683-7%af9q2n2s0c9u9w0P1M9zat0g1b2Da$2w2B0M0b0W0P1#1!0F7N7P0 aw9J0P9L9A0X0VaC789|aJ95aG0Z6ma19b9i3F4FaN8ZaK5Nbbac8g1(aV9q8 8~8@90br918w8JaD7db79~6Abcbj6Y4WbhaP8VbD5,aW8y7z040P7C8w8r9m0M7A9P80bT8y8t0e8v2/bUad7y8a048c2U8.4%7)8Hbx93bBb96NbE8#5l4=bIbda3b ab3laWbN7%bW7}bY0c8jb+8385cebn0=0k0P0`5qb^9{aEb`1}3F6!b}9c5l57c1bFcyc5agb*cj8z0`bRci4v8m2TcK5db$b(3ncF3Q8Ab.8Ccqcf7(0`b@6qcY2waFct6y6;cwbec,8XaOc2a95l5pcDc79q8yca8ncO4%b$d0610V0`2ib;7?0`7+c(cL047:dc5d8Fd8238t0Zdj1(cl5ob43N8Lcs0M5A5Cc.c3dwc;bib~dA7vcEbOcIbSb)c}bX9Qd3dk85cR3NcT5XcM8odK7%b?dr2Hdt7m9~5QaIbJ6k20cAdD6y8%c6c{dT4%bP2B0c7VdWcSdLdeb2dn0=7)0Ae23RdMbZbzcG7)0yd!7cc)du5A982 94cxeidBd+5%9kd=8-880`390v8edgb=c#eed$8!d(a0ekb7em6ya59gc?aQ0qa0bMd?d cl1S0R0ldO1(d2b!dYdae6ca7~e9d~8s0`0LeY8l04c ezd9040Ie:018t0J0Je{dp6=eCb6d%b90qaSeHep6Yf7eoeN8VfcdFd?d@610`0Ye{e!dXbV7M0X7O7Q0k7S2C7V7X7Z7#b59m7)dbeadddffGdh0`7^e#fqcbdNe@8hfLe{caeUa?eXfR1(dicpfGc*dv6ybbf9fe6kbgeMcB5Ablesc7d 0QfnchfNcZfVfsa{fv7TfybRfAe6fEe(7/e1fZe3fTf}cGfV0)fXf{04e/gf3Qf13jgcc!04fMfpf~dVg70`e`f$fCbAf5c+3fbDf,f;6ybHf:d/gGc`eSeubQdJe,fOfmgncP8=0S8`dR8qf_gy04c$47dcf(5Ab|gIgN0qc0gMeJ3fb|eRfiet9md_0$d|fU0`f`gBdsf4eEf6cvg;g_0qczg^c/6ZgPc{dH04eweyfJeAg*f3crgEf)3Gc-hchh6:fdgJhwhjg}hld`h2gX5:fleC0J7b6^766`731d0c6}hT2O2Jb21!2I6{8J0#0%0)0v04.

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

.128013vt4=8fw2pmuP(751,:cSsrék63;0 dg)/n9qiyelh_b*oax-050E0N0c0U0L0O0v0D0t0O0U0v0v0e010c0L0j010406050v0l0k0k0U0w0M040u0T0O0l0;0T0I050H0{0}0 110_0j04051h1a1k0H1h0_0E0L0b0)0+0-0/0+0I0F0l0U0F0N0W0j0M0c0P180D0P0L0F0P0O1M0P0c0@050!0R0O0N1t0,0.011L1N1P1N0c1V1X1T0c0w1i1H0)140v0j0U0I0/0i011Z1v010g0$0N0I0U0k0N1T1^1`1 1#221X25270@0a0D0m0w0T0j0T0v0L170I0D0Y1?0w0w0N0t2s1a2a0I1i0H1H2F1/1;1:1U0E2c1w0L0I242p1T1q1s0*1!2P2R0I0T2V1T0j2y1i2D2F2,0`1_2t2X202#0w0~0O1T0U1K2y0g0/030Q0Q0t2$0N1P2!0T0W0d0W0q0@0q1a0U2-2:0^2/2b2=1#2@2_2{2}0N2 01313335372S3a0W1}040i3g3i1`3k2D2O013p0U2`1i2|0P2~3032340Y3z2#3B0A0@0A3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0d0@0d3(1b3*3l2;1u3o0T2^3O3r3S3t3U3x3X3`3Z3b0p0@0p402,3+2:3L3/4a3?3w3W364g393b0z0@0z4m423,453.473q3Q3s3u4u3_383B0o0@0o4D3I4o3m4G3M4I494K4b4M3^4f4P3b0f0@0f4U2E4W442Y4Z483:3=4c3@4e4w4+0W0J0@0J4:2F2)0N2F2V2I0E1;2N3-014v2U1r1i572+3j3)3I054v5m2b0L0E0/322D3B3d4K5u5w4~3Y4y3c1~2g0N5D4v5F5z1T0H3h433L0y0@0Y0g5o2E5S5f0h0@0D5Y5s4?2?0g0@0N0V2o0Q2y0t5)5!4Y0?040n5^4F4@0I0@0V5~4p5f5{0r5)5(5 2?0@19415p6b1#5{0G0s5)0_6f5Z3K5C015x2:3B3D3;0D6r4)4 3{3C5I265K6s5E4x6v5P5R6h0/5$040D6R5(6o5*3L0v0E0@020K0l0T0c0B6!6$6(6*6%0B6m645t5v6H5y3b3#5B6?6A5N6_6E275L4O6C6`3(6N016X5%6S2l0x340I1q2s0D0s0D0V0D0Z0D2t0v180c2u0N0(240;0N0w0v6:6U5S6z0Q6^3a3r7E5M6J3|706G6}7L7H2F6M654Y796Q7b2p0c7e7g0L1J7j0+0D0g182A7%2t2y0I0b0T0L1Y0V0S0S6e4n6;2t7E7G4j6{724*6C4j7o6F856B4h0W83767U4@7W6S0D6-6,6#6.8m6/6U6n2.6q6|7F6u4z7I8w7K504A89716H8C6C4A7S7X6R5_4@5U040L5X6U6a8h6c047}3j8V4X4@0T0@0e0e698O200k0L0@0C7 3L5{6l8s8?818y0W4R848H738d4R8F7O6I508 3G8k8k8-1#8Q2y0c0l0w8Z3I8#5+1#8/3e7B8u4p8|1`3B4-907P504-958b6~0W9x9a6S9d0/8Q360v0N8,778^9r5n8v5D7G529y976C529C91868d9X9H9b9m5T0@9g9i9k2E9-5f6104638U9J018(040S9P8W3o5.5:0T5=2z8?660@5}7C779_9{9s8$2067a2aja48Yam9n0/9 0Waq3L9p043faea30/6j9S5p0H5r1l2*1a5a1a0c5caM2L2G0U1W58aK5j6n0Y0!0$0v04.

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

.128013vt4=8fw2pmuP(751,:cSsrék63;0 dg)/n9qiyelh_b*oax%-050E0N0c0U0L0O0v0D0t0O0U0v0v0e010c0L0j010406050v0l0k0k0U0w0M040u0T0O0l0=0T0I050H0|0~10120`0j04051i1b1l0H1i0`0E0L0b0*0,0.0:0,0I0F0l0U0F0N0X0j0M0c0P190D0P0L0F0P0O1N0P0c0^050#0R0O0N1u0-0/011M1O1Q1O0c1W1Y1U0c0w1j1I0*150v0j0U0I0:0i011!1w010g0%0N0I0U0k0N1U1_1{201$231Y26280^0a0D0m0w0T0j0T0v0L180I0D0Z1@0w0w0N0t2t1b2b0I1j0H1I2G1:1=1;1V0E2d1x0L0I252q1U1r1t0+1#2Q2S0I0T2W1U0j2z1j2E2G2-0{1`2u2Y212$0w0 0O1U0U1L2z0g0:030Q0Q0t2%0N1Q2#0T0X0p0X0q0^0D0q1b0U2.2;0_2:2c2?1$2^2`2|2~0N3001323436382T3b0X1~040D0i3i3k1{3m2E2P013r0U2{1j2}0P2 3133350Z3B2$3D0A3f0A3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0d3f0d3+1c3-3n2=1v3q0T2_3R3t3V3v3X3z3!3}3$3c0p3f0p432-3.2;3O3=4d3_3y3Z374j3a3c0z3f0z4p453/483;4a3s3T3u3w4x3|393D0o3f0o4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0f3f0f4X2F4Z472Z4$4b3?3^4f3`4h4z4.0X0J3f0J4?3M4s3:4{4M3@4O4g4y3#4B3d0C0^0q0C584^4t4%4}5f505h4A3D0q3e045z5p465r4|4v4 4Q4-3~3d3F0q3I0H3j3,4Y5E5b4u4)4w4,525L0q3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{443L1m2+1b2W2J0E1=2O5b4y2V1s1j2*0N2,3l5|1j4y6r2c0L0E0:332E5y3t6y6A635x3c3e0D2h0N6G5w535A3+5~210y0^0Z0g6t5-4`0h3f6Z6T3q0g0^0N0V2p0Q0E0w6(5a4#0@040n6?4!5 0^0V6|4_216_0r6t0D6!2@0^1a6a2F781$6_0G0s6t0`7c6w2u6F016B2;3D3F5e7o5Z643c1~6L276N7p6H537t5{6)0:6$3G0D7M713O0v0E0^020K0l0T0c0B7T7V7X7Z7W0B7j7O7v0Q6C3c5%7u6z7D6P5L3(7A286O5?4k0X7/7H6@4`7Q3f7M2l0w0x350I1r2t0)0s0D0V0D0!6L0D0v190c2v0N0)250=0N0w0v7)7l5E7+7-0X5^7:7{5K7}407_7C7w6I8B1U806}21837L7M0m2q0c898b0L1K8e0,0D0g192B8Z2u2z0I0b0T0L1Z0V0S0S7b4q7*7;7q1{3D668D7=7|5j4m8I8E5!7}908O721$8R850D7$7#7U7%9h7(7l7k2/3N8z7r4C6E8|7E5L4D96928F5j4D2G3j9f7e0:6V040L6Y7l777I3P7a769H010T0^0e0e9S9P0k0L0^5o8x9P6_7i9n8{6G8A4U4N7+7?7}4U9z8K539;3J9f9G9P9J2z0c0l0w8_3l9O81219#5m8w9p4s9r8~4/9u977x0X4:9`9w7}4:9E3m9)ag9v8A559=9v9@5j55apaC3Daz9~859T9J4z9M2-a98P3q9R9N9T9V040W9Zaa1$ac045PaPaV9W9YaU9!9$049(afaR0:9+ae6s9qax9s5kak9A985j5n1 6Mal8Lb3at9 aK9P0I0^0UaZa?9U9Wbg9c3;6,6.0T6:6=avbh6_6{bsbl9Q0470bw3O74bk4taTa)9PaW0H0HbE5ba$a(a`a!a@0^0Ga_6ba{9/a}5za 9{5#6Kb5b0amb!b9baaQbxa20!a5a73Lb/bF04bfa-bRbi040SbM5.bebV7dbX7D8A5Ob#aqb27zb)b$7}caat9obQ6xa|ai3d7/2}9?935y7^cfcccu8N9Fbbb~aM1QaOa89Tbd04b@2Fb_5baWaYb}bhbOc24`aW9XcTaba/3hbB5ba^9-bBah0I5y8CcraBct6J8HcwaGc;cz8S9 cHc4cQbxcVcXaS046-6/6;7Oc$0^bva=bxcIbAdbbC0^75c~dg6`d7c3cJdmcU0^0XdpcYadc#6^bTd10:bJbLdjbNa/bPbWb~7gc57m0Dc*65cbc@3d95c?c:dRc_b.cM4#b;a4a6dzbydecGbI0^c1dDdnb|bHb~aWd-d;bhcId:458x0H6v6c6q6e6n1b0c6he42M2H0U1Xe10H6f7k0Z0#0%0v04.

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

.128013vt4=8fw2pmuP(751,:cSsré]kE[63;0 dg)/+n9qiyelh_bàoax.-050H0R0c0Y0P0S0v0G0t0S0Y0v0v0e010c0P0j010406050v0l0k0k0Y0w0Q040u0X0S0l0_0X0M050K101214160~0j04051m1f1p0K1m0~0H0P0b0.0:0=0@0:0M0I0l0Y0I0R0#0j0Q0c0T1d0G0T0P0I0T0S1R0T0c0|050)0V0S0R1y0;0?011Q1S1U1S0c1!1$1Y0c0w1n1M0.190v0j0Y0M0@0i011(1A010g0+0R0M0Y0k0R1Y1}1 241*271$2a2c0|0a0G0m0w0X0j0X0v0P1c0M0G0%1{0w0w0R0t2x1f2f0M1n0K1M2K1@1_1^1Z0H2h1B0P0M292u1Y1v1x0/1)2U2W0M0X2!1Y0j2D1n2I2K2;0 1~2y2$252*0w130S1Y0Y1P2D0g0@030U0U0t2+0R1U2)0X0#0o0#0q0|0G0q1f0Y2=2^0}2@2g2`1*2|2~30320R340136383a3c2X3f0#22040G0i3m3o1 3q2I2T013v0Y2 1n310T333537390%3F2*3H0D3j0D3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0d3j0d3/1g3;3r2_1z3u0X2}3V3x3Z3z3#3D3(413*3g0p3j0p472;3=2^3S3_4h3}3C3%3b4n3e3g0C3j0C4t493?4c3^4e3w3X3y3A4B403d3H0o3j0o4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0f3j0f4#2J4%4b2%4*4f3`3|4j3~4l4D4=0#0N3j0N4`3Q4w3@4 4Q3{4S4k4C3)4F3h0F0|0q0F5c4|4x4+515j545l4E3H0q3i045D5t4a5v504z534U4;423h3J0q3M0K3n3:4$5I5f4y4-4A4:565P0q3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570q4H5F4J6d4u5;636i5#5M5%683g0q4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570i5p046=5H6g4d6-655_5O6!0i5E716_6+6{5h6}5z6Z5n0i3J7c744(6V775y5N5(705+0i5-5V6e6*7g6,7i5^796 7b5|0i5~7q6s6`4O6|7j6y6N3I6a0i6c7D3p1q2/1f2!2N0H1_2S5f4C2Z1w1n2.0R2:7Q7r1n4C7*2g0P0H0@372I5C3x7;7?6:5)232l0R7|6l7~2K5V7F010z0|0%0g607/4}250h3j8d6t2{0g0|0g0l2v1d8j870{040n8s753^0|0S3l7,8k1*8u0r8d0G8E8z040S5T2?8t0|0J0s8d0~8D3R7{017@2^3H3J5i8Y7J6;7 2b818Z7}701Y5 878h3K0G8`8x7t1*0v0H0|020O0l0X0c0E92949698950E8U8|2y8)0U7^3g5+8(7=8/836!3,0G80827a3+8=868y018 3j8`2p0w0x390M1v2x0G0s0G8B0G0(9N0i0G0v1d0c2z0R0l0Z9N0P0v0c0R0-1@0P0x9)9e8W4w9h9j0#5|9m9u7y3H449s8-9`7l5n9^8?9z9B8_8`0m2u0c9H9J0P1O9M0:0G0g1d2Fae2y2D0M0b0X0P1%0l2W9#9%1%9+9-1{0M9%2w0laA2Aah8o8q2y9/8P9;9n8!1 3H6a9_9o9v4p8,2ca06z0#aTa48}0@a69D9X9N0q9P9W8NaM7Q8XaP9i8#4G7`a_9p5n4H9~aZaV9{a|858e3Sa+9D0A0Z0R0k0j1$9La?3P5I9=a{3fa}a!7K4Yb28.8*5P6C3/87ba8`aJam0n0B0i0r0G0DbH0pbH0f0y0r0B0qbH0d0y0J0Gaoaqas0GbQbHbGbIbKbM0ybj2Jbla_9?6PaUbv6!4@btbq57b;a(8f8~90a70G9b9a939cc39d7,8VaN7:b/bn6$b=8:5n59b_b4a13Hcf5.caa@aO7|9?5rbpcla#cvckb?5ncvb7a,8K3T0|0M8C2;8J870X0|0e8IcG0M0V8A299f3S8u8w9:a)cH8McKcrc$8u0Jb,b8bmaR6A5Ecga 5C3icAchc_9xc1cScI8O3pcM9zcO04cQ7,d4c$cTcV1ec#b~0@cZcX5Z8Ad2bk8Q04c-c9cXc:0M5C8%319hc^6A22c{dz5Qc~cF870M8A9%cRcNcPdL9z8u0Bb+d9cG0t5E030G2V2w0P3V9$0Y9KaH31bC1OaHa/9Q8N8JdrdfdYcdc;3h9ldxa~aWd{aYbuc|6A9l5.dG9zdI040Pc)3Pdadg01d6d8cLcG0k0P0|5sdT87dV0|dX2V1v0t1%930P9T0R0w9W0W0G1~0w390l0w0P0wa.c.b.ctbn0q9^d}b`5{e1eV6!eSdF9Dd0eadm2Jee3SehdOc$elene.efer04et9I0Pew0GeyeAeC0GeEeGeIeKeMa=d?cb9gd_du6AaTeUcx7K0q4qdCd fie#8{8789040h1Q1$e=4x0|ebfv5fd6020S96fz5=cIece*cG0X8^1 0HfF63fxe)3KfK91fDc8ejdHd1fP258u8Tf8c*faeQd`6ncwcB5Cb19tfg6m6o3Na,e7c$fq0P8cepe88AfIb85fdQdjfGeag4cG8udSfYd5fVfEg1dbdlg84~g7d@dke(gmf$0|0yf(6sd@dt5Cbxfff:6Absf?gD3hbxe6f{gLe%0,0cgs1*d60!gQ8L0Y0j0j29fOgp4)dig#fQc(gU01gof9fwgag+gddqgxg.gz6Of/e33hb^gGg|0qb|3ngLgMfZg:gjefe-h8g/fyhbfA0|0Lf#1*e:5FeOa^f,fc6#g{dD0qcjg hscoh3h4cGfq3b0v0Rhidh0|gw49gyfb8$6?c@d 6=eXf@5PhQcEh4f|efe9gOg+gSg+e9gWgY9Ig;0|c!g.gqf7h/g$0|0Bh%fRh,04bUhmcs8/9?71hrhPc`hvi4fnhWe+gq0PfSia4)hagfgkgrheifhghF01hkg4cqdnh aQhp7ci3b53IdBi6iyiwhVfo9zf~g0ihhYfxg4ie4~eheid3e%cJh{hI5XhKho8$d|d^eY7b9riBcm3g7oi8hX3Sfq2D0ceJdeiJg/h!ikiOimi{2{glg(gt04h^j13uh`j5hG040sgehJg^hLi+eTi#hS709}i)a#7Bi8hAfxiIiRh6iciniPine90MfSgchHh~cciYi+fejigH7NhRjKa%hyh5iG0|i;i?jydJgPi~gRi}i^h:gbdoj4h=g)hdj*j2jbeO0K7.7R7)7T7$1f0c7Wj`2Q2L0Y1#j@0K7U8V0%0)0+0v04.

😥 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

.128013vt4=8fw2pmuP(751,:cSsré]kE[63;0 dg)/+n9qiyelh_bàoax.-050H0R0c0Y0P0S0v0G0t0S0Y0v0v0e010c0P0j010406050v0l0k0k0Y0w0Q040u0X0S0l0_0X0M050K101214160~0j04051m1f1p0K1m0~0H0P0b0.0:0=0@0:0M0I0l0Y0I0R0#0j0Q0c0T1d0G0T0P0I0T0S1R0T0c0|050)0V0S0R1y0;0?011Q1S1U1S0c1!1$1Y0c0w1n1M0.190v0j0Y0M0@0i011(1A010g0+0R0M0Y0k0R1Y1}1 241*271$2a2c0|0a0G0m0w0X0j0X0v0P1c0M0G0%1{0w0w0R0t2x1f2f0M1n0K1M2K1@1_1^1Z0H2h1B0P0M292u1Y1v1x0/1)2U2W0M0X2!1Y0j2D1n2I2K2;0 1~2y2$252*0w130S1Y0Y1P2D0g0@030U0U0t2+0R1U2)0X0#0f0#0q0|0G0q1f0Y2=2^0}2@2g2`1*2|2~30320R340136383a3c2X3f0#22040G0i3m3o1 3q2I2T013v0Y2 1n310T333537390%3F2*3H0D3j0D3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0d3j0d3/1g3;3r2_1z3u0X2}3V3x3Z3z3#3D3(413*3g0p3j0p472;3=2^3S3_4h3}3C3%3b4n3e3g0C3j0C4t493?4c3^4e3w3X3y3A4B403d3H0o3j0o4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0f3j0f4#2J4%4b2%4*4f3`3|4j3~4l4D4=0#0N3j0N4`3Q4w3@4 4Q3{4S4k4C3)4F3h0F0|0q0F5c4|4x4+515j545l4E3H0q3i045D5t4a5v504z534U4;423h3J0q3M0K3n3:4$5I5f4y4-4A4:565P0q3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570q4H5F4J6d4u5;636i5#5M5%683g0q4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570i5p046=5H6g4d6-655_5O6!0i5E716_6+6{5h6}5z6Z5n0i3J7c744(6V775y5N5(705+0i5-5V6e6*7g6,7i5^796 7b5|0i5~7q6s6`4O6|7j6y6N3I6a0i6c7D6G7t764,6.6Y7y3H0i6o7Y7f4}7u7T787k6z3I6C0i6E7P6T7R7G7v6L6l5P0i6P7{5c1q2/1f2!2N0H1_2S5f4C2Z1w1n2.0R2:3p601n4C8e2g0P0H0@372I5C3x8l8n6:5)232l0R8t7_6!5E3/7F010z0|0%0g8g6t250h3j8K8E0M0g0|0g0l2v1d5T2?8E0{040n8P753^0|0S3l7r8j7$1*8#0r8(7=3T8+8Y8f8!0|0J0s8g0~8.5I8s018o2^7X8r8m968u708w2b8y9c8A7b1Y5 8E8N3K0G9q8@8:0@0v0H0|020O0l0X0c0E9y9A9C9E9B0E919s0G95971 3+9a8z7a9Q0G8x9S7W3g5+8D8)019v3j9q2p0w0x390M1v2x0G0s0G8,0G0(9@0i0G0v1d0c2z0R0l0Z9@0P0v0c0R0-1@0P0xa99K933R9N0U8p439R9i9Tal9V9g9X7l5n5|9#8^9(9p9q0m2u0c9.9:0P1O9?0:0G0g1d2FaG2y2D0M0b0X0P1%0l2Wa5a71%abad1{0Ma72w0la$2AaJ8U8W2yaf8Z4waiak0#6a5iai9j3H4qaq2cas7+a{9m9$ay9*a19@0q9_a00S8{5Xaga@9b9O0M3H6oa|bk9d5n4Hb19h7J57bob6ax9waz0G0A0Z0R0k0j1$9=a=8|bj8ta_6Cbpb37K4YbubS57bQbz9t9%bBb9a/aO0n0B0i0r0G0Db-0pb-0f0yb-0B0qb-0d0y0J0GaQaSaU0Gb_b-b,b.b:b=0ybL3P94bqa_6PbRan9Y3f9fb2ciat3HcgbZ3Sb89*9H9G9z9Icv9J8.92a?8kce983g6$chbw5P59bVcn7+cI5.b98L3u0|0M8-2;0GcT0@0X0|0e8gcZ8Q0V8+299L5f8#8%bi8^0M8+cXbM8^8#0Jcb2JcdbOcG5oamcK8B5pcNd65n5r9l3ncS8QcVbg2Jc*9$c$04c(8.dkc@c,042kc/4)c;dv638`dy25c}c 8/9McF9P6A8C31a}ao3h3id9br5C8CcR9*c!8_dta7c)dWdmdocYdW8#0BcadpdW0t5E039M0M2w0P3Va60Y9;a-31b(1Oa-bc9`bfcZcB9La^d35Sd5dR6A22dQa~edddbCdWc^040Pc`3Pdqb!d$d!8E0k0P0|5sd-8Ed/0|d;2V1v0t1%9z0P9}0R0wa00W0G1~0w390l0w0P0wbbdEd19ca_5*ebeg3h3,efdNe$2KdedVdgemdi3Kd#c%et9$evexe`8^eB04eD9/0PeG0GeIeKeM0GeOeQeSeUeWbfeYahdHbm6AavdLbqe(0q44e+cjfqeidf9$8G040h1Q1$e~b!elenfD3Sdm020S9CfH5ZcVeodjd#9o1 0HfN5=0|0Pe?eqfI9xfLcAd(e;0Mf!d)0|90e6c?2ye8dI3ha{fnbW5)b09WcO7K0qb5e/b99r8Efy0P8Jez9$el8,dB8;0|0Bgf8*emfQdFc:0|d,f*dlf%fMgbc@dAf=3Sd*gjdXfZgB8#0yf:6sgyf@fk3hbof{g06mbtf da5Cbyg4g5fwgwdY0cgBdm0!gBel0Y0j0j29fVgygo8$g)c_gEghg?glg^04b}fhbNe!e9bQgOgT6AbUgSec3hbYgWgXg6gcfYgmf#5fesgvfEhgfW4~dm0Lho25e|5Fg cEd2f^0qcgh4h9hAclbvhDcqhce:fx0|3b0v0Rhsgg04gH49gJfj5CcIhCfpcMh8h!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:dUgXiS8T4eiqgCj00X9o2Vj00Mds0w1 1Hh_g`gDi1hR8?iYi204f,g|8 hwiGib7X9!hZife*iOcj7oh(h)hegZ0,g#jfir04h/i9fOh=g,g.jcjFdXh}jJdwg_jPfFg|g~i8iFiKbl7Xfmj#i=frjwii3Iavi{g5i}042D0ceT1ejicUh,dpiEccfijqijf`j)e(7Ni@iL70g3ejg7fYiUi$ioe=j2i!j6dhi*joj)a_7YiejxgRark97bgVimhK8^fyaL0wklemj2j4j`iVfEj8jahPjPdxjVhnkP0|jhkKiujkgmi5jnjZk0h0j$ijh3k5ifh7kvh57,jzjAkhjDh-jHg`h?jNkTg=kRdtkZ8}04gil00PjXi7gIi-iH3IhBk,jx4@ih7+7{k=h*3Sfyj@j_kFk^k$d00K8i7 8d818a1f0c84lB2Q2L0Y1#ly0K82920%0)0+0v04.

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

.128013vt4=8fw2pmuP(751:,cSsré]k[63;0 dg)/n9qiyelh_boa-050G0P0c0V0N0Q0v0F0t0Q0V0v0v0e010c0N0j010406050v0l0k0k0V0w0O040u0U0Q0l0;0U0K050J0{0}0 110_0j04051h1a1k0J1h0_0G0N0b0)0+0-0/0+0K0H0l0V0H0P0W0j0O0c0R180F0R0N0H0R0Q1M0R0c0@050!0T0Q0P1t0,0.011L1N1P1N0c1V1X1T0c0w1i1H0)140v0j0V0K0/0i011Z1v010g0$0P0K0V0k0P1T1^1`1 1#221X25270@0a0F0m0w0U0j0U0v0N170K0F0Y1?0w0w0P0t2s1a2a0K1i0J1H2F1/1;1:1U0G2c1w0N0K242p1T1q1s0*1!2P2R0K0U2V1T0j2y1i2D2F2,0`1_2t2X202#0w0~0Q1T0V1K2y0g0/030S0S0t2$0P1P2!0U0W0L0W0q0@0F0q1a0V2-2:0^2/2b2=1#2@2_2{2}0P2 01313335372S3a0W1}040F0i3h3j1`3l2D2O013q0V2`1i2|0R2~3032340Y3A2#3C0C3e0C3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0d3e0d3*1b3,3m2;1u3p0U2^3Q3s3U3u3W3y3Z3|3#3b0p3e0p422,3-2:3N3;4c3^3x3Y364i393b0B3e0B4o443.473:493r3S3t3v4w3{383C0o3e0o4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0f3e0f4W2E4Y462Y4#4a3=3@4e3_4g4y4-3a3e0L4=3L4r3/4`4L3?4N4f4x3!4A3c0E0@0q0E564@4s4$4|5d4 5f4z3C0q3d045x5n455p4{4u4~4P4,3}3c3E0q3H0J3i3+3K1l2*1a2V2I0G1;2N594x2U1r1i2)0P2+3k5Q2E054x5+2b0N0G0/322D5w3s5?5^505g5{0F2g0P5~5u525y3*4H4_0z0@0Y0g5-5;4^200h3e6g5C590K0g0@1/0N0S0g0l2q186m6a200?040n6z584!0K0@0%0c6F4Z4_6C0I0r6g0_435R3M5}015_2:3C3E5c6X4+515J1}6226646Y5 5v3b6$5O6h3N6k3F0F6}6M6i1#0v0G0@020M0l0U0c0D7577797b780D6S6 0F6(0S5`3b3%4M7k665J3%6-27654Q7s1T6^6n4!723e6}2k0w0x340K1q2s0F0r0F6K0F0P0v0c0F0l2R7P0N7T0P7h6U5.6W5@6:7m0W3 7p7*6)603~1~637w5I4j7-7z5P6A71736|6}0m2p0c7J7L0N1J7O0+0F0g182A892t2y0K0b0U0N1Y7W1Y1P7!0F760N7R7T7P2|8r0c1Y6s0x7#7%3l8G5C7k7,4l7/7_6*7{4l7u6/7;6=0W8M3I6T2.7)5~7,4C8N6:7r7{4C8S8O7=0W8(696G4_7D820F7e7d767f8|7g8G8Z5,8#7+6!3b4T8)8U524T8.8*7x7{993I7F0F7B4_6I04198G9l7 0/0U0@0e6g9s8@2?0T6J247i596C6E8I9t3O6J7T9F4!6P7$8!4r8K970W4/9a6;524/9e9b5J9X9j7F9m206c040N6f9r9,3p0@9q2,9z6N209v04020Q799x9=9K0k0N5k9O6O0@6R927i9U1`3C0L5|7:9Z5Jai9$al7{ai2F3i9k9k9?0/9.2y0c0l0w9_3k9{703:9M6Lad9J9Tak7,5laj8/8VaPao8+5haPas8`aw019.360v8F9`a!6Cac4paeaN9V5xaQ9f7`aW3daU9ga_7}8`av9K9o0k9ya!9~a3a*b19^b49K9~0J0Jbb9A1#a60@5Na.aL5=a:ag3b5Ma?9%7{bsa{a^5w6@atau6~9Kay0ZaBaD3KaF4s0@6v6xbI7(bh0/9Ha92?6r0w6tbN8hbU1#bTbnaG9L046Kb#bS0@0Aa-94bRb*b3b(3N6C0y0I0sbg9|9@046s6u6wb!b_9G0@9I9Sc0aHb+9Nc79Pb/b-b@cja,b|0I9y935R0J5:5S5*5U5%1a0c5Xcy2L2G0V1Wcv0J5V6T0Y0!0$0v04.

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

.128013vt4=8fw2pmuP(j751:,cSsr]kE[63;0 dg)/+n9qiyelh_bàCoaL.!-050H0R0c0Z0P0S0w0G0u0S0Z0w0w0e010c0P0j010406050w0l0k0k0Z0x0Q040v0Y0S0l0{0Y0M050K12141618100j04051o1h1r0K1o100H0P0b0:0=0@0_0=0M0I0l0Z0I0R0%0j0Q0c0T1f0G0T0P0I0T0S1T0T0c0~050+0V0S0R1A0?0^011S1U1W1U0c1$1(1!0c0x1p1O0:1b0w0j0Z0M0_0i011*1C010g0-0R0M0Z0k0R1!1 21261,291(2c2e0~0a0G0m0x0Y0j0Y0w0P1e0M0G0)1}0x0x0R0u2z1h2h0M1p0K1O2M1_1{1`1#0H2j1D0P0M2b2w1!1x1z0;1+2W2Y0M0Y2$1!0j2F1p2K2M2?11202A2(272,0x150S1!0Z1R2F0g0_030U0U0u2-0R1W2+0Y0%0r0F3h0~0G0r1h0Z2@2`0 2_2i2|1,2~3032340R3601383a3c3e2Z3h3j24040G0i3o3q213s2K2V013x0Z311p330T3537393b0)3H2,3J0%0D3l0D3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0%0d3l0d3=1i3@3t2{1B3w0Y2 3X3z3#3B3%3F3*443,460q3l0q4b2?3^2`3U3|4l403E3)3d4r3g460C3l0C4x4d3_4g3{4i3y3Z3A3C4F433f3-0p3l0p4O3R4z3u4R3V4T4k4V4m4X424q4!460f3l0f4)2L4+4f2)4.4j3}3 4n414p4H4_3j0N3l0N4~3S4A3`534U3~4W4o4G3+4J3j3i0~3i5g504B4/555n585p4I3-0r0r5u3n0K3p3?4*4e5y544D574Y4^455s3L0r3O5K3Q4 5O5j4C4;4E4@5a5V3h3/040r3;5!5M5$4Q525)5m4=5o4Z5.0r485;4a5@4c5N5`2}5z5R4?595q5F4u5;4w662^1u2;1h2$2P0H1{2U5j4G2#1y1p2:0R2=3r5^1p4G6B2i0P0H0_392K5F3z6I6K6e5E465H0G2n0R6Q5D5b3k2M5L691,0z0~0)0g6D5%4-0h3l6.6(3{0g0~1_0P0U0w3d2G2I672L6/520}040n6?5i4-0M0~1W0w0c0R794,750~0J0s6D10726G2A6P016L2`3-3L5m7t5,6f46246V2d6X7u6R6!7y5@6@016;3M0G7R7i51270w0H0~020O0l0Y0c0E7Z7#7%7)7$0E7o7T0G7A6}7w465:7z6J7I6Z5.3/7F2e6Y604s3j7_7M7a527W3l7R0G7e7g0G0R7f2B1)0c0Q0j1)8e7h7q7p2^3T7=6M46637`825U8447256W8A5-8C8y877j7V7X7Q7R0!330g1f2H0P1Q2F0M0b0Y0P8o338p0G6{0R1)200x0G4i0H2F0:2t0P0@210c0#7/7q5O8v7@3j6h8z7|835r0%4u807H7B6S921!8K7U1,8a8O0G0A0S1(0G1d0-8^8o02030D0N0E3X0I4i2y0T2e8j8)0x0P0G8-0G6~1(8U1f0#0G0X9u9w0E8h0c9p2A6{0G7,7%2b9J0=0u0R9$7.8r7:90213-4L4V7=7}8C4L9a8G7C3j9@3=7N9j8c9#7!7-9-9-8}8t4A9;0M4#6O7{9c6!4$9}958B974$6$9k74276*048S0x6D0Gat3w0~0PazaB0_0Y7P2XaF7N0M0V0~0x211J7:5j76788~aMaO042maT4-aVa$5{7d8^7ga)27760JaL88270Y0~0%a=8L1,0k0P5ua.1,a:7n9/aXadai7?9=4`ah9~9d0%4{amaj5.4{ara5a5aG3VaD0M1x9+0Ua~1g7qaA7Na^040ea{9h3{aDab6C8ub88w5cbcan8H975dbh7J5.5dblbm7S7NavaxbD4B0~0ob$5jaIbqb*7baZaQ1F8qaca|0_a(b6b^bp04aEbxbobA0Lb.52a~b0b{bE01760tc42}aZa#c83Ub`b@c97ca!a,b?bIa?b27l7mcd1,0u5H04030G2F0u0T0R0xcD1)2C0S9T9x2XbscI0l0Gbv0P0k13bH3R8 bK913JbNbi8C5tbS9`975tbWbXc/c:c;c:bocx0~cA0H210/9o2F7fcI8$8dco0n0W2B8@7ga;b5ck7;cZba5scy94c%c,6U8FbO9 3hdh5!c=bYcr0_av0P6-c0aMa+d0b1b_0~0BdDb}b)chaU0~0ycvaH7Y0S7%dOb}8pdH76dGdK7bbqcObuaKdZ7k040yb44y9:deaf6T7y339_965F7Edmdjd`9f3pdsbmbocmcN0PbtbvdTbAbCdzdudIcW73bJ6QbL5/c$bTc(7 d|emc,86e0c/bodwdy2?byede4bre60Rd%bweyc10~0$ebeHdAb~dW0~d-3rezb|c^cz8gcDaR1)0wcL0E0-0G0Q0G330l2Y9)0l0/8n0{8f0b3X0R0l8.c{0M0wef7rddeic!62elc+5F48c*d_6T8Jete1e1c@cycA0=9J160{cId8d18d8%cof0cYf3df3h93d@b8f76T99epfC5s93drdse3dBa-d)a/dFdHe4ePd+ccecb|cmdVfOcs04dYdc5(d#eDeFfTdNfWc9eadTfYftf!dEf$fRf*e7d(f(a%dMfVeMeAfMcpcX7NdXf{eOf^cadMfu0K6F1s6n0K6p1h0c6rgm2S2N0Z1%6A6o6x7p0)0+0-0w04.

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

.128013vt4=8fw2pmuP(751:,cSsré]kE[63;0 dg)/n9qiyelh_bCoaL.-050H0Q0c0X0O0R0v0G0t0R0X0v0v0e010c0O0j010406050v0l0k0k0X0w0P040u0W0R0l0^0W0L050K0 1113150}0j04051l1e1o0K1l0}0H0O0b0-0/0;0?0/0L0I0l0X0I0Q0!0j0P0c0S1c0G0S0O0I0S0R1Q0S0c0{050(0U0R0Q1x0:0=011P1R1T1R0c1Z1#1X0c0w1m1L0-180v0j0X0L0?0i011%1z010g0*0Q0L0X0k0Q1X1|1~231)261#292b0{0a0G0m0w0W0j0W0v0O1b0L0G0$1`0w0w0Q0t2w1e2e0L1m0K1L2J1?1^1@1Y0H2g1A0O0L282t1X1u1w0.1(2T2V0L0W2Z1X0j2C1m2H2J2:0~1}2x2#242)0w120R1X0X1O2C0g0?030T0T0t2*0Q1T2(0W0!0q0q3e0{0G0q1e0X2;2@0|2?2f2_1)2{2}2 310Q33013537393b2W3e3g21040G0i3l3n1~3p2H2S013u0X2~1m300S323436380$3E2)3G0!0D3i0D3M2G3o0}3Q3s0?3T3V053X3Z3A3#3D2U3F3f0!0d3i0d3/1f3;3q2^1y3t0W2|3U3w3Y3y3!3C3%413)430p3i0p482:3=2@3R3_4i3}3B3$3a4o3d430C3i0C4u4a3?4d3^4f3v3W3x3z4C403c3*0o3i0o4L3O4w3r4O3S4Q4h4S4j4U3 4n4X430f3i0f4$2I4(4c2$4+4g3`3|4k3~4m4E4?3g0M3i0M4{3P4x3@504R3{4T4l4D3(4G3g0q0F0{5q5d4}4y4,525k555m4F3*3f5s3k0K3m3:4%4b5w514A544V4=425p3I0q3L5H3N4|5L5g4z4.4B4;575S3e3,040q3.5X5J2I1p2.1e2Z2M0H1^2R5g4D2Y1v1m2-0Q2/3o5=1m4D662f0O0H0?362H5D3w6d6f565n6i0G2k0Q6l5B583h2J5I4N4 0z0{0$0g685!4*0h3i6E6y2`0g0{1?0O0T2U0v0Q0w2F493O6F4 0`040n6J5f4*0L6N0X0U6%4)6Z0{0r680G6Y2`0U0{1T0v0c6.4~246!0J6?6^1)0W0{0!020I0c0E746K3t6`046|6~6W5?7f0?6!6=7l3p7r5L6k016g2@3*3I5j7v5)6n43216p2a6r7w6m5C7F1X5;7n016H3J0G7U6 3R0v0H0{020N0l0W7c7#7%7)7$7(7d7r0}7t3Q7C0T6h435-7B6e7K6t5+3,7H2b6s4W807O6x6(4 7Y3i7U0G1Z0G0Q6}2y1$0c0P0j1$7j0Q687;2=7?7}7x1~3*454S7@7 4p3g45827J7D7M8E876b701)8b7T7U0Y300g1c2E0O1N2C0L0b0W0O8o308p8e0w0O0x1$1}0w0G4f0H2C0-2q0O0;1~0c0Z8r7W7@7_3g4r8A8v7L6u4r8G845R8D0!953/7Q8P8d0G0A0R1#0G1a0*8{8o02030D0M0E3U0I4f2v0S2b8j8+0O0G8:0G6R6T2w0Z0G0V9u9w0E8h0c9p2x6O8g2x0j0/0t0Q8 7:9197930!4I969c5*9e4I9b7~859?8L750?9j8d7*7.a17,7+7/4v9+6l9-4Z9:9_9d5o0!4Z9^8I6uab3M9k9}016A048U0w7e892`0{2U1u9%au6/240W7S2UaB8N3^7h0w1~1G7W5g6!6$7=av1)0k0O5saO4*6!0saH4y7h2jaY6:6#a*aw041Za-1)720J7qa7aS6c9,7y4@6j978Caf4^ai985+4^6w8Q9k6@7Q6*043a0Q2b0L7k2:bbaT0?77040ea$5#6+6-a`aI016!0Ba;3^ax0Laz8qbv3R6!0y90bG92a}59a 9;7EbOb4b13*5ab8ba8daobd0Obr4*bobq7rblaC3tbCbEbK8t4xbM8x435qbPad9=afb`bT9`b~5rbXbYb,bwaq0h1P1#b%4 b#ccaD7!7ba63oc63RaV0{0Fcf767S1~0HcqbBa/6,bAbx0{bzbGbs04b$b+aobo0!cv01cn5.czbIcLbo7a7ccLbdbfbhbj677Q7pb;c!b?a|b^5p0qb{aj5+5Ec0ae5Dc-c4c5bZbcbtcPcBczcecDaZ0{bJcH7Qb)cVc}d2a+cCb=b-cwcGbkcI78cLcN5GdebwcQ9*bLc*0L5D7A308Bc1dv226qbQ8J3e7A5Xc`anc|cFcR0{b*didKdhckdj04cKd6bmcMaWcOdrdo9Kdt5D7{dxb0dzb_81dCb|bR5,8Lc`b!dad$aPc dba.dR6Xc#d4dMbpd9be1#cYc%6X0K6a5@655_621e0c5|ei2P2K6,1#2J5`7;0$0(0*0v04.

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