Programmation Dynamique

Programmation Dynamique⚓︎

La programmation dynamique (PD) est une technique algorithmique permettant de résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples.

Elle est souvent utilisée pour résoudre des problèmes d'optimisation (comme par exemple maximiser des allocations de ressource, trouver le plus court chemin...).

Elle repose sur le principe d'optimalité de Bellman et utilise des solutions aux sous-problèmes pour construire la solution du problème original.

L'idée clé est de mémoriser les résultats des sous-problèmes pour éviter de les recalculer plusieurs fois. Cela est particulièrement utile dans les problèmes qui peuvent être découpés en sous-problèmes qui se répètent.

introduction⚓︎

Quel est l'avantage du code suivant par rapport au calcul récursif sans mémomïsation des termes de la suite de fibonacci ?

Python
def fibo_naif(n):
    if n < 2:
        return n
    return fibo_naif(n - 1) + fibo_naif(n - 2)
memo= {}

def fibo(n):
    global memo
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]

La version naive prend rapidement beaucoup de temps, elle recalcule de nombreuses fois des valeurs de fibo(i) déjà calculées...

Le Problème PLSC (Plus Longue sous-Séquence Commune)⚓︎

Le problème PLSC consiste à trouver la plus longue sous-séquence commune (PLSC) entre deux chaînes de caractères.

Une sous-séquence est une séquence obtenue en supprimant certains caractères sans changer l'ordre des caractères restants.

abcde est une sous-séquence de abracadrabramtesque.

Remqarque: pour un défintion plus formelle, une chaine sous_seq de longueur n est une sous-séquence d'une autre chaîne chaine de longueur m, sis et seulement si, il existe une fonction croissante f de $⟦ 0, n-1 ⟧$ sur $⟦ 0, m-1 ⟧$ telle que :

Pour tout i de $⟦ 0, n-1 ⟧$ : sous_seq[i] == chaine[f(i)].

Pour commencer, nous voulons écrire une fonction qui prend deux chaines de caractère en eparamètre et retourne True si la première est sous-séquence de l'autre.

Pour trouver la réponse, nous allons utiliser la récurrence en diminuant les longeurs des chaines à tester.

Nous utilisons 3 propriétés : - une chaine de longueur 0 (mot vide) est toujours sous-séquence d'une autre chaine - une chaine de longueur non nulle n'est jamais sous-séquence de la chaine vide - une chaine sseq est une sous-séquence de texte si et seulement si : - sseqest déjà sous-séquence de texte[:-1] (la chaine texte privée de sa dernière lettre)

Text Only
    OU

    - `sseq[:-1]` est une sous-séquence de `texte[:-1]` ET `sseq[-1] == texte[-1]` (sseq privée de sa dernière lettre est sous-séquence de texte privée de sa dernière lettre et les deux dernières lettres correspondent)

Complète le code suivant

Évaluations restantes : 5/5

.128013it3a;dv,FnT2S5wbcy14q: f-up08)_9eklohxrP=[s6(]/mg7050g0H0c0e0b0J0R0x0r0J0e0R0R0P010c0b0B010406050R0A0W0W0e0N0s040n0K0J0A0?0K0k050V0}0 11130{0B04051j1c1m0V1j0{0g0b0h0+0-0/0;0-0k0X0A0e0X0H0z0B0s0c0L1a0x0L0b0X0L0J1O0L0c0_050$0q0J0H1v0.0:011N1P1R1P0c1X1Z1V0c0N1k1J0+160R0B0e0k0;0m011#1x010y0(0H0k0e0W0H1V1`1|211%241Z27290_0a0x0O0N0K0B0K0R0b190k0x0!1^0N0N0H0r2u1c2c0k1k0V1J2H1;1?1=1W0g2e1y0b0k262r1V1s1u0,1$2R2T0k0K2X1V0B2A1k2F2H2.0|1{2v2Z222%0N100J1V0e1M2A0y0;030F0F0r2(0H1R2$0K0z0t3c0_0t1c0e2/2=0`2;2d2@1%2_2{2}2 0H3101333537392U3c0z1 040m3h3j1|3l2F2Q013q0e2|1k2~0L303234360!3A2%3C0d0_0d3H2E3k0{3L3o0;3O3Q053S3U3w3W3z2S3B3d0u0_0u3)1d3+3m2?1w3p0K2`3P3s3T3u3V3y3Y3{3!3d0o0_0o412.3,2=3M3:4b3@3x3X384h3b3d0S0_0S4n433-463/483r3R3t3v4v3`3a3C0Y0_0Y4E3J4p3n4H3N4J4a4L4c4N3_4g4Q3d0D0_0D4V2G1n2,1c2X2K0g1?2P3.014w2W1t1k2+0H2-3k3*3J054w562d0b0g0;342F3C0t3s5e5g4f4x4,3e0x2i0H5n4w3Z4z3e2H3i443M0I0_0!0y584=4G2!010p0_0x5I5c455L0k0y0_0H0R0c0F0R0K0A0R5!0H0v0A260r0H5Q5C4~0^040T5:5K2^0_0/5*5_4q5=0_0i5Q5P5`3p0_0c0H0M695 4Y5L5?0E0w5Q0{42593L5m015h2=3C3E3=0x6o4*5p3|3D205t5v4P6z6t0V3i0x6J65604Z5E040b5H6l2G6L6e2^0q0_2h6d5S225?5^6S5R4r5|0R5~6)5;4Z6g646:5L0K0_020X0c0f6?660;0W0b0_0C6 6M6f0_6i6)6U6#1%0r5k04030x5}0v5s02030d0G0f5X0c0x1{0*0-0+0L0%2T0x0h5e5/6)6k2:6n5f6p5!6r3d3$4L6w5o5x3#6B285u7L5w4y7U5A046K7(7c5D0_6Q647*4~0k6X046Z6/70016%6!6+04696b7F7I776$0_0E766V1%6_040P0P877d717304757^831%5?7a2.7/4Z7f0_7i7 690x7s0x7x0r7z3{7C7E6j7|7R5i3}5l7K6x7T8K5s7W6D4+6z3~7$7)8X8q5L6O2A0c0A0N1b7b6@220I0r0_0j3P6-8G8k5d8M7M1|3C4k7Q8`7Z5q4k8Q298S6y4i0z8~3H8Y8Z8-0_8$8(8*8p8,67047s5!5$5(6-5+5-81577_7{8^8f3N6,6.82880;5?638+7_0k686a6c9y3M5?0Q8o9v8l0;8a0z7|4~723f9Y6;0_0U869I9U010K5N04487.9k9F0_6(9D9z9K9m5Y9o5%5)9s0k5.9$785@a55{047ka88m0_9Rac9V0_9X9O9Z8h3gak9%040U9H9j9J9L80ag7`ae9S6m9,9Wax9!04an9`9P9(9*ataC9/1|0g8e7}abaoa60QaxaDaU22aFaH9T9EayaqaR4~8a8ca+4Z9|8v9uaBa(9QaXaiaEamax5?9)8@aI8I7N0z4B8 968Ob57V957Y6E98b63H7Ha%2vb38|3d4Sb7bd8T984S947X8N7!bn1V6H7%6K9?4 7g7i0r0.2w1!0q0.0H0i8z2~8B7A1!7k8x5Y8E0!b1bj6v8`8J0z4.bpbw5q4.bub8bxb(bz6IbC7_8#0#9ha/8!8/040l0N5,bZ590V5b4?554^521c0c4{cb2N2I0e1Yc80V4_6k0!0$0(0R04.

Plus longue sous-Séquence Comm⚓︎

Prenons deux chaînes de caractères :

S = "avion"
T = "aviron"

Nous cherchons la plus longue sous-séquence commune entre ces deux chaînes. Dans ce cas, la plus longue sous-séquence commune est "avion", qui apparaît dans les deux chaînes.

Explication de l'Algorithme⚓︎

L'algorithme de programmation dynamique pour résoudre ce problème utilise une matrice plsc où chaque cellule plsc[i][j] contient la longueur de la plus longue sous-séquence commune entre les premiers i caractères de la chaîne S et les premiers j caractères de la chaîne T.

Les étapes de l'algorithme sont les suivantes : 1. Si les caractères S[i-1] et T[j-1] sont égaux, alors plsc[i][j] = plsc[i-1][j-1] + 1. 2. Sinon, plsc[i][j] = max(plsc[i-1][j], plsc[i][j-1]).

Ce processus est répété pour toutes les paires de sous-chaînes de S et T jusqu'à ce que la matrice soit complètement remplie.

Code Python⚓︎

Complète le code Python qui implémente l'algorithme de PLSC :

Évaluations restantes : 5/5

.128013Cit3adv,nT2SR5éwbcy+14qL: f-up08)_j9eklohxrP=[s6(]/mg7050g0L0d0f0c0N0V0A0s0N0f0V0V0T010d0c0E010406050V0D0!0!0f0R0t040m0O0N0D0`0O0j050Z111315170 0E04051n1g1q0Z1n0 0g0c0h0/0;0?0^0;0j0#0D0f0#0L0C0E0t0d0P1e0A0P0c0#0P0N1S0P0d0}050*0r0N0L1z0=0@011R1T1V1T0d1#1%1Z0d0R1o1N0/1a0V0E0f0j0^0l011)1B010B0,0L0j0f0!0L1Z1~20251+281%2b2d0}0a0A0S0R0O0E0O0V0c1d0j0A0(1|0R0R0L0s2y1g2g0j1o0Z1N2L1^1`1_1!0g2i1C0c0j2a2v1Z1w1y0:1*2V2X0j0O2#1Z0E2E1o2J2L2=101 2z2%262+0R140N1Z0f1Q2E0B0^030I0I0s2,0L1V2*0O0C0l0C0v0}0A0v1g0f2?2_0~2^2h2{1+2}2 31330L350137393b3d2Y3g3g3k0l3n3p203r2J2U013w0f301o320P3436383a0(3G2+3I0e3k0e3M2I3q0 3Q3u0^3T3V053X3Z3C3#3F2W3H3h0w3k0w3.1h3:3s2`1A3v0O2~3U3y3Y3A3!3E3%403)3h0o3k0o462=3;2_3R3^4g3|3D3$3c4m3f3h0W3k0W4s483=4b3@4d3x3W3z3B4A3 3e3I0$3k0$4J3O4u3t4M3S4O4f4Q4h4S3~4l4V3h0G3k0G4!2K4$4a2(4)4e3_3{4i3}4k4C4;0C0K3k0K4_3P4v3?4~4P3`4R4j4B3(4E3i0F0}0v0F5b4{4w4*505i535k4D3I0v3j045C5s495u4 4y524T4:413i235E3L0Z3o3/4#5H5e4x4,4z4/555O0v3+5E3-5T3N4`5X4(5Z5h4-5j4U5(435E455-5V5/4L4}5=514.545l5B4p5E4r5~475W612|5v5K655z560v4G5E4I6c4t5:626h5!5L5$673h0v4X5E4Z6q4K5d5;6u5?5#665A6z4?5E4^6E6e6G6t5J6v6j5_4n3i585E5a6R606T6g6V6J6w6L560l5o046;5G6f4c6,645^5N6Z0l5D705b1r2:1g2#2O0g1`2T5e4B2!1x1o2/0L2;3q5 1o4B7j2h0c0g0^382J5B3y7q7s6/5(242m0L7y6k7A2L5U6_0^0M0}0(0B7l6s260q3k7P7J3S0B0}0E0-0s0I0c0!0E7U6*1+0|040X7*4%620}0m7:4|267-0i7l0A7Q3v0}0k7^3R7-0H0z7l0 6d2K5H7x017t2_3I5Q5h8d6x6M3J0A7C7E6Y5m8i5-0A8v7~7V0j0}1f8a7o7_7,0}7|8C8x7+3@0}0!7}7 0^0O0}0T8O8y0r0}2l835e7-7/8C8P3S7?8Z4(858H2=8J7;2|8W048Y8%7V8#8+7=04828_8K018588838k0I7u3h5*8j7r8e7z6Z3+8o2c7D9d7F9f1Z5-892@3Q96980C5{9b8q6~5m439h2d9x5%6Z9v8u8w8(0s5D030A0b0R0p0f2y2A1(0;0A141^0c0s1(2B0!0p0!4d0c0V9R0c1P0f0h2F0A1%0.0h3U0L0D0R0.2W2x0c9`0.5r8C9p7k9r9c8f203I699w9k8rac7B9i9D6y0Cad9H8v8(8z047Z0V0s8U918R048T8I8(7-0U0U8|260!0c0}a48/8(7L040B4daw8;80040IaS8E8Q7S042WaX4w8?0R201IaG8F7.a-8L048NaB7Vay0ua%5eaI5pa:920}0H0Ya{4(aOaQ0Rb48}aWa@axa!a$bcaT3@a)a+0La 8{90bh8)048BaMa^0}a`bgaY01a}5Ebmb1b3a595a9978g4F7wbH9l5m4G9B9j8l566n3Ma63O8cbH9t6BaebS5O4XbQak8mb#ao8:by9K0}9M0n0L7(1V0?1H9#9U329X0R9ZblbFbo2z9sbJ0C6Ob$9e5m4?b*af9y3Icab.aN0}b7b92|0}0cco1+0Obebs3qb/a(0}a*1Ec39q91bncEbpbA3mc5848Gcsa;cw3Ocy5ea_cObzaJbBcL8!b187c4cHc6bZc86#cbbN3I58cfb%6Zc,b.8wcSb5cmaRbx4w0}0JcVcucqcQ2Kc`62bjcCbCa/cZ4(cJdb8.cxaq8Md2bvcVdfdd4}85c$6rcLc7ab6z6=c-agdxai9Ccg9E5m5q9n3oc_dK9I7VaO0c7Oc~5Y8*dp7`0}aFdUaUcrdR4(ay0CdncXcKc(cM04bEbtax8SaAd:bpar8 d,c!04dXd{5;d0dl04d(d#4}dod dq0}0Yds48duc*dw3i5Ddzch6z3jc;cc5Beic^dLdKdjas7!0ge2d?di7Ve7eAd;04bwd@byaratavdY0^aDa ard!eH3Rd%d)a~eMb0d.d~a791ard1e526eUe)1+eCbX8`ea94ee7y9t0v8i3296c.6z23ene}5PdI04esetdN0}3c0VcDe#bp7-ec5We?9de^9ae{bMdA3i9g8pdEal5)f3f5f5eueKexe,8Q8ScVeJ7!dbe!e/e$cqe2e4eSa|d*db0YfH8b8ye1fA01e+fNdefPeX7-d/edd,dv0j5B9vflb+6l9Afqc=dG9G3obWfT4vf+68bLf:5(4pf0fn0vandJfvapfUevau0PeyfD7YfFf$dWePfKfWfYeDcIf#e8dVeZgl04e(gsa.f(cRd726b;049M0S1b0.0N1e1F1(0V0O0D0V0C0V0p0x0D2a9!9T0.112x0L0.0m0U0z0X0c3gb20A0)0A0kg*0X0J3ib2e=f*eff,6zbUf/fr8m6mdCbReoh0fug9gCaUeK0#gffWfEaufGgveRfcbyf%fS8Dc gwfLeVcYgyeNe;8Ihc0^gEgGgI9?gLgW0AgOgQgSgUgW0jgY0(g!0Dg$g(g@0cg/g;g?g+g_0lg{c%hn0Af~6zb#h2f@5Bb)f?h83ib-f`bGe@c80vcah/h@h~h6g16Zi27Hf4hb9J9L0A0y1(140Q7%12gZ0A1^0O9+g:0V0d0A0#150g0pg|h*h,6!g0h36lc:h?f10vc@g8g9fxgihxeYhqeuhmfIfdeaiOgbgxh*d|gAd68(ayezcRaq8?ifdb8$iMhi0sfziM7{gggc0sgegj04dhi(gbhedb0HiwiRc)h|eg6;iAh:3hj8g4ek3gdy9oh{fic870j9h@jljddF8heqiIhB01aO2E0d9|d5f4iKhji{iUfJbrfQjFd^dki{iZ3r8%0Z7n747i767f1g0d79jW2R2M0f1$jT0Z77890(0*0,0V04.

Exemple d'utilisation avec les mots "avion" et "aviron"⚓︎

S = "avion"

T = "aviron"

resultat = PLSC(S, T)

resultat:

	a	v	i	r	o	n
∅	0	0	0	0	0	0
a	1	1	1	1	1	1
v	1	2	2	2	2	2
i	1	2	3	3	3	3
o	1	2	3	3	4	4
n	1	2	3	4	4	5

Distance d'édition⚓︎

Lors de la comparaison de chaines de caractères, on cherche parfois des chaines plus ou moins proches les unes des autres. En particulier, on peut définir d'un point de vue mathématique trois opérations élémentaires permettant de passer d'une chaine à une autre :

substituer un caractère : "ABC" -> "AAC" ;
insérer un caractère : "ABC" -> "ABDC" ;
supprimer un caractère : "ABC" -> "AC".

On va supposer ici que le coût de ces opérations est le même. Le nombre d'opérations élementaires pour passer d'une chaine à une autre constitue la distance de Levenshtein.

On peut utiliser la formule récursive suivante, où on note $\|a\|$ la longueur de la chaine $a$, et $a-1$ la chaîne $a$ tronquée de sa première lettre :

\[\qquad\operatorname{lev}(a,b) = \begin{cases} \max(\|a\|,\|b\|) & \text{ si } \min(\|a\|,\|b\|)=0, \\ \operatorname{lev}(a-1,b-1) & \text{ si } a[0]=b[0], \\ 1 + \min \begin{cases} \operatorname{lev}(a-1,b)\\ \operatorname{lev}(a,b-1)\\ \operatorname{lev}(a-1,b-1) \end{cases} & \text{ sinon.} \end{cases} \]

L'objectif est d'écrire une fonction lev qui prends en paramètres deux chaînes de caractères a et b et qui renvoie un entier correspondant à la distance de Levenshtein.

Exemples

Python
>>> lev("distance", "distance")
0
>>> lev("distance", "distante")
1
>>> lev("distance", "distances")
1
>>> lev("distance", "dispense")
3
>>> lev("distance", "pense")
6
>>> lev("distance", "haricots")
8