Puissance Alpha — NSI 2024

Présentation de l'épreuve

Cette épreuve fait partie du concours Puissance Alpha (admission post-bac en cursus ingénieur), édition du samedi 27 avril 2024. L'épreuve « Sciences Appliquées » dure 1h et regroupe 38 exercices répartis en 5 matières (NSI, Sciences de l'Ingénieur, SVT, Physique-Chimie, Tronc commun) ; chaque candidat ne traite que les exercices correspondant à la matière qu'il présente au baccalauréat. 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. Un candidat doit choisir et traiter 6 exercices parmi les 7 de sa matière ; au-delà, seuls les 6 premiers traités sont corrigés.

Exercice 1 — Arbres binaires

On considère des arbres binaires disposant des méthodes suivantes : vide() (renvoie True si l'arbre est vide), g() et d() (sous-arbres gauche et droit), clef() (valeur de la racine). Un arbre vide est considéré comme un arbre binaire de recherche.

a) La fonction Python suivante est censée renvoyer True si un arbre binaire de clefs numériques est un arbre binaire de recherche, False sinon :

def est_abr(a):
    if a.vide() or (a.g().vide() and a.d().vide()):
        return True
    if (not a.g().vide()) and a.clef() < a.g().clef():
        return False
    if (not a.d().vide()) and a.clef() > a.d().clef():
        return False
    if not (a.g().vide() or a.d().vide()) and a.g().clef() > a.d().clef():
        return False
    return est_abr(a.g()) or est_abr(a.d())

Cette fonction est correcte.

b) À partir d'un parcours préfixe d'un arbre binaire, on peut déterminer sa hauteur avec une complexité en temps logarithmique ( $O(\ln(n))$ , $n$ étant le nombre de nœuds) dans le pire des cas.

c) À partir d'un parcours en largeur d'un arbre binaire, on peut déterminer sa hauteur avec une complexité en temps linéaire ( $O(n)$ ) dans le pire des cas.

d) On considère l'arbre binaire représentant l'expression $(4\times x)+3$ : la racine porte l'opérateur $+$ , son fils gauche porte l'opérateur $\times$ (lui-même de fils gauche $4$ et de fils droit $x$ ), et son fils droit est la feuille $3$ . Lors d'un parcours postfixe (ou suffixe) de cet arbre, l'ordre de visite des nœuds correspond à l'écriture $4\times x+3$ .

Exercice 2 — Réseaux et sécurité

a) La seule différence entre les protocoles de routage OSPF et RIP réside dans la métrique utilisée pour choisir les routes.

b) Si l'on envoie des données personnelles à un serveur Web via une requête HTTP de méthode POST à travers une connexion HTTPS, ces données n'apparaissent pas dans l'URL. Un attaquant qui parviendrait à déchiffrer la requête ne pourrait donc, dans tous les cas, jamais les voir.

c) Les commutateurs (switchs) utilisent un protocole de routage pour échanger entre eux des informations de routage.

d) Lors d'un échange HTTPS avec un serveur Web, un attaquant qui intercepte les requêtes ne peut pas en lire le contenu (chiffré), mais il pourrait, en l'absence de vérification de certificat, se faire passer pour le serveur et transmettre de fausses informations au client sans que celui-ci ne puisse s'en apercevoir.

Exercice 3 — Système d'exploitation, processus

On exécute la suite de commandes suivante dans un terminal :

$ pwd
/home/camille/web/static/
$ ls
style.css logo.png
$ mkdir img
$ mv logo.png img/
$ cp img/logo.png ../logo-saved.png
$ ls

a) Le dernier ls de cette suite de commandes affiche : style.css logo-saved.png.

b) À l'exception du processus init, tout processus est nécessairement lancé par un autre processus (son processus parent).

c) L'UID d'un processus est un identifiant unique attribué par le système d'exploitation à ce processus.

d) Sous un système de la famille UNIX, chaque fichier dispose de quatre types de droits modifiables : le droit de modifier les droits eux-mêmes, le droit de lecture, le droit d'écriture et le droit d'exécution.

Exercice 4 — Graphes

On considère un graphe non orienté connexe $G$ , muni d'une méthode voisins(s) renvoyant la liste des voisins du sommet s. La distance entre deux sommets est la longueur (en nombre d'arêtes) d'un plus court chemin les reliant.

a) La fonction suivante permet de déterminer correctement la distance entre les sommets depart et arrivee d'un graphe non orienté connexe G :

def distance(depart, arrivee, G):
    d = 0
    vus = {}
    pile = [depart]
    while len(pile) > 0:
        s = pile.pop()
        if s == arrivee:
            return d
        vus[s] = True
        d = d + 1
        for v in G.voisins(s):
            if v not in vus:
                pile.append(v)
    return d

On rappelle que le degré d'un sommet, dans un graphe non orienté, est le nombre d'arêtes incidentes à ce sommet.

b) Le degré du sommet d'indice $i$ d'un graphe non orienté est égal à la somme des éléments de la $i$ -ième colonne et de la $i$ -ième ligne de sa matrice d'adjacence.

c) On considère le graphe non orienté à 9 sommets numérotés de 0 à 8, formé de 5 composantes connexes : $\{0,1\}$ (reliés par une arête), $\{2,3,4\}$ (chaîne $2-3-4$ ), $\{5\}$ (isolé), $\{6,7\}$ (reliés par une arête), $\{8\}$ (isolé). La fonction Python suivante compte le nombre de composantes connexes d'un graphe :

def mystere(G):
    vus = {}
 
    def rec(s):
        vus[s] = True
        for v in G.voisins(s):
            if v not in vus:
                rec(v)
 
    total = 0
    for s in G.sommets():
        if s not in vus:
            rec(s)
            total = total + 1
    return total

Appliquée au graphe ci-dessus, cette fonction renvoie 5.

d) Un graphe non orienté a pour matrice d'adjacence (sommets numérotés de 0 à 4) :

\begin{pmatrix}0&1&0&1&0\\1&0&0&0&0\\0&0&0&1&0\\1&0&1&0&1\\0&0&0&1&0\end{pmatrix}

Ce graphe est acyclique.

Exercice 5 — Bases de données

On considère une base de données Voyage dont le schéma relationnel est le suivant (clés primaires soulignées, clés étrangères précédées de #) :

Voyageur(idVoyageur, nom, prenom)
Sejour(idSejour, #idVoyageur, #codeResidence, debut, duree)
Residence(code, nbrPlace, adresse)
Activite(#codeResidence, codeActivite, description)

a) D'après ce schéma, il est possible qu'une résidence ne propose aucune activité.

b) Ce schéma n'est pas correct, car codeResidence est à la fois une clé primaire (partielle) et une clé étrangère pour la table Activite.

c) Ce schéma permet de déterminer si une personne, dont on connaît le nom et le prénom, a pu se voir proposer une activité de code ski.

d) La requête SQL suivante donne la durée des séjours effectués dans une résidence proposant 4 places ou plus, proposant l'activité Surf mais ne proposant pas l'activité Voile :

SELECT duree
FROM Sejour AS S
JOIN Residence AS R ON S.codeResidence = R.code
JOIN Activite AS A ON A.codeResidence = R.code
WHERE R.nbrPlace >= 4
  AND A.codeActivite = 'Surf' AND A.codeActivite <> 'Voile'

Exercice 6 — Analyse de programme, débogage

a) Une fonctionnalité classique d'un débogueur est de déterminer, pour un programme quelconque fourni en entrée, si ce programme boucle indéfiniment pour certaines entrées.

b) Une bonne couverture de tests unitaires permet de démontrer qu'une fonction renvoie toujours, pour toute donnée respectant ses préconditions, la valeur attendue par sa spécification.

c) La fonction appartient_cercle suivante permet de déterminer correctement si un point $M$ appartient au cercle de centre $C$ et de rayon $r$ :

import math
 
def distance(A, B):
    xA, yA = A
    xB, yB = B
    return math.sqrt((xA - xB) ** 2 + (yA - yB) ** 2)
 
def appartient_cercle(C, r, M):
    return distance(C, M) == r

d) La fonction suivante s'arrête toujours, quel que soit le tableau trié t et l'entier x fournis en entrée, car b - a en constitue un variant de boucle :

def recherche_dichotomique(t, x):
    assert sorted(t) == t
    a = 0
    b = len(t) - 1
    while a <= b:
        m = (a + b) // 2
        if t[m] == x:
            return m
        if t[m] < x:
            a = m
        else:
            b = m
    return -1

Exercice 7 — Méthodes algorithmiques

Le problème du sous-tableau de somme maximale consiste, pour un tableau t de taille $n$ , à trouver la valeur maximale de la somme $t[i]+t[i+1]+\ldots+t[j-1]$ pour $0\leqslant i<j\leqslant n$ . Par exemple, pour t = [-2, 1, -3, 4, -1, 2, 1, -5, 4], le sous-tableau [4, -1, 2, 1] a la plus grande somme : 6.

On admet l'existence d'une fonction somme_max_inclu(t, g, d, k) qui renvoie la somme maximale parmi les sous-tableaux contigus de t entre les indices g et d et contenant l'indice k. Par exemple, somme_max_inclu([-2, 1, -3, 4, -1, 2, 1, -5, 4], 0, 8, 7) renvoie 5, car le sous-tableau de somme maximale contenant l'indice 7 est [4, -1, 2, 1, -5, 4].

a) La fonction somme_coupe_max suivante renvoie la somme maximale parmi les sous-tableaux contigus de t entre les indices g et d, en s'appuyant sur somme_max_inclu :

def somme_coupe_max(t, g, d):
    if g == d:
        return t[g]
    m = (g + d) // 2
    return max(
        somme_coupe_max(t, g, m - 1),
        somme_coupe_max(t, m + 1, d),
        somme_max_inclu(t, g, d, m),
    )

Pour $1\leqslant i<n$ , on pose $x_0=t[0]$ , $y_0=t[0]$ , $x_i=\max(t[i], x_{i-1}+t[i])$ , et $y_i=\max(y_{i-1}, x_i)$ .

b) La valeur $x_{n-1}$ correspond à la somme maximale parmi les sous-tableaux contigus de t.

c) Il existe un algorithme basé sur cette relation de récurrence, résolvant le problème avec une complexité en temps linéaire ( $O(n)$ ) en la taille du tableau.

d) La fonction suivante résout correctement le problème :

def somme_coupe_maxi(t):
    assert t
    meilleur = t[0]
    max_local = 0
    for i in range(len(t)):
        max_local = max_local + t[i]
        if meilleur < max_local:
            meilleur = max_local
        if max_local < 0:
            max_local = 0
    return meilleur