Sujet Bac Blanc Lycée Français International André Malraux 23-24
Quand un code est à compléter (code à trous), la ligne (et uniquement la ligne) est à recopier sur votre copie.
Le sujet ne doit pas être rendu
L'usage de la calculatrice n'est pas autorisé.
Durée : 3h30
Exercice 1
On considère dans ce sujet la base de données netflix contenant des informations sur les programmes de la plateforme. Cette base contient plusieurs relations/tables :
countries : contient des informations décrivant des pays :
id : l'identifiant du pays (entier, clé primaire)
country : le nom du pays (texte)
directors : contient des informations décrivant les réalisateurs des programmes :
id : l'identifiant du réalisateur (entier, clé primaire)
director : le nom du ou des réalisateurs (texte)
genres : décrit les genres des programmes :
id : l'identifiant du genre (entier, clé primaire)
genre : le nom du genre (texte)
programs : décrit les programmes :
show_id : l'identifiant du programme (texte, clé primaire)
type : l'identifiant du type de programme (entier, clé étrangère pointant vers types.id)
title : le nom du programme (texte)
director : l'identifiant du ou des réalisateurs (entier, clé étrangère pointant vers directors.id)
country : l'identifiant du pays du programme (entier, clé étrangère pointant vers countries.id)
date_added : la date d'ajout sur la plateforme (texte)
release_year : la date de réalisation du programme (entier)
rating : l'identifiant de la classification du programme (entier, clé étrangère pointant vers ratings.id)
duration : la durée du programme en saison ou minutes (texte)
ratings : décrit les classifications des programmes :
id : l'identifiant de la classification (entier, clé primaire)
rating : le nom de la classification (texte)
show_genres : décrit les genres associés à chaque programme :
show_id : l'identifiant du programme (texte, clé étrangère pointant vers programs.show_id)
genre : l'identifiant du genre (entier, clé étrangère pointant vers genres.id)
La clé primaire de cette table est le couple (show_id, genre).
types : décrit les types de programmes :
id : l'identifiant du type (entier, clé primaire)
type : le nom du type (texte)
Question 1
Donner le schéma relationnel de cette base de données.
Corrigé
countries(id,country)
directors(id, director)
genres(id,genre)
programs(show_id, #type, title, #director, #country, date_added, release_year, #rating, duration)
ratings(id, rating)
show_genres( #show_id,#genre)
types(id,type)
Question 2
Écrire les requêtes SQL qui permettent :
a. Afficher le nom des programmes ainsi que leur date d'ajout sur la plateforme.
Corrigé
SELECT title, date_added
FROM programs;
b. Afficher le nom et la date de réalisation des programmes réalisés après 2020 (inclus):
Corrigé
SELECT title, release_year
FROM programs
WHERE release_year>=2020;
c. Quel est l'identifiant du réalisateur nommé Michael Bay ?
Corrigé
SELECT directors.id
FROM directors
WHERE director="Michael Bay";
d. La série The Witcher comporte désormais 2 saisons alors que la base n'en indique qu'une seule. Corriger cette erreur.
Corrigé
UPDATE programs
SET duration = '2 seasons'
WHERE title = 'The Witcher';
e. Insérer la série télévisée The Sandman, ajoutée en 2022, de réalisateurs multiples (utiliser l'identifiant correspondant à Not Given), et de classification TV-MA. Les autres champs seront laissés vierges.
Corrigé
INSERT INTO programs (title, release_year, director, rating)
VALUES ('The Sandman', 2022, (SELECT id FROM directors WHERE director = 'Not Given'), (SELECT id FROM ratings WHERE rating = 'TV-MA'));
f. Quels sont les noms des programmes réalisés en France ?
Corrigé
SELECT title
FROM programs
JOIN countries ON countries.id = programs.country
WHERE countries.country = 'France';
g. Combien de programmes ont été réalisés en 2020 en Inde (India dans la base) ?
Corrigé
SELECT COUNT(*)
FROM programs
JOIN countries ON countries.id = programs.country
WHERE countries.country = 'India' AND release_year = 2020;
h. Afficher les noms et la date de réalisation des séries télévisées réalisées en Uruguay dans l'ordre décroissant de leur date de réalisation.
Corrigé
SELECT title, release_year
FROM programs
JOIN countries ON countries.id = programs.country
WHERE countries.country = 'Uruguay'
ORDER BY release_year DESC;
i. À quel genre (au format texte) est associée la série Downton Abbey ?
Corrigé
SELECT genres.genre
FROM show_genres
JOIN programs ON programs.show_id = show_genres.show_id
JOIN genres ON genres.id = show_genres.genre
WHERE programs.title = 'Downton Abbey';
Exercice 2
Vous pouvez voir ci-dessus une carte de France représentant les 12 régions métropolitaines (sans la Corse pour des raisons de simplification du problème).
On se demande s'il est possible de colorier la carte en respectant les contraintes suivantes :
- utiliser un minimum de couleurs ;
- faire en sorte que deux régions limitrophes (ayant une frontière commune) soient coloriées de deux couleurs différentes.
La carte ci-dessus, on utilise 12 couleurs, une par région ; on peut faire mieux. Il y a des solutions optimales à 4 couleurs, d'autres qui s'en approchent. Nous allons voir plusieurs algorithmes.
Pour tenter de résoudre ce problème, nous n'allons pas travailler directement sur la carte, mais sur un graphe associé à celle-ci.
Chaque région sera un sommet du graphe et, si deux régions sont limitrophes, il existera alors une arête entre ces deux sommets. Pour nommer les sommets nous utiliserons les codes suivants :
| Étiquette | Identifiant | Région |
|---|---|---|
| 0 | BRE | Bretagne |
| 1 | PLO | Pays de Loire |
| 2 | NAQ | Nouvelle Aquitaine |
| 3 | OCC | Occitanie |
| 4 | PAC | Provence-Alpes-Côte d'Azur |
| 5 | ARA | Auvergne-Rhône-Alpes |
| 6 | BFC | Bourgogne Franche-Comté |
| 7 | CVL | Centre-Val de Loire |
| 8 | IDF | Île de France |
| 9 | GES | Grand-Est |
| 10 | HDF | Hauts-de-France |
| 11 | NOR | Normandie |
Partie I : Implémentation du graphe
1. Représentez sur votre copie le graphe correspondant à la carte "Régions de France" en utilisant les identifiants pour les sommets.
Corrigé
2. Une des possibilités pour représenter un graphe \(G\) en machine est d'utiliser ce qu'on appelle une matrice d'adjacence. Dans ce type de représentation, les sommets sont ordonnés et considérés comme étiquetés par des entiers de \(0\) à \(n - 1\), où \(n\) est l'ordre du graphe.
2.a. Quel est l'ordre du graphe « Régions de France » ?
Corrigé
Il y a douze régions. L'ordre de ce graphe est donc 12.
2.b. On considère un graphe dont la matrice d'adjacence est modélisée en Python par la liste de listes donnée ci-dessous :
M = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]]
Dessiner ce graphe sur votre copie. Les sommets sont étiquetés dans cet ordre par \(0\), \(1\), \(2\), \(3\).
Corrigé
2.c. Écrire en python une fonction voisins telle que voisins(M, k) renvoie une liste contenant les voisins du sommet k dans le graphe \(G\) modélisé par la matrice d'adjacence M. Par exemple avec la matrice définie ci-dessus, on a :
>>> voisins(M, 2)
[1, 3]
Corrigé
def voisins(M, k):
voisins_k = []
for i in range(len(M)):
if M[k][i] == 1:
voisins_k.append(i)
return voisins_k
2.d. Combien d'éléments (0 ou 1) y a-t-il dans la matrice d'adjacence d'un graphe qui comporte \(1~000\) sommets ?
Corrigé
\(1~000^2\) soit \(1~000~000\)
3. On peut également modéliser, en Python, un graphe grâce à un dictionnaire contenant pour chaque clé (un sommet) la valeur associée : une liste de ses voisins, sans se soucier de l'ordre.
3.a. En considérant le graphe représenté ci-dessous, donner un dictionnaire G Python modélisant ce graphe avec un dictionnaire de listes de voisins.
On pourra écrire, par exemple, que les voisins de 'A' sont 'C' et 'D'.
Corrigé
G = {
"A": ["C", "D"],
"B": ["D", "E"],
"C": ["A", "D", "E"],
"D": ["A", "B", "C"],
"E": ["B", "C", "F"],
"F": ["E"],
}
3.b. Écrire en python une fonction voisins telle que voisins(G, k) renvoie une liste contenant les voisins du sommet k dans le graphe qui est modélisé par le dictionnaire G de listes de voisins. On aura, avec l'exemple précédent, et sans tenir compte de l'ordre :
>>> voisins(G, 'C')
['A', 'D', 'E']
Corrigé
def voisins(G,k):
return G[k]
3.c. Combien d'éléments y a-t-il dans ce dictionnaire si le graphe comporte \(1~000\) sommets ?
Corrigé
Il y a \(1~000\) couples clé-valeur.
Chaque valeur est une liste contenant de 0 à 999 valeurs. ```
Partie II : Coloration séquentielle ; un premier algorithme
Une première approche pour colorer le graphe est de prendre ses sommets les uns après les autres afin de leur affecter une couleur, tout en veillant à ce que deux sommets adjacents n'aient jamais la même couleur : c'est l'algorithme de coloration séquentielle. Nous modéliserons le graphe avec un dictionnaire Python en listes de voisins. On propose le code ci-dessous qui utilise la fonction voisins programmée à la question précédente :
1 def coloration(G) :
2 # Renvoie une coloration du graphe G
3 # version séquentielle, limitée à 6 couleurs
4
5 couleur = ['Rouge', 'Bleu', 'Vert', 'Jaune', 'Noir', 'Blanc']
6 coloration_sommets = {s_i: None for s_i in G}
7 for s_i in G:
8 couleurs_voisins_s_i = [coloration_sommets[s_j] for s_j in voisins(G, s_i)]
9 k = 0
10 while couleur[k] in couleurs_voisins_s_i:
11 k = k + 1
12 coloration_sommets[s_i] = couleur[k]
13 return coloration_sommets
1. À Quelle famille d'algorithme appartient le Code coloration ci-dessus ?
Corrigé
Il s'agit d'un algorithme glouton, il choisit la première couleur disponible et ne remet pas en cause son choix ensuite, même s'il n'est pas optimal.
2. Donner les couleurs que va attribuer ce code à chaque sommet si l'on considère le Graphe 1 ci-dessus. On considère que la boucle principale va envisager les sommets dans l'ordre lexicographique : tout d'abord A, puis B, puis C ...
Corrigé
- A, le choix est rapide : Rouge ;
- B, le choix est également rapide : Rouge ;
- C, le Rouge est indisponible, le choix est Bleu ;
- D, Rouge et Bleu sont indisponibles, le choix suivant est Vert ;
- E, Rouge et Bleu sont indisponibles, le choix suivant est Vert ;
- F, Vert est indisponible, le premier choix Rouge est validé.
3. On modélise maintenant un nouveau graphe avec le dictionnaire G_2 ci-dessous, et on appelle la fonction coloration avec ce graphe en paramètre. Représentez ce graphe sur votre copie et montrez qu'il existe une solution avec moins de couleurs.
>>> G_2 = {"A": ["C"], "B": ["D"], "C": ["A", "D"], "D": ["B", "C"]}
>>> coloration(G_2)
{'A': 'Rouge', 'B': 'Rouge', 'C': 'Bleu', 'D': 'Vert'}
Corrigé
Il y avait une coloration du graphe en deux couleurs seulement:
{'A': 'Rouge', 'B': 'Bleu', 'C': 'Bleu', 'D': 'Rouge'}
Partie III : L'algorithme de Welsh et Powell
Il s'agit maintenant d'utiliser l'algorithme de coloration séquentiel avec un ordre judicieux, en vue d'obtenir une coloration valide la plus « acceptable » possible. L'algorithme de Welsh et Powell consiste ainsi à colorer séquentiellement le graphe en visitant les sommets par ordre de degré décroissant. L'idée est que les sommets ayant beaucoup de voisins sont plus difficiles à colorer : il faut les colorier en premier.
Le degré d'un sommet est le nombre d'arêtes issues de ce sommet, c'est-à-dire son nombre de voisins.
1. On souhaite implémenter en Python une fonction tri_sommets telle que tri_sommets(G) renvoie la liste des étiquettes des sommets du graphe G passé en paramètre triés par degrés décroissants.
Recopiez les lignes incomplètes de code en les complétant.
def tri_sommets(G) :
"""Renvoie la liste des sommets, triée par degré décroissant"""
sommets = [sommet for sommet in G]
for i in range(...):
i_sommet_max = i
degre_sommet_max = len(G[sommets[i]])
for j in range(..., len(sommets)):
if len(G[sommets[j]]) > degre_sommet_max:
i_sommet_max = ...
degre_sommet_max = ...
tmp = sommets[i]
sommets[i] = sommets[i_sommet_max]
sommets[i_sommet_max] = ...
return sommets
Corrigé
for i in range(len(sommets)):
for j in range(i + 1, len(sommets)):
i_sommet_max = j
degre_sommet_max = len(G[sommets[j]])
sommets[i_sommet_max] = tmp
2. Quel type de tri est implémenté dans la fonction tri_sommets ci-dessus ?
Corrigé
Il s'agit d'un tri par sélection : on cherche le plus grand élément dans le tableau qui reste à trier et on le sélectionne pour être échangé au début de la section à trier, on poursuit avec le reste du tableau.
3. Citer un exemple de tri plus efficace en temps que celui-ci.
Corrigé
Parmi les tris efficaces dans le pire des cas, il y a le tri fusion.
4. Quelle sera la liste renvoyée par l'appel de fonction tri_sommets(R) où on passe en paramètre le dictionnaire R : pour chaque région, la liste des régions voisines, réalisé à la question 1 de la partie I (cf. code ci-dessous) ?
R = {}
R["BRE"] = ["PLO", "NOR"]
R["PLO"] = ["BRE", "NAQ", "CVL", "NOR"]
R["NAQ"] = ["PLO", "OCC", "ARA", "CVL"]
R["OCC"] = ["NAQ", "PAC", "ARA"]
R["PAC"] = ["OCC", "ARA"]
R["ARA"] = ["NAQ", "OCC", "PAC", "BFC", "CVL"]
R["BFC"] = ["ARA", "CVL", "IDF", "GES"]
R["CVL"] = ["PLO", "NAQ", "ARA", "BFC", "IDF", "NOR"]
R["IDF"] = ["BFC", "CVL", "GES", "HDF", "NOR"]
R["GES"] = ["BFC", "IDF", "HDF"]
R["HDF"] = ["IDF", "GES", "NOR"]
R["NOR"] = ["BRE", "PLO", "CVL", "IDF", "HDF"]
Corrigé
>>> tri_sommets(R)
['CVL', 'ARA', 'IDF', 'NOR', 'PLO', 'BFC', 'NAQ', 'GES', 'HDF', 'OCC', 'PAC', 'BRE']
5. Quelles modifications doit-on apporter à l'algorithme séquentiel (dans la fonction coloration) pour implémenter l'algorithme de Welsh-Powell ? Vous ne recopierez pas toute la fonction, mais vous signalerez les lignes que vous insérez et celles que vous modifiez.
Corrigé
for s_i in tri_sommets(G):
6. Donnez alors la couleur attribuée à chaque région par votre fonction.
Corrigé
Dans l'ordre d'attribution finale, on a :
| id Région | Couleur |
|---|---|
| CVL | Rouge |
| ARA | Bleu |
| IDF | Bleu |
| NOR | Vert |
| PLO | Bleu |
| BFC | Vert |
| NAQ | Vert |
| GES | Rouge |
| HDF | Jaune |
| OCC | Rouge |
| PAC | Vert |
| BRE | Rouge |
Exercice 3 (Sujet concours geipi-polytech 2022)
À l'école IPIEG , chaque étudiant est affecté à une section sportive au début de sa première année d'étude ; durant son internat, il pratiquera essentiellement le sport auquel il aura été affecté et vivra en communauté avec les camarades de sa section. Lors des affectations initiales, l'objectif de l'école est de favoriser l'épanouissement individuel des étudiants, en leur permettant de s'orienter vers leur sport préféré, mais également d'assurer la réputation sportive de l'école, en sélectionnant pour chaque sport les étudiants qui obtiendront les meilleurs résultats lors des compétitions. Ainsi, les affectations s'appuient sur les préférences des étudiants, les capacités d'accueil de chaque activité sportive et les classements fournis par les responsables sportifs.
L'école souhaite que toutes les sections puissent présenter de bonnes équipes féminines même s'il y a moins d'étudiantes que d'étudiants. Les responsables sportifs doivent retoucher leur classement initial de sorte qu'il respecte la propriété de parité faible, qui garantit qu'à tout rang \(k\), il n'y a pas plus de garçons que de filles parmi les \(k\) premières places du classement, sauf s'il n'y a plus de fille après la \(k\)-ième place ; le classement initial des filles entre elles et celui des garçons entre eux, ne doivent jamais être modifiés.
Dans la suite de l'exercice, on suppose que les étudiants sont identifiés par une chaîne de caractères
commençant par un F majuscule pour les filles et par un G majuscule pour les garçons.
Question 1
Le classement C1 ci-dessous ne respecte pas la propriété de parité faible : il y a plus de garçons que
de filles dans les trois premières places alors qu'il reste au moins une fille dans la suite du classement.
Comment retoucher ce classement pour qu'il respecte la propriété de parité faible, sans modifier ni le classement initial des filles entre elles, ni le classement initial des garçons entre eux ?
C1 = ['F1', 'G4', 'G7', 'G2', 'G3', 'G6', 'G1', 'F2', 'G8', 'G5', 'F3']
Corrigé
C1 = ['F1', 'G4', 'F2', 'G7', 'F3', 'G2', 'G3', 'G6', 'G1', 'G8', 'G5']
Question 2
Reprenez la question précédente pour le classement C2 ci-dessous.
C2 = ['F2', 'F3', 'G5', 'G1', 'F4', 'G7', 'G3', 'G2', 'G4', 'F1', 'G6']
Corrigé
C2 = ['F2', 'F3', 'G5', 'G1', 'F4', 'G7', 'F1', 'G3', 'G2', 'G4', 'G6']
Question 3
Complétez la fonction fille pour qu'elle renvoie True si la chaîne de caractères qu'elle reçoit en argument désigne une fille et False sinon.
def fille(etu):
return ... == 'F'
Corrigé
return etu[0] == 'F'
Question 4
Complétez la fonction suivante qui, étant donné une liste d'étudiant etus et un indice i, renvoie l'indice de la première fille dans L à partir de l'indice i. Par exemple, suivante(C1,0) renvoie 0 (indice de F1 dans le classement C1) et suivante(C1,1) renvoie 7 (indice de F2 dans le classement C1).
def suivante(etus, i):
if i >= len(etus) or fille(etus[i]):
return ...
return suivante(etus, ...)
Corrigé
def suivante(etus, i):
if i >= len(etus) or fille(etus[i]):
return i
return suivante(etus, i+1)
Question 5
Complétez la fonction forcer_parite qui, étant donnée une liste ordonnée d'étudiants, renvoie une copie modifiée de façon à respecter la propriété de parité faible ; la fonction part d'une copie du classement initial dont elle supprime itérativement les étudiants à mesure qu'ils sont ajoutés au classement final. Le classement initial des étudiants de même genre entre eux n'est pas modifié.
def forcer_parite(etus):
etus = etus.copy()
(classt, nbf) = ([], 0)
idxf = suivante(etus, 0)
while etus:
if fille( ... ):
classt.append(etus.pop(0))
nbf = nbf + 1
idxf = suivante(etus, ... )
elif nbf < ... and idxf < ... :
classt.append(etus.pop( ... ))
nbf = nbf + 1
idxf = suivante(etus, ... )
else:
classt.append(etus.pop(0))
idxf = idxf - 1
return classt
Corrigé
def forcer_parite(etus):
etus = etus.copy()
(classt, nbf) = ([], 0)
idxf = suivante(etus, 0)
while etus:
if fille(etus[0]):
classt.append(etus.pop(0))
nbf = nbf + 1
idxf = suivante(etus,0)
elif nbf < 0.5*(len(classt)+1) and idxf < len(etus) :
classt.append(etus.pop(idxf))
nbf = nbf + 1
idxf = suivante(etus,idxf)
else:
classt.append(etus.pop(0))
idxf = idxf - 1
return classt
Quand tous les responsables sportifs ont fourni leur classement, respectant la propriété de parité faible, l'école utilise l'algorithme des mariages stables pour tenir compte des préférences des étudiants (en priorité) et des classements par activité sportive. Cet algorithme converge toujours vers la même solution pour des conditions de départ identiques, quel que soit l'ordre dans lequel on traite les étudiants. Il procède comme suit :
-
Choisir un étudiant.
-
Affecter provisoirement cet étudiant à la section sportive qu'il préfère.
-
Recommencer l'étape 1 avec un autre étudiant jusqu'à ce que la capacité d'accueil soit dépassée d'une unité dans le sport choisi ; dans ce cas, on regarde tous les étudiants affectés à ce sport et on élimine le moins bien classé par le responsable de ce sport. Cet étudiant est éliminé définitivement du sport en question et affecté provisoirement au sport de son second choix (ou troisième s'il était affecté au sport de son deuxième choix et ainsi de suite).
-
On itère à partir de l'étape 1 jusqu'à ce qu'il n'y ait plus aucune modification la solution est alors trouvée.
On implémente cet algorithme en python en utilisant les structures de données suivantes :
-
Les listes d'étudiants et les listes de sports sont représentées par des listes de chaînes de caractères ;
-
Les préférences des étudiants sont représentées par un dictionnaire dont les clefs sont les étudiants et les valeurs sont les listes des sports classés par ordre de préférences ;
-
Les classements par sport sont représentés par un dictionnaire dont les clefs sont les sports et les valeurs les listes des étudiants ordonnés selon le classement des responsables sportifs ;
-
Les capacités d'accueil des sections sportives sont représentées par un dictionnaire dont les clefs sont les sports et les valeurs sont le nombre maximum d'étudiants pouvant être accueillis dans la section.
Par exemple, avec trois étudiants et deux sections sportives :
etudiants = ['F1', 'G1', 'G2']
sports = ['escrime', 'judo']
preferences = {'F1': ['judo', 'escrime'], 'G1': ['escrime','judo'],
'G2': ['escrime', 'judo']}
classements = {'escrime': ['F1', 'G2', 'G1'], 'judo': ['F1', 'G1', 'G2']}
quotas = {'escrime': 1, 'judo': 3}
Le résultat de l'algorithme est un dictionnaire d'affectations dont les clefs sont les sports et dont les valeurs sont les listes des étudiants affectés. On décompose l'algorithme en trois fonctions : insertion_selon_classement, affectation_etudiant et mariages_stables.
Question 6
La fonction insertion_selon_classement attend trois arguments, un étudiant, le classement des étudiants dans un sport et une liste des étudiants déjà affectés à ce sport, et elle ajoute l'étudiant dans la liste des affectations à la position qui respecte le classement dans le sport. Par exemple :
insertion_selon_classement('F1', ['F1', 'G2', 'G1'], ['G2'])renvoie['F1','G2'],insertion_selon_classement('G1', ['F1', 'G2', 'G1'], ['G2'])renvoie['G2','G1'].
Complétez le code donné ci-dessous.
def insertion_selon_classement( etu, classement, affectation ):
i = 0
rang = classement.index(etu)
while i < len(affectation) and rang > classement.index( ... ):
i = i + 1
affectation.insert( ... )
Corrigé
def insertion_selon_classement( etu, classement, affectation ):
i = 0
rang = classement.index(etu)
while i < len(affectation) and rang > classement.index( affectation[i]):
i = i + 1
affectation.insert( i,etu )
Question 7
La fonction affectation_etudiant attend cinq arguments, un étudiant et quatre dictionnaires : les affectations temporaires, les préférences des étudiants, les classements par sport et les capacités d'accueil par sport ; elle ne renvoie aucune valeur rien mais elle modifie le dictionnaire des affectations de sorte à y intégrer l'étudiant, en suivant les étapes 2 et 3 de l'algorithme des mariages stables décrit plus haut ; lorsqu'un étudiant se fait éliminer d'un sport, ce sport est supprimé du dictionnaire indiquant ses préférences.
Complétez le code donné ci-dessous.
def affectation_etudiant( etu, affect, prefs, classts, quotas ):
sport = ...
insertion_selon_classement( ... , ... , ... )
if len(affect[sport]) > quotas[sport]:
elimine = affect[sport].pop()
prefs[etu].pop( ... )
affectation_etudiant( ... , affect, prefs, classts, quotas )
Corrigé
def affectation_etudiant( etu, affect, prefs, classts, quotas ):
sport = prefs[etu][0]
insertion_selon_classement(etu, classts[sport], affect[sport])
if len(affect[sport]) > quotas[sport]:
elimine = affect[sport].pop()
prefs[etu].pop(0)
affectation_etudiant( elimine , affect, prefs, classts, quotas )
Question 8
La fonction mariages_stables prend en paramètres trois dictionnaires (préférences, classements et quotas) et renvoie le dictionnaire final des affectations.
Complétez le code ci-dessous.
def mariages_stables(prefs, classts, quotas):
prefs = prefs.copy()
affectation = { sport: [] for sport in classts.keys() }
for ... in ... :
affectation_etudiant( ... , ... , ... , ... , quotas)
return affectation
Corrigé
def mariages_stables(prefs, classts, quotas):
prefs = prefs.copy()
affectation = { sport: [] for sport in classts.keys() }
for elt in prefs :
affectation_etudiant( elt , affectation , prefs , classts , quotas)
return affectation