Course list Sign in

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline No deadline
Submission limit No limitation

Sign in

Sign in

[TP.01] Les marches du pouvoir - quotient de D'hondt

La méthode de D’Hondt débute de la même manière que celle dite du plus fort reste en donnant à chaque parti un nombre de sièges correspondant à la partie entière de la valeur théorique. Le processus d’attribution s’effectue ensuite de manière itérative ; chaque itération consiste à attribuer un des sièges restants à un parti.

Posons \(v_i\), le nombre de votes remportés par le \(i^e\) parti et \(s_i^j\), le nombre de sièges accordés au \(i^e\) parti à la \(j^e\) itération. La toute première partie de l’algorithme consiste donc à assigner \(s_i^0\) à la partie entière de l’allocation exacte. À l’itération j, un siège supplémentaire est accordé au parti i tel que

\(i = \text{argmax}_k \left(\frac{v_k}{s_k^{j-1}+1}\right)\)

L’addition au dénominateur peut être vue comme l’attribution d’un siège fictif supplémentaire. Au terme de l’itération, un des partis acquiert ce siège fictif de manière effective. Dès lors, le rapport maximisé correspond au nombre d'électeurs représentés par siège si un siège supplémentaire est accordé au parti. On choisit le parti pour lequel il y a le plus d'électeurs représentés.

Si l’on adapte notre exemple pour qu’il y ait onze sièges à pourvoir et que l’on applique cette méthode, cela donne :

Parti Nombre de voix Allocation exacte Initialisation (\(s_i^0\)) Itération 1 (\(s_i^1\)) Itération 2 (\(s_i^2\))
Utly 437 4,807 4 5 5
Siditu 478 5,258 5 5 5
Ismo 85 0,935 0 0 1
Question 1: Plus forte moyenne

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier plus_forte_moyenne.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def plus_forte_moyenne(n_sieges, resultat_vote):
    '''
    Calcul la repartition des sieges selon la methode de la plus
    forte moyenne (variante de D Hondt)
    pre: `n_sieges` > 0
    pre: len(`resultat_vote`) > 1
    pre: `resultat_vote[i]` >= 0
        pour tout `i` tel que 0 <= `i` < len(`resultat_vote`)
    post: retourne un tableau `t` de meme longueur que `resultat_vote`
        et tel que `t[i]` est le nombre de sieges attribues au parti
        correspondant a `resultat_vote[i]`
    '''
Question 2: Borne supérieure

Déterminez la borne supérieure du nombre d'itérations effectuées par votre implémentation (en supposant qu'elle ne fait pas de d'opérations inutiles).