Mines Informatique MP-PC-PSI 2015

Thème de l'épreuve Tests de validation d'une imprimante
Principaux outils utilisés algorithmique, bases de données, méthode d'Euler, méthode des trapèzes
Mots clefs checksum, arbre, codage de Huffman

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Énoncé obtenu par reconnaissance optique des caractères


A 2015 INFO. ECOLE DES PONTS PARISTECH. SUPAERO (ISAE), ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH MINES DE SAINT-ETIENNE, MINES NANCY, TELECOM BRETAGNE, ENSAE PARISTECH (Filiere MP). ECOLE POLYTECHNIQUE (Filiere TSI). CONCOURS 2015 EPREUVE D'INFORMATIQUE (Duree de l'epreuve : 1h30 heures) L'usage de l'ordinateur ou de la calculatrice est interdit. Sujet mis a la disposition des concours : Cycle international, Ecoles des Mines, TELECOM INT, TPE-EIVP. L'enonce de cette epreuve comporte 10 pages de texte. Si, au cours de l'epreuve, un candidat repere ce qui lui semble etre une erreur d'enonce, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amene a prendre. Tests de validation d'une imprimante Le sujet comporte des questions de programmation. Le langage a utiliser est Python dans les parties I a IV. Dans la partie V, on demande d'utiliser Scilab. Introduction Les imprimantes sont des systemes mecatroniques fabriques en grande serie dans des usines robotisees. Pour ameliorer la qualite des produits vendus, il a ete mis en place differents tests de fin de chaine pour valider l'assemblage des produits. Pour un de ces tests, un operateur connecte l'outil de test sur la commande du moteur de deplacement de la tete d'impression et sur la commande du moteur d'avance papier. Une autre connexion permet de recuperer les signaux issus des capteurs de position. Differentes commandes et mesures sont alors executees. Ces mesures sont envoyees par liaison de donnees sous la forme d'une suite de caracteres ASCII vers un ordinateur. Cet ordinateur va effectuer differentes mesures pour valider le fonctionnement de l'electromecanique de l'imprimante. L'ensemble des mesures et des analyses est sauvegarde dans un fichier texte. Cette sauvegarde s'effectue dans une base de donnees et, afin de minimiser l'espace occupe, les fichiers sont compresses. La base de donnees permet a l'entreprise d'ameliorer la qualite de la production par diverses etudes statistiques. Imprimante Carte mesures commandes Liaison de donnees Ordinateur Serveur SQL Rappels et definitions : · Une liste commence par un crochet [ et se termine par un crochet ]. Les elements d'une liste sont ordonnes (indexes). · On pourra utiliser la surcharge de l'operateur + : ['a']+['b']=['a','b']. · Un dictionnaire definit une relation une a une entre des cles et des valeurs. Celui-ci se note entre accolades {}. · Un tuple est une collection d'elements ordonnes comme dans une liste mais une fois le tuple cree, ses elements ne peuvent pas etre modifies independamment les uns des autres. Il se note entre parentheses (). Exemple : (4,'e',[1,3]) I Reception des donnees issues de la carte d'acquisition Les mesures sont faites a l'aide de convertisseurs analogique/numerique (CAN). Le resultat de conversion est code sur 10 bits signes en complement a 2. Q1. Quelle plage de valeurs entieres pourra prendre le resultat de la conversion ? 2/10 Q2. Si on considere que les valeurs analogiques converties s'etendent en pleine echelle de -5V a 5V, quelle est la resolution de la mesure en volt ? Une liaison serie asynchrone permet la communication entre la carte de commande/acquisition et le PC. Les echantillons correspondant a une mesure sont envoyes par la carte electronique sous la forme d'une trame (suite de caracteres ASCII). Cette suite de caracteres se presente sous la forme suivante : · un entete qui permet d'identifier la mesure sur un caractere ('U' tension moteur, 'I 'courant moteur, 'P' position absolue), · le nombre de donnees envoyees (3 caracteres), · les donnees constituees des mesures brutes issues de la conversion analogique-numerique, chaque mesure etant codee a l'aide du caractere '+' ou '-' suivi de 3 caracteres pour la valeur absolue, · un checksum, somme des valeurs absolues des donnees precedentes modulo 10000 sur 4 caracteres. Le nombre de donnees transmises n'est pas inclus dans le checksum. Exemple : Mesure de la tension sur 5 echantillons. Caracteres recus : 'U' '0' '0' '5' '+' '0' '1' '2' '+' '0' '0' '4' '-' '0' '2' '3' '-' '0' '0' '2' '+' '0' '4' '2' '0' '0' '8' '3' t La commande carac_recus=com.read(nbre_car) permet de recuperer nbre car caracteres recus sous la forme d'une chaine de caracteres. En supposant que les caracteres recus correspondent a l'exemple precedent, apres l'execution de carac_recus=com.read(5), la variable carac_recus contiendra la chaine "U005+". Apres une nouvelle execution de carac_recus=com.read(3), la variable carac_recus contiendra la chaine "012". Q3. Ecrire une fonction lect_mesures() en langage Python qui retourne une liste contenant : le type de la mesure ('U','I' ou 'P'), une liste contenant l'ensemble des valeurs des mesures recues et le checksum. Exemple : ['U',[12,4,-23,-2,42],83]. Cette fonction doit attendre que le caractere d'entete recu soit correct ('U','I' ou 'P') avant de realiser le stockage des informations dans la liste qui sera retournee. Q4. On suppose que toutes les mesures sont disponibles dans la liste mesures[], et le checksum recu dans la variable CheckSum. Ecrire une fonction check(mesure,CheckSum) en langage Python qui retourne True si la transmission presente un checksum valide et False sinon. Q5. Les mesures etant dans la liste mesures, ecrire une fonction affichage(mesure) en langage Python qui produit un affichage graphique comme represente en Figure 1, sachant que la resolution de la conversion analogique-numerique du courant est de 4 mA et que les mesures ont ete effectuees toutes les 2 ms. On ne demande pas de legender les axes ni de donner un titre a la figure. On suppose que les bibliotheques necessaires ont ete importees. 3/10 Courant moteur | 3.5 lntensite (A) l l l l l l l 0 50 100 150 200 250 300 350 400 Temps (ms) FIGURE 1 -- Affichage de la mesure. II Analyse des mesures La suite des valeurs de mesure du courant en Ampère du moteur de la tête d'impression est contenue dans une liste. Les mesures ont été effectuées toutes les 2 ms. Ces mesures sont disponibles dans la liste mesure. Deux traitements permettent de valider le fonctionnement de l'imprimante : o Le calcul de la valeur moyenne I...Oy du signal [(t) sur la durée d'acquisition. 1 tfmaz 1...Oy : / [(t) dt tfinal 0 . Le calcul de l'écart type [ec du signal [(t) sur la durée d'acquisition. 1 tfinal 160 = / (I(t) _ 1...Oy)2 dt tfinal 0 Q6. Écrire une fonction en langage Python qui retourne I...Oy après l'avoir calculée par la mé-- thode des trapèzes. Q7 . Écrire une fonction en langage Python qui retourne [ec après l'avoir calculé en utilisant la fonction précédente. III Base de données Une représentation simplifiée de deux tables de la base de données qu'on souhaite utiliser est donnée ci--dessous : 4/10 testfin nSerie dateTest ... Imoy Iec ... fichierMes 0.45 0.11 mesure31025.csv 230-588ZX2547 2012-04-22 14-25-45 230-588ZX2548 2012-04-22 14-26-57 0.43 0.12 mesure41026.csv .. .. .. .. .. .. .. . . . . . . . production Num nSerie dateProd type 20 230-588ZX2547 2012-04-22 15-52-12 JETDESK-1050 21 .. . 230-588ZX2549 2012-04-22 15-53-24 JETDESK-3050 .. .. .. . . . Apres son assemblage et avant les differents tests de validation, un numero de serie unique est attribue a chaque imprimante. A la fin des tests de chaque imprimante, les resultats d'analyse ainsi que le fichier contenant l'ensemble des mesures realisees sur l'imprimante sont ranges dans la table testfin. Lorsqu'une imprimante satisfait les criteres de validation, elle est enregistree dans la table production avec son numero de serie, la date et l'heure de sortie de production ainsi que son type. Q8. Rediger une requete SQL permettant d'obtenir les numeros de serie des imprimantes ayant une valeur de Imoy comprise strictement entre deux bornes Imin et Imax. Q9. Rediger une requete SQL permettant d'obtenir les numeros de serie, la valeur de l'ecart type et le fichier de mesures des imprimantes ayant une valeur de Iec strictement inferieure a la valeur moyenne de la colonne Iec. Q10. Rediger une requete SQL qui permettra d'extraire a partir de la table testfin le numero de serie et le fichier de mesures correspondant aux imprimantes qui n'ont pas ete validees en sortie de production. IV Preparation du fichier texte avant envoi : la compression Le fichier de resultat va etre stocke sous la forme d'un fichier binaire. Une des etapes de l'algorithme de compression utilise le codage de Huffman. IV.1 Presentation : Le codage de Huffman utilise un code a longueur variable pour representer un symbole de la source (par exemple un caractere dans un fichier). Le code est determine a partir d'une estimation des probabilites d'apparition des symboles de source, un code court etant associe aux symboles de source les plus frequents. La premiere etape du codage de Huffman consiste a creer un 5/10 dictionnaire contenant la liste des caractères présents dans le texte, associé a leur fréquence dans ce texte. Exemple : "AABCDCCEF" donnera {'A' :2, 'B' :1, 'C' :3, 'D' :1, 'E' :1, 'F' :1}. La deuxième étape consiste a construire un arbre de Hufin1an qui permet ensuite de coder chaque caractère. FIGURE 2 -- Arbre de Hufin1an. Notre texte "AABCDCCEF" de 9 caractères ASCII (72 bits) sera ainsi codé en binaire "10 10 010 1100011 11011001"(22 bits). Chaque caractère constitue une des feuilles de l'arbre a laquelle on associe un poids valant son nombre d'occurrences. Puis l'arbre est créé suivant un principe simple : on associe a chaque fois les deux noeuds de plus faibles poids pour créer un noeud dont le poids équivaut a la somme des poids de ses fils jusqu'à n'en avoir plus qu'un, la racine. On associe ensuite par exemple le code 0 a la branche de gauche et le code 1 a la branche de droite. Pour obtenir le code binaire de chaque caractère, on descend sur la Figure 2 de la racine jusqu'aux feuilles en ajoutant a chaque fois au code un 0 ou un 1 selon la branche suivie. Pour pouvoir être décodé par l'ordinateur, l'arbre doit aussi être transmis. Le code Python permettant de construire un arbre de Hufin1an et de coder chaque caractère est fourni en annexe. Les feuilles de l'arbre de Hufin1an (leaf) sont codées sous la forme de tuple avec comme pre-- mier élément le caractère et comme deuxième élément le poids. Pour l'arbre donné en exemple en Figure2,onaura6tuples: ('A',2), ('B',1), ('C',3), ('D',1), ('E',1) et ('F',1). Q11. La documentation de l'instruction isinstance(object , classinfo) décrit le fonctionne-- ment suivant : "Return True if the object is an instance of the classinfo argument. If object is not a class instance of the given type, the function returns False." Décrire succinctement le rôle des fonctions suivantes et indiquer le type de la variable retournée : . test() . get1() . get2() 6/10 IV.2 Analyse des fonctions make_huffman_tree() et freq_table() Q12. Donner le contenu des variables node1 et node2 suite a l'execution des commandes node1=make_huffman_tree(('F',1),('E',1)). node2=make_huffman_tree(('D',1),('B',1)). Q13. De meme, donner le contenu de la variable node3 suite a l'execution de la commande node3=make_huffman_tree(node1,node2). Q14. Donner le contenu de la variable f suite a l'execution de la commande f=freq_table('AABBCB'). IV.3 Analyse de la fonction insert_item() Cette fonction permet d'inserer un noeud ou une feuille dans une liste de noeuds et de feuilles tries par poids croissant, en conservant l'ordre de tri. Q15. Quelle est la particularite de cette fonction ? Q16. Montrer qu'un invariant d'iteration est "tous les elements de la sous liste lst[0 a pos-1] ont un poids inferieur a celui de la variable item". On demontrera qu'il est vrai a l'initialisation, puis a chaque iteration, sachant que cette fonction doit etre appelee avec l'argument d'entree pos=0 produisant ainsi une liste vide. IV.4 Analyse de build_huffman_tree() Q17. D'apres la description precedente et le resultat de la question Q13, commenter la fonction de maniere a expliquer comment l'arbre de Huffman est construit. On demande de proposer des redactions pour les commentaires correspondant aux lignes 8 dans la fonction build_huffman_tree(). Q18. Donner le nombre de tests dans le meilleur des cas et dans le pire des cas effectues dans la fonction insert_item() pour une liste lst contenant n elements. Les resultats devront etre justifies. Q19. Donner la complexite en temps dans le meilleur des cas et dans le pire des cas de la fonction build_huffman_tree pour une liste lst contenant n elements en tenant compte de la fonction insert_item. On negligera le cout en complexite de la fonction lst.sort. Les resultats devront etre justifies. Q20. Donner le contenu de la variable htree apres l'execution de la commande htree=build_huffman_tree("ZBBCB"). 7/10 Q21. Dessiner l'arbre de Huffman correspondant a htree de la question precedente en vous inspirant de la Figure 2. V Simulation physique Une possible source de pannes dans chaque imprimante est la defectuosite d'un moteur particulier. On suppose disposer d'enregistrements du signal d'entree e et du signal de sortie s de cet element. Ces variables sont supposees satisfaire une equation differentielle lineaire du premier ordre d s-e s = -k dt 10 ou k est un parametre reel strictement positif. On va chercher a verifier le bon fonctionnement du moteur en analysant des simulations. Q22. Ecrire en langage Scilab une fonction qui calcule de maniere approchee la solution de l'equation differentielle precedente pour le signal e(t) = sin(t), avec s(0) = 0, sur l'intervalle t [0,10] pour une valeur quelconque de k. La fonction doit retourner une estimation de s(t) aux instants [0, 0.1, 0.2,..., 10]. Q23. Trois valeurs sont possibles pour le parametre k : 0.5, 1.1 et 2. On decide de declarer le moteur defectueux si aucune de ces valeurs ne permet d'expliquer l'enregistrement s realise experimentalement aux instants [0, 0.1, 0.2,..., 10]. Definir un code Scilab utilisant la fonction precedemment definie pour realiser une validation ou une invalidation de la defectuosite du moteur suivant un critere a proposer. 8/10 Annexe Huffman tree : def make_leaf ( symbol , weight ) : return ( symbol , weight ) def test ( x ) : return isinstance (x , tuple ) and \ len ( x ) == 2 and \ isinstance ( x [0] , str ) and \ isinstance ( x [1] , int ) def get1 ( x ) : return x [0] def get2 ( x ) : return x [1] def get3 ( huff_tree ) : return huff_tree [0] def get4 ( huff_tree ) : return huff_tree [1] def get5 ( huff_tree ) : if test ( huff_tree ) : return [ get1 ( huff_tree ) ] # Attention le symbole est dans une liste else : return huff_tree [2] def get6 ( huff_tree ) : if test ( huff_tree ) : return get2q ( huff_tree ) else : return huff_tree [3] def make_huffman_tree ( left_branch , right_branch ) : return [ left_branch , right_branch , get5 ( left_branch ) + get5 ( right_branch ) , get6 ( left_branch ) + get6 ( right_branch ) ] def freq_table ( txt ) : ftble = {} for c in txt : if c not in ftble : ftble [ c ] = 1 else : ftble [ c ] += 1 return ftble 9/10 def freq_cmp(nodel, node2): freq1, freq2 = get6(nodel), get6(node2) if freq1 < freq2: return --1 elif freq1 > freq2: return 1 else: return 0 noeuds et feuilles def insert_item(item, lst, pos): if pos == len(lst): lst.append(item) elif freq_cmp(item, lst[pos]) <= 0 lst.insert(pos, item) else: insert_item(item, lst, pos+1) return def build_huffman_tree(txt): ftble = freq_table(txt) lst list(ftble.items()) lst.sort(key=lambda lst: lst[1]) if len(lst) == 0: return None elif len(lst) == 1: return lst[O] else: while len(lst) > 2: new_node = make_huffman_tree(lst[0], lst[1]) del lst[O] del lst[O] insert_item(new_node, lst, O) else: return make_huffman_tree(lst[0], lst[1]) Manual and Auto Generation of Huffman Trees in Python, Vladimir Kulyukin http : / / Vkedco . blogspot.fr/2012/02/manual--and--auto--generation--of--huffman.html Huffman tree generator http : //huffman. ooz . ie/ 10/10

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


 Mines Informatique PC 2015 -- Corrigé Ce corrigé est proposé par Julien Dumont (Professeur en CPGE) ; il a été relu par Guillaume Batog (Professeur en CPGE) et Jean-Julien Fleck (Professeur en CPGE). Le sujet porte sur différents aspects de tests de validation d'une imprimante. Les parties sont indépendantes. · La première partie porte sur la réception des données issues de la carte d'acquisition, en se concentrant plus particulièrement sur la trame contenant les informations. · La deuxième, très courte et proche du cours, met en place des programmes de calcul approché d'intégrales, qui sont utilisés pour obtenir la moyenne et l'écart-type des données physiques reçues dans les trames. · La troisième partie s'intéresse à la gestion d'un parc d'imprimantes en cours de validation à l'aide de bases de données. · La quatrième aborde le thème de la compression de données, principalement en étudiant un long programme fourni en annexe. · Enfin, la cinquième partie examine un schéma numérique de résolution d'équations différentielles afin de définir un test de validation des moteurs utilisés dans l'imprimante. Ce sujet est intéressant sur le principe mais il est décevant : beaucoup de notions sont hors programme et ne sont pas définies ; le programme proposé dans la quatrième partie ne marche pas, ce qui conduit à des questions n'ayant pas vraiment de sens pour un candidat rigoureux ; les formulations des questions sont parfois très imprécises et on ne sait pas réellement ce qui est demandé... Bref, cet énoncé a tout pour désarçonner un candidat ayant sérieusement préparé le concours. Cependant, en vue des révisions, c'est un sujet qui balaie de nombreux domaines et, si on lit les indications du corrigé pour savoir ce qu'il est possible de faire ou pas, ce problème varié mérite que l'on s'y attarde. Indications La mention (HP) dans une indication signale une question hors programme, pour laquelle une explication détaillée est fournie dans le corrigé. Q1 (HP) Q3 Penser à regarder soigneusement les structures demandées en retour de fonction. Q4 Ne pas oublier le modulo. Q5 (HP) Q6 Cette question et la suivante se rapprochent des algorithmes de première année. Q8 (HP) Faire comme si l'on pouvait définir une constante en SQL comme Imin ou Imax. Q9 Utiliser des requêtes imbriquées. Q10 Écrire une requête portant sur une table dans laquelle la clause WHERE dépend d'une requête portant sur une autre table. Q11 (HP) Q12 On suppose que le programme proposé marche. Q14 (HP) On peut deviner la réponse en s'inspirant de l'énoncé, sans plus de connaissances sur les dictionnaires. Q16 (HP) Un invariant d'itération est l'équivalent d'un invariant de boucle pour les fonctions récursives. Q22 (HP) Q23 Il faut construire ici une fonction permettant d'évaluer si un moteur est défectueux ou non. Par exemple, on peut proposer un test comparant quelques solutions simulées et la sortie mesurée. Tests de validation d'une imprimante Le complément à 2 est une méthode de représentation des entiers relatifs sur un nombre fini de bits. Un des bits est utilisé pour coder le signe, les suivants permettent de représenter la valeur absolue du nombre. La façon de représenter cette valeur absolue n'est pas nécessaire pour répondre à cette question. On donne ici une réponse générale indépendante de la convention, l'emploi de la terminologie « complément à 2 » imposant en fait l'intervalle demandé. En complément à 2, puisqu'un bit sert à coder le signe, cela signifie qu'il en reste 9 pour coder la valeur absolue, soit 29 = 512 valeurs possibles. Traditionnellement, on considère que l'on code ici les entiers compris entre -512 et +511. Mais on peut représenter de façon générale tout intervalle de nombres entiers contenant 210 = 1024 valeurs, si l'on décide arbitrairement d'une convention. Q1 Le résultat de la conversion peut prendre toute plage de valeurs entières de 1024 valeurs. Cependant, rien n'interdit de coder plusieurs fois une même valeur. Ainsi, une autre méthode de représentation de nombres qui consiste à coder le signe par le premier bit et la valeur absolue par les suivants en tant qu'entier naturel conduit à coder deux fois le zéro. Par exemple, sur 4 bits, les binaires 0000 et 1000 représentent « respectivement » +0 et -0, codant deux fois la même chose. L'intérêt des différentes méthodes de représentations de nombres est précisément de pallier ce genre de défaut. [ 1]Q2 La résolution de la mesure se déduit de la possibilité de représenter 1024 éléments sur N = 10 bits. 2N éléments permettent de définir 2N - 1 intervalles. La plage de tension P étant de 10 V, la résolution vaut = P = 1.10-2 V -1 2N Q3 Le principe du programme est le suivant. On initialise une variable nonstop à la valeur booléenne True. On lit alors un à un les caractères reçus jusqu'à tomber sur un caractère d'en-tête. On change alors la valeur de nonstop pour sortir de la boucle. On lit par la suite le nombre N de données envoyées. On sait que la longueur totale de la trame est exactement 8 + 4N : un caractère correspond à l'en-tête, trois au nombre de données envoyées, 4N permettent de détailler ces dernières et quatre caractères donnent le checksum. On utilise également à répétition la conversion du type chaîne de caractères vers le type entier grâce à int. def lect_mesures(): '''Fonction qui renvoie une trame à partir du premier en-tête''' nonstop=True resultat=[ ] #Liste que l'on renverra à la fin while nonstop: test=com.read(1) if test in ['U','I','P']:#A-t-on trouvé l'en-tête ? resultat=[test] #Si oui, on le stocke nonstop=False #Et on fait en sorte de sortir du while N=int(com.read(3)) #On stocke le nombre de données à lire donnees=[ ] #Liste vide contenant les données for inc in range(N): #On lit 4 caractères que l'on convertit #en entier pour les stocker donnees.append(int(com.read(4))) resultat.append(donnees) #On stocke donnees resultat.append(int(com.read(4))) return resultat Q4 Notons une confusion de l'énoncé entre mesure et mesures qui peut déstabiliser à la lecture du sujet, surtout lors de l'emploi de la notation mesures[], utilisée par exemple en Java... Ce qui est demandé est toutefois relativement compréhensible entre les lignes. Enfin, ne pas oublier le modulo 10000. def check(mesure,CheckSum): '''Vérifie la validité d'un checksum''' #On calcule la somme des données reçues somme=0 for x in mesure: somme += abs(x) #On teste la validité du checksum return somme%10000==CheckSum Q5 On suppose ici que la bibliothèque matplotlib.pyplot a été importée sous l'alias plt. def affichage(mesure): Temps=[ ] #On connaît exactement la plage nécessaire : on part de 0ms #et on va à 400ms par pas de 2ms. On met donc 401 pour atteindre #400 inclus mais sans dépasser cette valeur. for t in range(0,401,2): Temps.append(t) mesures=[ ] #Initialisation des mesures for m in mesure: #On balaie les données fournies mesures+=[m*4e-3] #Conversion des données en intensités plt.plot(Temps,mesures) plt.xlabel('Temps (ms)') plt.ylabel('Intensité (A)') plt.title('Courant moteur') Ce programme suivant est enrichi des commandes qui auraient permis d'obtenir tout le graphique proposé. Selon l'interface de développement, on peut être amené à ajouter la fonction show pour que le graphique créé s'affiche effectivement. On peut également le sauver à l'aide de la fonction savefig. Notons toutefois que, d'après le programme officiel, aucune commande