Geipi Polytech — NSI 2023

Présentation de l'épreuve

Cette épreuve de Numérique et Sciences Informatiques fait partie du concours Geipi Polytech, édition 2023. Elle comporte 2 exercices indépendants : le premier porte sur la modélisation d'un réseau de transport par téléphériques urbains, le second sur la détection de photos en double dans une photothèque numérique.

Exercice 1 — Un réseau de téléphériques urbains

On modélise un réseau de téléphériques urbains desservant des stations en continu. Une station est représentée par une chaîne de caractères (son nom) ; deux stations différentes portent toujours des noms différents.

Une ligne est représentée par un dictionnaire à trois clés : 'num' (un entier identifiant la ligne, unique), 'arrets' (une liste ordonnée et sans doublon de noms de stations, dans l'ordre où les cabines les desservent) et 'circulaire' (un booléen indiquant si la ligne fonctionne en boucle fermée, sans jamais faire demi-tour — auquel cas elle n'a pas de terminus). Un réseau est une liste non ordonnée et sans doublon de lignes.

On considère un réseau à deux lignes : la ligne 1, circulaire, dessert dans cet ordre les stations Gare, Marché et Château ; la ligne 2, non circulaire, va du Port à la Place en desservant Marché puis Stade.

1. Compléter le code Python ci-dessous pour que les variables ligne1 et ligne2 représentent ces deux lignes.

ligne1 = { 'num': ..., 'arrets': [...], 'circulaire': ... }
ligne2 = { 'num': ..., 'arrets': [...], 'circulaire': ... }

2. Compléter la fonction direct pour qu'elle renvoie True s'il existe un trajet direct (sans changer de ligne) entre les stations depart et arrivee dans le réseau reseau, False sinon. Indication : sur une ligne non circulaire, le trajet s'effectue dans un sens à l'aller et dans l'autre au retour ; il suffit donc que les deux stations figurent sur la même ligne, quel que soit leur ordre dans 'arrets'.

def direct(reseau, depart, arrivee):
    for ligne in ①:
        nb = ②
        for station in ③:
            if (station == depart) ④ (station == arrivee):
                nb = ⑤
        if ⑥ == 2:
            return True
    return False

3. Compléter la fonction lister_lignes, qui reçoit un réseau et renvoie un dictionnaire associant à chaque station la liste (non ordonnée, sans doublon) des numéros de lignes qui la desservent.

def lister_lignes(reseau):
    dico = {}
    for ligne in ①:
        for station in ②:
            if ③:
                dico[station].append(④)
            else:
                dico[station] = ⑤
    return dico

4. Compléter la fonction direct_bis, qui reçoit le dictionnaire renvoyé par lister_lignes(reseau) ainsi que deux stations, et renvoie la même valeur que direct(reseau, depart, arrivee), mais en exploitant ce dictionnaire plutôt qu'en reparcourant tout le réseau.

def direct_bis(dico, depart, arrivee):
    for ligne in ①:
        if ligne in ②:
            return ③
    return ④

Exercice 2 — Détecter les photos en double dans une photothèque

Une application de gestion de photos souhaite repérer et supprimer automatiquement les doublons visuels d'une photothèque. Une photothèque est une liste de couples (nom du fichier, taille en octets) ; on note $(F_i, t_i)$ le couple associé à la photo $i$.

On dispose d'une fonction traits(fichier) qui s'appuie sur un réseau de neurones pour analyser une image et en extraire une liste de caractéristiques visuelles, sous la forme d'une liste de valeurs comprises dans $[0, 1]$ ; deux appels sur des fichiers différents renvoient des listes de même longueur.

Similarité cosinus. Pour mesurer la ressemblance entre deux photos, on calcule la similarité cosinus entre leurs listes de traits $x = [x_1, \ldots, x_n]$ et $y = [y_1, \ldots, y_n]$ :

1. Compléter la fonction simcos ci-dessous (on rappelle que sqrt calcule une racine carrée).

from math import sqrt
 
def simcos(x, y):
    produit = 0
    sx2 = 0
    sy2 = 0
    for i in range(0, len(x)):
        produit = produit + ①
        sx2 = sx2 + ②
        sy2 = sy2 + ③
    return ④ / sqrt(sx2 * sy2)

Algorithme glouton de regroupement. On parcourt la photothèque, et pour chaque couple $(F_i, t_i)$ pas encore retiré : on crée un groupe $G_i$ initialisé avec ce seul couple, on lui ajoute toutes les photos encore présentes dont la similarité avec $F_i$ dépasse un seuil donné, et on les retire de la photothèque. On renvoie la liste de tous les groupes ainsi formés.

2. Compléter la fonction regrouper.

def regrouper(base, seuil):
    tous_les_groupes = []
    while len(base) > 0:
        (F0, t0) = ①
        groupe = [②]
        x = traits(F0)
        for Fi, ti in ③:
            y = traits(Fi)
            if ④ >= seuil:
                groupe.append((Fi, ti))
        for g in groupe:
            base.remove(g)
        ⑤
    return tous_les_groupes

3. On souhaite ne conserver qu'une seule photo par groupe : celle dont le fichier est le plus lourd (en espérant que ce soit la meilleure qualité). Compléter les fonctions plus_lourde (renvoie le nom du fichier le plus lourd d'un groupe non vide) et plus_legeres (renvoie la liste des noms de fichiers à supprimer, c'est-à-dire tous les autres).

def plus_lourde(groupe):
    fichier, taille = groupe[0]
    for i in ①:
        if groupe[i][1] > ②:
            fichier, taille = groupe[i]
    return ③
 
def plus_legeres(groupe):
    liste = []
    fichier, taille = groupe[0]
    for i in range(1, len(groupe)):
        if groupe[i][1] > taille:
            liste.append(fichier)
            fichier, taille = groupe[i]
        else:
            liste.append(④)
    return liste

4. Compléter la fonction plan_suppression, qui appelle regrouper puis renvoie une liste de couples (fichier à conserver, liste des fichiers à supprimer), un couple par groupe formé.

def plan_suppression(base, seuil):
    return [ (①, ②) for g in ③ ]

5. Mise en cache. La fonction traits étant coûteuse, on souhaite éviter de la rappeler plusieurs fois pour une même photo. On utilise un cache sous forme de dictionnaire {nom de fichier : traits déjà calculés}. Compléter traits_cache, destinée à remplacer tous les appels à traits dans regrouper.

cache = {}
 
def traits_cache(fichier):
    if fichier ① cache:
        cache[fichier] = ②
    return ③