e3a Informatique MP 2008

12AN

9238

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'unepart 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é N I L.

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 à le
dans la liste L, pour tout entier k compris entre 1 et N.

I)) 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 le, 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
77. : 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 le et de longueur .
l est une suite de 1 indices consécutifs z',z° + 1, ...,i + Z ---- 1 sur 
lesquels T prend la valeur k: (T[7Ç] :
T[z° + 1] == --- : T[i +l --- 1] = le). 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 1 : 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.)

@) Qu'efiectue le programme ci--dessous :

PROG(L : liste d'entiers )

L2 <-- liste_vide E' <-- premier_element(L) tant que (E <> NIL) faire
Eg <-- premier_element(L2) SW <-- 0 tant que(E2 <> NIL et SW : 0) faire
si(E : E2) alors SW <-- 1 sinon E2 <-- element_suivant(L2) fin si fin faire si (SW : 0) alors L2 <-- aj outer_element(E) fin si E <-- element_suivant(L) fin faire retournerL2 On remarquera que les listes considérées par ce programme se terminent par un élément de marquage de fin de liste appelé N I L. b) Décrire l'exécution du programme N BS ci-dessous sur l'entrée (7, 3) : N B S (N : entier strictement positif, p : entier strictement positif)) si (N  U) alors faire
CÎ+--.9
nz+--i
7L+--j
fin faire
fin si
fin faire
retourner(£fi7n,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 = 13 + 53 + 
33. Ecrire un
programme qui calcule tous les nombres d'Armstrong à trois ou quatre ehiflres.

Exercice 5

Une liste d'entiers est dite convenable si elle se compose d'un nombre pair 
d'éléments ..., b1, (Lg, b2, ...,
ak,bk tels que 611 < b1 < a2 < ----bk_1 < ak < b;,. 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] U [4, 7] U ]--3, ----2] U [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. &) 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] U [4, 5], représenté par la liste convenable 1, 2, 4, 5 et de [--1, 3] U [5,7] U [8, 9], représenté par la liste convenable ----1, 3, 5, 7, 8, 9, est [1,2] U [5, 5] représenté par la liste convenable 1, 2, 5, 5. Ecrire la procédure : Intersection données L1 : 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 dis'oints res ectivement F1 et F2 et retourne la liste convenable d'entiers re résentant la dé-- ...] 7 P 7 P composition en réunion finie d'intervalles fermés disjoints de l'ensemble F1 0 F2. 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 [l, 2] U [4, 5], représenté par la liste convenable 1, 2, 4, 5 et de [----1, 3] U [5,7] U [8, 9], représenté par la liste convenable --1, 3, 5, 7, 8, 9, est [----1, 3] U [4, 7] U [8, 9] représenté par la liste convenable --1, 3, 4, 7, 8, 9. Ecrire la procédure : Reunion données L1: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 dis'oints res ectivement F et F2 et retourne la liste convenable d'entiers re résentant la dé-- 7 1 ) composition en réunion finie d'intervalles fermés disjoints de l'ensemble F1 U F2. Exercice 6 Si C est un langage sur un alphabet fini 2 et si n est un entier naturel non nul, on note £(n) le langage formé par les mots de E qui sont de longueur n. 1. Justifier que le langage £(n) est de cardinal fini. Dans la suite, on note uf,' le cardinal du langage En. 2. Dans cette question, l'alphabet E désigne l'alphabet a trois lettres 2 = {a, 19,0} et E est le langage des mots finis sur E qui contiennent au moins un c. Oe langage est donné par l'expression rationnelle : E = {a, b}*c{a, b, c}*. a) Dessiner un automate déterministe a deux états qui reconnait exactement le langage £. b) Soit n un entier naturel non nul. i) Dessiner un automate qui reconnait exactement le langage £(n). ii) On suppose n > 2. Soit Un_1 le langage {a,b,c}*(n --- 1). Démontrer que 
£(n) est
la réunion disjointe des langages {a, b}£(n -- 1) et cUn_1. En déduire la 
relation de

récurrence :
£ __ £ n--1

£

,, en fonction de n.

iii) Exprimer u

3. Dans cette question, on suppose que C est le langage reconnu par un automate 
déterministe

.À= (Q,E,1,f,ô) où:

0 Q est l'ensemble fini des états de A. On note m son cardinal et on suppose 
que m est un
entier naturel 2 2. Les états dans Q sont numérotés de 1 a m.

o 1 est le numéro de l'état initial de A,
0 f est le numéro de l'unique état final de A,

0 5 est la fonction de transition de A définie d'une partie de Q >< E dans Q. On considère la matrice (m, m) M = (m...-) définie par : m,,j est le nombre de transitions de source l'état z' et de but l'état j dans l'automate A. On note XM(X ) = X "" -- Ë__Ë (?......ka le polynôme caractéristique de la matrice M. Pour tout état j de Q, on note £j le langage reconnu par l'automate (Q, 2, j, f, 5) ; ainsi défini, £1 : .C. Pour tout entier n > 1, soit V(n) le vecteur de coordonnées @, ...,oem 
où a:,-- est le
cardinal du langage [i,--(n), pour tout j dans Q.

a) Expliciter les coordonnées du vecteur V(1) en fonction de 5 .

b) Démontrer que, pour tout entier n > 2 et pour tout j dans Q, £j(n) est la 
réunion disjointe
des langages a/Ç;,,(n -- 1) pour tout (j, a, 143) dans Q >< 2 >< Q tel que ô(j, &) = k. c) En déduire, pour tout entier n > 2, l'égalité V(n) : M "_1V(1).
£

,,) vérifie la relation

d) En utilisant le théorème de Cayley--Hamilton, démontrer que la suite (u

de récurrence :

.C _ .C C [.
un+m "" alun+m--l + a2un+m--2 + ' ° ' + amun '

Dans le cas où XM a m racines distinctes 011, ..., a..., que peut--on en 
déduire pour la suite
£ ?
(un) -

4. Soit E le langage sur l'alphabet E = {a, b} reconnu par l'automate B = (Q, 
2, 1, 2, 5) ci--dessous :

Figure 1: Automate B

a) Donner une expression rationnelle de £.

b) Expliciter la suite (uâ)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 (au, ..., oen_1) de {O, 
1}"_1, il existe un unique
fin dans {D, 1} tel que f(oe1,...,æn) : O.

1. Dans cette question, n = 2. Soit f1 la fonction boolénne définie par ses 
valeurs présentées dans
la table ci--dessous :

Démontrer que f1 définit implicitement sa seconde variable. Expliciter toutes 
les fonctions
booléennes sur {O, 1}2 qui définissent implicitement leur seconde variable.

Soit f une fonction booléenne a 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 :

V(oe1,...,oen_1,oen) EUR {07 1}n,f(OE1, ...,OEn_1,--În) : f(OE'1, °°°) fin)-

3. Soit f la fonction booléenne définie par :

n----l
V(oe1,...,oen_1,oen) EUR {0,1}",f(æ1,...,oen) : æ1oe2...oen + Zîfifin.
z'=1

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 9 sur {D,1}""', telle que

V(æ1,...,æn_1,oen) EUR {0,1}n, ( f(OE1,...,£En) : () <=> £En = g(æ1, ...,OEn_1) 
).

Préciser g.