E3A Informatique MP 2008

Thème de l'épreuve Six exercices d'informatique
Principaux outils utilisés programmation impérative et récursive, langages, fonctions booléennes

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


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.

Extrait du corrigé obtenu par reconnaissance optique des caractères


 E3A Informatique MP 2008 -- Corrigé Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par Vincent Puyhaubert (Professeur en CPGE) et Guillaume Batog (ENS Cachan). Le sujet comporte sept exercices indépendants. Ils se répartissent entre trois grandes thématiques : · Programmation : L'exercice 1 propose de trier une liste par dénombrement et de calculer la complexité d'un tel algorithme, dans le pire ou le meilleur des cas ainsi qu'en moyenne. Une bonne maîtrise du calcul de complexité est donc nécessaire. L'exercice 2 est composé de deux questions indépendantes. La première construit un programme pour remplir une matrice à partir des coefficients d'une liste donnée ; la seconde calcule le plus grand nombre de valeurs identiques consécutives dans un tableau donné. L'exercice 3 propose de trouver ce que calculent trois programmes écrits en pseudo-code. Il s'agit d'un exercice difficile dans lequel il faut avoir une bonne intuition, comprendre le but de chacune des variables utilisées et savoir rédiger une réponse satisfaisant le correcteur. L'exercice 4 demande d'écrire un programme restituant une liste d'entiers vérifiant une condition particulière visible sur leur écriture en base 10. L'exercice 5, nettement plus difficile d'un point de vue algorithmique, propose de représenter une union finie d'intervalles fermés disjoints à l'aide de la liste ordonnée de leurs extrémités. Il faut alors réaliser une fonction qui décide si une liste ordonnée correspond à une telle réunion, puis écrire deux fonctions qui réalisent respectivement les opérations d'intersection et d'union. · Automates : l'exercice 6 propose de calculer le cardinal de l'ensemble des mots de longueur n d'un langage rationnel. Il nécessite une bonne aptitude à manipuler les langages et les automates finis, et utilise le formalisme mathématique de l'algèbre linéaire (en particulier le théorème de Cayley-Hamilton). · Logique : l'exercice 7 étudie une classe particulière de fonctions booléennes pour lesquelles il est possible d'appliquer un théorème des fonctions implicites, en détaillant deux exemples. Pour le résoudre, il faut avoir bien compris la différence entre une fonction booléenne et son évaluation en une valeur de vérité. Il s'agit d'un sujet typique du concours E3A : une longue suite d'exercices très éloignés les uns des autres, de difficultés différentes. On a tout intérêt à le lire en entier au début de l'épreuve afin de sélectionner l'ordre dans lequel traiter les exercices. Il n'est pas nécessaire de faire l'ensemble du sujet pour avoir une note correcte : il vaut mieux explorer en détail quelques exercices plutôt qu'aborder superficiellement chacun d'entre eux. Indications 1.a Faire attention à la convention Caml qui numérote les tableaux à partir de 0. Un seul passage sur la liste suffit à résoudre le problème. 1.b Pour la complexité en moyenne, supposer que les entiers N et n sont fixés. Combien y a-t-il alors de listes L possibles ? Quel est le coût d'une exécution de l'algorithme sur une liste fixée, en fonction de ses coefficients ? En déduire une majoration la plus simple possible de la complexité en moyenne. 2.a Initialiser la matrice M avec la matrice nulle puis remplacer ses coefficients par ceux de la liste L tant que c'est possible. 2.b Parcourir le tableau T en mémorisant la longueur du plus grand plateau rencontré et la longueur du plateau courant (remarquer qu'un tableau se décompose en plateaux, éventuellement réduits à un seul élément). 3.a Commencer, au brouillon, par décrire l'exécution du programme sur l'entrée [1, 2, 2, 3, 1], puis essayer de trouver le rôle de chacune des variables. 3.b Écrire proprement les appels récursifs sur l'exemple (N = 7, p = 3) et relier ce calcul au nombre de manières de décomposer N en une somme de p entiers strictement positifs. 3.c Les deux premiers tests inclus dans la boucle pour sont à comprendre comme des cas disjoints. En particulier, ne pas rentrer dans le second test lorsque le premier a été positif. Corriger cette erreur puis essayer de faire tourner l'algorithme sur le tableau [5, -1, 1, 2, -3, -2, 1, 3, 2]. 4 Décomposer le problème en commençant par écrire une fonction qui teste si un entier à trois ou quatre chiffres est un nombre d'Armstrong. 5.a Écrire une fonction auxiliaire récursive prenant en entrée une liste L et un entier i et vérifiant que L est une liste convenable, dont le premier élément est strictement supérieur à i. 5.b, 5.c Il est possible d'écrire ces fonctions de manières récursives, à condition de bien penser aux cas de base. 6.2.b.i Préférer écrire un automate déterministe reconnaissant le langage L(n). Commencer par les petites valeurs de n. 6.2.b.iii Conjecturer au brouillon la valeur de la suite récurrente linéaire, puis prouver le résultat par récurrence. 6.3.b Raisonner par double inclusion, en utilisant la définition du langage Lj (n). 6.3.c Montrer que, pour tout n > 2, V(n) = M V(n-1) en exprimant les différentes coordonnées des deux vecteurs, puis conclure par récurrence. 6.4.b Utiliser l'idée développée à la question 6.3.d pour exprimer le terme uL n dans ce cas particulier. 7.2 Pour le sens direct, ne pas oublier qu'une fonction booléenne ne peut prendre que deux valeurs (0 ou 1). 7.3 Pour exhiber la fonction g, distinguer le cas du (n - 1)-uplet (x1 , . . . , xn-1 ) dont toutes les composantes valent 1, des autres. Rappelons ici quelques conseils que le jury livre chaque année dans ses rapports. L'épreuve étant essentiellement tournée vers la programmation, il est primordial que les candidats se préparent à cette épreuve : il est en effet plus délicat de proposer un programme correct sans pouvoir le tester sur machine. Même si le jury est clément sur les petites erreurs de syntaxe, le candidat doit s'efforcer de produire un code clair, indenté et largement commenté. Il peut aussi être intéressant de décrire rapidement le rôle d'une variable introduite dans un programme en expliquant son initialisation, ou de découper un programme long en plusieurs sous-programmes dont on décrit la finalité. Les exercices plus théoriques doivent être résolus comme s'ils faisaient partie d'une épreuve de mathématiques : les réponses doivent être concises, mais argumentées précisément. Exercice 1 1.a Afin d'écrire un programme correct en Caml, dans lequel un tableau de taille N est numéroté de 0 à N - 1, on choisit de modifier légèrement le résultat demandé par l'énoncé. Ainsi la fonction tri_denombrement prend en entrée un entier N et une liste L d'entiers compris entre 1 et N et renvoie un tableau M de taille N + 1 dont la case d'indice 0 contient 0 et dont la case d'indice k [[ 1 ; N ]] contient le nombre d'éléments égaux à k dans la liste L. Le programme écrit ci-dessous utilise une fonction auxiliaire passage, récursive, qui prend en entrée une liste et remplit convenablement le tableau M, élément après élément : à chaque fois que la valeur k est rencontrée dans la liste L, on incrémente la case d'indice k du tableau M. let tri_denombrement N L = let M = make_vect (N+1) 0 in let rec passage liste = match liste with | [] -> M | k::reste -> M.(k)<-M.(k)+1; passage reste in passage L;; Cette fonction n'est pas un algorithme de tri : pour faire cela, il faut reconstituer la liste triée des éléments de L à partir du tableau M. Présentons un exemple de fonction implémentant cette amélioration. Le programme récursif auxiliaire permet de limiter le nombre d'accès à une case du tableau M, puisque cette opération est supposée coûteuse dans cet exercice. let tri N L = let M = tri_denombrement N L in let rec range i k = (* renvoie la liste triée comprenant *) (* tous les éléments de L inférieurs à i *) if (i=N)&&(k=0) then [] else if k=0 then range (i+1) M.(i+1) else i::(range i (k-1)) in range 0 M.(0);; 1.b La seule opération élémentaire considérée ici est l'accès à une case de tableau : on suppose ici que cette opération a un coût linéaire en l'indice de la case voulue. Cette hypothèse, imposée par l'énoncé, est assez étrange puisque, contrairement à une liste, on a coutume de considérer que l'accès à un élément donné d'un tableau se fait en temps constant en Caml. Appelons n la longueur de la suite L. Remarquons que la seule opération coûteuse est l'accès à la case d'indice x du tableau M : cela coûte O(x). · Complexité dans le meilleur des cas : tous les éléments de la liste L sont égaux à 1 et donc chaque accès à une case a une complexité en O(1). La complexité dans le meilleur des cas est en O(n). · Complexité dans le pire des cas : tous les éléments de la liste L sont égaux à N et donc chaque accès à une case a une complexité en O(N). La complexité dans le pire des cas est majorée par C n N, où C est une constante indépendante de n et N. Mieux vaut éviter la notation O(nN) puisque les notations de Landau ne sont traditionnellement définies que pour une suite dépendant d'un unique paramètre. · Complexité en moyenne : précisons ici l'énoncé. On suppose que N et n sont des entiers fixés et on fait varier la liste L donnée en entrée de l'algorithme. L'ensemble des listes L possibles est un ensemble fini. Chaque élément de la liste peut prendre une valeur entre 1 et N. Comme elle est de taille n, l'ensemble des listes est de cardinal Nn . On considère donc que chaque liste a une chance sur Nn d'apparaître. Afin de calculer la complexité en moyenne, il faut donc trouver le coût de calcul sur chacune des listes. Considérons une liste fixée L : elle contient les éléments 1 , . . . , n . La complexité totale de l'exécution de l'algorithme sur la liste L est majorée par C (i +· · ·+n ) où C est une constante indépendante de la liste L et des entiers n et N. Ainsi, en sommant sur l'ensemble des listes L, la complexité en moyenne est majorée par N N P C P ··· (1 + · · · + n ) n N 1 =1 n =1 Quitte à réordonner la somme, il suffit de compter le nombre de fois qu'apparaît chaque valeur k [[ 1 ; N ]] parmi les termes i . Le nombre total de termes étant n Nn , et chaque valeur apparaissant un nombre identique de fois pour des raisons de symétrie, on en déduit que chaque valeur k [[ 1 ; N ]] apparaît n Nn-1 fois. Ainsi, la complexité en moyenne est majorée par N N C P Cn P C n N (N + 1) C n (N + 1) k n Nn-1 = k= = n N k=1 N k=1 N 2 2 Le tri par dénombrement a une complexité C n (N + 1) en moyenne majorée par . 2