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

.128013TSo4l57s_60:.w/+phPn[1gk2c=iF)-tfàear39,8(d v]é;umbyq050R0J0G0K0C0f0i0S0A0f0K0i0i0B010G0C0r010406050i0X0Y0Y0K0L0!040c0d0f0X0_0d0u050p101214160~0r04051m1f1p0p1m0~0R0C0T0.0:0=0@0:0u0x0X0K0x0J0F0r0!0G0s1d0S0s0C0x0s0f1R0s0G0|050)0Z0f0J1y0;0?011Q1S1U1S0G1!1$1Y0G0L1n1M0.190i0r0K0u0@0z011(1A010H0+0J0u0K0Y0J1Y1}1 241*271$2a2c0|0a0S0t0L0d0r0d0i0C1c0u0S0%1{0L0L0J0A2x1f2f0u1n0p1M2K1@1_1^1Z0R2h1B0C0u292u1Y1v1x0/1)2U2W0u0d2!1Y0r2D1n2I2K2;0 1~2y2$252*0L130f1Y0K1P2D0H0@030j0j0A2+0J1U2)0d0F0w3f0|0S0w1f0K2=2^0}2@2g2`1*2|2~30320J340136383a3c2X3f0F22040S0z3l3n1 3p2I2T013u0K2 1n310s333537390%3E2*3G0M3i0M3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0e3i0e3.1g3:3q2_1z3t0d2}3U3w3Y3y3!3C3%403)3g0g3i0g462;3;2^3R3^4g3|3B3$3b4m3e3g0k3i0k4s483=4b3@4d3v3W3x3z4A3 3d3G0h3i0h4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0P3i0P4!2J4$4a2%4)4e3_3{4i3}4k4C4;0F0N3i0N4_3P4v3?4~4P3`4R4j4B3(4E3f0l0|0w0l5b4{4w4*505i535k4D3G0w0w5p3k0p3m3/3O1q2/1f2!2N0R1_2S5e4B2Z1w1n2.0J2:3o5I2J054B5Z2g0C0R0@372I5B3w5+5-545l5:0S2l0J5?5z565D2K5H4L4}0y0|0%0H5#5)4|250o3i69494w0H0|2D0A0s0J0L6l0J6f63250{040Q6r5d4(0u0|0,0G6x4%4}6u0O690S6g5e6A042*0Y0Z2D6E6b1*6H6J6L6z666T3R6W473O6K6s3t0|686(5$6+0@6u0E0m690~6/6a0S5=015.2^3G3I5h6~4/55413H235{5}4U78735G6|5e6d3J0S7l6#5e0i0R0|020#0X0d0G0W7s7u7w7y7v0W6_6#750j5/3g3+4Q7G5~783+5`2b5|6 5@5A7J1Y7g6Y4}7p3i7l2p0L0V390u1v2x0S0m0S6C0S0J0i0G0S0X2W7;0C7^1%0I0S2.0C4d0C5`1O1@0C0V0J0O876Q2D7?7^7`2y0V0f0V2c0u7_6p6o0s0V2z1 0-0:7}7 6K6{6`2?3Q7G7I0F437L5,7T7N4n8I7a7R7c4:788J3.6;017#7k7l2S7@7_1$0S0L1 0x2z0X2z0V0Z1b2z1%8y6k6m8s8c7?7_0H7;1%8+1D8@7;31272y2A8_2E8{6p8v0u8x7^7E6{6g8G714o5;8L765^9o7Q2c8S778O4p617h4(8Z7%822u0G7+7-842y7:8y0H1d2F9K8*290T0d0C1%0R8/0Z0d198b9L8B4t7F9q7H9n0F4G8K9w9s9/8Q9v8M7d8O9:8W6y7!7q8!0S0b0L0X1%2v8e6R1%8%9f8x311U7 8d0(0S0D3U0ia72V1d0n9j8E4v9m1 4W9p9=7V0F4X9u7S9raA4X9A7Z259D7%7B7A7t7CaN7D8C9+5?8H4?9;9`8T8O4?aDaz56aX3M9EaJ1*65040C6.2;6*9 2{6!6{a@6F250d0|0B0B6X8X6Na=5!8X6u6^aT9k8F9,8H58aYaF5658a%aZ9x5mbga+9E7%a-0@a/2D0G0X0L1ea{bt3S6B9ibca^6V0|0v7n6Z040RbL6G0|0Ub3bH0@a 04b1bTa}6,6O0d8f6qbbat5*be9.5qaybm9?b/blbi78b/9Aa,b40|0YbZ6UbVb0c06$0|6wbGb!3@a`a?bCbW0qc46M6-bP6t0|0Ecg4(bW0p0pcn4}0Y0C0|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!0p5(5K5Y5M5V1f0G5Pd#2Q2L0K1#dY0p5N6`0%0)0+0i04.

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

.128013So4l57s_x60:w/+phPn[1gk2cC=i)-tfear39,8(d v]é;umbyq050P0H0F0I0C0e0h0Q0z0e0I0h0h0B010F0C0q010406050h0V0W0W0I0J0Y040b0c0e0V0@0c0t050o0~1012140|0q04051k1d1n0o1k0|0P0C0R0,0.0:0=0.0t0w0V0I0w0H0E0q0Y0F0r1b0Q0r0C0w0r0e1P0r0F0`050%0X0e0H1w0/0;011O1Q1S1Q0F1Y1!1W0F0J1l1K0,170h0q0I0t0=0y011$1y010G0)0H0t0I0W0H1W1{1}221(251!282a0`0a0Q0s0J0c0q0c0h0C1a0t0Q0#1_0J0J0H0z2v1d2d0t1l0o1K2I1=1@1?1X0P2f1z0C0t272s1W1t1v0-1%2S2U0t0c2Y1W0q2B1l2G2I2/0}1|2w2!232(0J110e1W0I1N2B0G0=030i0i0z2)0H1S2%0c0E0y0E0v0`0Q0v1d0I2:2?0{2=2e2^1(2`2|2~300H32013436383a2V3d3d3h0y3k3m1}3o2G2R013t0I2}1l2 0r313335370#3D2(3F0K3h0K3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0d3h0d3+1e3-3p2@1x3s0c2{3R3v3V3x3X3B3!3}3$3e0f3h0f432/3.2?3O3=4d3_3A3Z394j3c3e0k3h0k4p453/483;4a3u3T3w3y4x3|3b3F0g3h0g4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0N3h0N4X2H4Z472#4$4b3?3^4f3`4h4z4.0E0L3h0L4?3M4s3:4{4M3@4O4g4y3#4B3f0l0`0v0l584^4t4%4}5f505h4A3F0v3g045z5p465r4|4v4 4Q4-3~3f205B3I0o3l3,4Y5E5b4u4)4w4,525L0v3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530v4D5B4F692;1q2-1d2Y2L0P1@2Q5b4y2X1u1l2,0H2.3n5|1l4y6E2e0C0P0=352G5y3v6L6N635x3e3g0Q2j0H6T6h5#1W5{6c1(0x0`0#0G6G5-4`0n3h6:6*3;0G0`110j0C0W0 0i2B0z0V0J2t6/6a2H6;230_040O6^5a5.0`1Y7g4!4`7d0M6G0Q7b3s6-0H0X197l4_7c0`7p79047r6_3P0`251c7D7s0=7d0D0m6G0|7L3N6S016O2?3F5N5e7V5Z643e206Y296!7W6U537!6)7h6=3h0Q7_7y3O0h0P0`020Z0V0c0F0U80828486830U7R7{7$0i6P3e5%7#6M7.6$4k0E3(7+2a6#5?8n8i7=7m237}7^7_2o0T370t1t2v0+0m0Q1Y0Q0H0h0F0Q0V2U0Q1S8O0H0M2x7v198M8O8T02030K0L0U2T1t0z1#0P0V2x0T7w8P2y0.0Q730r0H0J0z8~8X8c7T4s8e8g0E5^8j8s5K8n408q7-7%6V996(5R7G8z7E7_8M8P7J8%8)8+8-0C8/8Y8T2 9t8`2 8}8 910H942;7U8k7X1}3F669b8l8t5j4m9g9c5!8n9R8w7z1(9o9q2n2s0F8E8G0C1M8J8{0G1b2D9:2w2B0t0R0c0C1#1!0Q6}6 0 9A8{8U0F1#7k7D7S9L969N8f7Y4C6Rah8m5j4D9X9T9dao9l6J9%0=9)9q8988818aaA8bad8dah984U4N8ean4T216Z9Y7(0EaK3J9*7M016,040C782/7F7?2_7u8^7qaX0c0`0B0Ba-7G0t7I2Ta?a)1(7d7Q7Da(8x1(0z5A030Q0A0/9A0X0/1#8R0Q0h0H0V0e0Q0T0e0T2a0t0F9K6F9M6T984:aLam9U3F4:aq9i53bwaV9*9qaXaZ2B0F757Ka%aXa^04acafb27N0`0u7{5Va+7x95bV017d0Sbr3L5E97aj54alaR9j55bC7/5L552I3laW7GaZ39bgbZ4#a~b,7abt7.985nb=ar9Z5jccb_aN6W5lb}9pbHb1aw7H040W0)a00Va{b(a/04a=b0aX7d7fb%cqbR0#a,cC7Gcz0pcxcHa_bObsa|bW040DcP3Ocz0o0ocY5bct0`5P4qaHbub:5zcdbD5#6XaQceaSc:cmco7`a@0`0jc%4#czcBbPc cs0I6~700W722C7577c47n0`cFbUcQbS0I0Xdh7A047Cd6cUcrcJb$dl3O7od25 6|cubhdqa}0`cXaGcG0Qb/9P6W7!2 aMbzdQaP7,b?6i7;b~c}bQ0`0YdC23d4d*7td8da7173dfa#dHcVdkcTb(bRbTd{cqdBcLdvbRct1SdGe2cy0`cOe8cqc)5Bd^b)7Bd-3;cReg7Oc7avdNaIc/8idSbyas5y8pc^c=8n5$auc}cp3OaZd@ec4td0ej01cz020e84d53neFb!04d)dM5bc6dLdzdO0t5y9aeudY5@dW8rc_9j0v9a5*eEb dvbK0$bNeMbReXc,dMe%65c;b`eB9Wezf6cg9#d#cobJ0`c29JeYc50`a f1e$erdP3f6k9SeAcgapf9cjfreDe^c~e`0`bLe}eJeVd1e#6F0o6I1o6q0o6s1d0F6ufS2O2Jdo1!2I6s7S0#0%0)0h04.

À vous de jouer 3 :

Compléter le script ci-dessous :

Évaluations restantes : 5/5

.128013So4l57s_xN60:w/+phPn[1gk2c=i)-tfear39,8(d v]é;umbyq050P0H0F0I0C0e0h0Q0A0e0I0h0h0B010F0C0r010406050h0V0W0W0I0J0Y040b0c0e0V0@0c0u050p0~1012140|0r04051k1d1n0p1k0|0P0C0R0,0.0:0=0.0u0x0V0I0x0H0E0r0Y0F0s1b0Q0s0C0x0s0e1P0s0F0`050%0X0e0H1w0/0;011O1Q1S1Q0F1Y1!1W0F0J1l1K0,170h0r0I0u0=0z011$1y010G0)0H0u0I0W0H1W1{1}221(251!282a0`0a0Q0t0J0c0r0c0h0C1a0u0Q0#1_0J0J0H0A2v1d2d0u1l0p1K2I1=1@1?1X0P2f1z0C0u272s1W1t1v0-1%2S2U0u0c2Y1W0r2B1l2G2I2/0}1|2w2!232(0J110e1W0I1N2B0G0=030i0i0A2)0H1S2%0c0E0K0E0w0`0Q0w1d0I2:2?0{2=2e2^1(2`2|2~300H32013436383a2V3d0E20040Q0z3k3m1}3o2G2R013t0I2}1l2 0s313335370#3D2(3F0K3h0K3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0d3h0d3-1e3/3p2@1x3s0c2{3T3v3X3x3Z3B3$3 3(3e0f3h0f452/3:2?3Q3@4f3{3A3#394l3c3e0l3h0l4r473;4a3?4c3u3V3w3y4z3~3b3F0g3h0g4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0N3h0N4Z2H4#492#4(4d3^3`4h3|4j4B4:0E0L3h0L4^3O4u3=4}4O3_4Q4i4A3%4D3f0m0`0w0m5a4`4v4)4 5h525j4C3F0w3g045B5r485t4~4x514S4/403f3H0w3K0p3l3.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 6S6f6U6I6v6K550z5n046:5a1o2-1d2Y2L0P1@2Q5d4A2X1u1l2,0H2.3n5~1l4A772e0C0P0=352G5A3v7e7g6.5%212j0H7m6j7o2I5T6e1(0y0`0#0G796r230o3h7D7x3?0G0`110j0C0W0 0i2B0A0V0J2t0G0i0R5R2;7J010_040O7I6)3s0`1Y7,4$4|7)0M790Q7E7.040#0X197_7{0=0c0`0B817%0y0A0`0k1b0H7;4{237@877-3?0`251c6c2H7`7%8404868p3I8201898b8d8f3Q7)0D0n790|8w5G7l017h2?3F3H5g8M6w6L3G7p297r8N7n6Y8R5}7%7G3I0Q8,8D5d0h0P0`020Z0V0c0F0U8?8^8`8|8_0U8I8D8T0i7i3e5)8S7f8!7t6Y3*0Q7q7s6X5l988(8k018:3h8,2n0J0T370u1t2v0+0n0Q1Y0Q0H0h0F0Q0V2U0Q1S9E0H0M2x0H7 9F9D9F0e02030K0L0U2T1t0A1#0P0V2x0T9Q9O9J2 7T0s0H0J0A9;9N928K3P94960E5`999h5M6Y429f8Ya25$a41W9l7=239o8+8,0$0Q8n9J9V9X9Z9v0C9$9-0.aj2Tas9/2C9;9?9;9`7$4u9}8P4n7k9a8U554oa62aa86x0E683-7%af9q2n2s0F9u9w0C1M9zat0G1b2Da$2w2B0u0R0c0C1#1!0Q7N7P0 aw9J0C9L9A0I0XaC789|aJ95aG0E6ma19b9i3F4FaN8ZaK5Nbbac8g1(aV9q8 8~8@90br918w8JaD7db79~6Abcbj6Y4WbhaP8VbD5,aW8y7z040C7C8w8r9m0u7A9P80bT8y8t0B8v2/bUad7y8a048c2U8.4%7)8Hbx93bBb96NbE8#5l4=bIbda3b ab3laWbN7%bW7}bY0F8jb+8385cebn0=0W0C0`5qb^9{aEb`1}3F6!b}9c5l57c1bFcyc5agb*cj8z0`bRci4v8m2TcK5db$b(3ncF3Q8Ab.8Ccqcf7(0`b@6qcY2waFct6y6;cwbec,8XaOc2a95l5pcDc79q8yca8ncO4%b$d0610X0`2ib;7?0`7+c(cL047:dc5d8Fd8238t0Edj1(cl5ob43N8Lcs0u5A5Cc.c3dwc;bib~dA7vcEbOcIbSb)c}bX9Qd3dk85cR3NcT5XcM8odK7%b?dr2Hdt7m9~5QaIbJ6k20cAdD6y8%c6c{dT4%bP2B0F7VdWcSdLdeb2dn0=7)0ve23RdMbZbzcG7)0Sd!7cc)du5A982 94cxeidBd+5%9kd=8-880`390h8edgb=c#eed$8!d(a0ekb7em6ya59gc?aQ0wa0bMd?d cl1S0H0VdO1(d2b!dYdae6ca7~e9d~8s0`0qeY8l04c ezd9040De:018t0p0pe{dp6=eCb6d%b90waSeHep6Yf7eoeN8VfcdFd?d@610`0je{e!dXbV7M0I7O7Q0W7S2C7V7X7Z7#b59m7)dbeadddffGdh0`7^e#fqcbdNe@8hfLe{caeUa?eXfR1(dicpfGc*dv6ybbf9fe6kbgeMcB5Ablesc7d 0YfnchfNcZfVfsa{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:fleC0p7b6^766`731d0F6}hT2O2Jb21!2I6{8J0#0%0)0h04.

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

.128013So4l57s_x60:w/phPn1gk2c*=i)-tfear39,8(d vé;umbyq050N0F0D0G0A0e0h0O0x0e0G0h0h0z010D0A0p010406050h0S0T0T0G0H0V040b0c0e0S0;0c0s050o0{0}0 110_0p04051h1a1k0o1h0_0N0A0P0)0+0-0/0+0s0u0S0G0u0F0C0p0V0D0q180O0q0A0u0q0e1M0q0D0@050!0U0e0F1t0,0.011L1N1P1N0D1V1X1T0D0H1i1H0)140h0p0G0s0/0w011Z1v010E0$0F0s0G0T0F1T1^1`1 1#221X25270@0a0O0r0H0c0p0c0h0A170s0O0Y1?0H0H0F0x2s1a2a0s1i0o1H2F1/1;1:1U0N2c1w0A0s242p1T1q1s0*1!2P2R0s0c2V1T0p2y1i2D2F2,0`1_2t2X202#0H0~0e1T0G1K2y0E0/030i0i0x2$0F1P2!0c0C0d0C0t0@0t1a0G2-2:0^2/2b2=1#2@2_2{2}0F2 01313335372S3a0C1}040w3g3i1`3k2D2O013p0G2`1i2|0q2~3032340Y3z2#3B0I0@0I3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0d0@0d3(1b3*3l2;1u3o0c2^3O3r3S3t3U3x3X3`3Z3b0f0@0f402,3+2:3L3/4a3?3w3W364g393b0k0@0k4m423,453.473q3Q3s3u4u3_383B0g0@0g4D3I4o3m4G3M4I494K4b4M3^4f4P3b0L0@0L4U2E4W442Y4Z483:3=4c3@4e4w4+0C0J0@0J4:2F2)0F2F2V2I0N1;2N3-014v2U1r1i572+3j3)3I054v5m2b0A0N0/322D3B3d4K5u5w4~3Y4y3c1~2g0F5D4v5F5z1T0o3h433L0v0@0Y0E5o2E5S5f0n0@0O5Y5s4?2?0E0@0F0j2o0i2y0x5)5!4Y0?040M5^4F4@0s0@0j5~4p5f5{0K5)5(5 2?0@19415p6b1#5{0B0m5)0_6f5Z3K5C015x2:3B3D3;0O6r4)4 3{3C5I265K6s5E4x6v5P5R6h0/5$040O6R5(6o5*3L0h0N0@020W0S0c0D0R6!6$6(6*6%0R6m645t5v6H5y3b3#5B6?6A5N6_6E275L4O6C6`3(6N016X5%6S2l0Q340s1q2s0O0m0O0j0O0Z0O2t0h180D2u0F0(240;0F0H0h6:6U5S6z0i6^3a3r7E5M6J3|706G6}7L7H2F6M654Y796Q7b2p0D7e7g0A1J7j0+0O0E182A7%2t2y0s0P0c0A1Y0j0y0y6e4n6;2t7E7G4j6{724*6C4j7o6F856B4h0C83767U4@7W6S0O6-6,6#6.8m6/6U6n2.6q6|7F6u4z7I8w7K504A89716H8C6C4A7S7X6R5_4@5U040A5X6U6a8h6c047}3j8V4X4@0c0@0z0z698O200T0A0@0l7 3L5{6l8s8?818y0C4R848H738d4R8F7O6I508 3G8k8k8-1#8Q2y0D0S0H8Z3I8#5+1#8/3e7B8u4p8|1`3B4-907P504-958b6~0C9x9a6S9d0/8Q360h0F8,778^9r5n8v5D7G529y976C529C91868d9X9H9b9m5T0@9g9i9k2E9-5f6104638U9J018(040y9P8W3o5.5:0c5=2z8?660@5}7C779_9{9s8$2067a2aja48Yam9n0/9 0Caq3L9p043faea30/6j9S5p0o5r1l2*1a5a1a0D5caM2L2G0G1W58aK5j6n0Y0!0$0h04.

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

.128013So4l57s_x60:w/phPn1gk2c*=i%)-tfear39,8(d vé;umbyq050O0G0E0H0A0e0h0P0x0e0H0h0h0z010E0A0p010406050h0T0U0U0H0I0W040b0c0e0T0=0c0s050o0|0~10120`0p04051i1b1l0o1i0`0O0A0Q0*0,0.0:0,0s0u0T0H0u0G0D0p0W0E0q190P0q0A0u0q0e1N0q0E0^050#0V0e0G1u0-0/011M1O1Q1O0E1W1Y1U0E0I1j1I0*150h0p0H0s0:0w011!1w010F0%0G0s0H0U0G1U1_1{201$231Y26280^0a0P0r0I0c0p0c0h0A180s0P0Z1@0I0I0G0x2t1b2b0s1j0o1I2G1:1=1;1V0O2d1x0A0s252q1U1r1t0+1#2Q2S0s0c2W1U0p2z1j2E2G2-0{1`2u2Y212$0I0 0e1U0H1L2z0F0:030i0i0x2%0G1Q2#0c0D0f0D0t0^0P0t1b0H2.2;0_2:2c2?1$2^2`2|2~0G3001323436382T3b0D1~040P0w3i3k1{3m2E2P013r0H2{1j2}0q2 3133350Z3B2$3D0J3f0J3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0d3f0d3+1c3-3n2=1v3q0c2_3R3t3V3v3X3z3!3}3$3c0f3f0f432-3.2;3O3=4d3_3y3Z374j3a3c0k3f0k4p453/483;4a3s3T3u3w4x3|393D0g3f0g4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0M3f0M4X2F4Z472Z4$4b3?3^4f3`4h4z4.0D0K3f0K4?3M4s3:4{4M3@4O4g4y3#4B3d0l0^0t0l584^4t4%4}5f505h4A3D0t3e045z5p465r4|4v4 4Q4-3~3d3F0t3I0o3j3,4Y5E5b4u4)4w4,525L0t3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{443L1m2+1b2W2J0O1=2O5b4y2V1s1j2*0G2,3l5|1j4y6r2c0A0O0:332E5y3t6y6A635x3c3e0P2h0G6G5w535A3+5~210v0^0Z0F6t5-4`0n3f6Z6T3q0F0^0G0j2p0i0O0I6(5a4#0@040N6?4!5 0^0j6|4_216_0L6t0P6!2@0^1a6a2F781$6_0C0m6t0`7c6w2u6F016B2;3D3F5e7o5Z643c1~6L276N7p6H537t5{6)0:6$3G0P7M713O0h0O0^020X0T0c0E0S7T7V7X7Z7W0S7j7O7v0i6C3c5%7u6z7D6P5L3(7A286O5?4k0D7/7H6@4`7Q3f7M2l0I0R350s1r2t0)0m0P0j0P0!6L0P0h190E2v0G0)250=0G0I0h7)7l5E7+7-0D5^7:7{5K7}407_7C7w6I8B1U806}21837L7M0r2q0E898b0A1K8e0,0P0F192B8Z2u2z0s0Q0c0A1Z0j0y0y7b4q7*7;7q1{3D668D7=7|5j4m8I8E5!7}908O721$8R850P7$7#7U7%9h7(7l7k2/3N8z7r4C6E8|7E5L4D96928F5j4D2G3j9f7e0:6V040A6Y7l777I3P7a769H010c0^0z0z9S9P0U0A0^5o8x9P6_7i9n8{6G8A4U4N7+7?7}4U9z8K539;3J9f9G9P9J2z0E0T0I8_3l9O81219#5m8w9p4s9r8~4/9u977x0D4:9`9w7}4:9E3m9)ag9v8A559=9v9@5j55apaC3Daz9~859T9J4z9M2-a98P3q9R9N9T9V040B9Zaa1$ac045PaPaV9W9YaU9!9$049(afaR0:9+ae6s9qax9s5kak9A985j5n1 6Mal8Lb3at9 aK9P0s0^0HaZa?9U9Wbg9c3;6,6.0c6:6=avbh6_6{bsbl9Q0470bw3O74bk4taTa)9PaW0o0obE5ba$a(a`a!a@0^0Ca_6ba{9/a}5za 9{5#6Kb5b0amb!b9baaQbxa20!a5a73Lb/bF04bfa-bRbi040ybM5.bebV7dbX7D8A5Ob#aqb27zb)b$7}caat9obQ6xa|ai3d7/2}9?935y7^cfcccu8N9Fbbb~aM1QaOa89Tbd04b@2Fb_5baWaYb}bhbOc24`aW9XcTaba/3hbB5ba^9-bBah0s5y8CcraBct6J8HcwaGc;cz8S9 cHc4cQbxcVcXaS046-6/6;7Oc$0^bva=bxcIbAdbbC0^75c~dg6`d7c3cJdmcU0^0DdpcYadc#6^bTd10:bJbLdjbNa/bPbWb~7gc57m0Pc*65cbc@3d95c?c:dRc_b.cM4#b;a4a6dzbydecGbI0^c1dDdnb|bHb~aWd-d;bhcId:458x0o6v6c6q6e6n1b0E6he42M2H0H1Xe10o6f7k0Z0#0%0h04.

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

.128013So4l57s_x60:.w/+phPn[1gk2c=i)-tfàear39,8(d v]é;umbyqE050Q0I0F0J0C0e0h0R0A0e0J0h0h0B010F0C0r010406050h0W0X0X0J0K0Z040b0c0e0W0_0c0u050p101214160~0r04051m1f1p0p1m0~0Q0C0S0.0:0=0@0:0u0x0W0J0x0I0E0r0Z0F0s1d0R0s0C0x0s0e1R0s0F0|050)0Y0e0I1y0;0?011Q1S1U1S0F1!1$1Y0F0K1n1M0.190h0r0J0u0@0z011(1A010G0+0I0u0J0X0I1Y1}1 241*271$2a2c0|0a0R0t0K0c0r0c0h0C1c0u0R0%1{0K0K0I0A2x1f2f0u1n0p1M2K1@1_1^1Z0Q2h1B0C0u292u1Y1v1x0/1)2U2W0u0c2!1Y0r2D1n2I2K2;0 1~2y2$252*0K130e1Y0J1P2D0G0@030i0i0A2+0I1U2)0c0E0g0E0w0|0R0w1f0J2=2^0}2@2g2`1*2|2~30320I340136383a3c2X3f0E22040R0z3m3o1 3q2I2T013v0J2 1n310s333537390%3F2*3H0L3j0L3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0d3j0d3/1g3;3r2_1z3u0c2}3V3x3Z3z3#3D3(413*3g0f3j0f472;3=2^3S3_4h3}3C3%3b4n3e3g0k3j0k4t493?4c3^4e3w3X3y3A4B403d3H0g3j0g4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0O3j0O4#2J4%4b2%4*4f3`3|4j3~4l4D4=0E0M3j0M4`3Q4w3@4 4Q3{4S4k4C3)4F3h0l0|0w0l5c4|4x4+515j545l4E3H0w3i045D5t4a5v504z534U4;423h3J0w3M0p3n3:4$5I5f4y4-4A4:565P0w3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570w4H5F4J6d4u5;636i5#5M5%683g0w4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570z5p046=5H6g4d6-655_5O6!0z5E716_6+6{5h6}5z6Z5n0z3J7c744(6V775y5N5(705+0z5-5V6e6*7g6,7i5^796 7b5|0z5~7q6s6`4O6|7j6y6N3I6a0z6c7D3p1q2/1f2!2N0Q1_2S5f4C2Z1w1n2.0I2:7Q7r1n4C7*2g0C0Q0@372I5C3x7;7?6:5)232l0I7|6l7~2K5V7F010y0|0%0G607/4}250o3j8d6t2{0G0|0G0W2v1d8j870{040P8s753^0|0e3l7,8k1*8u0N8d0R8E8z040e5T2?8t0|0D0m8d0~8D3R7{017@2^3H3J5i8Y7J6;7 2b818Z7}701Y5 878h3K0R8`8x7t1*0h0Q0|020!0W0c0F0V92949698950V8U8|2y8)0i7^3g5+8(7=8/836!3,0R80827a3+8=868y018 3j8`2p0K0U390u1v2x0R0m0R8B0R0(9N0z0R0h1d0F2z0I0W0j9N0C0h0F0I0-1@0C0U9)9e8W4w9h9j0E5|9m9u7y3H449s8-9`7l5n9^8?9z9B8_8`0t2u0F9H9J0C1O9M0:0R0G1d2Fae2y2D0u0S0c0C1%0W2W9#9%1%9+9-1{0u9%2w0WaA2Aah8o8q2y9/8P9;9n8!1 3H6a9_9o9v4p8,2ca06z0EaTa48}0@a69D9X9N0w9P9W8NaM7Q8XaP9i8#4G7`a_9p5n4H9~aZaV9{a|858e3Sa+9D0#0j0I0X0r1$9La?3P5I9=a{3fa}a!7K4Yb28.8*5P6C3/87ba8`aJam0P0v0z0N0R0LbH0fbH0O0T0N0v0wbH0d0T0D0Raoaqas0RbQbHbGbIbKbM0Tbj2Jbla_9?6PaUbv6!4@btbq57b;a(8f8~90a70R9b9a939cc39d7,8VaN7:b/bn6$b=8:5n59b_b4a13Hcf5.caa@aO7|9?5rbpcla#cvckb?5ncvb7a,8K3T0|0u8C2;8J870c0|0B8IcG0u0Y8A299f3S8u8w9:a)cH8McKcrc$8u0Db,b8bmaR6A5Ecga 5C3icAchc_9xc1cScI8O3pcM9zcO04cQ7,d4c$cTcV1ec#b~0@cZcX5Z8Ad2bk8Q04c-c9cXc:0u5C8%319hc^6A22c{dz5Qc~cF870u8A9%cRcNcPdL9z8u0vb+d9cG0A5E030R2V2w0C3V9$0J9KaH31bC1OaHa/9Q8N8JdrdfdYcdc;3h9ldxa~aWd{aYbuc|6A9l5.dG9zdI040Cc)3Pdadg01d6d8cLcG0X0C0|5sdT87dV0|dX2V1v0A1%930C9T0I0K9W0H0R1~0K390W0K0C0Ka.c.b.ctbn0w9^d}b`5{e1eV6!eSdF9Dd0eadm2Jee3SehdOc$elene.efer04et9I0Cew0ReyeAeC0ReEeGeIeKeMa=d?cb9gd_du6AaTeUcx7K0w4qdCd fie#8{8789040o1Q1$e=4x0|ebfv5fd6020e96fz5=cIece*cG0c8^1 0QfF63fxe)3KfK91fDc8ejdHd1fP258u8Tf8c*faeQd`6ncwcB5Cb19tfg6m6o3Na,e7c$fq0C8cepe88AfIb85fdQdjfGeag4cG8udSfYd5fVfEg1dbdlg84~g7d@dke(gmf$0|0Tf(6sd@dt5Cbxfff:6Absf?gD3hbxe6f{gLe%0,0Fgs1*d60ngQ8L0J0r0r29fOgp4)dig#fQc(gU01gof9fwgag+gddqgxg.gz6Of/e33hb^gGg|0wb|3ngLgMfZg:gjefe-h8g/fyhbfA0|0qf#1*e:5FeOa^f,fc6#g{dD0wcjg hscoh3h4cGfq3b0h0Ihidh0|gw49gyfb8$6?c@d 6=eXf@5PhQcEh4f|efe9gOg+gSg+e9gWgY9Ig;0|c!g.gqf7h/g$0|0vh%fRh,04bUhmcs8/9?71hrhPc`hvi4fnhWe+gq0CfSia4)hagfgkgrheifhghF01hkg4cqdnh aQhp7ci3b53IdBi6iyiwhVfo9zf~g0ihhYfxg4ie4~eheid3e%cJh{hI5XhKho8$d|d^eY7b9riBcm3g7oi8hX3Sfq2D0FeJdeiJg/h!ikiOimi{2{glg(gt04h^j13uh`j5hG040mgehJg^hLi+eTi#hS709}i)a#7Bi8hAfxiIiRh6iciniPine90ufSgchHh~cciYi+fejigH7NhRjKa%hyh5iG0|i;i?jydJgPi~gRi}i^h:gbdoj4h=g)hdj*j2jbeO0p7.7R7)7T7$1f0F7Wj`2Q2L0J1#j@0p7U8V0%0)0+0h04.

😥 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

.128013So4l57s_x60:.w/+phPn[1gk2c=i)-tfàear39,8(d v]é;umbyqE050Q0I0F0J0C0e0h0R0A0e0J0h0h0B010F0C0r010406050h0W0X0X0J0K0Z040b0c0e0W0_0c0u050p101214160~0r04051m1f1p0p1m0~0Q0C0S0.0:0=0@0:0u0x0W0J0x0I0E0r0Z0F0s1d0R0s0C0x0s0e1R0s0F0|050)0Y0e0I1y0;0?011Q1S1U1S0F1!1$1Y0F0K1n1M0.190h0r0J0u0@0z011(1A010G0+0I0u0J0X0I1Y1}1 241*271$2a2c0|0a0R0t0K0c0r0c0h0C1c0u0R0%1{0K0K0I0A2x1f2f0u1n0p1M2K1@1_1^1Z0Q2h1B0C0u292u1Y1v1x0/1)2U2W0u0c2!1Y0r2D1n2I2K2;0 1~2y2$252*0K130e1Y0J1P2D0G0@030i0i0A2+0I1U2)0c0E0O0E0w0|0R0w1f0J2=2^0}2@2g2`1*2|2~30320I340136383a3c2X3f0E22040R0z3m3o1 3q2I2T013v0J2 1n310s333537390%3F2*3H0L3j0L3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0d3j0d3/1g3;3r2_1z3u0c2}3V3x3Z3z3#3D3(413*3g0f3j0f472;3=2^3S3_4h3}3C3%3b4n3e3g0k3j0k4t493?4c3^4e3w3X3y3A4B403d3H0g3j0g4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0O3j0O4#2J4%4b2%4*4f3`3|4j3~4l4D4=0E0M3j0M4`3Q4w3@4 4Q3{4S4k4C3)4F3h0l0|0w0l5c4|4x4+515j545l4E3H0w3i045D5t4a5v504z534U4;423h3J0w3M0p3n3:4$5I5f4y4-4A4:565P0w3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570w4H5F4J6d4u5;636i5#5M5%683g0w4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570z5p046=5H6g4d6-655_5O6!0z5E716_6+6{5h6}5z6Z5n0z3J7c744(6V775y5N5(705+0z5-5V6e6*7g6,7i5^796 7b5|0z5~7q6s6`4O6|7j6y6N3I6a0z6c7D6G7t764,6.6Y7y3H0z6o7Y7f4}7u7T787k6z3I6C0z6E7P6T7R7G7v6L6l5P0z6P7{5c1q2/1f2!2N0Q1_2S5f4C2Z1w1n2.0I2:3p601n4C8e2g0C0Q0@372I5C3x8l8n6:5)232l0I8t7_6!5E3/7F010y0|0%0G8g6t250o3j8K8E0u0G0|0G0W2v1d5T2?8E0{040P8P753^0|0e3l7r8j7$1*8#0N8(7=3T8+8Y8f8!0|0D0m8g0~8.5I8s018o2^7X8r8m968u708w2b8y9c8A7b1Y5 8E8N3K0R9q8@8:0@0h0Q0|020!0W0c0F0V9y9A9C9E9B0V919s0R95971 3+9a8z7a9Q0R8x9S7W3g5+8D8)019v3j9q2p0K0U390u1v2x0R0m0R8,0R0(9@0z0R0h1d0F2z0I0W0j9@0C0h0F0I0-1@0C0Ua99K933R9N0i8p439R9i9Tal9V9g9X7l5n5|9#8^9(9p9q0t2u0F9.9:0C1O9?0:0R0G1d2FaG2y2D0u0S0c0C1%0W2Wa5a71%abad1{0ua72w0Wa$2AaJ8U8W2yaf8Z4waiak0E6a5iai9j3H4qaq2cas7+a{9m9$ay9*a19@0w9_a00e8{5Xaga@9b9O0u3H6oa|bk9d5n4Hb19h7J57bob6ax9waz0R0#0j0I0X0r1$9=a=8|bj8ta_6Cbpb37K4YbubS57bQbz9t9%bBb9a/aO0P0v0z0N0R0Lb-0fb-0O0Tb-0v0wb-0d0T0D0RaQaSaU0Rb_b-b,b.b:b=0TbL3P94bqa_6PbRan9Y3f9fb2ciat3HcgbZ3Sb89*9H9G9z9Icv9J8.92a?8kce983g6$chbw5P59bVcn7+cI5.b98L3u0|0u8-2;0RcT0@0c0|0B8gcZ8Q0Y8+299L5f8#8%bi8^0u8+cXbM8^8#0Dcb2JcdbOcG5oamcK8B5pcNd65n5r9l3ncS8QcVbg2Jc*9$c$04c(8.dkc@c,042kc/4)c;dv638`dy25c}c 8/9McF9P6A8C31a}ao3h3id9br5C8CcR9*c!8_dta7c)dWdmdocYdW8#0vcadpdW0A5E039M0u2w0C3Va60J9;a-31b(1Oa-bc9`bfcZcB9La^d35Sd5dR6A22dQa~edddbCdWc^040Cc`3Pdqb!d$d!8E0X0C0|5sd-8Ed/0|d;2V1v0A1%9z0C9}0I0Ka00H0R1~0K390W0K0C0KbbdEd19ca_5*ebeg3h3,efdNe$2KdedVdgemdi3Kd#c%et9$evexe`8^eB04eD9/0CeG0ReIeKeM0ReOeQeSeUeWbfeYahdHbm6AavdLbqe(0w44e+cjfqeidf9$8G040o1Q1$e~b!elenfD3Sdm020e9CfH5ZcVeodjd#9o1 0QfN5=0|0Ce?eqfI9xfLcAd(e;0uf!d)0|90e6c?2ye8dI3ha{fnbW5)b09WcO7K0wb5e/b99r8Efy0C8Jez9$el8,dB8;0|0vgf8*emfQdFc:0|d,f*dlf%fMgbc@dAf=3Sd*gjdXfZgB8#0Tf:6sgyf@fk3hbof{g06mbtf da5Cbyg4g5fwgwdY0FgBdm0ngBel0J0r0r29fVgygo8$g)c_gEghg?glg^04b}fhbNe!e9bQgOgT6AbUgSec3hbYgWgXg6gcfYgmf#5fesgvfEhgfW4~dm0qho25e|5Fg cEd2f^0wcgh4h9hAclbvhDcqhce:fx0|3b0h0Ihsgg04gH49gJfj5CcIhCfpcMh8h!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:dUgXiS8T4eiqgCj00c9o2Vj00uds0K1 1Hh_g`gDi1hR8?iYi204f,g|8 hwiGib7X9!hZife*iOcj7oh(h)hegZ0,g#jfir04h/i9fOh=g,g.jcjFdXh}jJdwg_jPfFg|g~i8iFiKbl7Xfmj#i=frjwii3Iavi{g5i}042D0FeT1ejicUh,dpiEccfijqijf`j)e(7Ni@iL70g3ejg7fYiUi$ioe=j2i!j6dhi*joj)a_7YiejxgRark97bgVimhK8^fyaL0Kklemj2j4j`iVfEj8jahPjPdxjVhnkP0|jhkKiujkgmi5jnjZk0h0j$ijh3k5ifh7kvh57,jzjAkhjDh-jHg`h?jNkTg=kRdtkZ8}04gil00CjXi7gIi-iH3IhBk,jx4@ih7+7{k=h*3Sfyj@j_kFk^k$d00p8i7 8d818a1f0F84lB2Q2L0J1#ly0p82920%0)0+0h04.

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

.128013So4l57s_60:w/phPn[1gk2c=i)-tfear39,8(d v]é;umbyq050M0E0C0F0z0e0h0N0x0e0F0h0h0y010C0z0o010406050h0S0T0T0F0G0V040b0c0e0S0;0c0r050n0{0}0 110_0o04051h1a1k0n1h0_0M0z0O0)0+0-0/0+0r0u0S0F0u0E0B0o0V0C0p180N0p0z0u0p0e1M0p0C0@050!0U0e0E1t0,0.011L1N1P1N0C1V1X1T0C0G1i1H0)140h0o0F0r0/0w011Z1v010D0$0E0r0F0T0E1T1^1`1 1#221X25270@0a0N0q0G0c0o0c0h0z170r0N0Y1?0G0G0E0x2s1a2a0r1i0n1H2F1/1;1:1U0M2c1w0z0r242p1T1q1s0*1!2P2R0r0c2V1T0o2y1i2D2F2,0`1_2t2X202#0G0~0e1T0F1K2y0D0/030i0i0x2$0E1P2!0c0B0I0B0t0@0N0t1a0F2-2:0^2/2b2=1#2@2_2{2}0E2 01313335372S3a0B1}040N0w3h3j1`3l2D2O013q0F2`1i2|0p2~3032340Y3A2#3C0H3e0H3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0d3e0d3*1b3,3m2;1u3p0c2^3Q3s3U3u3W3y3Z3|3#3b0f3e0f422,3-2:3N3;4c3^3x3Y364i393b0j3e0j4o443.473:493r3S3t3v4w3{383C0g3e0g4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0K3e0K4W2E4Y462Y4#4a3=3@4e3_4g4y4-3a3e0I4=3L4r3/4`4L3?4N4f4x3!4A3c0k0@0t0k564@4s4$4|5d4 5f4z3C0t3d045x5n455p4{4u4~4P4,3}3c3E0t3H0n3i3+3K1l2*1a2V2I0M1;2N594x2U1r1i2)0E2+3k5Q2E054x5+2b0z0M0/322D5w3s5?5^505g5{0N2g0E5~5u525y3*4H4_0v0@0Y0D5-5;4^200m3e6g5C590r0D0@1/0z0i0D0S2q186m6a200?040L6z584!0r0@0%0C6F4Z4_6C0A0l6g0_435R3M5}015_2:3C3E5c6X4+515J1}6226646Y5 5v3b6$5O6h3N6k3F0N6}6M6i1#0h0M0@020W0S0c0C0R7577797b780R6S6 0N6(0i5`3b3%4M7k665J3%6-27654Q7s1T6^6n4!723e6}2k0G0Q340r1q2s0N0l0N6K0N0E0h0C0N0S2R7P0z7T0E7h6U5.6W5@6:7m0B3 7p7*6)603~1~637w5I4j7-7z5P6A71736|6}0q2p0C7J7L0z1J7O0+0N0D182A892t2y0r0O0c0z1Y7W1Y1P7!0N760z7R7T7P2|8r0C1Y6s0Q7#7%3l8G5C7k7,4l7/7_6*7{4l7u6/7;6=0B8M3I6T2.7)5~7,4C8N6:7r7{4C8S8O7=0B8(696G4_7D820N7e7d767f8|7g8G8Z5,8#7+6!3b4T8)8U524T8.8*7x7{993I7F0N7B4_6I04198G9l7 0/0c0@0y6g9s8@2?0U6J247i596C6E8I9t3O6J7T9F4!6P7$8!4r8K970B4/9a6;524/9e9b5J9X9j7F9m206c040z6f9r9,3p0@9q2,9z6N209v04020e799x9=9K0T0z5k9O6O0@6R927i9U1`3C0I5|7:9Z5Jai9$al7{ai2F3i9k9k9?0/9.2y0C0S0G9_3k9{703:9M6Lad9J9Tak7,5laj8/8VaPao8+5haPas8`aw019.360h8F9`a!6Cac4paeaN9V5xaQ9f7`aW3daU9ga_7}8`av9K9o0T9ya!9~a3a*b19^b49K9~0n0nbb9A1#a60@5Na.aL5=a:ag3b5Ma?9%7{bsa{a^5w6@atau6~9Kay0ZaBaD3KaF4s0@6v6xbI7(bh0/9Ha92?6r0G6tbN8hbU1#bTbnaG9L046Kb#bS0@0sa-94bRb*b3b(3N6C0P0A0Jbg9|9@046s6u6wb!b_9G0@9I9Sc0aHb+9Nc79Pb/b-b@cja,b|0A9y935R0n5:5S5*5U5%1a0C5Xcy2L2G0F1Wcv0n5V6T0Y0!0$0h04.

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

.128013So4l57s_L06:.w/+phPn[1gk2cCj=i)-tfàear39,8(d v];u!mbyqE050S0K0H0L0E0e0h0T0A0e0L0h0h0D010H0E0r010406050h0X0Z0Z0L0M0#040b0c0e0X0{0c0u050p12141618100r04051o1h1r0p1o100S0E0U0:0=0@0_0=0u0x0X0L0x0K0G0r0#0H0s1f0T0s0E0x0s0e1T0s0H0~050+0!0e0K1A0?0^011S1U1W1U0H1$1(1!0H0M1p1O0:1b0h0r0L0u0_0z011*1C010I0-0K0u0L0Z0K1!1 21261,291(2c2e0~0a0T0t0M0c0r0c0h0E1e0u0T0)1}0M0M0K0A2z1h2h0u1p0p1O2M1_1{1`1#0S2j1D0E0u2b2w1!1x1z0;1+2W2Y0u0c2$1!0r2F1p2K2M2?11202A2(272,0M150e1!0L1R2F0I0_030i0i0A2-0K1W2+0c0G0w0k3h0~0T0w1h0L2@2`0 2_2i2|1,2~3032340K3601383a3c3e2Z3h3j24040T0z3o3q213s2K2V013x0L311p330s3537393b0)3H2,3J0G0N3l0N3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0G0d3l0d3=1i3@3t2{1B3w0c2 3X3z3#3B3%3F3*443,460f3l0f4b2?3^2`3U3|4l403E3)3d4r3g460l3l0l4x4d3_4g3{4i3y3Z3A3C4F433f3-0g3l0g4O3R4z3u4R3V4T4k4V4m4X424q4!460Q3l0Q4)2L4+4f2)4.4j3}3 4n414p4H4_3j0O3l0O4~3S4A3`534U3~4W4o4G3+4J3j3i0~3i5g504B4/555n585p4I3-0w0w5u3n0p3p3?4*4e5y544D574Y4^455s3L0w3O5K3Q4 5O5j4C4;4E4@5a5V3h3/040w3;5!5M5$4Q525)5m4=5o4Z5.0w485;4a5@4c5N5`2}5z5R4?595q5F4u5;4w662^1u2;1h2$2P0S1{2U5j4G2#1y1p2:0K2=3r5^1p4G6B2i0E0S0_392K5F3z6I6K6e5E465H0T2n0K6Q5D5b3k2M5L691,0y0~0)0I6D5%4-0o3l6.6(3{0I0~1_0E0i0h3d2G2I672L6/520}040R6?5i4-0u0~1W0h0H0K794,750~0F0m6D10726G2A6P016L2`3-3L5m7t5,6f46246V2d6X7u6R6!7y5@6@016;3M0T7R7i51270h0S0~020$0X0c0H0W7Z7#7%7)7$0W7o7T0T7A6}7w465:7z6J7I6Z5.3/7F2e6Y604s3j7_7M7a527W3l7R0T7e7g0T0K7f2B1)0H0#0r1)8e7h7q7p2^3T7=6M46637`825U8447256W8A5-8C8y877j7V7X7Q7R0j330I1f2H0E1Q2F0u0U0c0E8o338p0T6{0K1)200M0T4i0S2F0:2t0E0@210H0n7/7q5O8v7@3j6h8z7|835r0G4u807H7B6S921!8K7U1,8a8O0T0%0e1(0T1d0-8^8o02030N0O0W3X0x4i2y0s2e8j8)0M0E0T8-0T6~1(8U1f0n0T0B9u9w0W8h0H9p2A6{0T7,7%2b9J0=0A0K9$7.8r7:90213-4L4V7=7}8C4L9a8G7C3j9@3=7N9j8c9#7!7-9-9-8}8t4A9;0u4#6O7{9c6!4$9}958B974$6$9k74276*048S0M6D0Tat3w0~0EazaB0_0c7P2XaF7N0u0!0~0M211J7:5j76788~aMaO042maT4-aVa$5{7d8^7ga)27760FaL88270c0~0Ga=8L1,0Z0E5ua.1,a:7n9/aXadai7?9=4`ah9~9d0G4{amaj5.4{ara5a5aG3VaD0u1x9+0ia~1g7qaA7Na^040Da{9h3{aDab6C8ub88w5cbcan8H975dbh7J5.5dblbm7S7NavaxbD4B0~0Cb$5jaIbqb*7baZaQ1F8qaca|0_a(b6b^bp04aEbxbobA0qb.52a~b0b{bE01760Pc42}aZa#c83Ub`b@c97ca!a,b?bIa?b27l7mcd1,0A5H04030T2F0A0s0K0McD1)2C0e9T9x2XbscI0X0Tbv0E0Z13bH3R8 bK913JbNbi8C5tbS9`975tbWbXc/c:c;c:bocx0~cA0S210/9o2F7fcI8$8dco0R0J2B8@7ga;b5ck7;cZba5scy94c%c,6U8FbO9 3hdh5!c=bYcr0_av0E6-c0aMa+d0b1b_0~0vdDb}b)chaU0~0VcvaH7Y0e7%dOb}8pdH76dGdK7bbqcObuaKdZ7k040Vb44y9:deaf6T7y339_965F7Edmdjd`9f3pdsbmbocmcN0EbtbvdTbAbCdzdudIcW73bJ6QbL5/c$bTc(7 d|emc,86e0c/bodwdy2?byede4bre60Kd%bweyc10~0YebeHdAb~dW0~d-3rezb|c^cz8gcDaR1)0hcL0W0-0T0#0T330X2Y9)0X0/8n0{8f0U3X0K0X8.c{0u0hef7rddeic!62elc+5F48c*d_6T8Jete1e1c@cycA0=9J160{cId8d18d8%cof0cYf3df3h93d@b8f76T99epfC5s93drdse3dBa-d)a/dFdHe4ePd+ccecb|cmdVfOcs04dYdc5(d#eDeFfTdNfWc9eadTfYftf!dEf$fRf*e7d(f(a%dMfVeMeAfMcpcX7NdXf{eOf^cadMfu0p6F1s6n0p6p1h0H6rgm2S2N0L1%6A6o6x7p0)0+0-0h04.

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

.128013So4l57s_L60:.w/phPn[1gk2cC=i)-tfear39,8(d v]é;umbyqE050P0H0F0I0C0e0h0Q0z0e0I0h0h0B010F0C0q010406050h0V0W0W0I0J0Y040b0c0e0V0^0c0t050p0 1113150}0q04051l1e1o0p1l0}0P0C0R0-0/0;0?0/0t0w0V0I0w0H0E0q0Y0F0r1c0Q0r0C0w0r0e1Q0r0F0{050(0X0e0H1x0:0=011P1R1T1R0F1Z1#1X0F0J1m1L0-180h0q0I0t0?0y011%1z010G0*0H0t0I0W0H1X1|1~231)261#292b0{0a0Q0s0J0c0q0c0h0C1b0t0Q0$1`0J0J0H0z2w1e2e0t1m0p1L2J1?1^1@1Y0P2g1A0C0t282t1X1u1w0.1(2T2V0t0c2Z1X0q2C1m2H2J2:0~1}2x2#242)0J120e1X0I1O2C0G0?030i0i0z2*0H1T2(0c0E0v0v3e0{0Q0v1e0I2;2@0|2?2f2_1)2{2}2 310H33013537393b2W3e3g21040Q0y3l3n1~3p2H2S013u0I2~1m300r323436380$3E2)3G0E0K3i0K3M2G3o0}3Q3s0?3T3V053X3Z3A3#3D2U3F3f0E0d3i0d3/1f3;3q2^1y3t0c2|3U3w3Y3y3!3C3%413)430f3i0f482:3=2@3R3_4i3}3B3$3a4o3d430k3i0k4u4a3?4d3^4f3v3W3x3z4C403c3*0g3i0g4L3O4w3r4O3S4Q4h4S4j4U3 4n4X430N3i0N4$2I4(4c2$4+4g3`3|4k3~4m4E4?3g0L3i0L4{3P4x3@504R3{4T4l4D3(4G3g0v0l0{5q5d4}4y4,525k555m4F3*3f5s3k0p3m3:4%4b5w514A544V4=425p3I0v3L5H3N4|5L5g4z4.4B4;575S3e3,040v3.5X5J2I1p2.1e2Z2M0P1^2R5g4D2Y1v1m2-0H2/3o5=1m4D662f0C0P0?362H5D3w6d6f565n6i0Q2k0H6l5B583h2J5I4N4 0x0{0$0G685!4*0o3i6E6y2`0G0{1?0C0i2U0h0H0J2F493O6F4 0`040O6J5f4*0t6N0I0X6%4)6Z0{0m680Q6Y2`0X0{1T0h0F6.4~246!0D6?6^1)0c0{0E020w0F0U746K3t6`046|6~6W5?7f0?6!6=7l3p7r5L6k016g2@3*3I5j7v5)6n43216p2a6r7w6m5C7F1X5;7n016H3J0Q7U6 3R0h0P0{020Z0V0c7c7#7%7)7$7(7d7r0}7t3Q7C0i6h435-7B6e7K6t5+3,7H2b6s4W807O6x6(4 7Y3i7U0Q1Z0Q0H6}2y1$0F0Y0q1$7j0H687;2=7?7}7x1~3*454S7@7 4p3g45827J7D7M8E876b701)8b7T7U0j300G1c2E0C1N2C0t0R0c0C8o308p8e0J0C0T1$1}0J0Q4f0P2C0-2q0C0;1~0F0n8r7W7@7_3g4r8A8v7L6u4r8G845R8D0E953/7Q8P8d0Q0!0e1#0Q1a0*8{8o02030K0L0U3U0w4f2v0r2b8j8+0C0Q8:0Q6R6T2w0n0Q0A9u9w0U8h0F9p2x6O8g2x0q0/0z0H8 7:9197930E4I969c5*9e4I9b7~859?8L750?9j8d7*7.a17,7+7/4v9+6l9-4Z9:9_9d5o0E4Z9^8I6uab3M9k9}016A048U0J7e892`0{2U1u9%au6/240c7S2UaB8N3^7h0J1~1G7W5g6!6$7=av1)0W0C5saO4*6!0MaH4y7h2jaY6:6#a*aw041Za-1)720D7qa7aS6c9,7y4@6j978Caf4^ai985+4^6w8Q9k6@7Q6*043a0H2b0t7k2:bbaT0?77040Ba$5#6+6-a`aI016!0ua;3^ax0taz8qbv3R6!0S90bG92a}59a 9;7EbOb4b13*5ab8ba8daobd0Cbr4*bobq7rblaC3tbCbEbK8t4xbM8x435qbPad9=afb`bT9`b~5rbXbYb,bwaq0o1P1#b%4 b#ccaD7!7ba63oc63RaV0{0lcf767S1~0PcqbBa/6,bAbx0{bzbGbs04b$b+aobo0Ecv01cn5.czbIcLbo7a7ccLbdbfbhbj677Q7pb;c!b?a|b^5p0vb{aj5+5Ec0ae5Dc-c4c5bZbcbtcPcBczcecDaZ0{bJcH7Qb)cVc}d2a+cCb=b-cwcGbkcI78cLcN5GdebwcQ9*bLc*0t5D7A308Bc1dv226qbQ8J3e7A5Xc`anc|cFcR0{b*didKdhckdj04cKd6bmcMaWcOdrdo9Kdt5D7{dxb0dzb_81dCb|bR5,8Lc`b!dad$aPc dba.dR6Xc#d4dMbpd9be1#cYc%6X0p6a5@655_621e0F5|ei2P2K6,1#2J5`7;0$0(0*0h04.

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