Algorithmes dichotomiques

Retour sur la recherche linéaire (séquentielle)⚓︎

Exercice
1. Écrire une fonction appartient telle que appartient(e, L) renvoie un booléen permettant de savoir si e appartient à la liste L.

Donner le nombre de comparaisons (une comparaison étant une utilisation de == ou <, par exemple) effectuées par appartient pour des valeurs suivantes de e et L :
- e = 2 et L = [2, 4, 1, 7]
- e = 3 et L = [2, 4, 1, 7]
- e = 1 et L = [2, 4, 1, 7]
Soit L une liste de taille $n$. Quel est le nombre minimum de comparaisons réalisées par appartient sur la liste L ? Et le nombre maximum ? Quel est l'indicateur qui vous semble le plus pertinent ?
En supposant avoir un ordinateur à 1 GHz (permettant de réaliser $10^9$ opérations par seconde), et qu'une comparaison demande une opération pour le processeur, combien de temps au plus prendrait l'exécution de appartient sur une liste de taille $10^{11}$ ?

Solution

1.

Python
def appartient(e, L):
        for x in L:
            if x == e:
                    return True
        return False

- 1 seule comparaison : appartient(e, L) s'arrête tout de suite
- 4 comparaisons : appartient(e, L) parcourt toute la liste
- 3 comparaisons
Nombre minimum : 1. Nombre maximum : len(L). Le pire cas est plus pertinent car il si on veut éviter d'attendre trop longtemps.
1011 / 109 = 100 secondes

Complexité temporelle d'un algorithme.⚓︎

D'après Wikipedia, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat.

En comparant les instances en entrée de même taille, il est possible d'avoir des temps différents. Pour une taille n donnée le temps le plus long correspond au pire des cas. Le temps le plus court au meilleur des cas.

Dans l'exemple de la recherche séquentielle, si l'élément comparé est le premier de la liste, nous sommes dans le meilleur des cas. Une comparaison est nécessaire.

A l'opposé, si l'élément est le dernier de la liste de taille n ou si l'élément n'est pas présent, nous sommes dans le pire des cas. n comparaisons sont nécessaires.

Pour l'étude de la complexité d'un algorithme, on précisera souvent la complexité asymptotique (quand n devient très grand) dans le pire des cas.

On utilis la notation avec le grand o de Landau : $\mathcal{O}$

Définition

On dit qu’un algorithme, dont le nombre d'étapes élémentaires égale f(n), a une complexité en O(g(n)) s’il existe deux constantes C > 0 et n₀ ≥ 0 telles que :

$\forall n \ge n_0,\quad f(n) \le C \cdot g(n)$

Autrement dit, g(n) constitue une borne supérieure asymptotique pour f(n).

Classe	Nom
O(1)	Constante
O(log n)	Logarithmique
O(n)	Linéaire
O(n log n)	Quasi-linéaire
O(n²)	Quadratique
O(n³)	Cubique
O(2ⁿ)	Exponentielle
O(n!)	Factorielle

Une question essentielle en informatique est alors ? Peut-on trouver un autre algorithme répondant au même problème mais avec une classe de complexité meilleure.

Dichotomie⚓︎

Dans la langue française, une dichotomie désigne un choix entre 2 possibilités. En informatique, c'est une technique algorithmique où, à chaque étape, on divise la taille du problème par 2.

L'exemple le plus classique est la recherche par dichotomie dans une liste triée : on souhaite savoir si un élément $e$ appartient à une liste triée L.

Exercice : Écrire une fonction croissant telle que croissant(L) renvoie un booléen indiquant si L est triée par ordre croissant. Cette fonction ne sera pas utilisée dans la suite (on supposera que la liste est bien triée, sans vérifier).

Considérons par exemple L = $[-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]$ et $e$ = $14$.

Au lieu de commencer par regarder le 1er élément de L, on va regarder l'élément du milieu (ici $9$):

$[-2, 1, 2, 4, 6, 7, 8, \underline{\mathbf{9}}, 11, 12, 14, 15, 18, 22, 54]$

Comme $9 < 14$ et que la liste est triée par ordre croissant, on en déduit que $e$, s'il est dans L, est forcément dans la partie droite :

$[-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, 12, 14, {15}, 18, 22, 54}]$

On se restreint donc par la suite à la partie de L qui est encadrée. On compare $e$ au milieu de cette partie, c'est-à-dire $15$ :

$[-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, 12, 14, \underline{\textbf{15}}, 18, 22, 54}]$

Comme $e < 15$, on peut cette fois se restreinte à la partie gauche. On cherche donc maintenant $e$ dans la zone suivante :

$[-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, {12}, 14}, {15}, 18, 22, 54]$

On compare encore une fois $e$ au milieu :

$[-2, 1, 2, 4, 6, 7, 8, {9}, \boxed{11, \underline{\textbf{12}}, 14}, {15}, 18, 22, 54]$

Comme $e > 12$, on regarde à droite : $[-2, 1, 2, 4, 6, 7, 8, {9}, 11, {12}, \boxed{\underline{\textbf{14}}}, {15}, 18, 22, 54]$

On a trouvé $e$ !

Quel a été le nombre de comparaisons nécessaires pour la recherche par dichotomie sur cet exemple ? Et si on avait utilisé appartient(e, L) ? Quelle méthode vous semble la plus efficace ?

$4$ comparaisons pour la recherche dichotomique contre $11$ (c'est-à-dire l'indice de $14$) pour la recherche séquentielle (appartient).

Pour se souvenir de la zone dans laquelle on cherche l'élément $e$ (encadrée sur l'exemple ci-dessus), on utilise deux indices $i$ et $j$.

Exercices⚓︎

Écrire le code d'une fonction est_croissant qui renvoie True si une liste est triée en ordre croissant, False sinon.

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

.128013/p:i+Fvl4P);Th=obkL5uancgrtS_ef12w y]m[-s(d3050R0E0B0w0e0i0P0J0y0i0w0P0P0p010B0e0c010406050P0v0M0M0w0A0K040C0q0i0v0-0q0x050b0@0_0{0}0=0c04051d161g0b1d0=0R0e0h0#0%0)0+0%0x0z0v0w0z0E0O0c0K0B0o140J0o0e0z0o0i1I0o0B0:050W0r0i0E1p0(0*011H1J1L1J0B1R1T1P0B0A1e1D0#100P0c0w0x0+0H011V1r010F0Y0E0x0w0M0E1P1;1?1{1X1~1T21230:0a0J0k0A0q0c0q0P0e130x0J0U1/0A0A0E0y2o16260x1e0b1D2B1+1-1,1Q0R281s0e0x202l1P1m1o0$1W2L2N0x0q2R1P0c2u1e2z2B2(0?1=2p2T1|2X0A0`0i1P0w1G2u0F0+030D0D0y2Y0E1L2W0q0O0G360:0G160w2)2,0;2+272.1X2:2=2@2_0E2{012}2 31332O360O1_040H3b3d1?3f2z2K013k0w2?1e2^0o2`2|2~300U3u2X3w0S0:0S3B2y3e0=3F3i0+3I3K053M3O3q3Q3t2M3v370j0:0j3Z173#3g2-1q3j0q2;3J3m3N3o3P3s3S3=3U370u0:0u3{2*1j2$162R2E0R1-2J3(013R241e4m1f4k4i2*4t2%2,0J0e0R0+2~2z3w0G3m4F4H49324b35374L0J2c0E4O4t3T4S382B3c3~3G0s0:0U0F3!3D4)4r0I0:0J4/2A4;403)0F0:0E0P0B2 2i0e0)1?0B4_4C3h4|010/040Q594{2U3H0:0t5h3%5c5e0d594^5o5j0x0r0:1L515n4D4r5e0l5s5i1|0q0:0O020z0B0m5G5u2/5x040r0q105B5b5j5q590=3|4:3F4N014I2,3w3y3,4E4G5,4P4!5/1`4W4Y3;345`4%040J635t5C5c4+040F425Q665v0:0e6c5Z5I4?042M6h3 5v5T0A1?1y5Y6o1|5e5g5(4`5R3j5T2b6u3G6x6F4r0x5l6I5p0:5F6z625H1X5J040O6n3G0M0e396M5!6O5r6Q5%2*5*5?5-1?3V4M6.5^4R6;4V224X5@4Z6^373W616473656i1X680e4.6Q756v3j6L6Q6S0+5e0N6$2/6f7l1X5e0L6X4r6U5M5O7s5c6K045m7g6B7i0:7k7C6d7m6l7x5j6U0f7L1|6Z6#7H767E040L6)2(6+3e4)5+6/0x3w3^3L5=5}4a5 3@5{6{7.4Q7:0O7+3B747}7c4*0:2u0B0v0A157b7h010s0y0:0g3J0P0E5$6F7%0D4J4d6=7@5_8m6`238o6 0O4e726488688284862(7 4r8a0:0n0A0v8g6*5h0b4B1h4k0b4w2C4o162F8X0w1S0E2B4m5%0U0W0Y0P04.

Compléter le code suivant permettant de rechercher un élément dans une liste triée, par dichotomie.

Évaluations restantes : 5/5

.128013/p:i+F,vl4P);Th=obkL56uancgrtS_ef12wé yq]0m[-s789(dj3050Z0G0D0y0e0j0U0M0A0j0y0U0U0q010D0e0c010406050U0x0R0R0y0C0N040E0r0j0x0_0r0z050b101214160~0c04051m1f1p0b1m0~0Z0e0i0.0:0=0@0:0z0B0x0y0B0G0T0c0N0D0p1d0M0p0e0B0p0j1R0p0D0|050)0s0j0G1y0;0?011Q1S1U1S0D1!1$1Y0D0C1n1M0.190U0c0y0z0@0J011(1A010H0+0G0z0y0R0G1Y1}1 241*271$2a2c0|0a0M0l0C0r0c0r0U0e1c0z0M0%1{0C0C0G0A2x1f2f0z1n0b1M2K1@1_1^1Z0Z2h1B0e0z292u1Y1v1x0/1)2U2W0z0r2!1Y0c2D1n2I2K2;0 1~2y2$252*0C130j1Y0y1P2D0H0@030F0F0A2+0G1U2)0r0T0J0T0I0|0M0I1f0y2=2^0}2@2g2`1*2|2~30320G340136383a3c2X3f3f3j0J3m3o1 3q2I2T013v0y2 1n310p333537390%3F2*3H0#3j0#3L2H3p0~3P3t0@3S3U053W3Y3B3!3E2V3G3g0k3j0k3-1g3/3r2_1z3u0r2}3T3x3X3z3Z3D3$3 3(3g0v3j0v452;3:2^3Q3@4f3{3C3#3b4l3e3g0w3j0w4r473;4a3?4c3w3V3y3A4z3~3d3H0V3j0V4I3N4t3s4L3R4N4e4P4g4R3}4k4U3g0W3j0W4Z2J4#492%4(4d3^3`4h3|4j4B4:0T0X3j0X4^3O4u3=4}4O3_4Q4i4A3%4D3h0Q0|0I0Q5a4`4v4)4 5h525j4C3H0I3i045B5a1q2/1f2!2N0Z1_2S5d4A2Z1w1n2.0G2:3p3.3N054A5V2g0e0Z0@372I5A3x5%5)535k5,0M2l0G5/5y555C3-4K4|0t0|0%0H5X2J483Q0K3j645#4{2{0H610e0A1N0D0r0R0e0G6a665d0{040Y6o5~2{0|0u6u5c4%6r0h6z4$4|0z0|6n465Y6v1*6r0m0d6a0~6K653P5.015*2^3H224P6W4.54403I5?2b5^6X5:5z3g6#3L0M6^0M6p4%6H040e6E6c6N0|6D6T046`6M3?0|0!6a776A4|0r0|0q7c6{4|6l0|5q757k256C7j783R0s0|2k703Q6r6t7p7u6}6y7D7e7r0|0m7t7I1*7g040T7M6F257m5D7c7d7T1*0A5C030M0e0M0(0M0!0M0U1d0D0M1$0-2V1v0A0G0-2A0u7*0z1@1%7?0O0x3b0-1O6h0G0C897*6R7z6%0F5+3g3*6$5(6/5`6*3*6,2c5_4T8p1Y0b3n6_7Y710@60040K1Q1$7S8B3R0|6 758A3Q7P020j0D0n7i8N7q3u7a7z6q0|6Q8W7u7#0|7%0)800M84000+0M2D0U0D1%0y0x0M0R0r2V0-0I0M0L0j0L2c8.29817=7{7(0z7_9c7)7+7b756S2?6V8m6Y1 3H428l8t4/6*428r6.6(5;418w8y8z6_8X79040R8I8P7h9L8#6s8!6|8L9O4%7P0f9U6G8Z7H7Z0@6O9Y257P0b0b9)1*7V3K9#8J8*047%6l1U0G8|2A9h7;9j4s8f9o8h6Z4n5-a48o4m0T4o9y9u6)ab4o2K9E9F8O5d8D0e638(7N9I6J2;am9V0|8R8T9.9I7G9mas016r0S9R9Z9JaJ7J040P8%a29=7(a48i0T4F9t8n8uab4FaeaZ9va#9D76al9F9H8K04a13paw7f9Nar9$a:9Ka`8J7P7Ra~3Q7V3lb25O7$8?0G0B140%0C2z1 0-0:0M1~0C0_1%bb0x898eaS8gaV4WaY9A6;0T4Wa%bx55bv6@a-a/8D4Baqava/6}aua?a/8Q0BaAb69S04aD5W7uaHaM8YaLaS9PaPbraE5$aUa60T4=bw6:554=bBb?6*b;bFa-9G7E9TbUa^048VbLc0b%c6aF9WaB01b4cc9@7%2Dbb0Cbdbf0zbh31bkbm2z2r2wbO4!a35/aV57b=aa5l57b_cC3HcAb}a.7ubI0,cv6UaF6raQ47bsb.9q3g5pa8af9B5m235@c!bycYaja,b~6^bH0|2D0D0x0C1ec2250t0A0|0o0C85cfb81O311@0r0x0i0L8d9kcx6/aV5BcZa(ag5ldgcFa!dk5|8xc-a@c{c;0(c@c_c9a{c|0|0g3T0UcO76a/cg7*5?00cp0;930Ddad6d80Lb+5W0b5!5G5U5I5R1f0D5Ld$2Q2L0y1#dZ0b5J6S0%0)0+0U04.

Puis tester votre fonction avec le jeu de tests suivant (assert déclenche une erreur si son argument est False) :

Python
L1, L2, L3 = [0, 2], [0, 2, 5], [-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]
assert (dichotomie(L1, 0) and not dichotomie(L1, 1))
assert (dichotomie(L2, 5) and not dichotomie(L2, 7))
assert (dichotomie(L3, 14) and not dichotomie(L3, -4))

dichotomie est donc beaucoup plus rapide que appartient.

Écrire une version récursive de la recherche dichotomique.

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

.128013/p:iF+,vl4P);Th=obk56uancgrtS_ef12w y]0m[-s789(d3050W0F0C0x0e0j0R0K0z0j0x0R0R0q010C0e0c010406050R0w0O0O0x0B0L040D0r0j0w0=0r0y050b0|0~10120`0c04051i1b1l0b1i0`0W0e0i0*0,0.0:0,0y0A0w0x0A0F0Q0c0L0C0p190K0p0e0A0p0j1N0p0C0^050#0s0j0F1u0-0/011M1O1Q1O0C1W1Y1U0C0B1j1I0*150R0c0x0y0:0I011!1w010G0%0F0y0x0O0F1U1_1{201$231Y26280^0a0K0l0B0r0c0r0R0e180y0K0Z1@0B0B0F0z2t1b2b0y1j0b1I2G1:1=1;1V0W2d1x0e0y252q1U1r1t0+1#2Q2S0y0r2W1U0c2z1j2E2G2-0{1`2u2Y212$0B0 0j1U0x1L2z0G0:030E0E0z2%0F1Q2#0r0Q0k0Q0H0^0K0H1b0x2.2;0_2:2c2?1$2^2`2|2~0F3001323436382T3b0Q1~040K0I3i3k1{3m2E2P013r0x2{1j2}0p2 3133350Z3B2$3D0X3f0X3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0k3f0k3+1c3-3n2=1v3q0r2_3R3t3V3v3X3z3!3}3$3c0u3f0u432-3.2;3O3=4d3_3y3Z374j3a3c0v3f0v4p453/483;4a3s3T3u3w4x3|393D0S3f0S4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0T3f0T4X2F4Z472Z4$4b3?3^4f3`4h4z4.0Q0U3f0U4?3M4s3:4{4M3@4O4g4y3#4B3d0N0^0H0N584^4t4%4}5f505h4A3D0H3e045z581m2+1b2W2J0W1=2O5b4y2V1s1j2*0F2,3l3,3L054y5T2c0e0W0:332E5y3t5#5%515i5*0K2h0F5-5w535A3+4I4`0t0^0Z0G5V2F463O0J3f625Z4_2@0G0^0F0R0C0E5R0R256g2z0z68645b0@040V6o5|2@0^1Q6f0F6u5a4#6r0d680K6p4#0y0s6x0e6f6B4!4`6r0h6G6I4`0y0^0i3R0F0w0B6P6a1$6E6U6v3q6L042R0C6(3O6r0m6,6C4`0r0^0Q020A0C0n6`6Q2@6/0s0r156?6q0^6F444Y6?5,015(2;3D3F5e7i4,523~3E1 5=5@4R7s7n0b3j0K7C6H6-0:5~6:617f2F7E6{210r66042$6=7K3G6V6w046y0C6A7U7W6*7d680`7$3N7p0E5)3c3(4N7.5^7s3(5;275?7j5.5x7;1U7A3G7D857%7G0^2z0C6$1a7U7M751$0t0z0^0f3R6j7*7h5$7~7:3b5+8q7q5/3 7u7|7w4-7s402G3j7+2/7-8v7/7l4l8u8B7r4k0Q4m7{288P8x8S827B7D873P0^0O746)0:6}040q8*4t6/2g7b6D0^6t7,7N3q6M6z8@6R0^6_8e8$8-0b0b8:5b0O0e0^3I7U8H5U8J5-8s4D7?8K7^8R4D8U7}8w800Q9l3J867F017H0e7J2-8f8+8%7Y6N7!90216r0P9L8}048)8{8g0:6r0M994#8-0q8/949z6X046Z1Y6$9P9V7)9f8p9j8M0Q4U9m8W9u4U9r9{539_9x858#9z7H8a8c9Y5}8j040o0B0w7#4q9=8r9@4:9`7~9o5j4:9~an7x8Rala27C8$7H4z9D3l9F4t6Y6!9-9%8|8,0^020j72a97X7Zag9haJ019N9.9H9S8IaU9W7eah9T2u7.8s55am9t5355ara/7sa-awa3ay890!a8aI9U9H6e6g6i6k0E6maX6r8`a!b09)aRb80^0Pa%aTbc8(bf040M6Ta 9G9)9+6#6%a)6@928obwa+9@5n8Oas8C8RbDa=7 5_5l8F84axa56d0(aS5W9z6+9;bA8K8s5zbEa?bH3ebJao5y5`83a3a4aUa6a}0B8d9E8$9)b26h2z6j0y6l2Abmbabjbr8~9Kbw7c049Oc96Jblcd6|0^0gaX9b5mbm0dboaP9QbtaHbb9G6^bz2/0b5Y5E5S5G5P1b0C5JcF2M2H0x1XcC0b5H7+0Z0#0%0R04.

Exponentiation rapide

L'algorithme naif de calcul de la puissance $a^n* avec $n$ itérations ou boucles n'est pas optimal.

On peut faire mieux en utilisant le fait que, si on connaît $b = a^{\frac{n}{2}}$, il suffit de calculer $b^2$ pour avoir la valeur de $a^n$, ce qui demande $1$ multiplication au lieu de $\frac{n}{2}$. L'idée de l'exponentiation rapide est de partir de $r = a$ et de mettre $r$ au carré un certain nombre de fois jusqu'à obtenir $a^n$. Cependant, si $n$ est impair, on ne peut pas diviser $n$ par $2$ et il faut à la place multiplier $r$ par $a$.

On met en oeuvre cette idée avec l'algorithme suivant :

Python
def puissance_rapide(a, n):
    r = 1
    while n != 0:
        if n % 2 == 1:
            r = r * a
        a = a * a
        n = n // 2
    return r

Exécuter à la main puissance_rapide(2, 12). On donnera la valeur de r, a et n à la fin de chaque passage dans la boucle while.
Comparer le nombre de multiplications dans l'exemple ci-dessus avec le nombre de multiplications réalisé par puissance(2, 12).
Montrer que la valeur de $r a^n$ reste identique à chaque passage dans le while. En déduire que puissance_rapide(a, n) renvoie bien $a^n$.
Comment pourrais-t-on utiliser une multiplication de moins dans puissance_rapide. Modifier la fonction pour ce faire.

Solution

Text Only
1.

| Nombre de passages dans le while |               r               |       a      |   n  |
|:--------------------------------:|:-----------------------------:|:------------:|:----:|
|                 1                |              $1$              |      $2$     | $12$ |
|                 2                |              $1$              |      $4$     |  $6$ |
|                 3                |              $1$              |  $4^2 = 16$  |  $3$ |
|                 4                |              $16$             | $16^2 = 256$ |  $1$ |
|                 5                | $16\times 256 = \boxed{4096}$ |      ...     |  ... |

2. L'exponentiation rapide a effectué $6$ multiplications, alors que `puissance(2, 12)` en fait $12$.

3. On vérifie que $r a^n$ ne change pas dans les deux possibilités suivantes :
- Si `n` est pair, on remplace $a^n$ par $(a^2)^\frac{n}{2}$ et $r$ ne change pas, donc $ra^n$ ne change pas.
- Si `n` est impair, on remplace $n$ par $\frac{n - 1}{2}$ (car `n // 2` effectue la division entière) donc $ra^n$ est remplacé par $(r\times a)(a^2)^{\frac{n - 1}{2}} = r \times a^n$.

4. Une fois la dernière valeur de `r` calculée, il ne sert à rien de mettre à jour `a`. Donc on pourrait écrire :

```python
def puissance_rapide(a, n):
    r = 1
    while n > 1:
        if n % 2 == 1:
            r = r * a
        a = a * a
        n = n // 2
    return r * a  # dernière modification de r, quand n == 1
```

Complète le code de la fonction zero_fonction qui permet de trouver la solution approchée de l'équation $f(x) = 0$ sur l'intervalle $[inf, sup]$ avec une precision epsilon.

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

.128013/*p:i+,vl4P);h=obk56uanzcgrtS_ef12w y0m-s7(d3050S0F0C0w0f0j0P0K0z0j0w0P0P0p010C0f0d010406050P0v0N0N0w0B0L040D0q0j0v0.0q0x050b0^0`0|0~0?0d04051e171h0b1e0?0S0f0i0$0(0*0,0(0x0A0v0w0A0F0O0d0L0C0o150K0o0f0A0o0j1J0o0C0;050X0r0j0F1q0)0+011I1K1M1K0C1S1U1Q0C0B1f1E0$110P0d0w0x0,0I011W1s010G0Z0F0x0w0N0F1Q1=1@1|1Y1 1U22240;0a0K0l0B0q0d0q0P0f140x0K0V1:0B0B0F0z2p17270x1f0b1E2C1,1.1-1R0S291t0f0x212m1Q1n1p0%1X2M2O0x0q2S1Q0d2v1f2A2C2)0@1?2q2U1}2Y0B0{0j1Q0w1H2v0G0,030E0E0z2Z0F1M2X0q0O0Q0O0H0;0H170w2*2-0=2,282/1Y2;2?2^2`0F2|012~3032342P370O1`040I3d3f1@3h2A2L013m0w2@1f2_0o2{2}2 310V3w2Y3y0T0;0T3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380k0;0k3#183%3i2.1r3l0q2=3L3o3P3q3R3u3U3@3W380t0;0t3}2)3(2-3I3,473:3t3T334d36380u0;0u4j3 3)423+443n3N3p3r4r3?353y0Q0;0Q4A3F1i2%172S2F0S1.2K3*014s2R1o1f2$0F2(3g3$4S4s4-280f0S0,2 2A3y3a4H4@4_4b4t4M383a0K2d0F504s3V4v391Q0b3e403I0s0;0V0G4/2B5h4#0J0;0K5n4=412V3J0G0;0y0F2j0E0G152x0f155u5p4D010:040R5K4C5x0x0;5m3~4S5S1}5O0h5u5t5Z3l0;2N5W2+5)0,5O0e5%5L5T0r5V0j0q0w0C5R4m4#5#5?5/3J0;0^0d5 3j5M5;63605M0x5_040G5{5}695w5!0;5$5X2B5(6e5T0;0F0d2n5{166r5v3I6c6C6t6a5^5`5|5~6C5@6o040m5=6C0?6N3H4 014`2-3y3A3.0K6X3=4c533z1{57594L3^6-2C3e0K6_6H6n5*040N6d6I1}0q0;0p706|5:0;5Q6V6u2:660v686G6O1Y73040g764n5+0x5-4.645O0m7n4#7k0b7w5M0N0f0;3C6T6m6(4^6Y0E4{383Y4~7J6*526=3Y5623587K5a4u3X5e6^6`7i0,5j040f7r3F6{7o04677A5x7k0O7@7d7,7q7{7j0;020j0C0n757h645U046x6z5J7b711Y6F4k7H6)7L6!3_3o8k7Z6,3`7V246:6+6=3`6@046`8B7:4#7+2v0C0v0B6B2)8D6f0;6 7G8e2q8k7M0O4g7P8v7S4e8V6.7W8Y5b3y8W3D8B7)017+7-7 3+5V7H61798^8N7}7.5o7t0;7v877c80040c8=656i8{5x5O7a5.948?6~9b6P928L8.7k8284987C0;0M9j8g0;6S8i8R7I508U4x8X7Y6;8!4x8t7X7R8)4w7$8A8C6_8.8F0W8I8K3g8M6v045B5D5F0x5H8d9f8f785P9v9h8~6D8_046q9,77995,9:5N6p9~898P9`6Ea09A4#898b0Z9+7s9g9 6Q5u6Ua48T8m378o7Q519Nam9K8(7!384O8z8-649U8H8J98899$0q5E5G2ya76b8`aK9!9=8.62aN7|a3ad9-af9_aV9{897?aS9w9^a16w6yab9X5Yae7uah5K0b4;4T4,4V4)170C4Ya}2I2D0w1Ta`0b4W6U0V0X0Z0P04.