WikiPrépaLivrets

E3A Option Informatique MP 2008Sujet et rapport du jury

Pas encore noté
Logo concours E3A

Explorer les annales

BanqueE3AAnnée2008FilièreMPMatièreInformatique
Annales E3A MP InformatiqueE3A MP 2008MP InformatiqueInformatique 2008

Téléchargements

Télécharger le sujet (PDF)
Rapport du juryLire en ligneLaTeXWord
  • Corrigé : pas encore disponible

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

CONCOURS ENSAM - ESTP - ARCHIMEDE

Épreuve d'Informatique MP

Durée 3 h

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, d'une part il le signale au chef de salle, d'autre part il le signale sur sa copie et poursuit sa composition en indiquant les raisons des initiatives qu'il est amené à prendre.

L'usage de calculatrices est interdit.

Indiquer en tête de copie ou de chaque exercice le langage utilisé
Quel que soit le langage utilisé, le candidat pourra supposer qu'il dispose d'une fonction test_liste_vide qui prend en entrée une liste et renvoie le booléen 1 si la liste est vide et 0 sinon.
Le candidat pourra, s'il le juge utile, supposer que chaque liste se termine par un élément de marquage de fin de liste appelé NIL.

Exercice 1

a) Ecrire la fonction :
Tri_denombrement
    données N:entier naturel
        L: liste d'entiers tous compris entre 1 et N
    résultat M:tableau de longueur N
qui prend en entrée un entier naturel non nul N et une liste L d'entiers tous compris entre 1 et N et renvoie le tableau de longueur N, dans lequel la k-ième case contient le nombre d'éléments égaux à k dans la liste L, pour tout entier k compris entre 1 et N.
b) Calculer en fonction de n, n étant la longueur de la liste L, et de N, le coût de ce tri dans le meilleur des cas, dans le pire des cas et en moyenne. On supposera que le temps d'accès à la k-ième case du tableau est linéaire en k, le reste des opérations ayant un coût négligeable.
Exercice 2
(les questions a et b sont indépendantes.)
a) Ecrire la fonction :
Matrice
    données L:liste
        n: entier
    résultat M: tableau à deux entrées de taille n,n
qui prend en entrée une liste L et l'entier n et renvoie le tableau des coefficients d'une matrice carrée de taille n remplie ligne par ligne de gauche à droite par les coefficients de la liste L. La liste contient des entiers relatifs. Si la liste L n'est pas suffisamment longue, la matrice est complétée par des 0 . Si la liste L est trop longue, le programme s'arrête lorsque la matrice est remplie.
b) Soit T un tableau rempli avec des entiers naturels. Un plateau de T de valeur k et de longueur l est une suite de l indices consécutifs i, i + 1, …, i + l − 1 sur lesquels T prend la valeur k(T[i] = T[i + 1] = ⋯ = T[i + l − 1] = k ). Par exemple, le tableau [1, 2, 3, 3, 3, 1, 2, 6, 6] posséde un plateau de valeur 3 et de longueur 3 , un plateau de valeur 6 et de longueur 2 , deux plateaux de valeur 1 et de longueur 1 et deux plateaux de valeur 2 et de longueur 1 .
Ecrire la fonction :
LongueurMaxPlateau
    données T:tableau
        N: entier naturel
    résultat l:entier naturel
qui prend en entrée un tableau d'entiers naturels et sa longueur N et renvoie la plus grande longueur de ses plateaux.

Exercice 3

(les questions a, b et c sont indépendantes.)
a) Qu'effectue le programme ci-dessous :
$P R O G$ ( $L$ : liste d'entiers)
$L_{2} \leftarrow$ liste_vide
$E \leftarrow$ premier_element $(L)$
tant que ( $E<>N I L$ ) faire
    $E_{2} \leftarrow$ premier_element $(L 2)$
    $S W \leftarrow 0$
    tant que $\left(E_{2}<>N I L\right.$ et $\left.S W=0\right)$ faire
        $\operatorname{si}\left(E=E_{2}\right)$ alors $S W \leftarrow 1$
        sinon $E_{2} \leftarrow$ element_suivant $\left(L_{2}\right)$
        fin si
    fin faire
    si ( $S W=0$ ) alors $L_{2} \leftarrow$ ajouter_element $(E)$
    fin si
    $E \leftarrow$ element_suivant $(L)$
fin faire
retourner $L_{2}$
On remarquera que les listes considérées par ce programme se terminent par un élément de marquage de fin de liste appelé NIL.
b) Décrire l'exécution du programme NBS ci-dessous sur l'entrée (7, 3) :
$N B S(N:$ entier strictement positif, $p:$ entier strictement positif))
si $(N<p)$ alors $S \leftarrow 0$
sinon si ( $p=1$ ) alors $S \leftarrow 1$
sinon $S \leftarrow N B S(N-1, p-1)+N B S(N-p, p)$
fin si
retourner $(S)$
Que calcule ce programme ?
c) Que calcule la procédure suivante :
$M S(N:$ entier, $T:$ tableau d'entiers de longueur $N$,
    $U \leftarrow-1$
    $m \leftarrow-1$
    $n \leftarrow-1$
    $S \leftarrow-1$
    $b \leftarrow 0$
pour $k$ de 1 à $N$ faire
        si $(b=0)$ et $(T[k] \geqslant 0)$ alors faire
                $b \leftarrow 1$
                $i \leftarrow k$
                $j \leftarrow i$
                $S \leftarrow T[k]$
            fin faire
        si ( $b=1$ )et ( $T[k] \geqslant 0$ ) alors faire
                $j \leftarrow k$
                $S \leftarrow S+T[k]$
            fin faire
        si $(T[k]<0)$ alors $b \leftarrow 0$
        fin si
        si $(k=N)$ alors $b \leftarrow 0$
        fin si
        si ( $b=0$ )et ( $S>U$ ) alors faire
                $U \leftarrow S$
                $m \leftarrow i$
                $n \leftarrow j$
            fin faire
        fin si
fin faire
retourner $(U, m, n)$

Exercice 4

Un nombre d'Armstrong est un nombre qui est égal à la somme des cubes des chiffres de son écriture en base 10 ; par exemple 153 est un nombre d'Armstrong puisque 153 = 1^3 + 5^3 + 3^3. Ecrire un programme qui calcule tous les nombres d'Armstrong à trois ou quatre chiffres.

Exercice 5

Une liste d'entiers est dite convenable si elle se compose d'un nombre pair d'éléments a_1, b_1, a_2, b_2, …, a_k, b_k tels que a_1 ⩽ b_1 < a_2 ⩽ ⋯b_(k − 1) < a_k ⩽ b_k. On représente une réunion finie de k intervalles fermés disjoints dont les extrémités sont des entiers relatifs par la liste ordonnée de leurs extrémités, selon l'ordre croissant. On admet que cette liste est alors convenable. Par exemple, [ − 1, 2] ∪ [4, 7] ∪ [ − 3, − 2] ∪ [8, 8] est représentée par la liste − 3, − 2, − 1, 2, 4, 7, 8, 8. L'ensemble vide est représenté par la liste vide.
a) Ecrire la procédure :
Convenable
    données L:liste d'entiers
    résultat b:booléen
qui prend en entrée une liste d'entiers L et retourne la valeur 1 si elle est convenable et 0 sinon.
b) On admet que l'intersection de deux réunions finies d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs est aussi une réunion finie d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs. Par exemple, l'intersection de [1, 2] ∪ [4, 5], représenté par la liste convenable 1, 2, 4, 5 et de [ − 1, 3] ∪ [5, 7] ∪ [8, 9], représenté par la liste convenable − 1, 3, 5, 7, 8, 9, est [1, 2] ∪ [5, 5] représenté par la liste convenable 1, 2, 5, 5. Ecrire la procédure :
Intersection
    données }\quad\mp@subsup{L}{1}{}\mathrm{ :liste convenable d'entiers
        L2:liste convenable d'entiers
    résultat L':liste convenable d'entiers
qui prend en entrée deux listes convenables d'entiers représentant chacune une réunion finie d'intervalles fermés disjoints, respectivement F_1 et F_2, et retourne la liste convenable d'entiers représentant la décomposition en réunion finie d'intervalles fermés disjoints de l'ensemble F_1 ∩ F_2.
c) On admet que la réunion de deux réunions finies d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs est aussi une réunion finie d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs. Par exemple, la réunion de [1, 2] ∪ [4, 5], représenté par la liste convenable 1, 2, 4, 5 et de [ − 1, 3] ∪ [5, 7] ∪ [8, 9], représenté par la liste convenable − 1, 3, 5, 7, 8, 9, est [ − 1, 3] ∪ [4, 7] ∪ [8, 9] représenté par la liste convenable − 1, 3, 4, 7, 8, 9. Ecrire la procédure :
Reunion
    données Li:liste convenable d'entiers
        L2:liste convenable d'entiers
    résultat L':liste convenable d'entiers
qui prend en entrée deux listes convenables d'entiers représentant chacune une réunion finie d'intervalles fermés disjoints, respectivement F_1 et F_2, et retourne la liste convenable d'entiers représentant la décomposition en réunion finie d'intervalles fermés disjoints de l'ensemble F_1 ∪ F_2.

Exercice 6

Si L est un langage sur un alphabet fini Σ et si n est un entier naturel non nul, on note L(n) le langage formé par les mots de L qui sont de longueur n.
  1. Justifier que le langage L(n) est de cardinal fini.
Dans la suite, on note u_n^L le cardinal du langage L_n.
2. Dans cette question, l'alphabet Σ désigne l'alphabet à trois lettres Σ = {a, b, c} et L est le langage des mots finis sur Σ qui contiennent au moins un c. Ce langage est donné par l'expression rationnelle :
L = {a, b}^∗ c{a, b, c}^∗
a) Dessiner un automate déterministe à deux états qui reconnait exactement le langage L.
b) Soit n un entier naturel non nul.
i) Dessiner un automate qui reconnait exactement le langage L(n).
ii) On suppose n ⩾ 2. Soit U_(n − 1) le langage {a, b, c}^∗(n − 1). Démontrer que L(n) est la réunion disjointe des langages {a, b}L(n − 1) et cU_(n − 1). En déduire la relation de récurrence :
u_n^L = 2u_(n − 1)^L + 3^(n − 1).
iii) Exprimer u_n^L en fonction de n.
3. Dans cette question, on suppose que L est le langage reconnu par un automate déterministe A = (Q, Σ, 1, f, δ) où :
  • Q est l'ensemble fini des états de A. On note m son cardinal et on suppose que m est un entier naturel ⩾ 2. Les états dans Q sont numérotés de 1 à m.
  • 1 est le numéro de l'état initial de A,
  • f est le numéro de l'unique état final de A,
  • δ est la fonction de transition de A définie d'une partie de Q × Σ dans Q.
On considère la matrice (m, m)M = (m_(i, j)) définie par : m_(i, j) est le nombre de transitions de source l'état i et de but l'état j dans l'automate A. On note χ_M(X) = X^m − ∑_(k = 0)^(m − 1)a_(m − k)X^k le polynôme caractéristique de la matrice M.
Pour tout état j de Q, on note L_j le langage reconnu par l'automate ( Q, Σ, j, f, δ ); ainsi défini, L_1 = L. Pour tout entier n ⩾ 1, soit V(n) le vecteur de coordonnées x_1, …, x_m où x_j est le cardinal du langage L_j(n), pour tout j dans Q.
a) Expliciter les coordonnées du vecteur V(1) en fonction de δ.
b) Démontrer que, pour tout entier n ⩾ 2 et pour tout j dans Q, L_j(n) est la réunion disjointe des langages aL_k(n − 1) pour tout ( j, a, k ) dans Q × Σ × Q tel que δ(j, a) = k.
c) En déduire, pour tout entier n ⩾ 2, l'égalité V(n) = M^(n − 1)V(1).
d) En utilisant le théorème de Cayley-Hamilton, démontrer que la suite (u_n^L) vérifie la relation de récurrence :
u_(n + m)^L = a_1 u_(n + m − 1)^L + a_2 u_(n + m − 2)^L + ⋯ + a_m u_n^L.
Dans le cas où χ_M a m racines distinctes α_1, …, α_m, que peut-on en déduire pour la suite (u_n^L) ?
4. Soit L le langage sur l'alphabet Σ = {a, b} reconnu par l'automate B = (Q, Σ, 1, 2, δ) ci-dessous :
Figure 1: Automate B
a) Donner une expression rationnelle de L.
b) Expliciter la suite (u_n^L)_(n ⩾ 1).

Exercice 7

Soit n un entier naturel ⩾ 2. Soit f une fonction booléenne à n variables. On dit que f définit implicitement sa n-ième variable si pour tout n-uplet ( x_1, …, x_(n − 1) ) de {0, 1}^(n − 1), il existe un unique x_n dans {0, 1} tel que f(x_1, …, x_n) = 0.
  1. Dans cette question, n = 2. Soit f_1 la fonction boolénne définie par ses valeurs présentées dans la table ci-dessous :
x_1 x_2 f_1(x_1, x_2)
0 0 1
0 1 0
1 0 0
1 1 1
Démontrer que f_1 définit implicitement sa seconde variable. Expliciter toutes les fonctions booléennes sur {0, 1}^2 qui définissent implicitement leur seconde variable.
Soit f une fonction booléenne à n variables.
2. Démontrer que f définit implicitement sa n-ième variable si et seulement si f vérifie la propriété suivante :
∀(x_1, …, x_(n − 1), x_n) ∈ {0, 1}^n, f(x_1, …, x_(n − 1), x¯_n) = f(x_1, …, x_n)^–.
  1. Soit f la fonction booléenne définie par :
∀(x_1, …, x_(n − 1), x_n) ∈ {0, 1}^n, f(x_1, …, x_n) = x_1 x_2…x_n + ∑_(i = 1)^(n − 1)x¯_i x¯_n.
Démontrer que f définit implicitement sa n-ième variable. Démontrer plus précisément qu'il existe une fonction booléenne g sur {0, 1}^(n − 1), telle que
∀(x_1, …, x_(n − 1), x_n) ∈ {0, 1}^n, (f(x_1, …, x_n) = 0 ⇔ x_n = g(x_1, …, x_(n − 1))).
Préciser g.

Pas de description pour le moment