Bac NSI 2025 Métropole remplacement jour 1

Le routeur R2, interface G0. C’est son interface directement reliée au réseau local, pas une interface vers un autre routeur.

172.16.255.254. La dernière adresse du bloc,172.16.255.255, est réservée à la diffusion. La précédente est donc le dernier hôte utilisable, conformément à la politique donnée.

Un /30 laisse 2 bits hôtes, soit 4 adresses. Les deux adresses utilisables sont.5 et.6 ; la première est déjà prise.

Les lignes manquantes sont 192.168.2.0/24 : G3,1 ;192.168.3.0/24 : G3,2 ;50.50.50.20/30 : G1,1 ;50.50.50.24/30 : G2,1. Pour.20/30, on peut atteindre un routeur attaché au réseau par R5 viaG 1 ou R4 viaG 2. Les métriques étant égales, G1 est retenue.

Un réseau directement raccordé coûte 0 ; atteindre un réseau derrière un autre routeur ajoute un saut. Il n’est pas nécessaire de traverser les deux extrémités d’un réseau de liaison pour l’atteindre.

# Ligne2
((192, 168, 2, 0, 24), 'G3', 1),
# Ligne3
((192, 168, 3, 0, 24), 'G3', 2),
# Ligne11
((50, 50, 50, 20, 30), 'G1', 1),
# Ligne12
((50, 50, 50, 24, 30), 'G2', 1)

Chaque entrée contient un quintuplet réseau, la chaîne d’interface et la métrique entière. Le masque /n est le cinquième élément du quintuplet, pas un sixième champ du triplet.

(255, 255, 255, 252)

Les 24 premiers bits donnent trois octets 255. Les 6 bits réseau restants forment 11111100, soit 252 ; les deux bits hôtes restent nuls.

Adresse : 00110010.00110010.00110010.00000110
Masque  : 11111111.11111111.11111111.11111100
ET      : 00110010.00110010.00110010.00000100

50 vaut 32+16+2, et 6 vaut 4+2. Le résultat est 50.50.50.4/30 : seuls les deux derniers bits sont effacés.

def is_in_network(address, network):
    network_mask = mask_for_size(network[4])
    for i in range(4):
        if et_bit_a_bit(network_mask[i], address[i]) != network[i]:
            return False
    return True

Le masque provient du cinquième élément, d’indice 4. On compare chacun des octets masqués au réseau canonique donné. Une seule différence suffit pour retourner faux ; vrai vient seulement après les quatre comparaisons. Les tuples network du sujet sont déjà de véritables adresses réseau.

def choose_interface(t_routage, destination_ip):
    for network, interface, metrique in t_routage:
        if is_in_network(destination_ip, network):
            return interface
    return None

On décompose chaque triplet et on réutilise le test d’appartenance. La métrique a déjà servi à construire la table ; il n’est pas nécessaire de refaire ici un calcul de chemin. Dans les réseaux non chevauchants du sujet, le premier match est le seul.

Avec une table générale comportant des préfixes imbriqués, le routage réel choisirait le plus long préfixe correspondant. Ce raffinement dépasse les données proposées et ne doit pas être confondu avec le simple parcours demandé.

On convertit d’abord tous les débits dans la même unité. Un débit plus grand donne un coût plus faible ; ces coûts s’additionnent le long d’une route.

Les lignes demandées sont :192.168.2.0/24 →G3,10 ;172.16.0.0/16 →G3,12 ;10.0.0.0/8 →G1,10 ;50.50.50.20/30 →G1,10. Pour rejoindre R6, la route R1-R2-R4-R6 vaut 10+1+1=12, bien moins que R1-R4-R6 à 101.

Le réseau.20/30 est accessible dès R5, atteint par G1à coût 10. Il ne faut pas ajouter le coût pour traverser ensuite ce lien vers R4.

La taille est 3, à partir de (0,1). Les lignes 0 à 2 et colonnes 1 à 3 forment neuf 1. Un carré de côté 4 reprendrait toute la carte et contiendrait des 0 ; aucun autre carré de côté 3 ne convient.

taille², soit taille * taille. Le carré possède exactement ce nombre de cellules et chacune vaut 1. Comme la carte ne contient que 0 et 1, atteindre cette somme est aussi suffisant pour prouver que toutes les cellules valent 1.

def est_constructible(carte, i_coin, j_coin, taille):
    s = 0
    for i in range(i_coin, i_coin + taille):
        for j in range(j_coin, j_coin + taille):
            s = s + carte[i][j]
    return s == taille * taille

La boucle extérieure parcourt les lignes du carré, l’intérieure ses colonnes. Les bornes droites sont exclues et donnent exactement taille positions chacune. La comparaison finale avec l’aire transforme la somme en booléen.

La fonction n’a pas à vérifier les limites de carte : cette condition est une précondition fournie. Elle examine toujours taille² cellules dans cette version, même si un 0 apparaît tôt.

def plus_grande_base_exhaustive(carte):
    n = len(carte)
    for taille in range(n, 0, -1):
        i = 0
        while i + taille <= n:
            j = 0
            while j + taille <= n:
                if est_constructible(carte, i, j, taille):
                    return (taille, i, j)
                j = j + 1
            i = i + 1

Pour chaque taille, on réinitialise i et, pour chaque ligne, j. Les tests i + taille <= n et j + taille <= n garantissent que le carré entier reste inclus. Tester les tailles décroissantes justifie le retour immédiat : aucun carré plus grand n’a convenu.

Le sujet garantit au moins un 1, donc on trouvera au plus tard un carré de taille 1. Sans cette hypothèse, on devrait définir un résultat pour une carte entièrement non constructible.

Il y a (n - t + 1)² positions pour un carré de taille t. Le nombre total de carrés atteint 1² + 2² + ... + n² = n(n+1)(2n+1)/6, donc croît comme n³. À 300 cases de côté, cela représente déjà 9 045 050 carrés possibles.

Et chaque test de côté t additionne t² cellules : le coût de cette version exhaustive peut croître comme n⁵. La figure compte les carrés, pas toutes les lectures de cellules. Augmenter simplement la vitesse de la machine ne supprime pas ces répétitions.

aux_B

Le 3 en(0,1) reprend la base maximale. Le 2 en(2,2) représente le carré du coin inférieur droit. Une cellule à 0 dans la carte donne 0 dans aux ; une case du bord ne peut commencer qu’un carré de taille 0 ou 1.

a=0, b=1, c=3, d=2. La case source de a vaut 0. Pour b, la case source vaut 1 mais sa voisine de droite a une valeur auxiliaire 0, donc aucun carré de côté 2 ne peut partir de b. Pour c, les trois voisines utiles valent 2 : 1 + min(2,2,2)=3. Pour d, elles valent 1,2,1 : 1 + min(1,2,1)=2.

def calcule_aux(carte):
    n = len(carte)
    aux = [[0 for j in range(n)] for i in range(n)]
    for k in range(n):
        aux[n - 1][k] = carte[n - 1][k]
        aux[k][n - 1] = carte[k][n - 1]
    for i in range(n - 2, -1, -1):
        for j in range(n - 2, -1, -1):
            if carte[i][j] == 1:
                aux[i][j] = 1 + min(aux[i + 1][j], aux[i][j + 1], aux[i + 1][j + 1])
    return aux

La dernière ligne et la dernière colonne sont des cas de base copiés de carte. On remplit ensuite depuis le bas et la droite, car les trois valeurs utilisées doivent déjà être disponibles.

Le minimum est le facteur limitant : pour agrandir un carré d’un cran, il faut que les zones à droite, dessous et en diagonale disposent toutes de cette taille. Si la cellule source vaut 0, aux reste à sa valeur initiale 0. La compréhension imbriquée crée des lignes indépendantes ; [[0]*n]*n partagerait une seule ligne et corromprait le calcul.

def plus_grande_base(carte):
    n = len(carte)
    aux = calcule_aux(carte)
    taille_max = aux[0][0]
    i_max = 0
    j_max = 0
    for i in range(n):
        for j in range(n):
            if aux[i][j] > taille_max:
                taille_max = aux[i][j]
                i_max = i
                j_max = j
    return (taille_max, i_max, j_max)

On mémorise ensemble la valeur et sa position. Mettre à jour seulement la taille perdrait les coordonnées. Avec un test strict >, le premier maximum dans l’ordre de parcours est conservé ; le sujet accepte n’importe quelle base de taille maximale.

3,6 secondes. Construire aux puis chercher son maximum demande un travail proportionnel au nombre de cellules, soit n². Tripler le côté multiplie le nombre de cellules par 9 : 0,4 × 9 = 3,6.

C’est une estimation à machine et conditions comparables. Elle s’appuie sur la complexité quadratique, pas sur une mesure réellement effectuée pour la carte 3000.

Une clé primaire est un attribut ou ensemble d’attributs choisi pour identifier chaque enregistrement de façon unique. Ses valeurs sont uniques et non nulles. Elle permet de référencer sans ambiguïté une ligne depuis d’autres tables.

Plusieurs papillons partagent un habitat : Prairies apparaît pour Monarque, Citron de Provence et Petite Tortue. La valeur ne distingue donc pas chaque ligne de la table. Les doublons visibles suffisent à réfuter l’unicité.

La clause WHERE sélectionne le Machaon, puis SELECT ne conserve que sa taille moyenne donnée dans l’extrait.

UPDATE papillon SET taille = 50 WHERE nomCo = 'Petite Tortue';

La modification porte sur taille dans la ligne de l’espèce concernée. Sans WHERE, toutes les tailles seraient remplacées. L’extrait Python de la partieBintègre déjà cette nouvelle valeur 50.

SELECT nomCo FROM papillon
WHERE habitat = 'Prairies' AND taille < 55;

La taille 55 est exclue. Dans l’extrait, Citron de Provence et Petite Tortue conviennent, que l’on considère la taille initiale 30 de cette dernière ou sa valeur mise à jour 50.

Asie a l’identifiant 4. La plante de cette zone est Coquelicot, dont le nom scientifique est Papaver rhoeas. Le résultat demande nomSc, pas nomCo.

SELECT papillon.nomCo, plante.nomCo
FROM papillon JOIN plante ON papillon.habitat = plante.habitat
WHERE papillon.taille < 55;

On joint ici sur l’habitat demandé, et non sur la zone. Plusieurs plantes peuvent partager cet habitat : une même espèce de papillon peut donc apparaître dans plusieurs couples. Ce produit de correspondances est voulu par la question.

Europe correspond à la zone 6. Paon-du-jour et Lilas sont les seules lignes des extraits qui y appartiennent. Leur habitat diffère, mais la requête filtre la zone et ne demande pas un habitat commun.

SELECT papillon.nomCo
FROM papillon JOIN plante ON papillon.zone = plante.zone
WHERE plante.nomCo = 'Coquelicot';

La table intermédiaire des zones n’est pas nécessaire : les deux clés étrangères peuvent être comparées directement. Le nom de plante sert à sélectionner sa zone sans supposer que son identifiant restera 4. Dans l’extrait, Robert-le-Diable est renvoyé.

def tri_collec(collec):
    for i in range(1, len(collec)):
        pap = collec[i]
        j = i
        while j > 0 and collec[j - 1]['taille'] > pap['taille']:
            collec[j] = collec[j - 1]
            j = j - 1
        collec[j] = pap
    return collec

On sauvegarde le papillon courant dans pap. Les éléments précédents plus grands sont décalés d’une case vers la droite jusqu’à libérer la position j. On y insère alors pap. Il faut comparer les champs taille des dictionnaires, pas les dictionnaires eux-mêmes.

Avec les six valeurs de la partieB, l’ordre devient Paon-du-jour 6, Robert-le-Diable 25, Citron de Provence 30, Petite Tortue 50, Machaon 85, Monarque 100. Le test strict conserve l’ordre initial entre tailles égales : le tri est stable.

Le tri par insertion. Il maintient un préfixe déjà trié et y insère un nouvel élément à chaque itération.

Quadratique, O(n²). Dans une liste initialement décroissante, le nouvel élément doit passer devant tous ceux déjà traités. Le nombre de décalages vaut 1 + 2 + ... + (n - 1) = n(n - 1)/2. Deux boucles ne suffisent pas à elles seules à justifier un carré ; le décompte des déplacements donne ici la raison.

On représente les observations connues et la nouvelle par des caractéristiques comparables, puis on calcule leur distance. On sélectionne les k observations connues les plus proches et on attribue à la nouvelle la classe majoritaire parmi elles, avec une règle de départage définie en cas d’égalité.

Le choix de k, des caractéristiques et de l’échelle des distances influence la décision. Un tri selon la taille seule ne suffit pas à valider une classification utilisant aussi les motifs ou couleurs.

def recherche_seq(seq, chaine):
    for i in range(len(chaine) - len(seq) + 1):
        j = 0
        while j < len(seq) and chaine[i + j] == seq[j]:
            j += 1
        if j == len(seq):
            return i
    return -1

Pour chaque alignement i, j compte les caractères consécutifs qui correspondent. La comparaison porte sur chaine[i+j] et seq[j]. Lorsque j atteint la longueur du motif, tous les caractères sont identiques et i est la première position de l’occurrence.

Le+1 dans la borne du range permet de tester le dernier alignement possible. Si le motif est plus long que la chaîne, aucun alignement n’est testé et-1 est renvoyé. Pour un motif vide, le programme renvoie 0, convention cohérente avec la recherche Python.

def dico_lettres(seq):
    d = {}
    for i in range(len(seq) - 1):
        d[seq[i]] = i
    return d

def recherche_BMH(seq, chaine):
    decalage = dico_lettres(seq)
    i = 0
    n = len(seq)
    while i <= len(chaine) - n:
        j = n - 1
        while j >= 0 and chaine[i + j] == seq[j]:
            j -= 1
        if j == -1:
            return i
        else:
            if chaine[i + n - 1] in decalage:
                i += n - decalage[chaine[i + n - 1]] - 1
            else:
                i += n
    return -1

Le motif est comparé de droite à gauche. En cas d’échec, on regarde le caractère de la chaîne aligné avec la dernière position du motif. Le dictionnaire mémorise la position la plus à droite de ce caractère dans le motif, en excluant sa dernière position. On décale pour aligner ces occurrences, ou de toute la longueur du motif si le caractère est absent.

Cette exclusion garantit un décalage positif. Les sauts peuvent ignorer plusieurs alignements impossibles et économiser des comparaisons par rapport au déplacement naïf de 1. Cela ne garantit pas un meilleur coût sur toute chaîne : le pire cas peut rester proportionnel au produit des longueurs du texte et du motif. Horspool emploie le caractère de fin de fenêtre, pas nécessairement celui où la comparaison a échoué.