Bac blanc

POO : Coloriage de carte¶

Un pays est composé de différentes régions. Deux régions sont voisines si elles ont au moins une frontière en commun. L'objectif est d'attribuer une couleur à chaque région sur la carte du pays sans que deux régions voisines aient la même couleur et en utilisant le moins de couleurs possibles.

La figure ci-dessous donne un exemple de résultat de coloration des régions de la France métropolitaine.

On rappelle quelques fonctions et méthodes des tableaux (le type list en Python) qui pourront être utilisées dans cet exercice :

len(tab) : renvoie le nombre d'éléments du tableau tab ;
tab.append(elt) : ajoute l'élément elt en fin de tableau tab ;
tab.remove(elt) : enlève la première occurrence de elt de tab si elt est dans tab. Provoque une erreur sinon.

Exemples.

len([1, 3, 12, 24, 3]) renvoie 5 ;
Avec tab = [1, 3, 12, 24, 3], on accède au premier élément de tab avec l'instruction tab[0] qui renvoie 1.

On accède au dernier élément de tab avec l'instruction tab[len(tab) - 1] qui renvoie 3. - Avec tab = [1, 3, 12, 24, 3].

L’instruction tab.append(7) modifie tab en [1, 3, 12, 24, 3, 7]. - Avec tab = [1, 3, 12, 24, 3].

L’instruction tab.remove(3) modifie tab en [1, 12, 24, 3].

Les deux parties de cet exercice forment un ensemble. Cependant, il n’est pas nécessaire d’avoir répondu à une question pour aborder la suivante. En particulier, on pourra utiliser les méthodes des questions précédentes même quand elles n’ont pas été codées.

On considère la classe Region qui modélise une région sur une carte et dont le début de l'implémentation est :

class Region:
    """ Modélise une région d'un pays sur une carte. """
    def __init__(self, nom_region):
        """ str -> NoneType """
        self.nom = nom_region
        # tableau des régions voisines. Initialement vide.
        self.tab_voisines = [] 
        # tableau des couleurs disponibles pour colorier la région
        self.tab_couleurs_disponibles = ['rouge', 'vert', 'bleu', 'jaune', 'orange', 'marron']
        # couleur attribuée à la région. Initialement non choisie.
        self.couleur_attribuee = None

Associer, en vous appuyant sur l’extrait de code précédent, les noms tab_voisines, Region et __init__ au terme
qui leur correspond parmi : objet, attribut, méthode ou classe.

tab_voisine est un attribut de la classe Region définit dans la méthode __init__
Donner une instruction permettant de créer une variable ge de type Region correspondant à la région dont le nom est « Grand Est ».
1
ge = Region("Grand Est")

Recopier et compléter la ligne 4 de la méthode de la classe Region ci-dessous :

def renvoie_premiere_couleur_disponible(self):
    """ Region -> str
    Renvoie la première couleur du tableau des couleurs disponibles. """
    return self.tab_couleurs_disponibles[0]

Compléter la méthode de la classe Region ci-dessous à partir de la ligne 4

def renvoie_nb_voisines(self):
    """ Region -> int
    Renvoie le nombre de régions voisines. """
    return len(self.tab_voisines)

Compléter la méthode de la classe Region ci-dessous à partir de la ligne 4.

def est_coloriee(self):
    """ Region -> bool
    Renvoie True si une couleur a été attribuée à self, False sinon. """
    return not self.couleur_attribuee == None

Compléter la méthode de la classe Region ci-dessous à partir de la ligne 6.

def retire_couleur(self, couleur):
    """ Region, str -> NoneType 
    Retire couleur du tableau des couleurs disponibles de la region self si la couleur
    est présente dans le tabeau. Ne fait rien sinon. 
    Modifie le tableau des couleurs disponibles. 
    """
    est_present = False
    for e in self.tab_couleurs_disponibles:
        if e == couleur:
            est_present = True
    if est_present:
        self.tab_couleurs_disponibles.remove(couleur)

Compléter la méthode de la classe Region ci-dessous, à partir de la ligne 4, en utilisant une boucle. On considèrera que deux régions sont identiques si et seulement si elles ont le même attribut nom.

def est_voisine(self, region):
    """ Region, Region -> bool
    Renvoie True si region est une voisine de self, False sinon. """
    for r in self.tab_voisines:
        if r.nom == self.nom:
            return True
    return False

Dans cette partie :

on considère qu’on dispose d’un ensemble d’instances de la classe Region pour lesquelles l’attribut tab_voisines a été renseigné ;
on pourra utiliser les méthodes de la classe Region évoquées dans les questions de la partie 1 :
- renvoie_premiere_couleur_disponible
- renvoie_nb_voisines
- est_coloriee
- retire_couleur
- est_voisine

On a créé une classe Pays :

class Pays:
    """ Représente un Pays """
    def __init__(self, c):
        self.tab_regions = c

cette classe modélise la carte d’un pays composé de régions ;
l’unique attribut tab_regions de cette classe est un tableau (type list en Python) dont les éléments sont des instances de la classe Region.

Compléter la méthode de la classe Pays ci-dessous à partir de la ligne 4.

def renvoie_tab_regions_non_coloriees(self):
    """ Pays -> [Region]
    Renvoie un tableau dont les éléments sont les régions du pays sans couleur attribuée """
    non_colo = []
    for r in self.tab_regions:
        if not r.est_coloriee():
            non_colo.append(r)
    return non_colo

On considère la méthode de la classe Pays ci-dessous.

def renvoie_max(self):
    """ Pays -> Region """
    nb_voisines_max = -1
    region_max = None
    for reg in self.renvoie_tab_regions_non_coloriees():
        if reg.renvoie_nb_voisines() > nb_voisines_max:
            nb_voisines_max = reg.renvoie_nb_voisines()
            region_max = reg
    return region_max

Expliquer dans quel cas cette méthode renvoie None.

Dans le cas où il n'y a aucun élément dans le tableau renvoyé par la méthode renvoie_table_regions_non_coloriees de la classe Region, c'est à dire lorsque l'on a attribué à chaque région du pays une couleur.
Indiquer, dans le cas où cette méthode ne renvoie pas None, les deux particularités de la région renvoyée.

La région renvoyée n'a pas été encore coloriée et c'est elle qui possède le plus grand nombre de région voisines parmi les régions du pays non encore coloriées.

Écrire une méthode colorie de la classe Pays qui choisit une couleur pour chaque région du pays de la façon suivante.

On récupère la région non coloriée qui possède le plus de voisines.
Tant que cette région existe :
- La couleur attribuée à cette région est la première couleur disponible dans son tableau de couleurs disponibles.
- Pour chaque région voisine de la région :
  - si la couleur choisie est présente dans le tableau des couleurs disponibles de la région voisine alors on la retire de ce tableau.
- On récupère à nouveau la région non coloriée qui possède le plus de voisines.

def colorie(self):
    """ Pays -> Nonetype """
    max_r = self.renvoie_max()
    while max_r is not None:
        coul = max_r.renvoie_premiere_couleur_disponible()
        max_r.couleur_attribuee = coul
        max_r.retire_couleur(coul)
        for r in max_r.tab_voisines:
            r.retire_couleur(coul)
        max_r = self.renvoie_max()

# On effectue quelques tests pour vérifier que les codes sont corrects.
def link(r1, r2):
    """ Region, Region -> None
    Rend les deux régions voisines. """
    r1.tab_voisines.append(r2)
    r2.tab_voisines.append(r1)

r1 = Region("Haut de france")
r2 = Region("Normandie")
r3 = Region("Grand Est")
r4 = Region("Ile de france")
r5 = Region("Bretagne")
r6 = Region("Pays de la loire")
r7 = Region("Centre val de loire")
r8 = Region("Bourgogne franche-comté")
r9 = Region("Nouvelle aquitaine")
r10 = Region("Auvergne rhône-alpes")
r11 = Region("Occitanie")
r12 = Region("Provence alpes côte d'azur")
r13 = Region("Corse")

link(r1, r2), link(r1, r3), link(r4, r1)
link(r4, r2), link(r4, r3), link(r5, r2) 
link(r6, r5), link(r6, r2), link(r7, r2) 
link(r7, r4), link(r7, r6), link(r8, r3) 
link(r8, r4), link(r8, r7), link(r9, r6) 
link(r9, r7)
link(r10, r7), link(r10, r8), link(r10, r9)
link(r11, r9), link(r11, r10)
link(r12, r11)
link(r13, r12) 

france = Pays([r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13])    
france.colorie()

# On ajoute une méthode à la classe Pays
def affiche_coloration(self):
    """ Pays -> None
    Affiche la coloration du pays self."""
    for r in self.tab_regions:
        print(f"Région {r.nom} : {r.couleur_attribuee}")

france.affiche_coloration()

Région Haut de france : rouge
Région Normandie : vert
Région Grand Est : jaune
Région Ile de france : bleu
Région Bretagne : rouge
Région Pays de la loire : bleu
Région Centre val de loire : rouge
Région Bourgogne franche-comté : vert
Région Nouvelle aquitaine : vert
Région Auvergne rhône-alpes : bleu
Région Occitanie : rouge
Région Provence alpes côte d'azur : vert
Région Corse : rouge

Arbres binaires : Arbres de pedigrée¶

Un éleveur de chiens gère les informations sur ses animaux à l'aide d'un logiciel qui mémorise le pédigrée de chacun de ses chiens. Le pédigrée d'un chien correspond à son arbre généalogique.

Une structure d'arbre de pedigrée est définie récursivement :

l'arbre vide est un arbre de pedigrée ;
la valeur du nœud racine est une chaîne de caractère qui représente le nom de l'animal ;
le sous-arbre gauche est l'arbre de pedigrée du père du chien ;
le sous-arbre droit est l'arbre de pedigrée de la mère du chien.

Par exemple, l'arbre A ci-dessous est un arbre de pedigrée :

Dans cet arbre :

le père de Mango est Domino et sa mère est Pinkie ;
les parents de Douchka ne sont pas connus ;
Iris est la mère de Pinkie ;
la mère de Tango n'est pas connue.

Pour manipuler les arbres de pedigrée, on dispose des quatre fonctions suivantes :

la fonction racine qui prend en paramètre un arbre de pedigrée non vide et renvoie la valeur de la racine.

Exemple. racine(A) renvoie "Mango".
La fonction gauche qui prend en paramètre un arbre de pedigrée non vide et qui renvoie son sous-arbre gauche correspondant à l'arbre de dédigrée du père.

Exemple. gauche(A) est l'arbre :
La fonction droit qui prend en paramètre un arbre de pedigrée non vide et qui renvoie son sous-arbre droit correspondant à l'arbre de dédigrée de la mère.

Exemple. droit(A) est l'arbre :
La fonction est_vide qui prend en paramètre un arbre de pedigrée et qui renvoie True si l'arbre est vide et False sinon.

Exemple : est_vide(A) renvoie False.

class Noeud:
    def __init__(self, etiquette):
        self.etiquette = etiquette
        self.gauche = None
        self.droit = None

def creer_vide(): return None
def est_vide(a): return a is None
def racine(a): return a.etiquette
def gauche(a): return a.gauche
def droit(a): return a.droit
def Arbre(e, a1, a2): return Noeud(e, a1, a2)
def tableau2arbre(tab):
    """ [int] -> Arbre
    Renvoie l'arbre binaire correspondant, rempli en largeur d'abord  """
    if not tab: return None
    root = Noeud(tab.pop(0))
    liste = [root]
    while not tab == []:
        noeud = liste.pop(0)
        x1 = tab.pop(0)
        if x1 is not None:
            noeud.gauche = Noeud(x1)
            liste.append(noeud.gauche)
        if not tab == []:
            x2 = tab.pop(0)
            if x2 is not None: 
                noeud.droit = Noeud(x2)
                liste.append(noeud.droit)
    return root

def affiche(a):
    """ Arbre -> Nonetype
    Affiche l'arbre a de manière infixe """
    if est_vide(a):
        pass
    else:
        print("(", end="")
        affiche(gauche(a))
        print(racine(a), end="")
        affiche(droit(a))
        print(")", end="")

Btab = ["Milka", "Éclair", "Nougat", None, "Étoile", "Neige", "Nuage", "Ulk", "Maya", "Museau", None, None, "Noisette", "Nemo", "Moka"]
B = tableau2arbre(Btab)
affiche(B)

((Éclair(((Nemo)Ulk(Moka))Étoile(Maya)))Milka(((Museau)Neige)Nougat(Nuage(Noisette))))

Pour toutes les questions de l'exercice, on suppose que tous les chiens d'un même arbre de pedigrée ont des noms différents.

On considère l'arbre de pédigrée B suivant.

Déterminer la valeur de la racine de cet arbre.
1
print(racine(B))
```
Milka
```

On appelle feuille d'un arbre de pédigrée un nœud dont les sous-arbres gauches et droits sont vides.

Déterminer l'ensemble des valeurs des feuilles de cet arbre.

def feuilles(a):
    if est_vide(a):
        return []
    elif est_vide(gauche(a)) and est_vide(droit(a)):
        return [racine(a)]          
    else:
        return feuilles(gauche(a)) + feuilles(droit(a))

print(feuilles(B))

['Nemo', 'Moka', 'Maya', 'Museau', 'Noisette']

Déterminer si Nuage est un mâle ou une femelle. Justifier.

"Nuage" est la racine du sous-arbre droit de l'arbre de racine "Noisette". Nuage est donc la mère de Noisette : c'est une femelle.
Déterminer le nom du père de Étoile.

Le père de étoile est Ulk.

Recopier et compléter la fonction python present ayant pour paramètres un arbre de pédigrée arb et le nom d'un chien nom et qui renvoie True si ce nom est présent dans l'arbre de pédigrée, et False sinon.

def present(arb, nom):
    if est_vide(arb):
        return False
    elif racine(arb) == nom :
        return True
    else:
        return present(gauche(arb), nom) or present(droit(arb), nom)

print(present(B, "Moka"))
print(present(B, "Kamo"))

True
False

Pour toute la suite de l'exercice, on pourra utiliser la fonction present même si la question n'a pas été traitée.

Écrire une fonction python parents ayant pour paramètre un arbre de pédigrée arb d'un chien et qui renvoie le p-uplet des deux parents de ce chien dans l'ordre père, mère. Si un des parents est inconnu, il sera noté "".

Exemple. parents(B) vaut ("Éclair", "Nougat"),

parents(gauche(B)) vaut ("", "Étoile").

def parents(arb):
    """ Arbre -> (str, str) | Nonetype """
    # Si l'arbre est vide alors il n'y a pas de parents
    if est_vide(arb):
        return 
    g, d = "", ""
    # Attention, il est possible que le sous-arbre gauche
    # soit vide : sa racine n'existe pas. 
    if not est_vide(gauche(arb)):
        g = racine(gauche(arb))
    if not est_vide(droit(arb)):
        d = racine(droit(arb))
    return (g, d)

print(parents(B))
print(parents(gauche(B)))

('Éclair', 'Nougat')
('', 'Étoile')

2. 1. On dit que deux chiens sont des frères et sœurs s'ils ont le même père ou la même mère. On considère les trois arbres de pédigrée suivants.

Arbre A
Arbre B
Arbre C
Parmi les trois chiens Mango, Milka, et Cacao, déterminer les liens de fratrie.

Mango et Cacao on le même père, ils sont frère et sœur. Milka et Cacao ont la même mère, ils sont frère et sœur. Mango n'a pas de frère et sœur parmi Milka et Cacao.

Écrire une fonction python frere_soeur ayant pour paramètres deux arbres de pédigrée arb1 et arb2 correspondant à deux chiens. Cette fonction renvoie True si les deux chiens ont le même père ou la même mère ou False sinon.

def frere_soeur(arb1, arb2):
    """ Arbre, Arbre -> bool """
    p1, m1 = parents(arb1)
    p2, m2 = parents(arb2)
    # pour que arb1 et arb2 soient frères et soeurs il faut qu'ils aient
    # un même parent (père ou mère) et que celui-ci existe !
    return (p1 == p2 and p1 != "") or (m1 == m2 and m1 != "")

Les ancêtres d'un chien d'arbre de pédigré arb sont les valeurs des nœuds présents dans le sous-arbre gauche ou dans le sous-arbre droit. Cela correspond à tous les nœuds de profondeur supérieure ou égale à 1.

Donner les ancêtres de Domino. Donner les ancêtres de Pinkie.

En déduire les ancêtres de Mango.

Les ancêtres de Mango sont Domino, Pinkie, ainsi que les ancêtres de Domino et de Pinkie.
Donner les ancêtres de Éclair. Donner les ancêtres de Nougat.

En déduire les ancêtres de Milka.

Les ancêtres de Milka sont Éclair, Nougat, ainsi que les ancêtres de Éclair et de Nougat.

Déduire des questions précédentes une fonction python récursive ancetres ayant pour paramètre un arbre de pédigrée arb non vide d'un chien et qui renvoie la liste de tous les ancêtres de ce chien.

On pourra compléter le squelette de la fonction ancetres ci-dessous, mais toute autre code python valide sera accepté.

def ancetres(arb):
    """ Arbre -> [str] """
    if parents(arb) == ("", ""):
        return []
    elif est_vide(gauche(arb)):
        return [racine(droit(arb))] + ancetres(droit(arb))
    elif est_vide(droit(arb)):
        return [racine(gauche(arb))] + ancetres(gauche(arb))
    else:
        return ancetres(gauche(arb)) + [racine(gauche(arb)), racine(droit(arb))] + ancetres(droit(arb))

print(ancetres(B))

['Étoile', 'Nemo', 'Moka', 'Ulk', 'Maya', 'Éclair', 'Nougat', 'Museau', 'Neige', 'Nuage', 'Noisette']

Exemple. ancetres(B) vaut ["Éclair", "Étoile", "Ulk", "Nemo", ..., "Nougat", ..., "Noisette"].

Étant donné l'arbre de pédigrée d'un chien, on considère que :

le niveau 0 est le niveau de la racine ;
le niveau 1 est le niveau des parents du chien ;
le niveau 2 est le niveau des grands-parents du chien ;
etc.

Proposer une fonction nombre_chiens ayant pour paramètre un arbre de pédigrée arb et un entier n et qui renvoie le nombre de noms connus dans l'arbre de pédigrée au niveau n.

Exemple. nombre_chiens(B, 3), renvoie 4, car les noms des chiens mentionnés dans l'arbre de pédigrée au niveau 3 sont "Ulk", "Maya", "Museau", et "Noisette".

def nombre_chiens(arb, n):
    if est_vide(arb):
        return 0
    else:
        if n == 0:
            return 1
        else:
            return nombre_chiens(gauche(arb), n - 1) + nombre_chiens(droit(arb), n - 1)

print(nombre_chiens(B, 3))           

Bases de données : Matchs de basket-ball¶

L’énoncé de cet exercice utilise les mots clefs du langage SQL suivants : SELECT, FROM, WHERE, JOIN ON, UPDATE, SET, INSERT INTO VALUES, COUNT, ORDER BY.

La ligue féminine de basket-ball publie les données relatives à chaque saison sur le site web de la ligue. On y retrouve des informations concernant les équipes participantes, les calendriers et les résultats des match ainsi que les statistiques des joueuses. Dans cet exercice, nous allons nous intéresser à la base de données relationnelle LFP_2021_2022 permettant le stockage et la gestion des données de la saison régulière de basket-ball féminin 2021-2022.

Voici ci-dessous le contenu entier de la relation (table) Equipe :

`id_equipe`	`nom`	`adresse`	`telephone`
1	Saint-Amand	39 avenue du Clos, 59230 Saint-Amand-les-Eaux	03 04 05 06 07
2	Basket Landes	15 place Saint-Roch, 40000 Mont-De-Marsan	05 06 07 08 09
3	Villeneuve d’Ascq	2 rue Breughel, 59650 Villeneuve-d’Ascq	03 02 01 00 01
4	Tarbe	Quai de l’Adour, 65000 Tarbes	05 04 03 02 02
5	Lyon	451 cours d’Emile Zola, 69100 Villeurbanne	04 05 06 07 08
6	Bourges	6 rue du Pré Doulet, 18000 Bourges	02 03 04 05 06
7	Charleville-Mézières	Rue de la Vieille Meuse, 08000 Charleville-Mézières	03 05 07 09 01
8	Landerneau	Kerouel, 29410 Pleyber-Christ	02 04 06 08 00
9	Angers	330 rue Saint-Léonard, 49000 Angers	02 00 08 06 04
10	Lattes Montpellier	157 rue de la Porte Lombarde, 34970 Lattes	04 03 02 01 00
11	Charnay	Allée des Ecoliers, 71850 Charnay-lès-Mâcon	03 01 09 07 05
12	Roche Vendée	BP 151, 85004 La Roche-Sur-Yon Cedex	02 05 08 01 04

On donne ci-dessous le schéma relationnel de la table Equipe sous forme de tableau.

Dans ce schéma, un attribut souligné indique qu’il s’agit d’une clé primaire.

Après le chargement de la table Equipe, expliquer pourquoi la requête suivante produit une erreur :
1 2
INSERT INTO Equipe VALUES (11, "Toulouse", "2 rue du Nord, 40100 Dax", "05 04 03 02 01");
L'attribut id_equipe est une clé primaire pour la relation table (il doit être donc unique) et il y a déjà un enregistrement dont l'attribut id_equipe vaut 11.
Donner le résultat de la requête suivante :
1
SELECT nom, telephone FROM Equipe WHERE id_equipe = 5;
Cela renvoie (Lyon, 04 05 06 07 08).
Donner et expliquer le résultat de la requête suivante :
1
SELECT COUNT(*) FROM Equipe;
Cette requête compte le nombre d'enregistrement de la relation Equipe. Cette requête renvoie donc 12.
Écrire la requête SQL permettant d’afficher les noms des équipes par ordre alphabétique.
1 2
SELECT nom FROM Equipe ORDER BY nom ;
Écrire la requête SQL permettant de corriger le nom de l’équipe dont l'id_equipe est égal à 4. Le nom correct est "Tarbes".
1 2 3
UPDATE Equipe SET nom = 'Tarbes' WHERE id_equipe = 4 ;

Sur le site web de la fédération de basket-ball féminin, nous pouvons consulter la composition des équipes. Pour chaque joueuse, on peut y lire en plus de son nom, sa date de naissance, sa taille ainsi que le poste occupé dans l'équipe. Ces informations sont présentées dans une page web dont le titre est « Fiche Joueuse », page construite à partir de la table Joueuse dont voici un extrait :

`id_joueuse`	`nom`	`prenom`	`date_naissance`	`taille`	`poste`	`id_equipe`
1	Berkani	Lisa	19/05/1997	176	2	7
2	Alexander	Kayla	05/01/1991	193	5	5
3	Magarity	Regan	30/04/1996	192	4	2
4	Muzet	Johanna	08/07/1997	183	3	11
5	Kalu	Ezinne	26/06/1992	173	2	8
6	Sigmundova	Jodie Cornelie	20/04/1993	193	5	9
7	Dumerc	Céline	09/07/1982	162	2	2
8	Slonjsak	Iva	16/04/1997	183	3	9
9	Michel	Sarah	10/01/1989	180	2	6
10	Lithard	Pauline	11/02/1994	164	1	1

On donne ci-dessous le schéma relationnel de la table Joueuse sous forme de tableau.

Un attribut souligné indique qu'il s'agit d’une clé primaire. Le symbole # devant un attribut indique qu’il s’agit d’une clé étrangère. La clé étrangère Joueuse.id_equipe fait référence à la clé primaire Equipe.id_equipe de la table Equipe.

Expliquer pourquoi il est possible de déclarer l’attribut id_equipe comme clé étrangère dans la table Joueuse.

L'attribut id_equipe est une clé primaire de la relation Equipe. On peut donc l'utiliser comme clé étrangère dans la relation Joueuse.
On souhaite supprimer toutes les informations relatives à une équipe. Expliquer pourquoi on ne peut pas directement supprimer cette équipe dans la table Equipe.

On ne peut pas supprimer un enregistrement de la relation Equipe dont l'attribut id_equipe est utilisé dans la relation Joueuse : on violerait une contrainte d'intégrité.
Écrire la requête SQL qui permet d’afficher les noms et les prénoms des joueuses de l’équipe d’Angers. On supposera que l’utilisateur qui écrit cette requête ne connaît pas l’identifiant de l’équipe d’Angers.
1 2 3
SELECT Joueuse.nom, Joueuse.prenom FROM Joueuse JOIN Equipe ON Equipe.id_equipe = Joueuse.id_joueuse WHERE Equipe.nom = 'Angers'

Les résultats des matchs sont aussi publiés sur le site web de la ligue. Par exemple, pour le match numéro 10 qui a opposé l’équipe de Villeneuve d’Ascq à l’équipe de Bourges le 23/10/2021 on retrouve les informations suivantes :

Le score final du match a été de 73 points pour l’équipe de Villeneuve d’Ascq qui a joué à domicile (nom affiché à gauche sur la page) contre 78 points pour l’équipe de Bourges qui a joué en déplacement (nom affiché à droite sur la page).
1. À partir de l’analyse de cet exemple, proposer un schéma relationnel (sous forme de tableau) pour la table Match. Préciser la clé primaire ainsi que le domaine de chacun des attributs retenus (on se restreindra aux domaines INT, DATE, et TEXT). Si des clés étrangères sont définies, préciser quelles tables et quels attributs elles référencent.
  
  La clé primaire de la relation est id_match. Les attributs equipe_dom et equipe_ext font tous deux référence à l'attribut id_equipe de la relation Equipe.
2. Écrire la requête SQL qui permet l’insertion dans la table Match de l’enregistrement correspondant à l’exemple donné ci-dessus.
  1 2
  INSERT INTO Match VALUES (10, '2021/10/23', 3, 6, 73, 78) ;

En plus du score final, sur la page web sont affichés des informations relatives aux performances des joueuses pendant le match. Nous allons retenir ici seulement 3 critères : le nombre de points marqués, les rebonds et les passes décisives effectués.

Voici un extrait des statistiques du match numéro 53 qui a opposé l’équipe de Landerneau à celle de Charleville-Mézières le 16/04/2022 :

Proposer un schéma relationnel (sous forme de tableau) pour la table Statistique qui permette de stocker les informations relatives aux statistiques des joueuses dans la base de données, telles que présentées ci-dessus.

Préciser la clé primaire ainsi que le domaine de chacun des attributs retenus. Si des clés étrangères sont définies, préciser quelles tables et quels attributs elles référencent.

La clé primaire de la relation Stat est (id_match, id_joueuse) (une joueuse ne joue qu'une fois dans un match). L'attribut id_match est une clé étrangère qui référence l'attribut id_match de la table Match. L'attribut id_joueuse est une clé étrangère qui référence l'attribut id_joueuse de la table Joueuse.

Écrire la requête SQL qui a été utilisée pour afficher la partie « Extrait des statistiques » de l’exemple ci-dessus.

SELECT Equipe.nom, Joueuse.nom, Joueuse.prenom, Stat.points, Stat.rebonds, Stat.passe_d FROM Stat
JOIN Joueuse ON Stat.id_joueuse = Joueuse.id_joueuse
JOIN Equipe ON Joueuse.id_equipe = Equipe.id_equipe
JOIN Match ON Equipe.id_equipe = Match.equipe_dom
JOIN Match ON Equipe.id_equipe = Match.equipe_ext
WHERE id_match = 53 ;

Système d'exploitation et processus¶

Partie A

Pour chacune des questions, une seule des quatre réponses est exacte. Vous indiquerez sur votre copie le numéro de la question et la lettre correspondant à la réponse exacte. Aucune justification n’est demandée. Une réponse fausse ou une absence de réponse n’enlève aucun point.

Parmi les commandes ci-dessous, laquelle permet d’afficher les processus en cours d’exécution ?

Il s'agit de ps
1. dir
2. ps
3. man
4. ls
5. Quelle abréviation désigne l’identifiant d’un processus dans un système d’exploitation de type UNIX ?
Il s'agit de PID (process identifier).
1. PIX
2. SIG
3. PID
4. SID
5. Comment s’appelle la gestion du partage du processeur entre différents processus ?
Il s'agit de l'ordonnancement de processus.
1. L’interblocage
2. L’ordonnancement
3. La planification
4. La priorisation
5. Quelle commande permet d’interrompre un processus dans un système d’exploitation de type UNIX ?
Il s'agit de kill.
1. stop
2. interrupt
3. end
4. kill

Partie B

Un processeur choisit à chaque cycle d’exécution le processus qui doit être exécuté. Le tableau ci-dessous donne pour trois processus P1, P2, P3 :
- la durée d’exécution (en nombre de cycles),
- l’instant d’arrivée sur le processeur (exprimé en nombre de cycles à partir de 0),
- le numéro de priorité.
Processus Durée d'exécution Instant d'arrivée Numéro de priorité

P1 3 3 1

P2 3 2 2

P3 4 0 3

Le numéro de priorité est d’autant plus petit que la priorité est grande. On suppose qu’à chaque instant, c’est le processus qui a le plus petit numéro de priorité qui est exécuté, ce qui peut provoquer la suspension d’un autre processus, lequel reprendra lorsqu’il sera le plus prioritaire.

Reproduire le tableau ci-dessous sur la copie et indiquer dans chacune des cases le processus exécuté à chaque cycle.

L'ordonnancement est P3, P1, P1, P1, P2, P2, P2, P3, P3, P3.
On suppose maintenant que les trois processus précédents s’exécutent et utilisent une ou plusieurs ressources non préemptibles (on ne peut retirer la ressource à un processus qui l'a acquise) et d'usage exclusif (plusieurs processus ne peuvent acquérir la même ressource simultanément) parmi R1, R2 et R3.

On propose trois scénarios d'ordonnancement des opérations d'acquisition, d'attente, et de libération des ressources R1, R2 et R3 par les processus P1, P2 et P3. On suppose qu'à l'issue de chacun des scénarios proposés, les processsus n'effectuent plus d'opérations d'acquisition ou d'attente de ressource. On suppose également qu'ils libèrent la ou les ressources qu'ils ont acquises lorsqu'ils ne sont plus en attente d'aucune autre ressource.

Parmi les scénarios ci-dessus, lequel provoque un interblocage (une seule bonne réponse possible) ? Justifier.

Une flèche en trait plein représente une ressource allouée à un processus. Une flèche en pointillés représente une demande de ressource de la part d'un processus. Une flèche barrée représente une ressource qui a été libérée par un processus. Seul le graphe d'allocation du scénario 2 possède un cycle \(P1 - R2 - P3 - R1 - P1\). Il y a donc un interblocage dans le scénario 2.

Processus	Durée d'exécution	Instant d'arrivée	Numéro de priorité
`P1`	3	3	1
`P2`	3	2	2
`P3`	4	0	3