Geipi Polytech — NSI 2021

Présentation de l'épreuve

Cette épreuve de Numérique et Sciences Informatiques fait partie du concours Geipi Polytech (admission post-bac en cursus ingénieur), édition 2021. Elle comporte 3 exercices indépendants portant sur les structures de données abstraites, les bases de données relationnelles couplées à Python, et les arbres binaires (tas).

Exercice 1 — File d'attente et algorithme du tourniquet

Une file est une structure de données abstraite fondée sur le principe « premier entré, premier sorti » (FIFO — First In, First Out). On la munit de quatre opérations primitives :

1. On choisit d'implémenter une file à l'aide d'une liste Python. Compléter les quatre fonctions ci-dessous pour qu'elles respectent la spécification donnée dans le tableau :

def creer_file():
    return ...
 
def est_vide(F):
    return ...
 
def enfiler(F, x):
    F. ...(x)
 
def defiler(F):
    return F.pop(...)

On simule l'exécution de trois tâches sur un serveur de calcul partagé, en suivant l'algorithme d'ordonnancement du tourniquet (round-robin). On pose les hypothèses suivantes : une seule instruction s'exécute à un instant donné ; l'exécution d'une instruction prend exactement une unité de temps ; la commutation entre deux tâches est instantanée ; les tâches ne se disputent aucune ressource autre que le processeur.

Trois tâches A, B et C comportent respectivement 4, 3 et 5 instructions. Le tourniquet exécute une instruction de A, puis une de B, puis une de C, puis revient à A, et ainsi de suite jusqu'à ce que les 12 instructions aient toutes été exécutées ; dès qu'une tâche est terminée, elle sort définitivement de la file.

2. Dans quel ordre sont exécutées les instructions des tâches A, B et C ?

On représente une tâche par un dictionnaire à trois clés : 'id', 'duree' (nombre total d'instructions) et 'temps' (nombre d'instructions déjà exécutées). Avant son passage, la tâche A est représentée par {'id': 'A', 'duree': 4, 'temps': 0}. Les tâches à exécuter sont stockées dans une file, qui ne doit être manipulée qu'avec les 4 opérations primitives ci-dessus.

3. La fonction tourniquet ci-dessous prend en paramètre une file de tâches et affiche la séquence des instructions exécutées, en suivant l'algorithme du tourniquet. Indiquer par quelles expressions remplacer ① et ②, et quelle instruction placer en ③.

def tourniquet(F):
    while not(est_vide(F)):
        x = defiler(F)
        x['temps'] = ①
        print(x['id'], "-", x['temps'])
        if ②:
            ③

4. Écrire les instructions Python qui préparent la file de tâches avant d'appeler tourniquet(F), pour simuler l'exemple des tâches A, B et C décrites plus haut (dans cet ordre).

Exercice 2 — Base de données et Python : une collection de jeux vidéo

Un joueur, perdu dans sa collection de jeux vidéo, décide de la répertorier dans un fichier mes_jeux.csv. Un extrait de ce fichier est donné ci-dessous ; un jeu apparaît autant de fois qu'il a de plateformes de sortie.

Pour consulter plus facilement cette liste, le joueur crée une base de données relationnelle exploitable en SQL, avec deux tables : jeux (clé primaire idjeu, attributs titre et annee) et sorties (clé étrangère idjeu référençant jeux, attribut plateforme). Les attributs titre et plateforme sont des chaînes de caractères, les attributs idjeu et annee sont des entiers.

1. Immédiatement après avoir créé ses deux tables (encore vides), quelle séquence de requêtes SQL le joueur doit-il écrire pour enregistrer le jeu « Nebula Drift » et ses deux plateformes de sortie ?

On suppose maintenant que les tables jeux et sorties contiennent toutes les données du tableau ci-dessus, et rien d'autre.

2. On rappelle que la fonction d'agrégation COUNT() compte le nombre d'enregistrements dans une table. Quel est le résultat de la requête SELECT COUNT(plateforme) FROM sorties; ?

3. Écrire la requête SQL qui liste les titres des jeux sortis entre 2000 (inclus) et 2020 (exclus).

4. Écrire la requête SQL, utilisant une jointure entre jeux et sorties, qui liste le titre et l'année de tous les jeux disponibles sur « PC ».

Le joueur souhaite aussi exploiter ces données en Python. Il crée deux listes de dictionnaires, liste_jeux et liste_sorties, contenant toutes les informations du tableau ; liste_jeux est triée par ordre alphabétique des titres, et liste_sorties par ordre alphabétique des plateformes.

liste_jeux = [ {'idjeu': 205, 'titre': 'Chrono Vale', 'annee': 2019},
               {'idjeu': 310, 'titre': 'Iron Horizon', 'annee': 2007},
               ... ]
 
liste_sorties = [ {'idjeu': 101, 'plateforme': 'PC'},
                   {'idjeu': 418, 'plateforme': 'PC'},
                   ... ]

5. Le joueur écrit une procédure pour afficher toutes les informations du tableau, dans l'ordre alphabétique des plateformes. Compléter le code de cette procédure.

for ① in ②:
    for ③ in ④:
        if ⑤:
            print(jeu['idjeu'], jeu['titre'], jeu['annee'], sortie['plateforme'])

6. Cette procédure n'affiche que 5 des 7 lignes attendues : le joueur réalise qu'il a fait des fautes de frappe en saisissant certains idjeu dans liste_sorties. Pour s'en prémunir à l'avenir, il écrit la fonction coherent ci-dessous, qui renvoie True si tous les idjeu de liste_sorties apparaissent bien dans liste_jeux, et False sinon.

def coherent(jeux, sorties):
    for s in sorties:
        if not contient_id(jeux, s['idjeu']):
            return False
    return True

Compléter la définition de la fonction contient_id (recherche séquentielle) pour obtenir le résultat attendu.

7. En supposant que liste_jeux est triée par ordre croissant d'idjeu, on peut remplacer contient_id par une fonction de recherche dichotomique, plus rapide. Écrire les expressions à utiliser pour remplacer ①, ② et ③ dans la définition récursive ci-dessous, qui prend en paramètres les indices minimum et maximum de l'intervalle de recherche :

def contient_id_rec(liste, id, imin, imax):
    if imin > imax:
        return False
    pivot = int((imin + imax) / 2)
    if liste[pivot]['idjeu'] < id:
        return ①
    if liste[pivot]['idjeu'] > id:
        return ②
    return ③

8. Le joueur modifie coherent pour remplacer l'appel à contient_id par un appel à contient_id_rec. Qu'a-t-il écrit à la place ?

9. Sans tri préalable, la vérification de cohérence peut être rendue plus rapide en stockant liste_jeux dans un dictionnaire dont les clés seraient les idjeu. Par quelle expression, utilisant une compréhension de dictionnaire, remplacer ① pour créer un tel dictionnaire à partir de liste_jeux ?

def coherent_rapide(jeux, sorties):
    dico = ①
    return len([s for s in sorties if s['idjeu'] not in dico]) == 0

Exercice 3 — Tas et file de priorité

On appelle tas (ou max-heap) un arbre binaire presque complet (tous les niveaux sont remplis, sauf éventuellement le dernier, rempli sur la gauche) tel que la valeur contenue dans un nœud est toujours supérieure ou égale aux valeurs contenues dans ses fils. On représente un tas contenant des entiers par une simple liste : la racine a pour indice 0, le fils gauche du nœud d'indice i a pour indice 2*i + 1, et son fils droit pour indice 2*i + 2. On suppose définies les fonctions gauche(i) et droite(i), qui renvoient respectivement ces deux indices.

1. Parmi les listes suivantes, lesquelles représentent un tas ?

2. Compléter la fonction parent pour qu'elle renvoie l'indice du parent du nœud d'indice i > 0.

def parent(i):
    return ...

3. Compléter la fonction est_feuille pour qu'elle renvoie True si le nœud d'indice i du tas T est une feuille, False sinon.

def est_feuille(T, i):
    return ...

4. L'appel echanger(T, i, j) échange les valeurs des éléments d'indices i et j dans la liste T. La fonction descendre ci-dessous permet de rétablir la propriété de tas après avoir diminué la valeur contenue dans le nœud d'indice i (elle compare ce nœud à son plus grand fils, et échange si nécessaire, en propageant récursivement). Indiquer par quelles expressions remplacer ①, ② et ③, et quelle instruction placer en ④.

def descendre(T, i):
    if not est_feuille(T, i):
        j = gauche(i)
        if droite(i) < len(T):
            if ①:
                j = ②
        if ③:
            echanger(T, i, j)
            ④

5. La fonction maximum renvoie le plus grand élément du tas, le supprime, et rétablit la propriété de tas. Indiquer par quelles expressions remplacer ① et ②, et quelle instruction placer en ③.

def maximum(T):
    x = T[①]
    T[①] = T.pop()
    ③
    return x