CCINP Option Informatique MP 2022Sujet, corrigé et rapport du jury

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH ÉPREUVE SPÉCIFIQUE - FILIÈRE MP

INFORMATIQUE

RAPPEL DES CONSIGNES

• Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
• Ne pas utiliser de correcteur.
• Écrire le mot FIN à la fin de votre composition.

Les calculatrices sont interdites.

Partie I - Automates

• Q un ensemble fini non vide d'états, de cardinal |Q|;
• Σ un alphabet;
• I ⊂ Q l'ensemble des états initiaux;
• δ : Q × Σ → P(Q) une fonction de transition : si q ∈ Q et a ∈ Σ, δ(q, a) désigne l'ensemble des états q^′ de Q tels qu'il existe une transition étiquetée par a de q vers q^′;
• F ⊂ Q l'ensemble des états finaux.

Figure 1 - Automate exemple

Partie II - Autour des tas

II. 1 - Arbre binomial

Figure 2 - Exemple d'arbre enraciné

• Vide(a) qui renvoit True si l'arbre a est vide, False sinon;
• Racine(a) qui renvoit la racine de a si a est non vide;
• Fils(a) qui renvoit la liste des arbres, fils de la racine de a.

• t_(n − 1) est un arbre binomial d'ordre ( k − 1 );
• ( r, [t_0, ⋯t_(n − 2)] ) est un arbre binomial d'ordre ( k − 1 );
• la racine de t_(n − 1) a une valeur supérieure ou égale à r .

Figure 3 - Exemple d'arbre binomial d'ordre 3

II. 2 - Tas binomial

Algorithme 1 - Insertion de $p$ dans T.
Entrées : un tas $\mathrm{T}=\left\{a_{0} \cdots a_{k}\right\}$, une valeur $p$
Sorties: un tas T augmenté de la valeur $p$
début
    $i \leftarrow 0$
    Coder $p$ dans un arbre binomial a d'ordre 0
    tant que $i<k+1$ et a non vide faire
        si $a_{i}$ est vide alors
            $a_{i} \leftarrow \mathrm{a}$
            Vider a
        sinon
            a $\quad a \oplus a_{i} \quad(* * *)$
            Vider $a_{i}$
        $i \leftarrow i+1$
    si a n'est pas vide alors
        Ajouter a au tas T.

Partie III - Autour de l'énumération des fractions positives

Notations

• n ∧ d le PGCD (Plus Grand Commun Diviseur) de n et d;
• ⌈x⌉ la partie entière supérieure de x. Ainsi ⌈3.45⌉ = 4;
• ⌊x⌋ la partie entière inférieure de x. Ainsi ⌊3.45⌋ = 3;
• log_2 la fonction logarithme de base 2. C'est la fonction réciproque de la fonction i ↦ 2^i.

• premier cas : les nœuds de valeur v_i et v_(i + 1) sont à même profondeur k, fils d'un même nœud N,
• deuxième cas : le nœud de valeur v_i est le dernier nœud à droite à la profondeur k,
• troisième cas : les nœuds de valeur v_i et v_(i + 1) sont à même profondeur k, mais ne sont pas fils d'un même nœud.
  On pose pour tout x > 0, f(x) = 1/(1 + 2⌊x⌋ − x).
  Q35. Montrer que dans le premier cas, v_(i + 1) = f(v_i).
  Q36. Montrer, en utilisant la Q26, que dans le deuxième cas on a encore v_(i + 1) = f(v_i).
  On étudie enfin le dernier cas : les nœuds de valeur v_i et v_(i + 1) sont sur une même profondeur k, mais ne sont pas les fils d'un même nœud. On va donc passer par la recherche d'un ancêtre commun de ces deux nœuds. Dans la suite, on s'intéressera toujours au premier ancêtre commun, c'est-à-dire celui de profondeur maximale.
  En partant de la racine r , il est possible d'atteindre n'importe quel nœud N = n/d de l'arbre par une suite de déplacements vers la gauche (G) ou vers la droite (D). Le chemin de r vers N peut donc être codé par un mot sur l'alphabet {G,D}.

FIN