Exercice 2 - Partie B · Bac Numérique et Sciences Informatiques Antilles-Guyane 2026 (jour 1)

Exercice 2 (6 points)

Cet exercice porte sur l'algorithmique et la programmation Python.

La recherche d'une plus longue sous-liste commune à deux listes est un problème connu sous le nom de « Longest Common Subsequence » (LCS).

Les éléments d'une plus longue sous-liste commune sont des éléments communs aux deux listes initiales, où ils apparaissent dans le même ordre, mais pas nécessairement de façon contiguë. Ainsi, les listes L_1 = [9, 3, 7, 5, 8] et L_2 = [9, 7, 8, 3, 7, 3] ont notamment en commun les sous-listes [], [9], [3], [9, 7], [9, 3, 7] ou [9, 7, 8]. Les plus longues sous-listes communes à ces deux listes sont [9, 3, 7] et [9, 7, 8], de longueur commune égale à 3.

En Python, il est possible d'obtenir la concaténée de deux valeurs de types list en utilisant +. Par exemple, [1, 2] + [3, 4] s'évalue à [1, 2, 3, 4] et []+[1] s'évalue à [1].

Partie B

Soient $m$ et $n$ deux entiers naturels, $m'$ et $n'$ des entiers tels que $0 \le m' < m$ et $0 \le n' < n$. On suppose, dans cette partie, disposer d'une fonction lcs qui, pour deux listes quelconques L_1 et L_2, de tailles respectives $m$ et $n$, et des entiers $m'$ et $n'$ passés en paramètres, renvoie une plus longue sous-liste commune à:

la sous-liste de L_1 constituée des $m'$ premiers éléments;

et la sous-liste de L_2 constituée des $n'$ premiers éléments.

Ainsi,

lcs([9, 3, 7, 5, 8], 0, [9, 7, 8, 3, 7, 3], 0) est une plus longue sous-liste commune à deux listes vides, soit [];

lcs([9, 3, 7, 5, 8], 3, [9, 7, 8, 3, 7, 3], 2) est une plus longue sous-liste commune à [9, 3, 7] et [9, 7], soit la sous-liste [9, 7].

4.

Indiquer ce que renvoie l'appel suivant:

lcs([9, 3, 7, 5, 8], 1, [9, 7, 8, 3, 7, 3], 1)

On suppose, dans cette question, que L_1 et L_2 sont des listes non vides dont les derniers éléments sont identiques: $m \ge 1$, $n \ge 1$, L_1[m-1] et L_2[n-1] égaux.

Exemple: $m = 5$, $n = 3$, L_1 = [9, 3, 7, 5, 8] et L_2 = [9, 7, 8].

5.

Écrire la relation de récurrence pour obtenir une plus longue sous-liste commune aux deux listes L_1 et L_2 à partir du résultat de lcs(L_1, m-1, L_2, n-1).

A contrario, lorsque les derniers éléments des listes sont différents ($m \ge 1$, $n \ge 1$, L_1[m-1] et L_2[n-1] distincts), une plus longue sous-suite commune aux deux listes L_1 et L_2 s'obtient en choisissant une plus grande liste parmi les résultats de lcs(L_1, m-1, L_2, n) et lcs(L_1, m, L_2, n-1).

Par exemple, avec $m = 5$, $n = 4$, L_1 = [9, 3, 7, 5, 8] et L_2 = [9, 7, 8, 3], on compare les longueurs d'une LCS de [9, 3, 7, 5] et L_2 = [9, 7, 8, 3] (soit [9, 7]) et d'une LCS de L_1 = [9, 3, 7, 5, 8] et [9, 7, 8] (soit [9, 7, 8]), ce qui permet d'obtenir la LCS [9, 7, 8] pour L_1 et L_2.

On implémente donc la fonction suivante qui prend en paramètres deux listes et qui renvoie une plus longue sous-liste commune:

def lcs_top_down(liste_x: list, liste_y: list):

def aux(liste_x, index_x, liste_y, index_y):

if (index_x < 0) or (index_y < 0):

return []

if liste_x[index_x] == liste_y[index_y]:

return aux(liste_x, index_x-1, liste_y, index_y-1) + [liste_x[index_x]]

resultat_1 = aux(liste_x, index_x, liste_y, index_y-1)

resultat_2 = aux(liste_x, index_x-1, liste_y, index_y)

if len(resultat_1) >= len(resultat_2):

return resultat_1

return resultat_2

return aux(liste_x, len(liste_x)-1, liste_y, len(liste_y)-1)

6.

Justifier que la fonction aux contenue dans la fonction lcs_top_down est récursive.

7.

Détailler le risque d'un tel choix dans la présente situation, lorsque les listes L_1 et L_2 sont très grandes.

8.

Proposer une solution pour éviter le problème évoqué à la question 7.