2022 Mayotte Jour 2

(4 points) Cet exercice porte sur les structures de données (pile). La notation polonaise inverse (NPI) permet d'écrire des expressions de calculs numériques sans utiliser de parenthèse. Cette manière de présenter les calculs a été utilisée dans des calculatrices de bureau dès la fin des années 1960. La NPI est une forme d’écriture d’expressions algébriques qui se distingue par la position relative que prennent les nombres et leurs opérations. Par exemple : Notation classique Notation NPI 3+9 3 9 + 8×(3+5) 8 3 5 + × (17+5)×4 17 5 + 4 × L’expression est lue et évaluée de la gauche vers la droite en mettant à jour une pile. • Les nombres sont empilés dans l’ordre de la lecture. • Dès la lecture d’un opérateur (+, -, ×, /), les deux nombres au sommet de la pile sont dépilés et remplacés par le résultat de l’opération effectuée avec ces deux nombres. Ce résultat est ensuite empilé au sommet de la pile. A la fin de la lecture, la valeur au sommet est renvoyée. Exemple : l’expression 7 3 25 + × qui correspond au calcul 7×(3+25) s’évalue à 196 comme le montrent les états successifs de la pile créée, nommée p : • On empile la valeur 7. • On empile la valeur 3. • On empile la valeur 25. • On remplace les deux nombres du sommet de la pile (25 et 3) par leur somme 28. • On remplace les deux nombres du sommet de la pile (28 et 7) par leur produit 196. Schéma descriptif des différentes étapes d’exécution. 7 3 25 + × 25 3 3 28 7 7 7 7 196 p p p p p p

(4 points) Cet exercice porte sur les bases de données. Dans cet exercice, on pourra utiliser les mots clés suivants du langage SQL : SELECT, FROM, WHERE, JOIN, ON, INSERT INTO, UPDATE, VALUES, OR, AND. Leur utilisation est rappelée en annexe 1 en fin de sujet. La gestion d'un hôtel est faite à l'aide d'une base de données dont voici le schéma relationnel. Chambres (NumChambre, Prix, lits) Clients (NumClient, Nom, Prenom, Telephone) Reservations (NumRes, #NumClient, #NumChambre, DateArr, DateDep) Dans ce schéma, les clés primaires sont soulignées et les clés étrangères sont précédées du symbole #.

(4 points) Cet exercice porte sur la représentation binaire d’un entier relatif et les systèmes d’exploitation.

Cet exercice porte sur les arbres binaires de recherche. Un arbre binaire est soit vide, soit un nœud qui a une valeur et au plus deux fils (le sous-arbre gauche et le sous-arbre droit). Dans la représentation ci-contre, X est un nœud G1 est le fils gauche de X D1 est le fils droit de X Un arbre binaire de recherche est ordonné de la manière suivante : Pour chaque nœud,  les valeurs de tous les nœuds du sous-arbre gauche sont strictement inférieures à la valeur du nœud  les valeurs de tous les nœuds du sous-arbre droit sont supérieures ou égales à la valeur du nœud Ainsi, par exemple, toutes les valeurs des nœuds G1, G2 et G3 sont strictement inférieures à la valeur du nœud X et toutes les valeurs des nœuds D1, D2 et D3 sont supérieures ou égales à la valeur du nœud X. Au fur et à mesure que les billets d'une loterie sont vendus, les numéros inscrits sur les billets sont insérés dans un arbre binaire de recherche. Chaque nœud de l'arbre est un couple, la 1ère valeur correspond au numéro du billet et la seconde est une référence permettant de connaître le lieu de vente du billet. Par exemple au couple (45,'AZ60') correspond le billet n°45 vendu par le commerçant 'AZ60'. Seul le numéro du billet est utilisé pour positionner le nœud dans l'arbre.

(4 points) Cet exercice porte sur les algorithmes et la programmation Python. Dans le jeu du TAKAZU, on dispose d'une grille de 10 lignes et 10 colonnes contenant des zéros et des uns. L'objectif est de compléter les cases blanches en respectant les règles ci-dessous : • [REGLE1] : chaque ligne et chaque colonne doivent contenir autant de 0 que de 1. • [REGLE2] : les lignes ou colonnes identiques sont interdites. • [REGLE3] : il ne doit pas y avoir plus de deux 0 ou plus de deux 1 placés à la suite, ni dans le sens vertical, ni dans le sens horizontal. Dans cet exercice, on suppose que les valeurs de chaque ligne sont stockées dans une liste en Python, et toutes les lignes sont à leur tour placées dans une liste globale notée grille. Ainsi, dans la situation représentée ci-contre, grille[0][2] vaut 1 et grille[0][3] vaut 0. On décide aussi de coder par -1 toutes les cases blanches, c'est-à-dire celles dont on ne connait pas encore la valeur. Dans notre exemple, au départ grille[0][1] vaut -1.