projet

Répondre

Messages : 0

Enregistré le : 28 déc. 2020 10:59

Classe : MPSI

projet

Message par benjaaa » 28 déc. 2020 11:07

Bonjour.
Serait-il possible d'obtenir une aide pour cet exercice?

Voici le sujet:
Dans une classe, on doit attribuer 𝑛 projets informatiques à 𝑛 binômes d’élèves (soit un projet pour chaque
binôme), en essayant de respecter au mieux un ensemble de vœux émis par les binômes. Pour ce faire, on
demande à chaque binôme de classer les 𝑛 projets par ordre de préférence, en attribuant le rang 1 au projet qu’il
préfère, 2 à son second choix, et ainsi de suite jusqu’à attribuer le rang 𝑛 au projet pour lequel il a le moins
d’intérêt. On décide de stocker l’ensemble des vœux dans un tableau numpy T de taille (𝑛, 𝑛) dans lequel T[i,j]
contient le rang 𝑘𝑖 𝑗 ∈ È1, 𝑛É attribué par le binôme 𝑖 au projet 𝑗 (les binômes et les projets seront numérotés de 0 à 𝑛 1). Une répartition des projets sera représentée par un tableau numpy R unidimensionnel de 𝑛 éléments dans
lequel R contiendra le numéro du projet attribué au binôme 𝑖. A chaque répartition 𝑅, on associe un coût
𝑐(𝑅) défini comme la somme des rangs attribués par chaque binôme au projet qui lui a été attribué par R, soit
𝑐(𝑅) = sigma𝑖 𝑘𝑖𝑅[𝑖]
La (ou les) répartition(s) optimale(s) est(sont) par définition celle(s) qui a(ont) le plus faible coût. On envisage
plusieurs méthodes pour déterminer la (ou les) répartition(s) optimale(s) associées à un tableau T donné.

Voici la question: Dans cette méthode, on construit explicitement toutes les répartitions 𝑅 possibles pour les 𝑛 projets sur
les 𝑛 binômes, puis on évalue le cout de chacune de ces répartitions, et on renvoie l’ensemble des répartitions
correspondant au coût minimal.

Je ne vois pas trop comment faire.

Merci à vous.
Cordialement.

Messages : 3854

Enregistré le : 04 sept. 2005 19:27

Localisation : Versailles

Re: projet

Message par JeanN » 28 déc. 2020 14:06

A ton avis, combien y a-t-il de répartitions possibles des n projets sur les n binômes ?
Professeur de maths MPSI Lycée Sainte-Geneviève

YS1

Messages : 10

Enregistré le : 06 févr. 2005 11:50

Classe : MPSI, PCSI, MP*, PC*

Re: projet

Message par YS1 » 02 janv. 2021 12:12

Voici la question: Dans cette méthode, on construit explicitement toutes les répartitions 𝑅 possibles pour les 𝑛 projets sur les 𝑛 binômes, puis on évalue le cout de chacune de ces répartitions, et on renvoie l’ensemble des répartitions correspondant au coût minimal.
Ce n'est pas une question… Un algorithme est sommairement décrit mais on ne sait pas ce qui est demandé. Écrire l'algorithme en Python ? Évaluer le nombre total d'opérations nécessaires ?

Répondre