Exercice 2 - Partie A · 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 A

Dans cette partie, on s'attache à déterminer une LCS selon la stratégie de « recherche exhaustive ». La première fonction implémentée construit toutes les sous-listes d'une liste passée en paramètre, en appliquant l'algorithme suivant:

Fonction sous_listes(L: list, accumulateur: list[list])

->list[list]

Début

| Si L est vide alors

| | renvoyer l'accumulateur (initialement égal à [[]])

| Sinon

| | Extraire e le dernier élément de L

| | Créer L_t une liste temporaire vide

| | Ajouter dans L_t chaque sous-liste présente dans

| | l'accumulateur, après lui avoir ajouté, en tête, e

| | Renvoyer le résultat d'un nouvel appel à la fonction

| | avec pour paramètres

| | - la liste diminuée de cet élément e

| | - l'union des éléments de l'accumulateur et de la

| | liste temporaire

| FinSi

Fin

1.

Recopier et compléter le tableau suivant, en indiquant la valeur des paramètres lors des appels récursifs, pour un appel initial sous_listes([9, 3, 7], [[]]).

Évolution des paramètres lors des appels récursifs

Appel

liste

accumulateur

appel initial

[9, 3, 7]

[[]]

1er sous-appel

[9, 3]

[[], [7]]

2nd sous-appel

dernier sous-appel

2.

La fonction suivante implémente l'algorithme étudié précédemment.

1 def sous_listes(liste: list, accumulateur = [[]]):

2 if len(liste) == 0:

3 return accumulateur

4 element = liste.pop()

5 tmp = []

6 for sous_liste in accumulateur:

7 tmp.append(...)

8 return sous_listes(...)

Recopier et compléter les lignes 7 et 8 du code de la fonction sous_listes.

3.

On implémente la fonction est_extraite ci-dessous qui renvoie True si une sous-liste peut être extraite d'une liste donnée et False sinon.

def est_extraite(sous_liste: list, liste: list):

index_ss_liste, index_liste = 0, 0

while index_ss_liste < len(sous_liste) and index_liste < len(liste):

if sous_liste[index_ss_liste] == liste[index_liste]:

index_ss_liste += 1

index_liste += 1

return index_ss_liste == len(sous_liste)

On implémente la fonction lcs_force_brute ci-dessous qui détermine une plus longue sous-liste commune à deux listes données et qui renvoie cette liste.

def lcs_force_brute(liste_1: list, liste_2: list):

tmp = sous_listes(liste_1)

resultat, maxi = [], 0

for element in tmp:

if est_extraite(element, liste_2) and len(element) > maxi:

resultat = element

maxi = len(element)

return resultat

Expliquer pourquoi l'exécution de la fonction lcs_force_brute risque de prendre beaucoup de temps selon la longueur des listes passées en paramètre. Justifier.