Aller au contenu

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
1
2
>>> parcours(G,'Av')
['Av', 'Ax', 'Mr', 'Ni', 'Ar', 'Di', 'Nc', 'To', 'Mp']
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
1
2
>>> distance(G,'Av')
{'Av': 0, 'Ax': 1, 'Mr': 1, 'Ni': 1, 'Ar': 2, 'Di': 2, 'Nc': 2, 'To': 2, 'Mp': 2}

10.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
1
2
>>> 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
1
2
3
4
5
6
7
8
9
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
1
2
3
4
5
6
7
8
9
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
1
L'arbre arbre_no3 est équilibré.

12.

Voici le code:

Python
1
2
3
4
5
6
7
8
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
1
2
3
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
1
2
3
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
1
2
INSERT INTO joueurs (nom_joueur, prenom_joueur, login, mdp)
VALUES ('Magid', 'Zora', 'zora', '2021');

5.

Pour obtenir les jours oĂč Alice Dupont joue :

SQL
1
2
3
4
5
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
1
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
1
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
1
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
1
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
1
2
3
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
1
2
print(jour_suivant(("samedi", 21, 10, 1995)))  # Renvoie ("dimanche", 22, 10, 1995)
print(jour_suivant(("mardi", 31, 10, 1995)))   # Renvoie ("mercredi", 1, 11, 1995)