2022 Mayotte Jour 1

(4 points) Cet exercice porte sur les structures de données (listes, piles et files). On cherche ici à mettre en place des algorithmes qui permettent de modifier l’ordre des informations contenues dans une file. On considère pour cela les structures de données abstraites de Pile et File définies par leurs fonctions primitives suivantes : Pile :  creer_pile_vide() renvoie une pile vide ;  est_pile_vide(p) renvoie True si la pile p est vide, False sinon ;  empiler(p, element) ajoute element au sommet de la pile p ;  depiler(p) renvoie l’élément se situant au sommet de la pile p en le retirant de la pile p ;  sommet(p) renvoie l’élément se situant au sommet de la pile p sans le retirer de la pile p. File :  creer_file_vide() renvoie une file vide ;  est_file_vide(f) renvoie True si la file f est vide, False sinon ;  enfiler(f, element) ajoute element dans la file f ;  defiler(f) renvoie l’élément à la tête de la file f en le retirant de la file f. On considère de plus que l'on dispose d'une fonction permettant de connaître le nombre d'éléments d'une file :  taille_file(f) renvoie le nombre d'éléments de la file f. On représentera les files par des éléments en ligne, l'élément de droite étant la tête de la file et l'élément de gauche étant la queue de la file. On représentera les piles en colonnes, le sommet de la pile étant le haut de la colonne. La file suivante est appelée f : 4 3 8 2 1 La pile suivante est appelée p : 5 8 6 2

(4 points) Cet exercice porte sur les structures de données (programmation objet) Dans un jeu de plateforme, des bulles de couleurs et de diamètres différents se déplacent de manière aléatoire. A chaque fois qu'une bulle touche une bulle plus grande, la petite cède son contenu à la plus grande, et donc celle-ci augmente de surface. Par exemple, si une bulle de 1 cm² rencontre une bulle de 4 cm², la petite bulle disparait et la plus grande a désormais une surface de 5 cm². A chaque collision, la vitesse de la grande bulle est réduite de moitié. Le développeur a choisi de coder en Python, chaque bulle est un objet disposant entre autre des attributs suivants : - xc, yc sont deux entiers, les coordonnées du pixel placé au centre de la bulle, - rayon est un entier, le rayon de la bulle en pixels, - couleur est un entier, la couleur de la bulle, - dirx, diry sont deux décimaux (float) qui déterminent les déplacements à l'horizontale et à la verticale à chaque fois que la bulle se déplace. Ces deux valeurs déterminent donc la direction et la vitesse de la bulle. Par exemple si dirx vaut 0.5 et diry vaut 0.0, la bulle se déplace vers la droite uniquement alors que si dirx vaut -1.0 et diry vaut 0.0, la bulle se déplace vers la gauche et deux fois plus vite que précédemment. On suppose que toutes les fonctions de la bibliothèque math ont déjà été importées par l’instruction from math import *. La fonction randint de la bibliothèque random prend en paramètre deux entiers et renvoie un entier alétoire dans la plage définie par les deux paramètres. Exemple : randint (-1, 5) peut renvoyer une des valeurs suivantes : -1, 0, 1, 2, 3, 4, 5. 22-NSIJ1LR1 Page 5 sur 16

(4 points) Cet exercice porte sur les bases de données (bases de données relationnelles, langage SQL). Un rappel sur la syntaxe de quelques fonctions SQL est donné en annexe 1 en fin de sujet. Un enseignant a mis en place un site web qui permet à ses élèves de faire des QCM (questionnaire à choix multiples) de NSI en ligne. L’enseignant a créé une base de données nommée QCM_NSI pour gérer ses QCM, contenant les quatre relations (appelé aussi communément "table") du schéma relationnel ci-dessous : Dans le schéma relationnel précédent, un attribut souligné indique qu’il s’agit d’une clé primaire. Un attribut précédé du symbole # indique qu’il s’agit d’une clé étrangère et la flèche associée indique l’attribut référencé. Ainsi, par exemple, l'attribut ideleve de la relation lien_eleve_qcm est une clé étrangère qui fait référence à l'attribut ideleve de la relation eleves. Dans le cas de la relation lien_eleve_qcm la clé primaire est composée de l’association des deux attributs ideleve et idqcm, eux-mêmes étant des clés étrangères. On donne ci-dessous le contenu exhaustif des relations : 22-NSIJ1LR1 Page 8 sur 16 Table eleves ideleve nom prenom 2 Dubois Thomas 3 Dupont Cassandra 4 Marty Mael 5 Bikila Abebe Table qcm idqcm titre Datecreation 1 Base de données 2021-09-20 2 POO 2022-04-08 3 Arbre Binaire 2022-01-09 4 Arbre Parcours 2022-02-15 5 Piles-Files 2021-12-05 Table lien_eleve_qcm ideleve idqcm note 2 1 12 2 3 18 2 4 13 2 5 15 3 1 20 3 2 9 3 3 18 3 5 13 4 4 15 4 5 20 5 4 15

(4 points) Cet exercice porte sur l’algorithmique (arbres binaires en profondeurs préfixe et infixe). On s’intéresse dans cet exercice à l’étude d’un arbre généalogique. Voici un extrait de l’arbre généalogique fictif d’une personne nommée Albert Normand. L’arbre généalogique est présenté avec les parents vers le bas et les enfants vers le haut. Albert Normand est considéré comme la génération 0. On considère ses parents comme la génération 1, ses grands-parents comme la génération 2 et ainsi de suite pour les générations précédentes. MODELISATION DE L’ARBRE L’arbre généalogique d’un individu est modélisé par un arbre :  chaque nœud de l’arbre représente un individu ;  le premier nœud du sous-arbre gauche d’un individu est associé à son père ;  le premier nœud du sous-arbre droit est associé à sa mère. IMPLEMENTATION DE L’ARBRE Pour implémenter l’arbre, on utilise des notions de programmation orientée objet. Chaque nœud de l’arbre est représenté par un objet qui est l’instance d’une classe Noeud ayant trois attributs. Ainsi l’objet N de type Noeud aura les attributs suivants :  N.identite de type tuple : (prenom,nom) de l’individu référencé par l’objet N ;  N.gauche de type arbre binaire : le sous-arbre gauche de l’objet N ;  N.droit de type arbre binaire : le sous-arbre droit de l’objet N. 22-NSIJ1LR1 Page 11 sur 16 Pour un individu, référencé par l’objet N de type Noeud, dont on ne connait pas les parents, on considèrera que N.gauche et N.droit ont la valeur None.

(4 points) Cet exercice porte sur : transmission de données dans un réseau, architecture d’un réseau, protocoles de routage, langages et programmation. Pour une "LAN PARTY", les organisateurs gèrent deux réseaux différents non liés physiquement suivant le schéma suivant : Réseau 1 : réseau contenant le commutateur 1 (switch1) ; Réseau 2 : réseau contenant le commutateur 2 (switch2). Dans cet exercice, on exploitera la notation CIDR pour l'adressage des deux réseaux. En notation CIDR, l'adresse IP d'une machine est composée d’une adresse IPv4 et d’une indication sur le masque de sous réseau. Par exemple : 172.16.1.10 / 16 signifie :  Adresse IP décimale : 172.16.1.10  Masque de sous-réseau en notation CIDR : 16 La notation CIDR /16 signifie que le masque de sous-réseau a les 16 bits de poids fort de son adresse IP à la valeur 1. C’est-à-dire, pour notre exemple: 11111111.11111111.00000000.00000000. Le PC3 du réseau 1 a pour adresse IPv4 172.150.4.30/24