Question 1b – Le résultat de la requête est :
Question 2 – La requête est la suivante :
Question 3a – L’attribut salle ne peut pas être une clé primaire pour la relation Ordinateur, car il existe au moins trois enregistrements dans la table Ordinateur pour lesquels la valeur de l’attribut salle est la même. Or une clé primaire est définie par un attribut pour lequel la valeur de chacun des enregistrements de la table est unique.
Question 3b – Le schéma relationnel de la table Imprimante est le suivant :
Imprimante (nom_imprimante : String, marque_imp : String, modele_imp : String, salle : String, nom_ordi : String)
Clé primaire (PK) | Clé étrangère (FK)
Question 4a – La requête SQL est la suivante :
INSERT INTO Videoprojecteur VALUES ("315", "NEC", "ME402X", false)
Question 4b – La requête SQL est la suivante :
SELECT Ordinateur.salle, Ordinateur.nom_ordi, Videoprojecteur.marque_video FROM Ordinateur INNER JOIN Videoprojecteur ON Ordinateur.salle = Videoprojecteur.salle WHERE tni = true ;
SELECT Ordinateur.salle, Ordinateur.nom_ordi, Videoprojecteur.marque_video FROM Ordinateur NATURAL JOIN Videoprojecteur WHERE tni = true ;
Algorithmes sur les graphes. |
||
---|---|---|
Contenus | Capacités attendues | Commentaires |
Source | ||
Algorithmes sur les graphes. |
|
Nouveau réseau social : « Troncho’scope »
Ce nouveau réseau social ne compte aujourd’hui que neuf inscrits : Aude, Brice, Carla, Damien, Eric, Fiona, Gina, Hugo et Inès.
L’examen de leurs profils montre que :
- Aude est amie avec Damien, Eric et Brice ;
- Brice est ami avec Aude, Carla et Fiona ;
- Carla est amie avec Brice ;
- Damien est ami avec Aude et Eric ;
- Eric est ami avec Aude, Damien, Gina et Hugo ;
- Fiona est amie avec Inès, Hugo et Brice ;
- Gina est amie avec Eric ;
- Hugo est ami avec Eric et Fiona ;
- Inès est amie avec Fiona.
Décrit de cette manière et à ce stade, il apparaît difficile de se faire une représentation claire des liens qui existent entre toutes les personnes inscrites. Alors qu’en sera-t-il dans un an sachant que tous les jours ce nouveau réseau social enregistre de nouveaux inscrits !
Afin de mieux se rendre compte des liens d’amitiés entre les membres de se réseau, on se propose d’en construire une représentation graphique, plus « visuelle », en appliquant le principe suivant :
- chaque personne sera figurée par un cercle à l’intérieur duquel sera écrit son prénom ;
- le lien « est ami.e avec… » sera figurée par un « trait » reliant les cercles des personnes concernées.
Construire une représentation graphique du réseau social « Troncho’scope »
Ce type de représentation est appelé un « Graphe ».
Il existe d’autres situations qui peuvent être représentées par un graphe :
- réseau de transports en commun d’une ville ;
- réseau routier entre les villes ;
- réseau informatique
Ce qu’il faut retenir (CQFR)…
Qu’il s’agisse d’un réseau social, d’un réseau routier ou encore d’un réseau informatique, il est possible de représenter ces situations sous la forme de graphes.
Un graphe est une structure relationnelle de données.
Un graphe est constitué de sommets et d’arêtes (ou arcs).
Une arête relie deux sommets adjacents.
Le degré d’un sommet est le nombre d’arêtes liés à ce sommet.
L’ordre d’un graphe est le nombre de sommets.
Une chaîne ou un chemin est une suite ordonnée de sommets consécutivement adjacents.
La distance entre deux sommets d’un graphe est le plus petit nombre d’arêtes d’une chaîne allant de l’un à l’autre.
L’excentricité d’un sommet est la distance maximale existant entre ce sommet et les autres sommets du graphe.
Le centre d’un graphe est un sommet d’excentricité minimale. Un graphe peut posséder plusieurs centres.
Le rayon d’un graphe correspond à l’excentricité d’un centre du graphe.
Le diamètre d’un graphe correspond à la plus grande distance entre deux sommets du graphe.
S’il existe un sens de parcours des arêtes, alors le graphe est dit orienté.
Le graphe est complet si chacun de ses sommets est relié à tous les autres.
Description d’un graphe
Un graphe peut être décrit par une matrice d’adjacence.
- Cette matrice comporte autant de lignes et de colonnes que le graphe comporte de sommets.
- La valeur notée à l’intersection d’une ligne et d’une colonne sera égale à zéro si les deux sommets ne sont pas adjacents.
- Elle sera égale à 1 si les deux sommets sont adjacents.
A | B | C | D | |
A | 0 | 1 | 1 | 1 |
B | 1 | 0 | 1 | 0 |
C | 1 | 1 | 0 | 0 |
D | 1 | 0 | 0 | 0 |
A | B | C | D | |
A | 0 | 1 | 0 | 1 |
B | 0 | 0 | 1 | 0 |
C | 1 | 0 | 0 | 0 |
D | 1 | 0 | 0 | 0 |
Un graphe peut être aussi décrit par des listes de successeurs, et des listes de prédécesseurs s’il est orienté.
Ainsi pour le graphe n°1 non orienté présenté plus haut, on aura les listes de successeurs suivantes :
- A : B, C, D
- B : A, C
- C : B, A
- D : A
Et pour le graphe n°2 orienté présenté plus haut, on aura :
- Listes de successeurs
- A : B, D
- B : C
- C : A
- D : A
- Listes de prédécesseurs
- A : C, D
- B : A
- C : B
- D : A
« Troncho’scope » : la suite…
Question 1 – Quel est l’ordre de ce graphe ?
Question 2 – Quel est le degré du sommet ‘Eric’ ?
Question 3 – Donner une chaîne dans laquelle figurent Aude et Inès.
Question 4 – Donner un cycle dans lequel figurent Eric et Fiona.
Question 5 – Écrire la matrice d’adjacence du graphe.
Question 6 – Écrire les listes de successeurs du graphe.
Question 7 – Cinq nouveaux membres ont rejoint le réseau social : Jean, Kurt, Léa, Marion et Noémie. Par ailleurs des relations précédentes se sont dénouées et de nouvelles se sont nouées entre les premiers membres. La matrice d’adjacence du graphe représentant le réseau social est la suivante :
A | B | C | D | E | F | G | H | I | J | K | L | M | N | |
A | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
B | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
C | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
D | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
E | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
G | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
H | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
I | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
J | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
K | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
L | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
M | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
N | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Seule la première lettre du prénom a été indiquée en tête de lignes et de colonnes
A partir de cette matrice, actualiser la précédente représentation graphique du réseau social.