[TP.01] Les marches du pouvoir - quotient de D'hondt - [LINFO1103] Introduction à l'algorithmique

[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

Paste this command into your terminal:

The password to connect is

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]`
    '''

# A implémenter

 
# A implémenter

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 d'opérations inutiles).

Nombre de partis - 1

Nombre de sièges à pourvoir

Nombre de partis

Author(s)	Vincent Branders, Pierre Dupont
Deadline	19/02/2025 14:00:00
Submission limit	No limitation

Information

Sign in