E3A Informatique MP 2007

Thème de l'épreuve Six exercices d'informatique
Principaux outils utilisés programmation impérative et récursive, langage d'un automate, formules logiques

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


Z12L e 3 a CONCOURS ENSAM - ESTP - ARCHIMEDE Épreuve d'Informatique MP durée 3 heures 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 la calculatrice est interdit Indiquer en tête de copie ou de chaque exercice le langage utilisé Exercice 1 &) Ecrire la fonction Sym données M : tableau à deux dimensions n : entier résultat 56 : boolêen qui prend en entrée le tableau des coefficients d'une matrice carrée de taille n et renvoie la valeur 1 si la matrice est symétrique et 0 sinon. (9) Ecrire la fonction Egalite--listes données L : liste L' : liste résultat b : booléen qui prend en entrée deux listes et renvoie la valeur 1 si les deux listes sont égales et 0 sinon. Ces listes contiennent des entiers positifs ou nuls et se terminent par la valeur --1. c) Un tableau d'entiers T est dit trié par ordre croissant si ses entrées sont triées par ordre croissant : si l est la longueur du tableau, Vi,j EUR {1, ..., l},i < j => T[i] { T[j]. Il est dit trié par ordre décroissant si ses entrées sont triées par ordre décroissant : si l est la longueur du tableau, Vi, j EUR {1, ..., l},i < j => T [2] > T ... Dans les deux cas, il est dit trié. Remarquons qu'un tableau T peut être à la fois trié dans l'ordre croissant et dans l'ordre décroissant, s'il vérifie : si l est la longueur du tableau, Vi, j EUR {1, ..., I}, T [i] = T [3] Il alors est dit constant. Ecrire la fonction Test--tri données T : tableau d'entiers l : entier résultat a: : entier qui prend en entrée un tableau T de longueur 1 et retourne la valeur 1 si le tableau T est trié par ordre croissant et non constant, --1 si T est trié par ordre décroissant et non constant, 0 si T est constant et 2 si T n'est pas trié. Ecrire la procédure Fusion données T : tableau d'entiers l : entier U : tableau d'entiers m : entier résultat W : tableau d'entiers trié qui fusionne deux tableaux triés tous deux par ordre croissant (respectivement tous deux triés par ordre décroissant), de longueurs respectives l, m ; le résultat est un tableau trié par ordre croissant (respectivement par ordre décroissant) de longueur 1 + m. Dans le cas où les deux tableaux ne sont pas tous deux triés dans un même ordre, la procédure Fusion renverra un tableau vide et un message d'avertissement. Exercice 2 a) Que retourne le programme suivant : S <-- 2007 i <-- 1 tant que (i2 < S) faire i<---- @ + 1 fin tant que afficher(i) b) Que calculent les procédures suivantes : TR(N : entier, T : tableau d'entiers de longueur N, 1 : entier, m : entier) si (1 5 l) et (l 5 m) et (m S N) faire pour (2°: 1) â(i=m--l+l) faireTR[i] <--T[l--1+i] retourner TR fin si Valeur(N : entier, T : tableau d'entiers de longueur N, l : entier) si (1 5 l) et (l 5 N) faire a: <-- T... 9 <-- 0 d +-- N + 1 j <-- 1 tant que (j 5 N) faire si (T... <æ) faire g+--g+1 Ulÿl <-- TÜl si (T... >:13) faire d<--d--1 Uldl *-- TU] fin si j <-- j + 1 fin tant que si (9 < 1 < d) afficher :1: sinon si (1 _<_ 9) faire Valeur(g,TR(N, U, 1,9), !) si (l 2 d) faire Valeur(N ---- d + 1, TR(N, U, d, N),l -- d + 1) fin si sinon retourner "! NON VALIDE" fin si Exercice 3 Soit n un entier naturel. On dit que n est un nombre parfait si 277. est la somme des entiers naturels diviseurs de n. Par exemple, l'entier 6 est un nombre parfait puisque 2 >< 6 = 12 = 6 + 3 + 2 + 1. Ecrire un programme qui détermine la liste des nombres parfaits n tels que n _<_ 9999. Exercice 4 Un entier naturel 77. étant donné, on calcule le produit prod(n) de ses chiffres dans son écriture en base 10, puis le produit des chiffres de prod(n) dans son écriture en base 10, et on recommence ainsi l'application de prod jusqu'à obtenir un chiffre entre 0 et 9. Le nombre minimal de fois où on applique prod pour transformer n en un chiffre entre 0 et 9 est appelé la persistance de n. Par exemple, la persistance de 9 est égale à. O, celle de 97 est égale à 3, car prod(97) = 9 >< 7 = 63,prod(ô3) = 6 >< 3 = 18,prod(18) = 1 >< 8 = 8, et celle de 9575 est égale à 5, car prod(9575) = 1575,pr0d(1575) = 175,prod(175) = 35,prod(35) = 15,prod(15) = 5. Ecrire un programme qui calcule le plus petit entier naturel de persistance 5. Exercice 5 On considère l'alphabet à deux lettres: 2 = {a, à}. Soit n un entier naturel non nul. Un buffer de taille n est modélisé par un automate A,, = (Q... A... 0,Fn) sur l'alphabet E défini par ; 0 Q... l'ensemble des états de A,, est l'ensemble {O, 1, 2, ..., n}. L'état i représente la présence de exactement z' bits dans le buffer. . La lettre & représente l'arrivée d'un bit dans le buffer. La lettre â représente la sortie d'un bit du buffer. . A... est l'ensemble des transitions de An : -- % EUR {O, ...n -- 1}, (i,a,z' + 1), ---- Vz' EUR {1,...,n}, (i,â,z' - 1), o 0 est l'état initial de A... . F,, = {O, ...,n} est l'ensemble des états finaux. On note En le langage reconnu par l'automate A... Dans la suite, 6 désigne le mot vide. 1. Soient m, n des entiers naturels non nuls. Justifier précisément l'équivalence : £...C£n©m b. Que signifie ceci pour les avions de cette compagnie ?

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


 E3A Informatique MP 2007 -- Corrigé Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été relu par Guillaume Batog (ENS Cachan) et Benjamin Monmege (ENS Cachan). Ce sujet comporte six exercices complètement indépendants qui permettent de réviser la quasi-totalité du cours d'informatique. La difficulté n'est pas homogène : certains exercices ne posent guère de difficultés tandis que d'autres nécessitent des rédactions délicates. · Le premier exercice concerne la programmation sur des listes et des tableaux. Les codes demandés ne sont pas compliqués. Il faut en revanche réfléchir un peu si l'on ne veut pas se retrouver à écrire des fonctions d'une page de long. · Le deuxième exercice propose de reconnaître des morceaux de codes. Les deux premiers se comprennent très facilement. En revanche, le dernier est plus délicat à identifier et l'explication de son rôle n'est de surcroît pas simple à rédiger. · Les exercices 3 et 4 demandent d'écrire des fonctions d'arithmétique. Les codes sont simples et très courts. · Le cinquième est un problème classique d'automates. C'est la partie la plus difficile à rédiger même si l'intuition du résultat vient rapidement. · Pour finir, le sixième exercice porte sur la logique. Il est court et sans prétention. Tout ceci constitue finalement une épreuve variée et intéressante bien qu'elle ne propose pas l'étude approfondie d'une problématique précise. C'est un très bon sujet pour vérifier que l'on maîtrise l'ensemble des connaissances du programme. Indications 1.a Utiliser des boucles pour parcourir le tableau tout en comparant les données d'indices (i, j) et (j, i). 1.b Écrire une fonction récursive qui compare dans un premier temps les têtes de listes puis effectue un appel récursif sur les queues. 1.c Utiliser la variable x comme une variable indiquant l'état possible du tableau et initialisée à 0 (le tableau est supposé constant au départ). Comparer T[i] et T[i+1] pour i allant de 0 à - 1 et mettre à jour la variable x en fonction des résultats des tests. Pour le programme de fusion, commencer par déterminer l'ordre des tableaux puis écrire une version modifiée de la fonction de fusion vue en cours sur les tris. 2.a Justifier que le code retourne la plus petite valeur dont le carré est supérieur à 2007. 2.b Justifier que la première fonction extrait une partie d'un tableau T. Démontrer ensuite que la seconde fonction renvoie la -ième plus petite valeur pour l'ordre naturel sur les entiers parmi les éléments du tableau T. 3 Écrire dans un premier temps un programme qui calcule la somme des diviseurs d'un entier n (qui fonctionne à l'aide d'une boucle). 4 Écrire une fonction récursive qui calcule le produit des chiffres d'un entier n en utilisant la division euclidienne de n par 10. Écrire ensuite un code récursif qui calcule la persistance d'un entier n. Remarquer que sauf cas particulier, cette dernière est égale à celle du produit des chiffres de n augmentée de 1. 5.1 Prouver que si m > n, le mot am est rejeté dans l'automate An à la lecture du (n + 1)-ième a. 5.2 Justifier que L1 = {aa} {, a}. 5.3 Décomposer un mot u de L2 suivant le parcours effectué dans A2 à la lecture de ce mot. 5.4.a Utiliser une technique similaire à la question précédente, sachant que l'on doit revenir à 0. 5.4.b Même remarque qu'à la question précédente, sachant que l'on doit cette fois aboutir en j. 5.4.c Démontrer par récurrence sur n que l'on peut calculer une expression de L0,j n pour tout entier n et tout j [[ 0 ; n ]]. S Remarquer ensuite que Ln = 06j6n L0,j n . 6.1 Utiliser le connecteur logique = pour représenter les formules. 6.2 On rappelle que x = y est équivalent à (¬x) y. 6.3 Démontrer l'impossibilité de contredire la formule à l'aide de la table de vérité. Pour une épreuve touchant à des domaines aussi variés du programme, il est difficile de dresser une synthèse globale des difficultés rencontrées par les élèves. Toutefois, la lecture du rapport révèle deux principaux écueils : · les programmes obscurs et/ou non commentés ; si le jury n'accorde pas une importance démesurée à la justesse syntaxique, il est toutefois sensible au fait que chaque fonction soit dissociée en plusieurs sousprogrammes ou que chaque partie du code comporte des explications. · les questions théoriques mal justifiées ; il est fréquent que les résultats de certaines questions soient rapidement devinés, mais les élèves sont parfois incapables de les justifier rigoureusement. Le rapport du jury rappelle donc à juste titre que les épreuves d'informatique nécessitent autant de rigueur que celles de mathématiques. Exercice 1 1.a L'énoncé n'est pas clair dans cette question. La variable resultat suggère de renvoyer un booléen. Pourtant, 0 ou 1 sont du type entier. Faisons donc le choix de respecter la signature de la fonction, et donc de renvoyer des booléens. Pour déterminer si une matrice A est symétrique, il suffit de vérifier la définition c'est-à-dire vérifier que Ai,j = Aj,i pour tout (i, j) [[ 1 ; n ]]2 . Il suffit pour cela d'utiliser deux boucles imbriquées qui parcourent tous les couples d'indices (i, j) [[ 1 ; n ]]2 . On peut toutefois remarquer que l'on peut se contenter des couples satisfaisant i < j pour raccourcir les boucles. Par défaut, la matrice est supposée symétrique. La variable x est ainsi initialisée à true. Lorsqu'on trouve un couple (i, j) qui ne vérifie pas la condition Ai,j = Aj,i , cette variable passe à false et l'exécution peut s'arrêter. À la fin de l'exécution, il n'y a plus qu'à renvoyer le contenu de x. On obtient alors le code suivant. Le type 'a vect vect est ici utilisé pour M mais d'autres possibilités sont envisageables (comme le type 'a list list). let Sym M n = let x = ref true and i = ref 0 and j = ref 1 in while !x = true && !i < n do while !x = true && !j < n do if M.(!i).(!j) <> M.(!j).(!i) then x := false; incr j; done; incr i; j:=i+1; done; !x;; Comme dans la plupart des codes testant si un certain nombre de propriétés sont satisfaites par une donnée, on gagne du temps en stoppant l'exécution quand une condition n'est pas satisfaite. Il faut bien noter toutefois que cela ne change jamais la complexité dans le pire des cas, et que l'on améliore rarement l'ordre de grandeur de la complexité moyenne (qui ici reste en O n2 opérations élémentaires). 1.b Pour tester si deux listes sont égales, il suffit de vérifier si leurs têtes et leurs queues sont égales. Cela donne la version récursive suivante de la fonction Egalite_listes. La récursivité s'arrête lorsque l'on atteint la fin d'une liste (à savoir une valeur -1), auquel cas il faut simplement vérifier que l'on est également à la fin de l'autre liste. let rec Egalite_listes L L' = match (L,L') with |([-1],_) -> (hd L') = [-1] |(_,[-1]) -> (hd L) = [-1] |(a::q,b::r) -> if a=b then Egalite_listes q r else false |(_,_) -> failwith "Liste non conforme" ;; Le symbole "-" de tiret est interprété comme une soustraction par Caml et ne peut être utilisé au sein d'un nom de variable. C'est pourquoi il a été remplacé par le symbole "_" (tiret bas, ou plus communément underscore) dans le nom de la fonction Egalite_listes. Suivre scrupuleusement le nom choisi par l'énoncé conduit à une erreur de compilation. Le programme donné ci-dessus ne fonctionne que pour les listes respectant les conventions de l'énoncé. Notamment, il ne s'applique que pour des listes d'entiers, et génère une erreur s'il n'y a pas de -1 dans l'une des listes. Il est très facile de modifier le programme précédent pour qu'il fonctionne quel que soit le type de liste : let rec Egalite_listes L L' = match (L,L') with |([],_) -> L' = [] |(_,[]) -> L = [] |(a::q,b::r) -> (a=b)&&(Egalite_listes q r) ;; Au passage, on profite de l'évaluation paresseuse des booléens pour raccourcir le code (l'appel récursif n'est effectué que si le premier test a réussi). 1.c Pour déterminer la nature d'un tableau, initialisons la variable x à 0, ce qui signifie que le tableau est supposé constant par défaut. Parcourons alors le tableau de gauche à droite en comparant T[i] et T[i+1] pour i allant de 0 à n - 1, en mettant à jour la variable x. Tant que la variable est à 0, plusieurs cas sont envisageables : · T[i] < T[i+1] : le tableau ne peut plus être constant. En revanche, il peut toujours être rangé par ordre croissant. On passe donc la variable x à 1. · T[i] > T[i+1] : à nouveau, le tableau ne peut plus être constant. Cependant, il peut être rangé par ordre décroissant. On passe donc la variable x à -1. · T[i] = T[i+1] : il n'y a rien à faire. Lorsque l'on est passé dans l'état 1, il n'y a plus que deux cas de figures pour la mise à jour de x : · T[i] <= T[i+1] : il n'y a rien à faire. · T[i] > T[i+1] : le tableau ne peut plus être trié ni par ordre croissant, ni par ordre décroissant. On passe donc la variable x à 2.