Puissance Alpha — NSI 2022

Présentation de l'épreuve

Cette épreuve fait partie du concours Puissance Alpha (admission post-bac en cursus ingénieur), édition 2022. L'épreuve « Sciences Appliquées » dure 1h et regroupe 28 exercices répartis en 4 matières (NSI, Sciences de l'Ingénieur, SVT, Physique-Chimie) ; un candidat ne traite que les 7 exercices de la matière qu'il a choisie. La calculatrice et tout appareil électronique sont interdits.

Barème. Chaque exercice comporte 4 affirmations a, b, c, d à qualifier de vraies (V) ou fausses (F). Une réponse exacte rapporte 1 point, une réponse fausse fait perdre 0,5 point, une abstention ne rapporte ni ne retire de point. Une bonification d'1 point supplémentaire est accordée chaque fois qu'un exercice est traité intégralement et correctement (les 4 affirmations justes). Un candidat doit traiter au maximum 6 des 7 exercices de sa matière ; au-delà, seuls les 6 premiers sont corrigés.

Exercice 1 — Bases de données

On considère une petite base de données de réservations de restaurant, structurée par le schéma relationnel suivant :

• Reservation (numéro, date)
• Client (nom, prénom, téléphone)
• Table (numéro, nombre de couverts)
• une association Effectue relie chaque réservation à exactement un client, un même client pouvant effectuer plusieurs réservations (cardinalité 1,1 côté Réservation vers 1,n côté Client) ;
• une association Correspond relie chaque réservation à exactement une table, une même table pouvant apparaître dans 0 à n réservations différentes (cardinalité 1,1 côté Réservation vers 0,n côté Table).

Dire si chacune des affirmations suivantes est vraie ou fausse.

a) MySQL est un langage de bases de données.

b) Une table du restaurant peut n'être associée à aucune réservation.

c) Il est impossible, à partir de ce schéma, de savoir si une même table a été réservée plusieurs fois à la même date.

d) On peut savoir, à partir de ce schéma, si une table est disponible à une date donnée.

Exercice 2 — Structures de données abstraites : liste, file, pile

Soit $F$ une file (structure de données abstraite), et $P_1$, $P_2$ deux piles, initialement vides.

a) Les deux piles $P_1$ et $P_2$ peuvent permettre de reconstituer le comportement d'une file $F$.

b) Le comportement d'une file est décrit par le sigle LIFO.

c) Le type list de Python correspond à la structure de données abstraite « liste ».

d) L'exécution d'une fonction factorielle implémentée de façon récursive en Python s'apparente, dans son fonctionnement interne, à l'utilisation d'une pile.

Exercice 3 — Graphes

On considère le graphe orienté à 5 sommets $A$, $B$, $C$, $D$, $E$, défini par les arcs suivants : $A\to B$, $A\to E$, $B\to C$, $C\to D$, $E\to C$, $E\to D$.

a) En ignorant l'orientation des arcs, la matrice d'adjacence de ce graphe (sommets classés par ordre alphabétique $A,B,C,D,E$) est :

b) En tenant compte de l'orientation des arcs, la matrice d'adjacence devient :

c) La liste des prédécesseurs de chaque sommet est : $A$ : aucun ; $B$ : $A$, $E$ ; $C$ : $B$, $E$ ; $D$ : $C$, $E$ ; $E$ : $A$.

d) La liste des successeurs de chaque sommet est : $A$ : $B$, $E$ ; $B$ : $C$ ; $C$ : $D$ ; $D$ : aucun ; $E$ : $C$, $D$.

Exercice 4 — Réseaux

On considère un petit réseau de 6 routeurs. Le routeur central R2 est relié directement à trois voisins : R1 (réseau 192.168.0.0, interface 192.168.0.100), R3 (réseau 32.0.0.0, interface 32.2.2.1) et R4 (réseau 16.0.0.0, interface 16.1.1.1). En aval de R4 se trouvent deux routeurs supplémentaires, R5 (réseau 17.0.0.0) et R6 (réseau 18.0.0.0).

a) La table de routage de R2 est la suivante :

b) Le message RIP émis par le routeur R3 est :

c) La ligne « Défaut » de la table de routage de R2 correspond à l'ensemble des datagrammes qui ne seront jamais transmis par ce routeur.

d) Dans une connexion HTTPS, la clé privée du serveur sert à chiffrer le message et la clé publique à le déchiffrer.

Exercice 5 — Décidabilité et récursivité

On considère les deux fonctions récursives suivantes, calculant chacune la suite de Syracuse d'un entier $n$ :

def seq(n: int):
    if n == 1:
        return n
    if n % 2 == 0:
        return seq(n // 2)
    else:
        return seq(3 * n + 1)
 
def seq2(n: int):
    if n % 2 == 0:
        return seq2(n // 2)
    else:
        return seq2(3 * n + 1)

a) Les deux fonctions seq et seq2 se terminent pour toute entrée $n$.

b) On conjecture que la suite de Syracuse atteint toujours 1, mais aucune démonstration mathématique n'a pour l'instant confirmé cette conjecture pour tout entier de départ : il s'agit donc d'un problème pour lequel on ne dispose pas d'algorithme de décision garanti.

c) Une fonction récursive permet toujours de diminuer la complexité d'un programme par rapport à une version itérative.

d) Pour la fonction seq, la programmation dynamique (mémoïsation) permettrait de réduire le coût de calcul en évitant de refaire des appels déjà traités.

Exercice 6 — Analyse et validation de programme

On donne le programme Python suivant, censé ouvrir un fichier en lecture de façon sécurisée :

def ouvrir_fichier_lecture(nom_fichier):
    erreur = ""
    f = None
    try:
        f = open(nom_fichier, "r")
    except FileNotFoundError:
        erreur = "le fichier est introuvable"
    return f, erreur
 
fic, err = ouvrir_fichier_lecture("test.txt")
if err != "":
    print(err)
 
f = open("test.txt", "r")

a) La fonction ouvrir_fichier_lecture suffit, à elle seule, à garantir que le programme entier ne « plantera » jamais.

b) Si le fichier n'existe pas, l'appel à ouvrir_fichier_lecture permet de produire un message d'erreur explicite plutôt qu'un plantage brutal.

c) L'instruction assert de Python permet de construire des tests unitaires pour valider le comportement d'une fonction.

d) La fonction isinstance suffit, à elle seule, à vérifier la totalité des conditions attendues sur une donnée fournie en entrée d'un programme.

Exercice 7 — Méthodes d'optimisation d'algorithmes

On rappelle la suite de Fibonacci, définie par $u_0=0$, $u_1=1$, et $u_n=u_{n-1}+u_{n-2}$ pour $n\geqslant2$. La fonction récursive naïve suivante permet de la calculer :

def fibo(n):
    if n == 0 or n == 1:
        return n
    else:
        return fibo(n - 1) + fibo(n - 2)

a) L'algorithme récursif ci-dessus est qualifié d'« algorithme naïf ».

b) La programmation dynamique de type « bottom-up » (calcul itératif en partant des petits indices) permet d'optimiser le calcul des termes de la suite de Fibonacci.

c) Comparé à un tri par insertion, le tri fusion permet de passer d'une complexité en $O(n^2)$ à une complexité en $O(n\log_2(n))$.

d) La méthode « diviser pour régner » est une approche efficace pour la recherche d'un motif dans un texte.