Exercice 3 - Tri et coût des algorithmes · 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.

Partie B. Classification d'une nouvelle espèce

Les espèces de papillons sont regroupées dans une liste de dictionnaires. Pour simplifier, seuls les attributs num (l'identifiant du papillon), nomCo (son nom commun), nomSc (son nom scientifique) et taille (sa taille) seront considérés dans cette partie.

Une partie de la liste papillon est donnée ci-dessous:

papillon = [

{'num': 458, 'nomCo': 'Monarque',

'nomSc': 'Danaus plexippu', 'taille': 100},

{'num': 459, 'nomCo': 'Citron de Provence',

'nomSc': 'Gonepteryx cleopatra', 'taille': 30},

{'num': 460, 'nomCo': 'Paon-du-jour',

'nomSc': 'Aglais io', 'taille': 6},

{'num': 461, 'nomCo': 'Machaon',

'nomSc': 'Papilio machaon', 'taille': 85},

{'num': 462, 'nomCo': 'Petite Tortue',

'nomSc': 'Aglais urticae', 'taille': 50},

{'num': 463, 'nomCo': 'Robert-le-Diable',

'nomSc': 'Polygonia c-album', 'taille': 25}

]

Le but de cette partie est de trier la liste des papillons par ordre croissant de taille et de classifier une nouvelle espèce photographiée.

La fonction tri_collec renvoie la liste de dictionnaires des papillons triée par ordre croissant de taille.

1 def tri_collec(collec):

2 """Renvoie la collection des papillons triées

3 par ordre croissant de leur taille.

4 Paramètre:

5 collec: liste de dictionnaires des papillons

6 Renvoie:

7 liste triée par ordre croissant des tailles

8 des papillons.

9 """

10 for i in range(1, len(collec)):

11 pap = collec[i]

12 j =...

13 while j > 0 and collec[j - 1]['taille'] >...:

14 collec[j] = collec[j - 1]

15 j =...

16 collec[j] = pap

17 return...

10.

Recopier et compléter les lignes 12, 13, 15 et 17 de la fonction tri_collec.

11.

Nommer le tri utilisé.

12.

Indiquer, en justifiant, parmi les propositions suivantes quel est le coût en temps de ce tri, dans le pire cas, pour un tableau de taille $n$: linéaire, quadratique, logarithmique ou exponentiel.

L'algorithme des $k$ plus proches voisins est utilisé pour classifier la nouvelle espèce photographiée.

13.

Expliquer brièvement le principe de cet algorithme.