Exercice 3 - Recherche textuelle et algorithme de… · Bac Numérique et Sciences Informatiques Métropole 1 remplacement 2025

Exercice 3 (8 points)

Cet exercice porte sur le langage SQL, sur la programmation en Python et la recherche textuelle.

Le sujet d'une étude porte sur les papillons, la corrélation entre leur présence et celle de certaines plantes ainsi que sur la classification de nouvelles espèces.

Partie A. Corrélation avec la présence des plantes

Dans cet exercice, on pourra utiliser les clauses du langage SQL pour:

construire des requêtes d'interrogation à l'aide de SELECT, FROM, WHERE (avec les opérateurs logiques AND, OR), JOIN... ON;

construire des requêtes d'insertion et de mise à jour à l'aide de UPDATE, INSERT.

Dans le cadre de cette étude, une base de données faune_flore.db a été créée pour étudier la corrélation entre la présence d'espèces de papillons et celle de certaines plantes. Cette base de données regroupe les tables papillon, plante et zone_geographique.

La table papillon comporte les informations suivantes:

l'identification du papillon ( num);

le nom commun du papillon ( nomCo);

le nom scientifique du papillon ( nomSc);

la taille moyenne du papillon en millimètres ( taille);

le principal habitat du papillon ( habitat);

la zone géographique où le papillon est le plus présent ( zone). Cet attribut fait référence à l'attribut num de la table zone_geographique.

Un extrait de cette table est donné ci-après.

Cette nouvelle espèce montre beaucoup de ressemblance avec l'espèce 'Aglais io' mais diffère par la taille et la couleur des motifs des ailes.

Pour vérifier l'hypothèse que la nouvelle espèce est l'espèce 'Aglais io' comportant une mutation génétique, une recherche naïve d'une séquence caractéristique des papillons 'Aglais io' est réalisée sur la chaîne d'ADN extraite de la nouvelle espèce. Une chaîne d'ADN est représentée en Python par une chaine de caractères. Cette recherche utilise la fonction recherche_seq(seq, chaine) qui renvoie l'indice du premier caractère de seq si la séquence seq est présente dans la chaîne d'ADN chaine et -1 sinon.

1 def recherche_seq(seq, chaine):

2 """Renvoie l'indice du premier caractère de

3 chaine où commence `seq` si la séquence `seq`

4 se trouve dans la chaine de caractères chaine,

5 -1 sinon

6 Paramètres:

7 seq: séquence à rechercher

8 chaine: chaine d'ADN

9 Renvoie:

10 indice du premier caractère de seq dans

11 la chaine, -1 sinon.

12 """

13 for i in range(len(chaine) - len(seq) + 1):

14 j = 0

15 while j < len(seq) and...:

16 j += 1

17 if...:

18 return i

19 return -1

14.

Recopier et compléter les lignes 15 et 17 de la fonction recherche_seq.

La fonction recherche_BMH(seq, chaine), donnée ci-dessous, implémente l'algorithme de Boyer-Moore Horspool.

1 def dico_lettres(seq):

2 d = {}

3 for i in range(len(seq) - 1):

4 d[seq[i]] = i

5 return d

6

7 def recherche_BMH(seq, chaine):

8 decalage = dico_lettres(seq)

9 i = 0

10 n = len(seq)

11 while i <= len(chaine) - n:

12 j = n - 1

13 while j >= 0 and chaine[i + j] == seq[j]:

14 j -= 1

15 if j == -1:

16 return i

17 else:

18 if chaine[i + n - 1] in decalage:

19 i += n - decalage[chaine[i + n - 1]] - 1

20 else:

21 i += n

22 return -1

15.

Expliquer le principe de cet algorithme et son avantage par rapport à la fonction naïve recherche_seq.