2022 Polynesie Jour 1

(4 points) Cet exercice traite du thème «programmation», et principalement de la récursivité. On rappelle qu'une chaîne de caractères peut être représentée en Python par un texte entre guillemets "" et que : • la fonction len renvoie la longueur de la chaîne de caractères passée en paramètre ; • si une variable ch désigne une chaîne de caractères, alors ch[0] renvoie son premier caractère, ch[1] le deuxième, etc. ; • l'opérateur + permet de concaténer deux chaînes de caractères. Exemples : >>> texte = "bricot" >>> len(texte) 6 >>> texte[0] "b" >>> texte[1] "r" >>> "a" + texte "abricot" On s'intéresse dans cet exercice à la construction de chaînes de caractères suivant certaines règles de construction. Règle A : une chaîne est construite suivant la règle A dans les deux cas suivants: • soit elle est égale à "a" ; • soit elle est de la forme "a"+chaine+"a", où chaine est une chaîne de caractères construite suivant la règle A. Règle B : une chaîne est construite suivant la règle B dans les deux cas suivants : • soit elle est de la forme "b"+chaine+"b", où chaine est une chaîne de caractères construite suivant la règle A ; • soit elle est de la forme "b"+chaine+"b", où chaine est une chaîne de caractères construite suivant la règle B. On a reproduit ci-dessous l'aide de la fonction choice du module random. >>>from random import choice >>>help(choice) Help on method choice in module random: choice(seq) method of random.Random instance Choose a random element from a non-empty sequence. La fonction A() ci-dessous renvoie une chaîne de caractères construite suivant la règle A, en choisissant aléatoirement entre les deux cas de figure de cette règle. 22-NSIJ1PO1 2/16 def A(): if choice([True, False]): return "a" else: return "a" + A() + "a"

(4 points) Cet exercice traite du thème « architecture matérielle », et principalement d'ordonnancement et d'expressions booléennes. Un système est composé de 4 périphériques, numérotés de 0 à 3, et d'une mémoire, reliés entre eux par un bus auquel est également connecté un dispositif ordonnanceur. À l'aide d'un signal spécifique envoyé sur le bus, l'ordonnanceur sollicite à tour de rôle les périphériques pour qu'ils indiquent le type d'opération (lecture ou écriture) qu'ils souhaitent effectuer, et l'adresse mémoire concernée. Un tour a lieu quand les 4 périphériques ont été sollicités. Au début d'un nouveau tour, on considère que toutes les adresses sont disponibles en lecture et écriture. Si un périphérique demande l'écriture à une adresse mémoire à laquelle on n'a pas encore accédé pendant le tour, l'ordonnanceur répond "OK" et l'écriture a lieu. Si on a déjà demandé la lecture ou l'écriture à cette adresse, l'ordonnanceur répond "ATT" et l'opération n'a pas lieu. Si un périphérique demande la lecture à une adresse à laquelle on n'a pas encore accédé en écriture pendant le tour, l'ordonnanceur répond "OK" et la lecture a lieu. Plusieurs lectures peuvent avoir donc lieu pendant le même tour à la même adresse. Si un périphérique demande la lecture à une adresse à laquelle on a déjà accédé en écriture, l'ordonnanceur répond "ATT" et la lecture n'a pas lieu. Ainsi, pendant un tour, une adresse peut être utilisée soit une seule fois en écriture, soit autant de fois qu'on veut en lecture, soit pas utilisée. Si un périphérique ne peut pas effectuer une opération à une adresse, il demande la même opération à la même adresse au tour suivant.

(4 points) Cet exercice traite du thème « base de données », et principalement du modèle relationnel et du langage SQL. L’énoncé de cet exercice peut utiliser les mots du langage SQL suivants : CREATE TABLE, SELECT, FROM, WHERE, JOIN ON, INSERT INTO, VALUES, UPDATE, SET, DELETE, COUNT, DISTINCT, AND, OR, AS, ORDER BY, ASC, DESC Un site web recueille des données de navigation dans une base de données afin d'étudier les profils de ses visiteurs. Chaque requête d'interrogation d'une page de ce site est enregistrée dans une première table dénommée Visites sous la forme d'un 5-uplet : (identifiant, adresse IP, date et heure de visite, nom de la page, navigateur). Le chargement de la page index.html par 192.168.1.91 le 12 juillet 1998 à 22h48 aura par exemple été enregistré de la façon suivante : (1534, "192.168.1.91", "1998-07-12 22:48:00", "index.html", "Internet explorer 4.1"). La commande SQL ayant permis de créer cette table est la suivante: CREATE TABLE Visites ( identifiant INTEGER NOT NULL UNIQUE, ip VARCHAR(15), dateheure DATETIME, nompage TEXT, navigateur TEXT );

(4 points) Cet exercice traite du thème « structures de données », et principalement des piles. La classe Pile utilisée dans cet exercice est implémentée en utilisant des listes Python et propose quatre éléments d'interface : • Un constructeur qui permet de créer une pile vide, représentée par [] ; • La méthode est_vide()qui renvoie True si l'objet est une pile ne contenant aucun élément, et False sinon ; • La méthode empiler qui prend un objet quelconque en paramètre et ajoute cet objet au sommet de la pile. Dans la représentation de la pile dans la console, cet objet apparaît à droite des autres éléments de la pile ; • La méthode depiler qui renvoie l'objet présent au sommet de la pile et le retire de la pile. Exemples : >>> mapile = Pile() >>> mapile.empiler(2) >>> mapile [2] >>> mapile.empiler(3) >>> mapile.empiler(50) >>> mapile [2, 3, 50] >>> mapile.depiler() 50 >>> mapile [2, 3] La méthode est_triee ci-dessous renvoie True si, en dépilant tous les éléments, ils sont traités dans l'ordre croissant, et False sinon. 1 def est_triee(self): 2 if not self.est_vide() : 3 e1 = self.depiler() 4 while not self.est_vide(): 5 e2 = self.depiler() 6 if e1 ... e2 : 7 return False 8 e1 = ... 9 return True 22-NSIJ1PO1 10/16

(4 points) Cet exercice traite du thème « algorithmique », et principalement des algorithmes sur les arbres binaires. On manipule ici les arbres binaires avec trois fonctions : • est_vide(A) qui renvoie True si l'arbre binaire A est vide, False s'il ne l'est pas ; • sous_arbre_gauche(A) qui renvoie le sous-arbre gauche de l'arbre binaire A ; • sous_arbre_droit(A) qui renvoie le sous-arbre droit de l'arbre binaire A. L'arbre binaire renvoyé par les fonctions sous_arbre_gauche et sous_arbre_droit peut éventuellement être l'arbre vide. On définit la hauteur d'un arbre binaire non vide de la façon suivante : • si ses sous-arbres gauche et droit sont vides, sa hauteur est 0 ; • si l'un des deux au moins est non vide, alors sa hauteur est égale à 1 + M, où M est la plus grande des hauteurs de ses sous-arbres (gauche et droit) non vides.