Skip to main content Informatique en prépa - Lycée Malherbe 

CCINP TSI 2019 - Sécurisation de l'entrée du personnel

Le sujet

Épreuve d'informatique de la filière TSI du Concours Commun INP, session 2019. Sujet original (PDF), © Concours Commun INP.

L'énoncé est reproduit tel quel (on répond ici dans les cellules plutôt que sur le Document Réponse). Les cellules de code, les vérifications et les données ont été ajoutés pour le traiter sur machine : la base de données est celle de l'annexe du sujet ; la photo de l'employé et la liste des codes sont fictives.

Remarques générales

Chaque partie de ce sujet peut être traitée séparément. Vous pouvez utiliser toutes les fonctions des questions précédentes même si vous ne les avez pas implémentées.

Si la réponse attendue est spécifique à un langage de programmation, seul le langage Python est permis.

Dans les questions où l'on demandera d'écrire une fonction, on donnera systématiquement sa signature, c'est-à-dire le nom de la fonction avec les types des paramètres ainsi que le type du résultat retourné par cette fonction. Par exemple, la fonction foo qui prend en entrée deux paramètres de type entier et retourne une liste, aura comme description : foo(int,int) -> list.

Sécurisation de l'entrée du personnel d'une entreprise

Partie I - Présentation

Une entreprise possède 5 sites de production. Le Directeur Général veut améliorer la sécurité. Il souhaite attribuer à chaque employé une carte personnelle et infalsifiable lui permettant l'accès à son site de production et peut-être à d'autres sites de l'entreprise. Chaque employé est affecté uniquement à un site que l'on appellera son site d'origine.

Chaque site de production ne pourra compter plus de 100 employés. La carte attribuée à l'employé comportera sa photo d'identité ainsi qu'une puce. Le code représentant le nom de la personne sera intégré dans la photo mais pas dans la puce. Il y a très peu de différences entre deux photos, l'une sans code, l'autre avec un code intégré.

Chaque employé sera référencé par un code composé d'un entier compris entre 1 et 5 (indiquant le site de référence où il travaille) ainsi qu'une séquence de 7 caractères (pris parmi les 7 premiers caractères de l'alphabet en majuscules : 'A' ... 'G'). Le site sera codé en machine sur 3 bits. Par exemple, pour un employé travaillant dans le site n° 3, le code pourrait être 3DABGEFC. Ce code n'affiche pas le nom de l'employé mais un automate permet, à partir des 7 caractères, de le retrouver.

Q1

Donner le nombre maximal d'employés par site ainsi que le nombre maximal de sites que pourrait gérer cette entreprise avec ce type de codage. La réponse peut être donnée par une expression numérique sans chercher à la calculer.

Indiquer si la technique de codage est suffisante pour gérer le personnel de cette entreprise.

Réponse

Partie II - Distance de Levenshtein

La problématique est de savoir si les codes créés pour gérer les employés sont suffisamment disjoints les uns des autres, c'est-à-dire si la mesure de la différence entre deux codes est suffisamment importante. Ceci est possible grâce à la distance de Levenshtein qui peut être utilisée pour analyser tous les codes. L'entreprise veut tester tous les codes associés aux employés et changer les codes de tous ceux dont la distance de Levenshtein est inférieure à la valeur 3.

Dans cette partie, nous allons développer les fonctions permettant de répondre à cette problématique.

La distance de Levenshtein est une valeur donnant une mesure de la différence entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu'il faut supprimer, insérer ou remplacer pour passer d'une chaîne A à une chaîne B.

On considère que chaque opération élémentaire mise en oeuvre (supprimer, insérer ou remplacer) a un coût de 1. On précise que chaque opération élémentaire ne porte que sur un seul caractère. La distance de Levenshtein, au sens mathématiques du terme, est la somme de ces coûts.

Par exemple, la distance de Levenshtein entre les chaînes Soveil et Soleil est de coût égal à 1 car il a fallu réaliser une seule transformation, une substitution pour remplacer 'v' par 'l' dans la chaîne Soveil.

On va s'intéresser à déterminer quelle est la distance de Levenshtein entre les chaînes de caractères Auttame et Automne.

Q2

Écrire, dans le langage Python, les transformations (insertion, substitution, suppression) appliquées à la chaîne Auttame afin d'obtenir la chaîne Automne. On déterminera systématiquement la valeur de la chaîne, notée s, avant et après chaque transformation ainsi que le nom de la transformation appliquée.

Calculer le coût de la distance de Levenshtein.

Python

Loading editor...

s = "Auttame"
Réponse

L'algorithme qui vous est proposé ci-après décrit le calcul de la distance de Levenshtein entre deux chaînes de caractères. Cet algorithme retourne un entier (éventuellement nul) donnant la distance entre deux chaînes de caractères au sens de Levenshtein.

levenshtein(chaine1, chaine2)
Entrée : chaine1[], chaine de caracteres d'indice 1 a n avec n egal a longueurChaine1 ; chaine2[], chaine de caracteres d'indice 1 a m avec m egal a longueurChaine2
Sortie : entier : la valeur de la distance
d[] : matrice de nombres entiers initialisée avec des 0, indice de 0 a n et de 0 a m
pour i de 0 a n faire
d[i, 0] ← i
pour j de 0 a m faire
d[0, j] ← j
pour i de 1 a n faire
pour j de 1 a m faire
si chaine1[i] = chaine2[j] alors
coutSubstitution ← 0
sinon
coutSubstitution ← 1
d[i, j] ← minimum(d[i-1, j] + 1, d[i, j-1] + 1, d[i-1, j-1] + coutSubstitution)
retourner d[n, m]

Dans minimum, le premier terme correspond à une suppression, le deuxième à une insertion, le troisième à une substitution.

Q3

Déterminer la matrice d de l'algorithme de Levenshtein après l'initialisation (les deux premières boucles) et à la fin de l'algorithme, ainsi que la distance de Levenshtein lors de son exécution entre les chaînes 'GAZ' et 'LA'.

Réponse
Q4

Déterminer la complexité de l'algorithme précédent.

Réponse
Question ajoutée

(Elle n'est pas dans le sujet, mais la fonction est nécessaire pour la suite.) Écrire en Python la fonction levenshtein(chaine1:str, chaine2:str) -> int correspondant à l'algorithme ci-dessus. Attention : les chaînes de Python sont indicées à partir de 0.

Python

Loading editor...

def levenshtein(chaine1, chaine2):
    pass
Vérification : levenshtein
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

Tous les codes ont été rassemblés dans une liste nommée table_code :

Python

Loading editor...

table_code = ['FDFBCBG', 'DGGAGFD', 'ECAACBB', 'DBBEBAD', 'GBABDBB', 'BDDCGDE', 'AEEADGD', 'CAEBCCE', 'BBGCBAD', 'BDADEDG',
              'GCDACDA', 'DCCFCBC', 'FDBFCDC', 'GGDDFBB', 'AGBDDGC', 'GCDFADA', 'BBACBAD', 'CDCGDGG', 'DCGEGFD', 'GBFGBGG',
              'ACCEGGE', 'EADCGAD', 'FDFBCBG', 'BBGDFCG', 'GBFFEAA', 'CCEFGGC', 'BCGDEDG', 'EGGACAA', 'EGBEAAG', 'GEAAGFC',
              'CBBBABA', 'EFFFEDC', 'ADEECGF', 'CBGAECB', 'DCEGCDG', 'AGDEFBB', 'CBABFBE', 'EFFFBDA', 'GBFFEAA', 'BEDCGDE',
              'ACFCDEB', 'ECGDFGD', 'EAEBADE', 'FEEDAGC', 'ACEFBBA', 'CCGADBC', 'FGBADGD', 'FDBABDB']
Q5

Écrire une fonction code_bon_lvs qui supprime tous les codes de la liste table_code dont la mesure de Levenshtein (avec un autre code de la liste) est inférieure ou égale à la valeur 3. Les codes à supprimer seront remplacés dans la liste table_code par le code nul, c'est-à-dire la chaîne de caractères '0000000'.

Signature de la fonction code_bon_lvs : code_bon_lvs(list) -> NoneType

Python

Loading editor...

def code_bon_lvs(table_code):
    pass
Vérification : code_bon_lvs
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q6

Écrire une fonction pourcentage_lvs qui détermine le pourcentage de codes nuls dans la liste table_code. Le résultat sera une chaîne de caractères constituée d'un nombre entier (pas un nombre flottant) et du caractère %. On permet l'arrondi d'un calcul à l'entier inférieur ou à l'entier supérieur.

Signature de la fonction pourcentage_lvs : pourcentage_lvs(list) -> str

Exemple :

>>> pourcentage_lvs(table_code)
'17%'
Python

Loading editor...

def pourcentage_lvs(table_code):
    pass
Vérification : pourcentage_lvs
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

Partie III - Gestion des données

Nous allons nous intéresser à la gestion des données qui sont stockées dans la base de données nommée Personnel et sera constituée de deux tables intitulées Employes et ListeCategories. Les contenus de ces tables se trouvent en annexe, à la fin de la page.

La table Employes est constituée de 8 champs :

La table ListeCategories est constituée de 2 champs :

Des lecteurs de codes sont installés aux portes des différents sites afin de limiter les accès aux seules personnes habilitées à y entrer.

Rappelons que le code est défini sous la forme d'une chaîne de 8 caractères, le premier caractère indiquant le numéro du site auquel appartient une personne. Par défaut, chaque personne est attribuée à un et un seul site, son site d'origine. Par contre, il est possible à toute personne de cette entreprise de se déplacer dans d'autres sites si l'autorisation en a été donnée (champ site de la table Employes). Le reste des caractères correspond à la clé de sécurité associée à chaque employé.

La gestion du champ site est particulière. On définit un entier qui permet de connaître les sites où l'employé est autorisé à entrer. On attribue les valeurs suivantes :

Ainsi, si un employé appartenant au site 1 est autorisé à entrer dans les sites 2 et 3, la valeur du champ site aura comme valeur 2 + 4, soit 6. Pour un autre employé appartenant au site 4 autorisé à entrer dans les sites 1, 2 et 5, la valeur du champ site sera 1 + 2 + 16, soit 19.

Attention : comme on peut le remarquer sur les deux exemples précédents, le numéro du site d'origine (le site où l'employé travaille par défaut) n'est jamais pris en compte dans le calcul donnant la valeur du champ site.

Q7

Écrire une fonction liste_site donnant la liste des sites où un employé peut se rendre en plus de son site d'origine dès que l'on donne une valeur (un entier) représentant la valeur du champ site de la table Employes. Si la valeur donnée est incorrecte, la fonction liste_site retournera une liste vide.

L'ordre des sites dans le résultat n'a pas d'importance.

Signature de la fonction liste_site : liste_site(int) -> list

Exemple :

>>> liste_site(21)
[1, 3, 5]
>>> liste_site(50)
[]
Python

Loading editor...

def liste_site(valeur):
    pass
Vérification : liste_site
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

L'équipe de direction souhaite avoir certaines informations au sujet des employés de l'entreprise.

Q8

Écrire en SQL la requête 1 suivante donnée en algèbre relationnel :

SQL

Loading editor...

Q9

Écrire en SQL la requête 2 donnant comme résultat l'adresse email (sans le nom de domaine) des employés pouvant accéder uniquement aux sites 3 et 4 en plus de leur site d'origine.

SQL

Loading editor...

Q10

Écrire en SQL la requête 3 donnant comme résultat le nom et la catégorie des personnes de l'entreprise ayant au moins 20 ans. Les noms seront classés par ordre alphabétique.

SQL

Loading editor...

Q11

Écrire en SQL la requête 4 donnant comme résultat la liste des âges des employés avec comme information associée le nombre d'employés ayant le même âge. On demande que cette liste soit décrémentale par rapport au nombre de personnes ayant le même âge.

Par exemple, dans la table Employes, il y a 2 personnes qui ont 22 ans.

SQL

Loading editor...

Partie IV - Codage des couleurs

La photo, une image couleur, est décrite informatiquement comme un tableau (une matrice) de pixels. Chaque pixel sera représenté par une couleur au format RGB.

Le système RGB

Le système RGB (Red, Green, Blue) ou en français (Rouge, Vert, Bleu), permet de coder les couleurs en informatique. Un écran informatique est composé de pixels représentant une couleur au format RGB.

La composante R est codée sur 8 bits de 0 à 255 en décimal et de 00 à FF en hexadécimal. Il en va de même pour les autres composantes. Le codage des couleurs va du plus foncé au plus clair.

Par exemple, la couleur d'un pixel orange pourrait avoir comme valeur (255,100,100). Un pixel sera de couleur gris si les composantes R, G et B sont identiques.

Par exemple, la couleur d'un pixel pourrait être en format RGB (64,78,191). Si on écrit les trois composantes RGB en code binaire, on aura le triplet (01000000, 01001110, 10111111). Le bit de poids faible de chacune des composantes RGB est représenté en gras. On va se servir de ce triplet de valeurs définies en gras pour coder une information dans l'image.

La modification du bit de poids faible a très peu de conséquences sur la représentation de l'image.

Q12

Donner le code RGB en décimal et en hexadécimal des éléments suivants :

  • un pixel de couleur bleu ;
  • un pixel de couleur blanc.

Un pixel est codé dans le format RGB en (10,10,10). Indiquez la couleur de ce pixel.

Réponse
Q13

Donner pour le codage RGB le nombre de couleurs possibles. La réponse peut être donnée par une expression numérique sans chercher à la calculer.

Réponse

Partie V - Codage de l'information

Cette partie sera consacrée à l'implémentation de fonctions qui serviront notamment dans la partie VI, réservée au décodage de l'information se trouvant dans la photo de l'employé(e).

Les informations constituant le code sont définies dans une trame composée de blocs non consécutifs. Chaque bloc sera associé à un pixel. Un premier bloc est constitué d'un pixel pour représenter le numéro du site et est suivi d'une séquence de 7 blocs représentant chacun un caractère. Le premier bloc sera considéré comme le bloc de référence.

Pour un pixel codant le numéro du site de l'employé, les bits de poids faible indiquent directement le numéro au format binaire. Ainsi, pour l'exemple précédent, le codage correspondant au site n° 3 sera (01000000, 01001111, 10111111) puisque le triplet 011 correspond à la valeur 3 en code décimal. Par conséquent, on met une information dans l'image en modifiant uniquement les bits de poids faible, ce qui a peu de conséquences sur la représentation de cette image.

Pour un pixel codant une des lettres de l'identifiant de l'employé, on valide la convention suivante : le caractère 'A' sera associé à 001, le caractère 'B' à 010, jusqu'au caractère 'G' qui aura comme valeur 111.

Par exemple, un pixel codant le caractère 'B' (010) pourrait avoir pour format RGB (...0, ...1, ...0). On ne traitera pas le caractère associé à 000 qui aura pour lettre 'W', réservée pour la gestion du personnel de service (gardiens, personnel de nettoyage, etc.) ayant l'autorisation d'entrer dans les sites de l'entreprise.

Chaque trame sera constituée de 8 blocs, c'est-à-dire 8 pixels.

Q14

Écrire une fonction bin2() qui, à partir d'un nombre entier, retourne un nombre en code binaire. Cette fonction convertit un nombre entier en une chaîne de chiffres binaires sans le 0b devant, comme le ferait la fonction bin() de Python. Le résultat sera toujours écrit sous la forme d'une séquence d'au moins 3 digits de type string.

Remarque : pour l'implémentation de cette fonction, l'utilisation de la fonction bin() est possible. On rappelle que la fonction bin() convertit et retourne la chaîne de caractères en format binaire d'un entier donné. Par exemple, bin(12) retourne comme valeur la chaîne de caractères '0b1100'.

Signature de la fonction bin2 : bin2(int) -> str

Exemples :

>>> bin2(45)
'101101'
>>> bin2(1)
'001'
Python

Loading editor...

def bin2(n):
    pass
Vérification : bin2
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q15

Écrire la fonction num() qui calcule à partir d'une chaîne en chiffres binaires, par exemple '010', sa valeur en décimal.

Si la chaîne est vide, la fonction retournera comme valeur −1.

Signature de la fonction num : num(str) -> int

Exemples :

>>> num('101')
5
>>> num('')
-1
Python

Loading editor...

def num(s):
    pass
Vérification : num
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

Partie VI - Décodage de l'information

Cette partie sera consacrée à l'implémentation de fonctions pour le décodage de l'information.

On donne le code suivant (la photo a123.bmp est fictive ; elle est déjà dans le répertoire de travail, d'où la suppression du changement de répertoire de l'énoncé) :

Python

Loading editor...

from PIL import Image
im = Image.open("a123.bmp")   # Lecture de l'image de l'employé dont la photo est a123.
imx, imy = im.size            # La taille de l'image (largeur, hauteur).
print(imx, imy)               # Résultat : (277, 250).
posi = (30,20)                # Position du pixel (x,y).
px = im.getpixel(posi)        # Récupère la valeur au format RGB du pixel situé aux coordonnées (30,20).
print(px)                     # Résultat : (2, 57, 139).
                              # Les indices lignes et colonnes débutent à 0.
import matplotlib.pyplot as plt
plt.clf()
plt.imshow(im)
plt.show()

Lorsque l'employé passe sa carte sur le lecteur pour ouvrir une porte, les données de la puce et le code se trouvant dans la photo sont lus par le lecteur qui génère 2 valeurs envoyées au processus d'analyse (dont vous allez implémenter certaines fonctions). Ces 2 valeurs sont le pixel de référence (avec sa valeur posi) et le code associé à l'employé (un entier suivi de 7 caractères). Le pixel de référence est différent pour chacun des employés.

Les caractères du code dans l'image ne sont pas placés d'une manière consécutive mais séparés les uns des autres par une même valeur (delta) calculée à l'aide des valeurs RGB du pixel de référence en réalisant la somme des 3 composantes R, G et B.

Q16

Écrire la fonction lettre() qui, à partir d'une chaîne de 3 bits, détermine le caractère. La codification des 7 caractères a été réalisée sur seulement 3 bits. On rappelle que le caractère 'A' est codé '001', le caractère 'B' est codé '010' et ainsi de suite jusqu'au caractère 'G' qui est codé '111', ceci en suivant l'ordre des 7 premières lettres de l'alphabet.

Signature de la fonction lettre : lettre(str) -> str

Exemples :

>>> lettre('001')
'A'
>>> lettre('101')
'E'
Python

Loading editor...

def lettre(bits):
    pass
Vérification : lettre
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q17

Écrire la fonction bpf qui récupère les valeurs des bits de poids faible d'un pixel.

Cette fonction a 2 paramètres, l'image et la position du pixel. Elle retourne une chaîne de caractères composée de 3 bits.

Signature de la fonction bpf : bpf(BmpImageFile, (int,int)) -> str

Exemple :

>>> bpf(im,posi)
'011'
Python

Loading editor...

def bpf(im, pos):
    pass
Vérification : bpf
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q18

Soit la fonction valeur_delta() dont le code est donné ci-dessous. Cette fonction a 2 paramètres : l'image et les coordonnées du point de référence (le pixel du point de référence).

Signature de la fonction valeur_delta : valeur_delta(BmpImageFile, (int,int)) -> int

Indiquer ce que fait cette fonction en précisant les valeurs retournées. Le résultat sera décrit sous la forme d'un intervalle ou d'une union d'intervalles de nombres entiers.

Python

Loading editor...

def valeur_delta(im,posi):
    px = im.getpixel(posi)
    inter = (px[0] + px[1] + px[2]) % (128-41) + 40
    if inter % 2 == 1 :
        return inter + 1
    else :
        return inter

valeur_delta(im, posi)
Réponse

Les deux fonctions suivantes position_bloc() et num_site() ne sont pas à implémenter (elles sont données ci-dessous).

La fonction position_bloc() détermine les coordonnées d'un bloc de la trame se trouvant à un indice compris entre 0 et 7, l'indice 0 représentant le pixel de référence. Le premier bloc des caractères du code se trouve à l'indice 1 et le dernier à l'indice 7. Rappelons que l'indice 0 (le pixel de référence) est le bloc constitué du numéro du site où l'employé travaille.

La fonction position_bloc() a 4 paramètres : la position initiale du pixel de référence, la valeur de l'intervalle, la largeur de l'image et l'indice du bloc. Elle retourne les coordonnées du pixel du bloc recherché.

Signature de la fonction position_bloc : position_bloc((int,int),int,int,int) -> (int,int)

>>> position_bloc(posi,70,imx,1)
(100, 20)

La fonction num_site() retourne comme résultat le numéro du site où la personne travaille. Cette fonction a 2 paramètres : l'image et la position du pixel de référence.

Signature de la fonction num_site : num_site(BmpImageFile,(int,int)) -> int

>>> num_site(im, posi)
3
Python
code masqué : pas besoin de le lire pour suivre, exécutez-le simplement
Q19

Écrire la fonction lecture_lettres() qui retourne la séquence des lettres codées dans l'image, c'est-à-dire les 7 lettres constituant une partie du code de l'employé.

Cette fonction a 2 paramètres, l'image et la position du pixel de référence. Elle retourne une chaîne de caractères.

Signature de la fonction lecture_lettres : lecture_lettres(BmpImageFile,(int,int)) -> str

Exemple :

>>> lecture_lettres(im,posi)
'DABGEFC'
Python

Loading editor...

def lecture_lettres(im, posi):
    pass
Vérification : lecture_lettres
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q20

Indiquer ce que fait la fonction suivante :

def lecture_code(im, posi):
    num = num_site(im, posi)
    msg = lecture_lettres(im, posi)
    return str(num) + msg
Réponse

Annexe : base de données « Personnel »

Table Employes :

idnomprenomemailagecodesitecode_categorie
1GenereuxAlainalain.genereux471AAACDEF01
2TanguyAlainalain.tanguy221BBACABE108
3SmithAlanalan.smith475BCABCAE52
4LefollClaudeclaude.lefoll282EEABECC241
5HerbertsDanydany.herberts581EEEEABC01
6KorbsEvaeva.korbs332FEAFEAB95
7NielsEdwinedwin.niels242EFDDACA284
8JolyEmilieemilie.joly253FAFABEF194
9EstebanFloreflore.esteban204BECEBAA122
10SerinJacquesjacques.serin222GBBCEAE216
11ClercJeromejerome.clerc293DDAABBC31
12BrownKatiakatia.brown465AFBECCA31
13ForbsLauralaura.forbs182CBAEAEC01
14PhilMarcmarc.phil334BCDABCD177
15AuzasMichelmichel.auzas325FECDAEA157
16KottaMichellemichelle.kotta272ABEEABC97
17LambertPierrepierre.lambert353DABGEFC102
18KladerSylviesylvie.klader322EAEAEAB201
19DurandSylviesylvie.durand311CBBCAEA166
20OlmTatianatatiana.olm254EFEFACB193

Table ListeCategories :

idcategorie
1ingénieur
2secrétaire
3comptable
4technicien
5opérateur
6administratif
7chef de projet
8responsable de département

Entrez le code donné en cours pour accéder à la solution :