Correction Bac Blanc 25 janvier

Exerice 1

1.

Le trajet le plus court est Mp -> Ar -> Ax -> Nc. La distance est de 332km (80 + 76 + 176)

2.

Il y'a deux chemins possibles en passant par 2 villes intermédiaires.

Le plus court en distance : Mp -> Ar -> Ax -> Nc et Mp -> Ar -> Mr -> Nc

3.

Voici la liste d'adjacence

Python

G = {
'Av': ['Ax', 'Mr', 'Ni'],
'Ni': ['Ar', 'Av', 'Mp'],
'Mp': ['Ar', 'Ni'],
'Ar': ['Ax', 'Mp', 'Mr', 'Ni'],
'Mr': ['Ar', 'Av', 'Ax', 'Nc', 'To'],
'Ax': ['Ar', 'Av', 'Di', 'Mr', 'Nc', 'To'],
'To': ['Ax', 'Mr', 'Nc'],
'Nc': ['Ax', 'Di', 'Mr', 'To'],
'Di': ['Ax', 'Nc']
}

4.

LIFO et FIFO sont des acronymes qui représentent respectivement le fonctionnement des piles et des files. LIFO : Last In, First Out, premier rentré, dernier sorti FIFO : First In, First Out, premier rentré, dernier sorti.

5.

Une file fonctionne selon le principe FIFO.

6.

Le parcours de cette fonction retourne

Python

>>> parcours(G,'Av')
['Av', 'Ax', 'Mr', 'Ni', 'Ar', 'Di', 'Nc', 'To', 'Mp']

Python

def parcours(graphe, sommet):
    f = creerFile()
    enfiler(f, sommet)
    visite = [sommet]
    while not estVide(f):
        s = defiler(f)
        for v in graphe[s]:
            if not (v in visite):
                visite.append(v)
                enfiler(f, v)
    return visite

7.

Ce code effectue un parcours en largeur.

8.

Nous reprenons le parcours en largeur en incrémentant de 1 les distances à chaque voisin d'un sommet. Voici le code de la fonction:

Python

def distance(graphe, sommet):
    f = creerFile() # Crée un file vide
    enfiler(f, sommet) # AJoute le sommet de départ
    visite = [sommet] # Liste des sommets déjà visités
    distance = {sommet:0} # Ajout de la première valeur dans le dictionnaire des distances
    while not estVide(f): # Parcours tant que la file n'est pas vide
        s = defiler(f) # Pour visiter les voisins du sommet le plus ancion
        for v in graphe[s]: # boucle des voisins
            if not (v in visite): # nous ne traitons que les voisins non déjà rencontrés
                distance[v] = distance[s] + 1 # s est déjà dans le dictionnaire
                visite.append(v) # ajout de v à la liste des sommets visités
                enfiler(f, v) # ajout de v à la file
    return distance

9.

Voici le retour de distance(G, 'Av')

Python

>>> distance(G,'Av')
{'Av': 0, 'Ax': 1, 'Mr': 1, 'Ni': 1, 'Ar': 2, 'Di': 2, 'Nc': 2, 'To': 2, 'Mp': 2}

10.

Python

def parcours2(G, s):
    p = creerPile() # Créer pile vide
    empiler(p, s) # Ajout de s à la pile du parcours
    visite = [] # vide, s sera ajouté avec le 1er dépilement
    while not estVide(p):
        x = depile(p) # On prend le dernier sommet
        if x not in visite: # Si il n'a pas déjà été visité
            visite.append(x) # Ajout à la liste visite
            for v in G[x]:
                empiler(p, v) # Empile les voisins, même ceux déja visités.
    return visite

11.

C'est un parcours en profondeur.

Python

>>> parcours2(G,'Av')
['Av', 'Ni', 'Mp', 'Ar', 'Mr', 'To', 'Nc', 'Di', 'Ax']

Exercice 2

1.

• Le noeud initial est appelé racine
• Un noeud qui n’a pas de fils est appelé feuille
• Un arbre binaire est un arbre dans lequel chaque noeud a au maximum deux fils.
• Un arbre binaire de recherche est un arbre binaire dans lequel tout nœud est associé à une clé qui est :
  • supérieure à chaque clé de tous les nœuds de son sous-arbre gauche
  • inférieure à chaque clé de tous les nœuds de son sous-arbre droit

2.

Le parcours préfixe donne: 1 - 0 - 2 - 3 - 4 - 5 - 6

3.

Le parcours suffixe donne : 0 - 1 - 2 - 6 - 5 - 4 - 3

4.

Le parcours infixe donne: 0 - 1 - 2 - 3 - 4 -5 - 6

5.

Voici le code correspondant àl'instanciation des abres 1, 2 et 3.

Python

arbre_no1 = ABR()
arbre_no2 = ABR()
arbre_no3 = ABR()
for cle_a_inserer in [1, 0, 2, 3, 4, 5, 6]:
    arbre_no1.inserer(cle_a_inserer)
for cle_a_inserer in [3, 2, 4, 1, 5, 0, 6]:
    arbre_no2.inserer(cle_a_inserer)
for cle_a_inserer in [3, 1, 5, 0, 2, 4, 6]:
    arbre_no3.inserer(cle_a_inserer)

6.

En utilisant la méthdode donnée, nous avons les hauteurs :

arbre_no1 : 5

arbre_no2 : 3

arbre_no3 : 2

7.

Voici le code complété

Python

def est_present(self, cle_a_rechercher):
    if self.est_vide() :
        return False
    elif cle_a_rechercher == self.cle() :
        return True
    elif cle_a_rechercher < self.cle() :
        return self.sag().est_present(cle_a_rechercher)
    else :
        return self.sad().est_present(cle_a_rechercher)

8.

Erreur: la méthode est est_present et non est_presente.

Le code effectue une recherche dans un ABR en cherchant dans le sous-arbre gauche quand la valeur est strictement inférieure au noued et dans le sous-arbre droit.

Le code qui effectue le moins d'appels récursifs est celui qui s'arrête à la prodondeur la plus faible. Ici pour arbre_no3

9.

Le code de est_partiellement_equilibre, indique qu’un arbre est partiellement équilibré s’il est vide ou si la différence de hauteur entre son sous arbre gauche et son sous-arbre droit est comprise entre -1 et 1.

10.

En vérifiant la propriété est_partiellement_equilibre à la racine des 3 arbres, nous avons bien 2 arbres sur 3 partiellement équilibrés :

arbre_no1 : sad().hauteur() : 4, sag().hauteur(): 0, abs(différence) : 4. l'arbre arbre_no1 n'est pas partiellement équilibré.

arbre_no2 : sad().hauteur() : 2, sag().hauteur(): 2, abs(différence) : 0. l'arbre arbre_no2 est partiellement équilibré.

arbre_no3 : sad().hauteur() : 1, sag().hauteur(): 1, abs(différence) : 0. l'arbre arbre_no3 est partiellement équilibré.

11.

Les sous-arbre de gauche, comme celui de doite de l'arbre arbre_no2 ne sont pas eux mêmes partiellement équilibrés. Donc l'arbre arbre_no2 n'est pas équilibré.

Text Only

L'arbre arbre_no3 est équilibré.

12.

Voici le code:

Python

def est_equilibre(self):
    if self.est_vide() :
        return True
    cond1 = abs(self.sag().hauteur() - self.sad().hauteur() ) <= 1 # Différence entre les sous-arbre
    cond2 = self.sag().est_equilibre() # sous-arbre gauche est équilibré
    cond2 = self.sad().est_equilibre() # sous-arbre droit est équilibré
    les 3 conditions doivent être vérifiées
    return cond1 and cond2 and  cond3

Exercice 3 SQL

1.

a. La clé primaire de la relation matchs est id_match b. La relation matchs possède plusieurs clés étrangères : id_creneau pointe vers la clé primaire de creneaux, id_terrain pointe ers la clé primaire de terrains, id_joueur1 et id_joueur2 qui pointent vers la clé primaire de `joueurs

2.

a. Déterminer le jour et la plage horaire du match entre Durand Belina et Caron Camilia

Dans la relation matchs, le match 2 oppose les joueuses avec les id_joueurs 2 et 3, il a lieu le 1er août 2020 sur le créneau 3, c'est a dire de 10h à 11h.

b. Déterminer le nom des deux joueurs qui sont les seuls à avoir joué dans le hangar

Pour identifier les joueurs ayant joué uniquement sur le terrain "hangar", nous cherchons le match avec id_terrain 3, c'est le match 5. Donc Dupont Alice et Durand Belina.

3.

a. Ecrire une requête qui renvoie les prénoms des joueurs dont le nom est ‘Dupont’

SQL

SELECT prenom_joueur
FROM joueurs
WHERE nom_joueur = 'Dupont';

b. Ecrire une requête qui modifie le mot de passe de Dorine Dupont, son nouveau mot de passe étant 1976

SQL

UPDATE joueurs
SET mdp = '1976'
WHERE nom_joueur = 'Dupont' AND prenom_joueur = 'Dorine';

4.

Ajouter un nouveau membre

Pour ajouter un nouveau membre « Zora MAGID » avec le login « zora » et le mot de passe 2021, et dans le cas où la clé primaire est auto-incrémentée :

SQL

INSERT INTO joueurs (nom_joueur, prenom_joueur, login, mdp)
VALUES ('Magid', 'Zora', 'zora', '2021');

5.

Pour obtenir les jours où Alice Dupont joue :

SQL

SELECT DISTINCT matchs.date
FROM matchs AS m
JOIN joueurs AS j
ON j.id_joueur = m.id_joueur1 OR j.id_joueur =  m.id_joueur2
WHERE j.nom_joueur = 'Dupont' AND j.prenom_joueur = 'Alice';

Exercice 3 Non SQL

1 a.

A partir de la liste jours, comment obtenir l’élément "lundi" ? Pour obtenir l'élément "lundi" dans la liste jours, on utilise l'indice 1 :

Python

jours[1]

1 b.

Que renvoie l’instruction jours[18%7] ? L'instruction 18 % 7 renvoie 4 (le reste de la division de 18 par 7). Ainsi, jours[18%7] renvoie l'élément à l'indice 4 dans la liste jours, soit "jeudi".

2.

Compléter l’instruction permettant d’obtenir le numéro du jour de la semaine n jours plus tard

L'instruction complète est :

Python

numero_jour = (jours.index(j) + n) % 7

3.

a. A partir du dictionnaire mois, comment obtenir le nombre de jours du mois de mars ?

Pour obtenir le nombre de jours du mois de mars, on utilise la clé 3 et accède au deuxième élément du tuple :

Python

mois[3][1]

b. Obtenir le nom du mois qu’il sera x mois plus tard

Pour obtenir le nom du mois qu’il sera x mois plus tard :

Python

nom_mois = mois[(numero_mois + x - 1) % 12 + 1][0]

Explications :

• (numero_mois + x - 1) ajuste pour les indices 1 à 12.
• % 12 permet de boucler sur l'année.
• + 1 recentre sur la plage 1 à 12.
• [0] récupère le nom du mois.

Exemple :

Python

numero_mois = 4
x = 5
nom_mois = mois[(numero_mois + x - 1) % 12 + 1][0]  # Renvoie "septembre"

4.

a. Que renvoie mois[date[2]][1] si date = ("samedi", 21, 10, 1995) ?

L'instruction mois[date[2]][1] accède au nombre de jours du mois d'octobre (clé 10) dans le dictionnaire mois. Elle renvoie : 31

b. Fonction jour_suivant(date)

Voici le code de la fonction jour_suivant :

Python

def jour_suivant(date):
    '''
    Rappels des variables globales
    jours = ["dimanche", "lundi", "mardi", "mercredi", "jeudi", "vendredi", "samedi"]
    mois = {
        1: ("janvier", 31), 2: ("février", 28), 3: ("mars", 31), 4: ("avril", 30),
        5: ("mai", 31), 6: ("juin", 30), 7: ("juillet", 31), 8: ("aout", 31),
        9: ("septembre", 30), 10: ("octobre", 31), 11: ("novembre", 30), 12: ("décembre", 31)
    }
    ''''

    nom_jour, numero_jour, numero_mois, annee = date # dépaquetage de la date

    # Calcul du jour suivant
    index_jour = (jours.index(nom_jour) + 1) % 7
    nouveau_nom_jour = jours[index_jour]

    # Vérifier si on passe au mois suivant
    if numero_jour < mois[numero_mois][1]:
        nouveau_numero_jour = numero_jour + 1
        nouveau_numero_mois = numero_mois
        nouvelle_annee = annee
    else:
        nouveau_numero_jour = 1
        if numero_mois == 12:  # Si on passe à l'année suivante
            nouveau_numero_mois = 1
            nouvelle_annee = annee + 1
        else:
            nouveau_numero_mois = numero_mois + 1
            nouvelle_annee = annee

    return (nouveau_nom_jour, nouveau_numero_jour, nouveau_numero_mois, nouvelle_annee)

Exemples d'utilisation :

Python

print(jour_suivant(("samedi", 21, 10, 1995)))  # Renvoie ("dimanche", 22, 10, 1995)
print(jour_suivant(("mardi", 31, 10, 1995)))   # Renvoie ("mercredi", 1, 11, 1995)