E3A Option Informatique MP 2010Sujet

CONCOURS ARTS ET MÉTIERS ParisTech - ESTP - ARCHIMEDE

Épreuve d'Informatique MP

Durée 3 h

L'usage de calculatrices est interdit.

Exercice 1

verification_liste
    données L:liste d'entiers naturels
    résultat b:booléen

tri_tableau
    données N: entier naturel
        T:tableau d'entiers naturels de longueur N
    résultat U:tableau d'entiers naturels de longueur N

Exercice 2

Exercice 3

1. On considère le programme suivant qui prend en entrée une liste contenant des listes de longueur fixée ne contenant que des 0 ou des 1 et retourne une liste de même type. On remarquera qu'une liste de listes peut contenir uniquement la liste vide.

$\operatorname{PROG}(L$ : liste de listes, $k$ : entier naturel non nul )
variables : $x$ : entier, $U$ : liste de listes, $V 0$ : liste de listes, $V 1$ : liste de listes.
$W 0$ : liste de listes, $W 1$ : liste de listes, $L 1$ : liste d'entiers,
$U \leftarrow L$
$V 0 \leftarrow$ liste_vide
$V 1 \leftarrow$ liste_vide
$W 0 \leftarrow$ liste_vide
$W 1 \leftarrow$ liste_vide
tant que test_liste_vide $(U)=0$ faire
        $L 1 \leftarrow$ tête $(U)$
        $x \leftarrow$ tête $(L 1)$
        si ( $x=0$ ) alors ajouter(supprimer_tête( $L 1$ ), $V 0$ )
        sinon ajouter(supprimer_tête(L1), V1)
        fin si
        supprimer_tête $(U)$
        fin faire
si $(k>1)$ faire $V 1 \leftarrow P R O G(V 1, k-1)$
    $V 0 \leftarrow P R O G(V 0, k-1)$
fin si
tant que test_liste_vide $(V 1)=0$ faire
        $L 1 \leftarrow$ tête $(V 1)$
        ajouter $(1, L 1)$
        ajouter( $L 1, W 1$ )
        supprimer_tête(V1)
        fin faire
tant que test_liste_vide $(V 0)=0$ faire
        $L 1 \leftarrow$ tête $(V 0)$
        ajouter $(0, L 1)$
        ajouter( $L 1, W 0$ )
        supprimer_tête( $V 0$ )
        fin faire
tant que test_liste_vide $(W 0)=0$ faire
        ajouter(tête( $W 0$ ), $U$ )
        supprimer_tête( $W 0$ )
        fin faire
tant que test_liste_vide $(W 1)=0$ faire
        ajouter(tête( $W 1$ ), $U$ )
        supprimer_tête( $W 1$ )
        fin faire
retourner $(U)$

FONCTION1( $n$ : entier naturel, $k$ : entier naturel)
variables : $x$ : entier, $y$ : entier, $i$ : entier, $L$ : liste d'entiers.
$L \leftarrow$ liste_vide
$x \leftarrow n$
pour $i$ de 1 à $k$ faire
    $y \leftarrow x$ MOD 2
    ajouter $(y, L)$
    $x \leftarrow(x-y) / 2$
    fin faire
retourner $L$

3. Qu'effectue la fonction ci-dessous :

FONCTION2( $L:$ liste d'entiers naturels, $k:$ entier nature)
variables : $x$ : entier, $y$ : entier, $i$ : entier, $L 1$ : liste d'entiers, $L 2$ : liste d'entiers, $U$ : liste de listes.
$L 1 \leftarrow L$
$U \leftarrow$ liste_vide
tant que test_liste_vide $(L 1)=0$ faire
    $x \leftarrow$ tête $(L 1)$
    $L 2 \leftarrow \operatorname{FONCTION1}(x, k)$
    ajouter $(L 2, U)$
    supprimer_tête(L1)
    fin faire
retourner $U$

4. a) Décrire l'éxécution de la fonction FONCTION2 sur la liste L = [6, 0, 3, 5] et l'entier k = 3 ? Quel est le résultat de PROG(FONCTION2(L, 3), 3) ?
   b) On souhaite utiliser la fonction FONCTION1, la FONCTION2 et le programme PROG pour trier par ordre croissant des listes d'entiers naturels. Quelle(s) fonction(s) faut-il ajouter? Quel est le domaine de validité de ce programme de tri ?

Exercice 4

1. Dans cette question, Σ est l'alphabet à deux lettres {x, y}. Déterminer l'ensemble des sous-mots du mot xyxyx. Combien y-en a t'il?
2. Dans le cas général, démontrer que l'ensemble des sous-mots du mot v = b_1…b_n est fini et proposer une majoration de son cardinal en fonction de n.
3. On suppose que u est un sous-mot de v. Soit M(u, v) l'ensemble des applications φ, φ application strictement croissante de {1, …, m} dans {1, …, n} telle que a_i = b_(φ(i)), pour tout entier i compris entre 1 et m.
   a) Soit j le plus petit indice dans {1, …, n} tel que b_j = a_1. Démontrer que toute application φ dans M(u, v) vérifie φ(1) ⩾ j.
   b) Démontrer qu'il existe une application φ_0 dans M(u, v) telle que, pour toute application φ dans M(u, v) et tout indice i dans {1, …, m}, φ(i) ⩾ φ_0(i).
   c) Ecrire un algorithme qui prend en entrée les listes U = [a_1, …, a_m] et V = [b_1, …, b_n] et qui renvoie la liste [φ_0(m), φ_0(m − 1), …, φ_0(1)].
   d) Ecrire un algorithme qui prend en entrée les listes U = [a_1, …, a_m] et V = [b_1, …, b_n] et qui renvoie un booléen égal à 1 si u est un sous-mot de v, 0 sinon. L'algorithme ne doit parcourir qu'une fois chacune des listes U et V. Estimer la complexité de votre algorithme en fonction des entiers m et n.
4. Le cardinal de l'ensemble M(u, v) est noté [u, v]. Soient u^′ et v^′ les mots tels que u = a_1 u^′ et v = b_1 v^′.
   a) Lorsque a_1 = b_1, démontrer l'égalité [u, v] = [u^′, v^′] + [u, v^′].
   b) Lorsque a_1 ≠ b_1, démontrer l'égalité [u, v] = [u, v^′].
   c) Proposer un algorithme récursif qui prend en entrée les listes U = [a_1, …, a_m] et V = [b_1, …, b_n] et qui renvoie la valeur de [u, v].
5. Dans cette partie, le mot u = a_1…a_m est fixé. On considère L(u) le langage formé par les mots v de Σ^∗ tels que u est un sous-mot de v.
   a) Dans le cas particulier où Σ est l'alphabet à deux lettres {x, y} et u = xy, on remarquera que le langage L(xy) est le langage reconnu par l'automate A représenté dans la figure 1 ci-dessous. Proposer une expression rationnelle de L(xy).
   b) Dans le cas général, démontrer que le langage L(u) est un langage rationnel et en proposer une expression rationnelle.
   c) Représenter graphiquement un automate déterministe qui reconnait le langage L(u). On démontrera précisément que le langage reconnu est L(u).

Figure 1: Automate A

Exercice 5

1. Ecrire la table de vérité de la fonction ⊕.
2. Démontrer la propriété d'associativité de la fonction ⊕, c'est-à-dire :

3. Ecrire f avec une formule booléenne.
4. Construire un circuit logique implémentant la fonction f utilisant uniquement des portes XOR (ou exclusif).
5. Etant donné un entier naturel n non nul, construire un circuit logique qui prend en entrée n bits et donne en sortie la parité du nombre de ces bits égaux à 1 en utilisant au plus n − 1 portes XOR.

Figure 2: Porte XOR (ou exclusif)