Geipi Polytech — NSI 2024

Présentation de l'épreuve

Cette épreuve de Numérique et Sciences Informatiques fait partie du concours Geipi Polytech, édition 2024. Elle comporte 2 exercices indépendants : le premier porte sur les bases de données relationnelles et le langage SQL, avec une ouverture vers Python et les dictionnaires ; le second porte sur les graphes, la récursivité et l'algorithme de Dijkstra.

Exercice 1 — Base de données d'une application de recettes de cuisine

On souhaite stocker la composition de recettes de cuisine ainsi que l'analyse nutritionnelle moyenne de leurs ingrédients (pourcentages de glucides, de lipides et de protéines). Le schéma relationnel comporte trois relations :

• recette(id_recette, nom)
• composition(#id_recette, #id_ingredient, quantite)
• valeurs_nutritives(id_ingredient, nom, glucides, lipides, proteines)

Les attributs dont le nom commence par id_ sont des entiers, les attributs nom sont des chaînes de caractères, les autres attributs sont des réels. Les clés primaires sont soulignées, les clés étrangères précédées de #. Le couple (composition.id_recette, composition.id_ingredient) est la clé primaire de composition ; composition.id_recette référence recette.id_recette, et composition.id_ingredient référence valeurs_nutritives.id_ingredient.

1. On suppose les trois tables encore vides. On considère les cinq requêtes d'insertion suivantes :

(r1) INSERT INTO recette VALUES (1, 'Salade de quinoa');
(r2) INSERT INTO composition VALUES (1, 10, 150.0);
(r3) INSERT INTO composition VALUES (1, 11, 30.0);
(r4) INSERT INTO valeurs_nutritives VALUES (10, 'quinoa', 21.3, 1.9, 4.4);
(r5) INSERT INTO valeurs_nutritives VALUES (11, 'huile de tournesol', 0.0, 100.0, 0.0);

Pour chacun des quatre ordres d'exécution suivants, indiquer si une erreur se produit (et, si oui, laquelle).

• Ordre 1 : (r1), (r2), (r3), (r4), (r5)
• Ordre 2 : (r1), (r5), (r4), (r3), (r2)
• Ordre 3 : (r2), (r3), (r4), (r5), (r1)
• Ordre 4 : (r5), (r1), (r4), (r2), (r3)

2. On suppose que les tables recette et composition contiennent chacune au moins un enregistrement.

(a) Le résultat de la requête ci-dessous peut-il être vide ? Justifier brièvement.

SELECT * FROM recette
JOIN composition ON recette.id_recette = composition.id_recette;

(b) Même question pour la requête ci-dessous.

SELECT * FROM composition
JOIN recette ON recette.id_recette = composition.id_recette;

3. Le mot-clé DISTINCT élimine les doublons du résultat d'une requête : un id_recette n'apparaîtra donc au plus qu'une fois dans le résultat. Compléter les requêtes ci-dessous.

(a) Liste des identifiants de recettes contenant l'ingrédient d'identifiant 7, celui d'identifiant 12, ou les deux :

SELECT DISTINCT id_recette
FROM ①
WHERE id_ingredient ② 7 ③ id_ingredient ② 12;

(b) Liste des identifiants de recettes contenant au moins un ingrédient dont la part de lipides dépasse 50 % :

SELECT DISTINCT id_recette
FROM ①
④
WHERE lipides > 0.5;

4. Compléter (sans ajouter de mot-clé SQL supplémentaire) la requête ci-dessous, dont le résultat indique la composition de chaque recette sous forme d'une liste d'enregistrements (id_recette, nom de la recette, nom de l'ingrédient), triée par ordre alphabétique des noms de recette puis des noms d'ingrédients.

SELECT recette.id_recette, recette.nom, valeurs_nutritives.nom
FROM recette
JOIN ① ON recette.id_recette = ②
JOIN ③ ON ④
ORDER BY recette.nom, valeurs_nutritives.nom;

On dispose côté Python d'une fonction composition(id_recette), qui renvoie un dictionnaire {identifiant d'ingrédient : quantité (en grammes, pour une portion individuelle)}, et d'une fonction analyse(id_ingredient), qui renvoie un dictionnaire {'glucides', 'lipides', 'proteines' : pourcentage}.

5. Compléter la définition de la fonction nutri, qui renvoie le poids de glucides, lipides et protéines d'une portion individuelle de la recette dont l'identifiant lui est transmis, sous forme d'un dictionnaire aux clés 'glucides', 'lipides', 'proteines'.

def nutri(id_recette):
    res = ①
    comp = composition(id_recette)
    for i in comp.keys():
        a = analyse(i)
        for k in a.keys():
            res[k] = ② + ③ / 100 * ④[i]
    return res

Exercice 2 — Itinéraires entre refuges de montagne

Un office de tourisme balise un réseau de sentiers de randonnée reliant des refuges de montagne, et publie une application de calcul d'itinéraires. Chaque sentier a un nom et une longueur (en mètres), et relie deux refuges. La liste des sentiers commence ainsi :

sentiers = [('Aster', 'Lac Bleu', 'Croix Rouge', 150),
            ('Edelweiss', 'Lac Bleu', 'Pic Vert', 250),
            ('Bruyere', 'Croix Rouge', 'Pic Vert', 400),
            ('Gentiane', 'Pic Vert', "Col d'Argent", 300),
            ('Myrtille', 'Croix Rouge', "Col d'Argent", 600)]

On modélise ce réseau par un graphe orienté dont les sommets sont les refuges, et les arcs les sentiers (chaque sentier, praticable dans les deux sens, donne lieu à deux arcs). Un itinéraire correspond à un chemin dans ce graphe ; sa longueur est la somme des longueurs des sentiers empruntés.

On représente le graphe par un dictionnaire {refuge : liste de ses arcs sortants}, chaque arc sortant étant un triplet (refuge d'arrivée, nom du sentier, longueur).

1. Compléter la fonction creer_dico_arcs_sortants, qui construit ce dictionnaire à partir de la liste des sentiers. Un sentier reliant p1 à p2 donne lieu à un arc de p1 vers p2, et à un arc de p2 vers p1, tous deux de même longueur.

def creer_dico_arcs_sortants(sentiers):
    arcs = ①
    for (n, p1, p2, d) in sentiers:
        if p1 not in arcs:
            arcs[p1] = []
        arcs[p1].append((p2, n, d))
        if ② not in arcs:
            arcs[②] = []
        arcs[②].append(③)
    return arcs

Pour rechercher le plus court chemin, on utilise l'algorithme de Dijkstra, qui prend en entrée le graphe et un refuge de départ, et construit progressivement, par ordre croissant de distance, la liste des refuges et de leur distance minimale au départ. On utilise deux dictionnaires : a_visiter (refuges dont la distance est en cours de calcul) et visites (refuges dont la distance minimale est définitivement connue). Leurs clés sont des noms de refuges, leurs valeurs des triplets (distance, prédécesseur, sentier emprunté depuis ce prédécesseur).

Initialisation : tous les refuges sont dans a_visiter, le refuge de départ avec une distance de 0, les autres avec une distance infinie (from math import inf) ; visites est vide.

Tant qu'il reste des refuges à visiter :

1. on choisit le refuge N de plus petite distance dans a_visiter ;
2. pour chaque voisin V de N encore dans a_visiter, relié par un sentier S de longueur d : si la distance actuelle de V est supérieure à (distance de N) + d, on la met à jour, ainsi que le prédécesseur (N) et le sentier (S) ;
3. on retire N de a_visiter et on l'ajoute à visites.

2. Compléter la fonction plus_proche, qui prend en argument le dictionnaire a_visiter et renvoie le nom du refuge de plus petite distance.

from math import inf
 
def plus_proche(a_visiter):
    meilleure_dist = ①
    proche = ''
    for (refuge, (dist, pred, sentier)) in a_visiter.items():
        if dist < ①:
            (proche, meilleure_dist) = (②, dist)
    return proche

3. Compléter la fonction meilleur_chemin, qui prend en entrée la liste des sentiers, un refuge de départ et un refuge d'arrivée, calcule le plus court chemin par l'algorithme de Dijkstra, puis appelle la fonction affichage (question 4).

def meilleur_chemin(sentiers, depart, arrivee):
    arcs = creer_dico_arcs_sortants(sentiers)
    a_visiter = {r: (inf, '', '') for r in arcs.keys()}
    a_visiter[depart] = (①, '', '')
    visites = {}
    while a_visiter != {}:
        n = plus_proche(a_visiter)
        (dist_n, pred_n, sentier_n) = a_visiter[n]
        for (v, s, d) in arcs[②]:
            if v in a_visiter:
                (dist_v, pred_v, sentier_v) = a_visiter[v]
                nouvelle_dist = ③ + d
                if nouvelle_dist < dist_v:
                    a_visiter[v] = (nouvelle_dist, ④, s)
        visites[n] = a_visiter[n]
        del a_visiter[n]
    affichage(visites, depart, arrivee)

4. La fonction affichage ci-dessous est incomplète (les pass sont des instructions vides à remplacer, sauf deux d'entre eux qui doivent rester tels quels). Indiquer, parmi les quatre instructions suivantes, laquelle placer à chacune des lignes 2, 6, 7 et 8 :

(i)   print('aucun chemin du point', depart, 'au point', arrivee)
(ii)  print('étape au point', arrivee, '(distance', dist, ')')
(iii) print('en passant par le chemin', nom)
(iv)  affichage(visites, depart, depuis)

1. def affichage(visites, depart, arrivee):
2.     pass
3.     (dist, depuis, nom) = visites[arrivee]
4.     if dist == inf:
5.         pass
6.         pass
7.     if depart != arrivee:
8.         pass
9.         pass
10.        pass

Indication : à l'appel meilleur_chemin(sentiers, 'Lac Bleu', "Col d'Argent"), l'affichage attendu est :

étape au point Lac Bleu (distance 0)
en passant par le chemin Edelweiss
étape au point Pic Vert (distance 250)
en passant par le chemin Gentiane
étape au point Col d'Argent (distance 550)