Compte Rendu CM4TD4
Programmation Dynamique :
Plus longue sous séquence commune
Préparé par : Mohamed Ouchene
Filière : ISN, Promo 2025
1
SOMMAIRE :
I. Analyse du problème
1. Description du problème…………………………………………………………………….3
2. Solutions Proposées……………………………………………………………..…………….3
II. Réponse à la problématique
1. Algorithme itératif……………………………………………………………4
2. Méthode récursive……………………………………………………………5
3. Méthode récursive avec mémoïsation…………………………………….6
4. Programmation simple………………………………………………………7
III. Conclusion
2
I. Analyse du problème
1. Description du problème
Le problème de la recherche de la plus longue sous-séquence commune (LCS, pour "Longest
Common Subsequence" en anglais) consiste à trouver la séquence la plus longue qui est commune à
deux séquences données. Cette séquence partagée peut être discontinue et contenir des éléments
dans un ordre différent de celui des séquences originales.
Le problème du LCS a de nombreuses applications, comme la comparaison de textes, l’alignement de
séquences génétiques en bio-informatique, la recherche d’informations, le contrôle de versions, etc.
Le LCS permet de repérer les ressemblances et les divergences entre deux séquences, ce qui est
pertinent dans plusieurs domaines scientifiques et informatiques.
2. Solutions proposées
Pour résoudre le problème de recherche de la plus longue sous-séquence commune (LCS) entre
deux séquences, nous pouvons envisager deux approches distinctes :
➢ Programmation Dynamique :
• Algorithme itératif : cette méthode une solution classique pour résoudre le
problème LCS. Elle consiste à utiliser un tableau à deux dimensions pour mémoriser
les longueurs des sous-séquences communes des préfixes des deux séquences. Puis,
on utilise ces données pour reconstituer la LCS.
• La méthode récursive : Une autre façon de chercher la LCS est fondée sur la
récursivité. Dans cette méthode, on découpe le problème en sous-problèmes plus
simples en parcourant les éléments des séquences un par un. On traite ces sous-
problèmes récursivement et on fusionne leurs solutions pour obtenir la LCS finale.
• La méthode récursive avec mémoïsation : En plus de la récursivité, on utilise une
mémoire pour stocker les résultats intermédiaires et éviter les calculs répétitifs.
➢ Programmation Simple :
• Algorithme simple : La méthode est similaire à l'approche itérative, où nous utilisons
deux boucles pour construire un tableau, cependant, dans cette méthode, nous
stockons la plus longue sous-séquence commune dans un tableau.
3
II. Réponse à la problématique
*Remarques :
Dans toute cette partie, on va utiliser le langage de programmation Python pour illustrer des
exemples d’applications.
On fait plusieurs testes sur différents cas, y compris des cas particuliers et cela fonctionne sans
exception dans tous les cas.
1. Algorithme itératif
Cette méthode s'applique à deux séquences données, que nous noterons X[1..m] et Y[1..n], et
elle permet de trouver la taille de la plus longue sous-séquence commune entre ces deux séquences.
Sa complexité est O(m*n).
Exemple d'application :
Figure 1 : Le code de la méthode itérative.
4
2. Méthode récursive
Cette approche permet de trouver la taille de PLSC. Elle requiert systématiquement les deux
séquences en tant qu'arguments, ainsi que leurs longueurs respectives.
Le fait que l'algorithme explore toutes les combinaisons possibles de caractères des deux chaînes, ce
qui conduit à un grand nombre de calculs répétés et une augmentation exponentielle du temps
d'exécution à mesure que la longueur des chaînes augmente. Sa complexité est donc O(2^(m+n)).
Figure 2 : Le code de la méthode récursive.
5
3. Méthode récursive avec mémoïsation
Pour optimiser l'algorithme, on évite de recalculer les mêmes sous-séquences communes à
plusieurs reprises, ce qui améliore considérablement les performances, en particulier lorsque les
chaînes d'entrée sont grandes. Sa complexité est O(m*n).
Figure 3 : Le code de la méthode récursive avec mémoïsation.
6
4. Programmation simple
La méthode est similaire à l'approche itérative, où nous utilisons deux boucles pour remplir un
tableau. Cependant, pour reconstruire la plus longue sous-séquence commune, nous ajoutons une
boucle while supplémentaire.
Sa complexité est donc O(m*n).
Figure 4 : Le code de la méthode simple.
7
III. Conclusion
En résumé, l'approche itérative de la programmation dynamique est généralement préférée
en raison de sa performance et de sa simplicité d'implémentation, sauf si la mémoire est une
préoccupation majeure. La méthode récursive avec mémoïsation est également efficace tout en
conservant la simplicité de l'approche récursive. L'approche récursive pure est rarement utilisée en
pratique en raison de sa faible efficacité. L'algorithme simple est une option pour ceux qui préfèrent
une approche plus intuitive, bien que ses performances et sa consommation mémoire soient
comparables à l'approche itérative de la programmation dynamique.
