Corrigé Centrale 2025 Informatique MPI — Partie A, II (Q7 à Q11) : File circulaire et complexité amortie par la méthode du potentiel

Sujet officiel du concours Centrale, session 2025, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Une file est rangée dans un tableau circulaire de capacité $c$ ; prochain est l'indice du prochain élément à sortir et la taille est le nombre d'éléments. Exemple de capacité $8$ et de taille $4$ , représentant la file $17 \leftarrow 25 \leftarrow 9 \leftarrow 8$ ( $17$ sort le premier, $8$ est le dernier entré) :


struct file_s {
    etat **tab;
    int prochain;
    int taille;
    int capacite;
};
typedef struct file_s file;

Q7. file *f_nouveau(void) (taille et capacité nulles) et void f_libere(file *f), qui ne libère pas les états contenus.
Q8. void f_change_capacite(file *f, int c), pour une file de taille $m ⩽ c$ : la capacité devient $c$ .
Q9. void f_enfile(file *f, etat *e) et etat *f_defile(file *f) ; quand la taille égale la capacité, on double la capacité avant d'enfiler ( $0$ devient $1$ ).

Pour Q10 et Q11 seulement, le coût d'une opération est son nombre d'accès (lectures ou écritures) aux cases de tab. Potentiel : $Φ (f) = ∣4 \cdot taille (f) - 2 \cdot capacite (f) ∣$ . Partant de la file $f_{0}$ vide de capacité nulle, $n$ opérations $op_{1}, \dots, op_{n}$ (enfiler ou défiler) donnent $f_{1}, \dots, f_{n}$ ; $C_{k}$ est le coût de $op_{k}$ .
Q10. Trouver un entier $K ⩾ 0$ tel que $C_{k} + Φ (f_{k}) - Φ (f_{k - 1}) ⩽ K$ pour tout $k \in [[1, n]]$ .
Q11. En déduire $\sum_{k = 1}^{n} C_{k} ⩽ K n$ , et conclure : coût amorti $O (1)$ .

Corrigé

Le code a été compilé avec celui de la partie I et exécuté : vingt enfilages entrecoupés de défilages ressortent dans l'ordre d'entrée (y compris quand la file « fait le tour » du tableau pendant un redimensionnement), et un compteur d'accès à tab a été placé dans chaque fonction pour Q10 et Q11.

Q7. Une file de capacité nulle n'a pas de tableau : on met tab à NULL.


file *f_nouveau(void) {
    file *f = malloc(sizeof(file));
    assert(f != NULL);
    f->tab = NULL;
    f->prochain = 0;
    f->taille = 0;
    f->capacite = 0;
    return f;
}

void f_libere(file *f) {
    free(f->tab);
    free(f);
}

f_libere rend le tableau de pointeurs puis la structure, dans cet ordre (après free(f), f->tab ne serait plus lisible) ; les états pointés ne sont pas touchés, comme demandé. free(NULL) ne fait rien, donc le cas de la capacité nulle est couvert. Coût $O (1)$ .

Q8. Les éléments, du prochain à sortir au dernier entré, occupent les indices $(prochain + k) mod c_{ancienne}$ pour $0 ⩽ k < m$ . On les recopie dans cet ordre au début du nouveau tableau, et prochain revient à $0$ .


void f_change_capacite(file *f, int c) {
    assert(c >= f->taille);
    etat **t = NULL;
    if (c > 0) {
        t = malloc(c * sizeof(etat *));
        assert(t != NULL);
    }
    for (int k = 0; k < f->taille; k++)
        t[k] = f->tab[(f->prochain + k) % f->capacite];
    free(f->tab);
    f->tab = t;
    f->prochain = 0;
    f->capacite = c;
}

Après l'appel, le $k$ -ième élément à sortir est en t[k], ce qui est la représentation d'une file de prochain $= 0$ ; la file représentée est inchangée. Le modulo n'est évalué que si $m ⩾ 1$ , donc jamais avec une capacité nulle. La recopie fait $m$ lectures et $m$ écritures dans les tableaux : $2 m$ accès, coût $O (m)$ hors allocation.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →