Exercice 1 SQL et chiffrement⚓︎

Partie A⚓︎

1. Nom_artiste comme clé primaire⚓︎

Non, il n’aurait pas été possible de choisir l'attribut Nom_artiste comme clé primaire dans la relation CD.

Une clé primaire doit être unique pour chaque n-uplet de la relation.

Or, dans la relation CD, l'attribut Nom_artiste n'est pas unique, car un artiste peut enregistrer plusieurs albums.

2. Réponses pour les artistes⚓︎

Artistes
Nightwish
The Rasmus

3. Réponses pour les années⚓︎

Année
1986
2001
1986

4. requête de mise à jour⚓︎

SQL
UPDATE CD
SET Annee = 2000
WHERE Titre_album = 'Wishmaster'

5. les albums de “Metal” rangés sur l’étagère 1⚓︎

SQL
SELECT Titre_album
FROM CD
JOIN Rangement ON CD.id_album = Rangement.id_album
JOIN Artiste ON CD.Nom_artiste = Artiste.Nom_artiste
WHERE Style = 'Metal' AND Numero_etagere = 1

6. Intégrité réferentielle⚓︎

Il est nécessaire de suivre l'ordre suivant pour garantir le respect des contraintes d'intégrité référentielles :

Supprimer les références dans la table Rangement :
Supprimer l'album dans la table CD :
Supprimer l'artiste dans la table Artiste

SQL
DELETE FROM CD
WHERE Titre_album = 'Dead Letters'

partie B⚓︎

7. Chiffrement symétrique⚓︎

Un algorithme de chiffrement symétrique utilise une clé partagée pour chiffrer et déchiffrer un message. Par exemple, Alice et Bob partagent une clé K. Alice chiffre un message M pour obtenir M'. Même si M' est intercepté, il reste illisible sans la clé K. Bob utilise la même clé K pour déchiffrer M' et retrouver le message original M.

8. Chiffrement asymétrique⚓︎

Un algorithme de chiffrement asymétrique utilise deux clés distinctes : une clé publique et une clé privée. La clé publique sert à chiffrer un message, et seule la clé privée correspondante peut déchiffrer ce message. Par exemple, Alice utilise la clé publique de Bob pour chiffrer un message, et Bob utilise sa clé privée pour le déchiffrer. La clé privée ne doit jamais être partagée.

9. Création d'une clé de session⚓︎

Pour envoyer la clé C de manière sécurisée au serveur, le serveur peut utiliser le chiffrement asymétrique. Le serveur chiffre la clé C avec la clé publique de Bob. Ainsi, seule la clé privée de Bob pourra déchiffrer la clé C. Même si le message est intercepté, il restera illisible sans la clé privée de Bob.

Une fois cette clé échangée la poursuite des échanges se chiffrée à l'aide d'un chiffrement symétrique avec la même clé C.

Exercice 2⚓︎

1.⚓︎

Python
class Marchandise:

    def __init__(self, p: int, v: int) -> 'Marchandise':
        assert v > 0
        self.prix = p
        self.volume = v

2.⚓︎

Python
m1 = Marchandise(20, 7)

3.⚓︎

Python
def ratio(self) -> float:
    return self.prix / self.volume

4.⚓︎

Python
def prixListe(tab: [int]) -> int
    total = 0
    for m in tab:
        total = total + m.prix
    return total

Partie B – Première approche de rangement⚓︎

5.⚓︎

Voici les combinaisons possibles et leurs prix associés :

Combinaison	Volume total	Prix total
𝑚1	20	40
𝑚2	70	210
𝑚3	40	160
𝑚4	50	50
𝑚1 + 𝑚2	90	250
𝑚1 + 𝑚3	60	200
𝑚1 + 𝑚4	70	90
𝑚3 + 𝑚4	90	210

Toutes les combinaisons à 3 et 4 marchandises dépassent le volume de 100l et donc ne sont pas possibles.

La combinaison qui maximise le prix total est donc m1 + m2

6.⚓︎

Le qualificatif qui s'applique le mieux à l'algorithme ChargementGlouton est glouton.

Justification, non demandée :

Cela vient du fait que l'algorithme choisit à chaque étape la marchandise avec le plus grand prix volumique, sans tenir compte de l'impact global de cette décision. Il suit une stratégie de "choix local optimal", typique des algorithmes gloutons.

7.⚓︎

Python
def tri(tab: [Marchandise]) -> None:
    n = len(tab)
    for i in range(1, n):
        marchandise = tab[i]
        j = i - 1
        while j >= 0 and marchandise.ratio() > tab[j].ratio() :
            tab[j + 1] = tab[j]
            j = j - 1
        tab[j + 1] = marchandise

8.⚓︎

Le nom du tri est tri par insertion.

La complexité temporelle dans le pire des cas est quadratique (O(n²)).

9.⚓︎

Python
def charge(tab:  [Marchandise], volume: int) -> list:
    tri(tab)  # Trie les marchandises par prix volumique décroissant
    chargement = []
    v_restant = volume  # Volume restant à remplir
    n = len(tab)

    for i in range(n):
        if tab[i].volume <= v_restant:  # Teste si la marchandise peut être chargée
            chargement.append(tab[i])  # ajout de la marchandise au chargement
            v_restant -= tab[i].volume  # Décrélentation du volume restant

    return chargement  # Retourne la liste des marchandises chargées

Partie C – Rangement optimisé par récursivité⚓︎

Python
def chargeOptimale(tab:  [Marchandise], v_restant: int, i: int) -> list:
    if i >= len(tab):  # Fin de liste, condtion d'arrêt
        return [] # liste vide qui sera complétée lors du dépilement des appels récursifs
    else:
        if tab[i].volume > v_restant:  # Si la marchandise i est trop volumineuse
            return chargeOptimale(tab, v_restant, i + 1)
        else:
            # Option 1: On prend  la marchandise i
            option1 = chargeOptimale(tab, v_restant - tab[i].volume, i + 1)

            # Option 2: On ne prend pas la marchandise i
            option2 = [tab[i]] + chargeOptimale(tab, v_restant, i + 1) # v_restant n'est donc pas modifié

            # On retourne l'option qui maximise le prix total
            if prixListe(option1) > prixListe(option2):
                return option1
            else:
                return option2

Exercice 3⚓︎

1.⚓︎

Voici la liste des attributs de la classe Piste avec leurs types précisés :

nom : str (chaîne de caractères)
denivele : int (entier)
longueur : float (nombre réel)
couleur : str (chaîne de caractères)
ouverte : bool (booléen)

2.⚓︎

Python
def set_couleur(self):
    if self.denivele >= 100:
        self.couleur = 'noire'
    elif self.denivele >= 70:
        self.couleur = 'rouge'
    elif self.denivele >= 40:
        self.couleur = 'bleue'
    else:
        self.couleur = 'verte'

3.⚓︎

Proposition D : une liste d'objets de type Piste.

L'attribut self.pistes est une liste qui contient des objets de type Piste (puisque dans la méthode ajouter_piste, des instances de la classe Piste sont ajoutées à cet attribut). Par conséquent, la méthode get_pistes() renvoie cette liste d'objets de type Piste.

4.⚓︎

Python
for piste in lievre_blanc.get_pistes():
    if piste.couleur == 'verte':
        piste.ouverte = False  

5.⚓︎

Python
def pistes_de_couleur(liste, couleur):
    resultat = []

    for piste in liste:
        if piste.couleur == couleur:  # Si la couleur de la piste correspond à celle demandée
            resultat.append(piste.get_nom())  

    return resultat

ou en liste par compréhension

Python
def pistes_de_couleur(lst, couleur):
    return [ piste.get_nom() for piste in liste if piste.couleur == couleur]

6.⚓︎

Python
def semi_marathon(L):
    distance = 0
    liste_pistes = lievre_blanc.get_pistes()
    for nom in L:
        for piste in liste_pistes:
            if piste.get_nom() == nom: # La poiste de l'entraînement correspond à celle de la boucle parmi les pistes du domaine
               distance = distance + piste.get_longueur()
    return distance > 21.1

7.⚓︎

domaine['E']['F']

8.⚓︎

Python
def voisins(G, s):
    return list(G[s].keys())

Une autre solution avec un boucle for est aussi acceptée

9.⚓︎

Python
def longueur_chemin(G, chemin):
    precedent = chemin[0] 
    longueur = 0
    for i in range(1, len(chemin)):  
        longueur = longueur + G[precedent][chemin[i]]
        precedent = chemin[i]  
    return longueur

10.⚓︎

La fonction parcours est récursive car elle s'appelle elle-même. Elle possède aussi une condition d'arrêt

11.⚓︎

Python
def parcours_dep_arr(G, depart, arrivee):
    liste = parcours(G, depart)
    res = []
    for l in liste :
        n = len(l)
        if l[n-1] == arrivee and l not in res: # l not in res permet de ne pas avoir de doublon
            res.append(l)
    return res

12.⚓︎

Python
def plus_court(G, depart, arrivee):
    liste_chemins = parcours_dep_arr(G, depart, arrivee)
    chemin_plus_court = liste_chemins[0]
    minimum = longueur_chemin(G, chemin_plus_court)
    for chemin in liste_chemins:
        longueur = longueur_chemin(G, chemin)
        if longueur < minimum :
            minimum = longeur
            chemin_plus_court = chemin
    return chemin_plus_court

13.⚓︎

En montagne, le chemin le plus court n'est pas forcément le plus rapide, la dénivelée ou un passage difficile peuvent par exemple compliquer l'accès.

Le choix du plus court chemin est donc discutable.