Sujet 1

Exercice 1

On représente un petit réseau de stations de métro par un dictionnaire d'adjacence :

metro = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D', 'E'], 'D': ['B', 'C', 'F'], 'E': ['C', 'F'], 'F': ['D', 'E']}

1. Quels sont les sommets voisins de la station 'C' ? 2. Représenter ce graphe sous forme d'un schéma (sommets et arêtes) et indiquer s'il est orienté ou non. 3. Ecrrie la fonction voisins(graphe, sommet) qui renvoie la liste des sommets voisins d'un sommet donné. 4. Proposer un parcours en profondeur du graphe à partir de la station 'A', en indiquant l'ordre de visite des sommets. 5. Compléter la fonction parcours_largeur(graphe, depart) ci-dessous, qui renvoie la liste des sommets visités dans l'ordre d'un parcours en largeur (BFS), en utilisant une file (une liste avec pop(0), ou collections.deque).

def parcours_largeur(graphe, depart):
    visites = []
    file = [depart]
    while file:
        sommet = file.pop(0)
        if sommet not in visites:
            visites.append(sommet)
            for voisin in graphe[sommet]:
                ...  # à compléter
    return visites

Exercice 2

On dispose des trois tables suivantes :

ADHERENT(id_adherent, nom, prenom, date_naissance) SEANCE(id_seance, activite, jour, horaire) INSCRIPTION(id_adherent, id_seance, date_inscription)

Les attributs en gras sont les clés primaires des tables.

1. Qu'est-ce qu'une clé primaire ?
2. Qu'est-ce qu'une clé étrangère ?
3. Que renvoie la requête SQL suivante ?

   SELECT nom, prenom
   FROM ADHERENT
   WHERE date_naissance < '2000-01-01';
   

4. Écrire la requête affichant les activités (sans doublon) proposées le lundi.
5. Écrire la requête affichant, pour chaque séance, l'activité et le nombre d'inscrits.