Bac NSI 2026 Antilles-Guyane jour 1

Un SGBD peut faire respecter l’intégrité des données (unicité d’un code de commande, existence du client et de la pizza) et gérer des accès simultanés avec des transactions, pour éviter des modifications incohérentes. Il permet aussi des droits d’accès et des requêtes reliant les tables sans recopier partout les coordonnées. Deux avantages expliqués suffisent ; le SGBD ne supprime pas le besoin d’un schéma bien conçu.

Non dans cette relation. num est la clé primaire de pizza : deux lignes ne peuvent partager ce numéro, quels que soient leurs prix ou couleurs. Une même couleur et un même prix peuvent au contraire apparaître sur des numéros distincts. La contrainte porte sur la clé, pas sur la totalité des autres attributs.

commande.id_client référence client.id. Autre réponse valable : commande.num_pizza référence pizza.num. Une commande doit désigner un client et une pizza existants ; la valeur étrangère peut apparaître dans plusieurs commandes, contrairement à la clé primaire de la table cible.

Les pizzas 2 et 4 vérifient la condition. Le résultat contient leurs prix, pas leurs numéros. Aucun ordre n’est garanti en l’absence d’ORDER BY ; ces deux lignes forment le résultat attendu.

SELECT couleur
FROM pizza
WHERE prix > 15;

Le filtre strict exclut une éventuelle pizza à exactement 15 €. Dans l’extrait, seule la pizza 4 convient, donc le résultat est Bianca. DISTINCT serait possible pour une liste de couleurs sans répétition, mais le sujet ne l’impose pas ici.

SELECT DISTINCT c.prenom
FROM client AS c
JOIN commande AS co ON co.id_client = c.id
WHERE co.livraison = 1 AND co.paiement = 0;

Les deux conditions portent sur la même commande : une pizza effectivement livrée et non réglée. La jointure retrouve ensuite le prénom du client. DISTINCT évite de répéter le même prénom dans la projection si plusieurs commandes répondent au filtre. L’extrait renvoie Raffaele. On ne doit pas utiliser OR : cela retiendrait aussi des commandes payées ou encore non livrées.

SELECT AVG(p.prix)
FROM client AS c
JOIN commande AS co ON co.id_client = c.id
JOIN pizza AS p ON p.num = co.num_pizza
WHERE c.nom = 'Esposito';

Chaque commande fournit un prix à la moyenne. Dans l’extrait : (11,5 + 12,5 + 11,5) / 3 = 35,5 / 3, soit environ 11,83 €. Ne pas écrire AVG(DISTINCT prix) : les commandes répétées doivent compter. La question filtre un nom, pas un identifiant unique ; si plusieurs clients s’appellent Esposito, leurs commandes sont toutes concernées. Le schéma ne stocke pas le prix au moment de la commande : on calcule avec les prix actuels de pizza, ce qui est la seule information disponible.

UPDATE commande
SET livraison = 1
WHERE code = 42365;

On conserve la date, le client et l’état du paiement déjà égal à 1. WHERE cible la commande, pas toutes les commandes du même client.

INSERT INTO client (id, nom, prenom)
VALUES (107, 'Girasole', 'Emanuele');

INSERT INTO commande
(code, id_client, num_pizza, date, livraison, paiement)
VALUES (42366, 107, 2, '2025-01-03', 0, 0);

Le client est créé avant sa commande pour que la clé étrangère 107 ait une cible. La demande n’est pas une livraison déjà réalisée : livraison vaut 0. Aucun règlement n’étant indiqué, on l’enregistre ici en attente avec paiement = 0 ; si le paiement était effectué lors de la réservation, seule cette valeur deviendrait 1. Ces hypothèses doivent être explicites, pas confondues avec les événements futurs.

Les commandes 42364 et 42365 référencent la pizza 1. Avec les clés étrangères activées et sans suppression en cascade, le SGBD refuse sa suppression ; sinon, l’historique contiendrait des références orphelines et perdrait le prix/couleur de la pizza. Une pizza retirée de la vente peut rester dans le catalogue historique avec un indicateur disponible = 0, plutôt que disparaître. Supprimer toutes ses anciennes commandes n’est pas une bonne façon de préserver l’historique.

La relation composition résout l’association plusieurs-à-plusieurs. Sa clé composée empêche d’associer deux fois le même ingrédient à la même pizza, tout en autorisant cet ingrédient sur d’autres pizzas. Un attribut quantite pourrait être ajouté si nécessaire, mais il n’est pas demandé. Stocker tous les ingrédients dans une chaîne séparée par des virgules rendrait les recherches et les contraintes beaucoup moins fiables.

Le principal enjeu est que chaque client ne voie que ses propres commandes. Il faut authentifier le compte, puis vérifier ses autorisations sur le serveur pour chaque requête ; cacher un bouton ou recevoir un id_client dans l’URL ne suffit pas. L’application doit communiquer en HTTPS, utiliser des requêtes paramétrées contre les injections SQL et un compte de base aux droits limités. La base n’a pas besoin d’être directement exposée à Internet : un serveur applicatif contrôle les requêtes. Des sauvegardes, mises à jour et journaux d’accès contribuent à protéger la disponibilité et à détecter les incidents.

À chaque étape, on conserve les sous-listes sans le nouvel élément, puis on ajoute celles qui le contiennent en tête. Comme les éléments sont retirés depuis la fin de liste, le placement en tête préserve l’ordre original. Le nombre de sous-listes double : 1, 2, 4, 8. Il ne s’agit pas de permuter les valeurs.

tmp.append([element] + sous_liste)
return sous_listes(liste, accumulateur + tmp)

[element] transforme l’entier en liste d’un élément avant la concaténation. La concaténation crée de nouvelles listes ; on n’insère pas l’élément dans les sous-listes existantes, qui doivent rester dans l’accumulateur sans cet élément. liste.pop(), en revanche, modifie bien la liste d’entrée. Après l’appel complet, elle est vide. Pour préserver une liste utilisée ensuite, appeler sous_listes(liste.copy()). Cette copie n’est pas indispensable au résultat de l’algorithme fourni, mais évite un effet de bord surprenant.

Pour une première liste de longueur m, chaque élément peut être conservé ou exclu, donc la fonction génère 2ᵐ choix de sous-séquences. Si des valeurs se répètent, certaines listes obtenues sont identiques, mais le programme les génère et les teste tout de même. Pour chaque candidat, est_extraite parcourt la seconde liste avec des indices croissants, en O(n) dans le pire cas. On obtient donc un coût de vérification pouvant atteindre O(n·2ᵐ), auquel s’ajoutent les constructions et copies de listes, de l’ordre de O(m·2ᵐ).

Passer de m à m + 1 double le nombre de candidats ; à m = 30, il dépasse le milliard. Le problème est aussi spatial : tmp conserve toutes les sous-listes simultanément. Le test est_extraite fonctionne pourtant efficacement pour un seul candidat : son indice dans la sous-liste avance seulement lorsqu’une valeur correspond, tandis que l’indice dans la liste cible avance toujours. C’est l’énumération exhaustive qui domine.

[9]

Les paramètres 1 désignent les nombres d’éléments des deux préfixes : chacun vaut [9]. Ils ne désignent pas ici l’indice du dernier élément. La plus longue sous-séquence commune est donc [9], pas [9, 3].

lcs(L_1, m - 1, L_2, n - 1) + [L_1[m - 1]]

Le dernier élément commun peut prolonger une LCS des préfixes privés de leurs derniers éléments. Il doit être ajouté à la fin pour préserver l’ordre. Pour [9,3,7,5,8] et [9,7,8], une LCS des préfixes est [9,7] ; on ajoute 8 et obtient [9,7,8].

L’idée de la récurrence est structurelle : si les derniers éléments diffèrent, une solution commune ne peut pas les utiliser tous les deux comme dernier élément. Il faut alors comparer les solutions obtenues en retirant la fin de l’une ou de l’autre liste, puis garder une plus longue. En cas d’égalité de longueur, plusieurs LCS peuvent être correctes.

La fonction aux s’appelle elle-même dans son propre corps, avec un ou deux indices diminués. Les appels de la branche d’égalité diminuent les deux indices ; ceux de la branche d’inégalité en diminuent un. Quand un indice devient négatif, le préfixe correspondant est vide et le cas de base renvoie []. Le nom top_down ne prouve pas à lui seul la récursivité : ce sont les auto-appels qui la caractérisent.

Les appels non terminés s’empilent. Une branche peut avoir une profondeur proportionnelle à m + n ; pour de grandes listes, elle peut dépasser la limite de récursion et provoquer RecursionError. Les cadres d’appels consomment aussi de la mémoire.

Un second problème s’ajoute : le programme fourni n’a aucune mémoïsation. Plusieurs branches recalculent les mêmes couples d’indices, ce qui peut rendre le temps exponentiel. Le qualifier « top_down » n’en fait donc pas automatiquement un algorithme dynamique efficace. Les copies de listes lors des concaténations ajoutent encore du travail. Il faut distinguer la profondeur de pile et le nombre total de sous-appels : diminuer l’un ne résout pas nécessairement l’autre.

Employer une programmation dynamique itérative : une table D[i][j] contient la longueur d’une LCS des i premiers éléments de L₁ et des j premiers éléments de L₂. Les bords D[0][j] et D[i][0] valent 0. Si les dernières valeurs correspondent, D[i][j] = 1 + D[i-1][j-1] ; sinon D[i][j] = max(D[i-1][j], D[i][j-1]). On remplit la table ligne par ligne sans appels récursifs.

Pour restituer une sous-séquence, on remonte depuis D[m][n] : une égalité des valeurs ajoute cet élément et fait reculer en diagonale ; sinon on va vers une case voisine de même meilleure longueur. Les éléments sont collectés à rebours puis inversés. On remplit (m+1)(n+1) cases, en O(mn) temps et mémoire pour cette version. Une mémoïsation récursive éviterait les recalculs mais conserverait la profondeur de pile ; elle ne répond pas à elle seule au risque de RecursionError. Augmenter la limite de récursion ne change pas la nature du problème.

R1 → R2 → R3 → R8. Ce chemin traverse quatre routeurs et trois liaisons entre eux. Toute route contournant R3 demanderait davantage de routeurs. Les coûts numériques des arêtes ne sont pas la métrique de RIP.

R1 → R2 → R3 → R7 → R6 → R4 → R5. La liaison R2-R4 de coût 10 est évitée ; R3-R6 de coût 1 est aussi moins intéressante que R3-R7-R6 de coût 0,2. Le choix optimal ne minimise donc pas le nombre d’arêtes.

1 + 1 + 0,1 + 0,1 + 0,01 + 1 = 3,21. On additionne une fois chaque liaison empruntée. Les connexions terminales Bob-R1 et R5-Alice n’ont pas de coût indiqué dans la figure : le total demandé est celui des liaisons pondérées.

Les routeurs détectent l’indisponibilité des liens vers R3 et mettent à jour leurs informations de routage. Après convergence, les communications peuvent continuer, car le réseau restant relie encore les destinations. Pour Alice, Bob peut suivre R1-R2-R4-R5 ; pour le DNS, R1-R2-R4-R6-R7-R8. Les nouvelles routes peuvent être plus coûteuses et une interruption temporaire peut se produire pendant la convergence.

HTTPS, c’est-à-dire HTTP transporté dans une connexion TLS. Le chiffrement protège les données en transit ; TLS ajoute aussi des mécanismes d’intégrité et d’authentification du serveur. L’adresse initiale http://alice.fr ne fournit pas à elle seule cette protection.

Elle permet de chiffrer et déchiffrer les messages échangés. L’émetteur utilise le secret pour produire le chiffré ; le destinataire possède le même secret pour retrouver le clair. La clé doit rester inconnue des tiers. Elle ne prouve pas à elle seule lequel des deux détenteurs a produit un message, puisque tous deux la connaissent.

Alice transmet sa clé publique à Bob et garde sa clé privée secrète. Bob chiffre la clé symétrique avec la clé publique d’Alice, puis lui envoie le résultat. Alice le déchiffre avec sa clé privée. La clé publique peut circuler ; elle ne permet pas à un observateur de déchiffrer ce message. La question raisonne dans le modèle d’échange de clés décrit, sans traiter ici la vérification de l’identité du propriétaire de la clé publique.

Le paquet complet est chiffré avec la clé publique d’Alice : sa clé privée permet de l’ouvrir. Alice récupère la clé symétrique et la signature, vérifie cette signature avec la clé publique de Bob, puis compare le condensé vérifié à un nouveau condensé calculé sur la clé reçue. Une modification de la clé provoque un désaccord ; une signature valide établit qu’elle a été produite avec la clé privée correspondant à celle de Bob.

Cette conclusion exige que la clé publique attribuée à Bob soit authentiquement la sienne. Un attaquant qui substituerait sa propre clé pourrait signer lui-même un message : l’envoi d’une clé publique sur un réseau hostile ne prouve pas son identité. La formulation du sujet « chiffrer avec la clé privée » est une image pédagogique de la signature ; les algorithmes de signature réels ne se résument pas tous à inverser un algorithme de chiffrement.

def somme(tab):
    total = 0
    for valeur in tab:
        total += valeur
    return total

L’accumulateur vaut la somme des éléments déjà parcourus. Il démarre à 0, élément neutre de l’addition, ce qui rend aussi la réponse correcte pour une liste vide. La liste d’entrée n’est pas modifiée. Le programme utilise une addition par valeur et parcourt la liste une seule fois.

def permuter(tab, i, j):
    temporaire = tab[i]
    tab[i] = tab[j]
    tab[j] = temporaire

La variable temporaire sauvegarde la première valeur avant de l’écraser. Sans elle, deux affectations successives naïves copieraient la même valeur aux deux endroits. L’affectation simultanée tab[i], tab[j] = tab[j], tab[i] convient également en Python. Le tableau est modifié sur place ; aucun return n’est nécessaire. Si i = j, l’échange laisse la liste inchangée.

permuter(tab, i, len(tab) - 1 - i)

Les indices symétriques sont i et n - 1 - i. La boucle ne parcourt que n // 2 positions afin de ne pas échanger une deuxième fois les mêmes paires. Pour n impair, la case centrale ne bouge pas, ce qui est correct. Pour n = 0 ou 1, aucun échange n’est nécessaire.

from random import randint

def generer_sac():
    sac = [randint(1, 5)]
    for i in range(7):
        s = somme(sac)
        nouvel_entier = randint(s + 1, 2 * s)
        sac.append(nouvel_entier)
    inverser(sac)
    return sac

Un premier élément est créé, puis sept autres pour un total de huit. À chaque étape, la somme est recalculée sur le sac déjà constitué. Le nouvel entier est strictement supérieur à la somme de tous les précédents : c’est la propriété supercroissante. Après inversion, chaque élément dépasse la somme de ceux qui le suivent. Cette propriété donnera une décision de déchiffrement sans ambiguïté. Écrire randint(s, 2*s) perdrait l’inégalité stricte, et la taille ne doit pas être neuf.

self.sac = outils.generer_sac()

L’appel fabrique une nouvelle clé pour l’instance. outils.generer_sac sans parenthèses conserverait la fonction elle-même au lieu de la liste. Le préfixe outils est nécessaire puisque l’import est import outils.

for i in range(8):
    produit = octet[i] * self.sac[i]
    tab_produits.append(produit)
s = outils.somme(tab_produits)

Le bit 0 sélectionne un produit nul et le bit 1 sélectionne le poids entier. Les indices des bits et du sac doivent rester alignés. On additionne les produits, pas les bits seuls ni tous les éléments du sac. Sur l’exemple, le bit de poids 205 vaut 0 : ce nombre ne contribue donc pas au total. La précondition impose huit bits ; une validation d’entrée serait une amélioration supplémentaire.

On examine les poids du plus grand au plus petit. Si le reste atteint le poids, le bit doit valoir 1 : les poids plus petits, tous réunis, ne pourraient atteindre ce poids. Sinon ce bit vaut nécessairement 0. Le reste final nul confirme que tous les termes sélectionnés reconstituent 688. Ce raisonnement utilise la supercroissance, pas simplement l’ordre décroissant.

def dechiffrer(self, entier):
    octet = []
    reste = entier
    for poids in self.sac:
        if reste >= poids:
            octet.append(1)
            reste -= poids
        else:
            octet.append(0)
    return octet

L’invariant est : entier initial = somme des poids déjà sélectionnés + reste. La boucle garde huit décisions dans l’ordre du sac. Pour un entier effectivement obtenu par chiffrer avec cette clé, le reste final est zéro et l’octet est unique. Tous les entiers entre 0 et la somme du sac ne sont pas forcément représentables ; pour accepter des données arbitraires, on pourrait vérifier reste == 0 et refuser sinon.

Ce mécanisme est un modèle pédagogique, pas une recommandation de cryptographie actuelle : avec seulement 256 octets possibles et une structure aussi visible, il ne fournit pas la sécurité des protocoles réels. L’intérêt de l’exercice est de comprendre pourquoi l’algorithme glouton est correct pour cette suite de poids particulière.