Mines Informatique Commune MP PC PSI 2015Sujet, corrigé et rapport du jury

ÉCOLE DES PONTS PARISTECH. SUPAERO (ISAE), ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH MINES DE SAINT-ÉTIENNE, MINES NANCY, TÉLÉCOM BRETAGNE, ENSAE PARISTECH (Filière MP). ÉCOLE POLYTECHNIQUE (Filière TSI).

ÉPREUVE D'INFORMATIQUE

Tests de validation d'une imprimante

Introduction

Cet ordinateur va effectuer différentes mesures pour valider le fonctionnement de l'électromécanique de l'imprimante. L'ensemble des mesures et des analyses est sauvegardé dans un fichier texte. Cette sauvegarde s'effectue dans une base de données et, afin de minimiser l'espace occupé, les fichiers sont compressés. La base de données permet à l'entreprise d'améliorer la qualité de la production par diverses études statistiques.

Rappels et définitions :

• Une liste commence par un crochet [ et se termine par un crochet ]. Les éléments d'une liste sont ordonnés (indexés).
• On pourra utiliser la surcharge de l'opérateur + : [ ' a ' ] + [ ' b ' ] = [ ' a ' , ' b ' ].
• Un dictionnaire définit une relation une à une entre des clés et des valeurs. Celui-ci se note entre accolades {}.
• Un tuple est une collection d'éléments ordonnés comme dans une liste mais une fois le tuple créé, ses éléments ne peuvent pas être modifiés indépendamment les uns des autres. Il se note entre parenthèses (). Exemple : (4, 'e', [1, 3] )

I Réception des données issues de la carte d'acquisition

• un entête qui permet d'identifier la mesure sur un caractère ('U' tension moteur, 'I 'courant moteur, 'P' position absolue),
• le nombre de données envoyées (3 caractères),
• les données constituées des mesures brutes issues de la conversion analogique-numérique, chaque mesure étant codée à l'aide du caractère '+' ou '-' suivi de 3 caractères pour la valeur absolue,
• un checksum, somme des valeurs absolues des données précédentes modulo 10000 sur 4 caractères. Le nombre de données transmises n'est pas inclus dans le checksum.

Exemple : Mesure de la tension sur 5 échantillons.

La commande carac_recus=com.read(nbre_car) permet de récupérer nbre_car caractères reçus sous la forme d'une chaîne de caractères. En supposant que les caractères reçus correspondent à l'exemple précédent, après l'exécution de carac_recus=com.read(5), la variable carac_recus contiendra la chaîne "U005+".

Figure 1 - Affichage de la mesure.

II Analyse des mesures

• Le calcul de la valeur moyenne I_(moy) du signal I(t) sur la durée d'acquisition.

• Le calcul de l'écart type I_(ec) du signal I(t) sur la durée d'acquisition.

III Base de données

IV Préparation du fichier texte avant envoi : la compression

IV. 1 Présentation :

Figure 2 - Arbre de Huffman.

• test()
• get1()
• get2()

IV. 2 Analyse des fonctions make_huffman_tree() et freq_table()

IV. 3 Analyse de la fonction insert_item()

IV. 4 Analyse de build_huffman_tree()

V Simulation physique

Annexe

Huffman tree :

###############################################################################
### Auto Generation of Huffman Trees
###########################################################################
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)]
### entr\'{e}e : string txt et retourne un dictionnaire contenant chaque
### caractere avec son occurrence dans le string txt
def freq_table(txt):
    ftble = {}
    for c in txt:
        if c not in ftble:
            ftble[c] = 1
        else:
            ftble[c] += 1
    return ftble

### Fonction de comparaison qui permet de comparer
### les noeuds de Huffman entre eux selon leur occurrence.
def freq_cmp(node1, node2):
    freq1, freq2 = get6(node1), get6(node2)
    if freq1 < freq2:
        return -1
    elif freq1 > freq2:
        return 1
    else:
        return 0
### ins\'{e}re un item \'{a} sa place appropri\'{e}e dans une liste de
    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
### Construction de l'arbre de Huffman
def build_huffman_tree(txt):
    ### 1. construire une table des occurrences \'{a} partir de txt
    ftble = freq_table(txt)
    ### 2. obtenir la liste des feuilles de Huffman
    lst = list(ftble.items())
    ### 3. classer leaf_lst par occurrence de la plus petite \'{a} la plus
    ### grande
    lst.sort(key=lambda lst: lst[1])
    ### 4. construction de l'arbre de huffman
    if len(lst) == 0:
        return None
    elif len(lst) == 1:
        return lst[0]
    else:
        ## 5.
            while len(lst) > 2:
                ## 6.
                new_node = make_huffman_tree(lst[0], lst[1])
                ## 7.
                del lst[0]
                del lst[0]
                ## 8.
                insert_item(new_node, lst, 0)
        else:
                return make_huffman_tree(lst[0], lst[1])