Mines Informatique MP-PC-PSI 2015

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