CCINP Informatique Commune TSI 2023Sujet et rapport du jury

Pas encore noté

Manipulation de listes et slicing
Dictionnaires
Copie superficielle et copie profonde
Algorithme de Dijkstra
Requêtes SQL

Explorer les annales

BanqueCCINP Année2023 FilièreTSI MatièreInformatique

Annales CCINP TSI Informatique CCINP TSI 2023 TSI Informatique Informatique 2023

Téléchargements

Télécharger le sujet (PDF)

Rapport du jury Lire en ligne LaTeX Word

Corrigé : pas encore disponible

Présentation du sujet

Difficulté moyenne

Tests d'erreurs informatiques en entreprise : numéro de sécurité sociale, carte bancaire, QR code, plus court chemin et SQL

Le sujet porte sur la programmation de méthodes de test d'erreurs pour une entreprise : validation d'un numéro de sécurité sociale, d'un numéro de carte de crédit avec la formule de Luhn, d'un QR code, recherche du plus court chemin par l'algorithme de Dijkstra sur un graphe de magasins, puis requêtes SQL. Il comporte 22 questions réparties en cinq parties de difficulté progressive.

1Partie I : test du code de sécurité socialeVérification de la validité d'un numéro de sécurité sociale par manipulation de listes et de chaînes.
2Partie II : test de numéro de carte de créditApplication de la formule de Luhn à l'aide de dictionnaires.
3Partie III : test de QR codeManipulation de listes de listes pour valider la structure d'un QR code.
4Partie IV : gestion réseauRecherche du plus court chemin entre magasins avec l'algorithme de Dijkstra, entièrement expliqué dans l'énoncé.
5Partie V : requêtes SQLInterrogation d'une base de données de l'entreprise en SQL.

Difficulté moyenne. Le rapport indique un sujet de longueur et de difficulté adaptées, avec une difficulté progressive dans chaque partie et une troisième partie nettement plus sélective, seuls les très bons candidats l'ayant bien traitée.

L'épreuve en chiffres

Moyenne 10,26 / 20 · écart-type 4,88 · 1 137 présents · où vous situez-vous ?

Moyenne: 10,26/ 20
Écart-type: 4,88
Présents: 1 137
Coefficient: 4
Durée: 3 h

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours, épreuve du 26 avril 2023. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

5 erreurs relevées

Question d'ouverture pourtant facile · Syntaxe des dictionnaires mal maîtrisée · Confusion sur la copie de listes

Le jury note une progression régulière des candidats sur les techniques de programmation Python, la structure du code et les indentations étant bien respectées. Des erreurs subsistent néanmoins sur les listes, le slicing, les dictionnaires et la syntaxe SQL. La partie sur l'algorithme de Dijkstra, hors programme de TSI mais entièrement expliquée dans l'énoncé, a été difficilement traitée.

Les erreurs les plus sanctionnées

1
Question d'ouverture pourtant facileQ1
Malgré un principe totalement décrit dans l'énoncé, tous les candidats n'ont pas réussi cette première question.
« Tous les candidats n'ont pas réussi à répondre à cette question particulièrement facile »
2
Syntaxe des dictionnaires mal maîtriséeQ7
L'accès à une valeur d'un dictionnaire, pourtant bien défini dans le nouveau programme, reste mal maîtrisé.
« Beaucoup trop de candidats ne connaissent pas la syntaxe des dictionnaires »
3
Confusion sur la copie de listesQ10
De nombreux candidats ne distinguent pas copie de référence, copie profonde et copie superficielle sur des listes de listes.
« un grand nombre de candidats qui n'ont pas compris ce qu'est la copie de référence »
4
Appropriation rapide de l'algorithme de DijkstraQ18
Bien que l'énoncé fournisse tous les éléments nécessaires, les candidats ont eu du mal à s'approprier l'algorithme en quelques minutes.
« les candidats ont eu des difficultés à s'approprier l'algorithme de Dijkstra en quelques minutes »
5
Syntaxe SQL fautiveQ21, Q22
Les deux dernières questions de requêtes SQL ont révélé de gros problèmes de syntaxe.
« Gros problèmes de syntaxe »

Ce qui a été bien réussi

La question 2 sur le code de sécurité sociale a été en général bien réussie.
La question 19 sur la gestion réseau a été généralement très bien traitée.

Conseils du jury

Bien maîtriser le slicing des listes, y compris avec des indices négatifs.
Distinguer clairement copie superficielle et copie profonde sur des listes de listes.
Commenter le code et soigner le style de programmation, ces éléments sont évalués.
Écrire une copie lisible avec des noms de variables explicites.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ÉPREUVE SPÉCIFIQUE - FILIÈRE TSI

INFORMATIQUE

Durée : 3 heures

N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.

RAPPEL DES CONSIGNES

Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
Ne pas utiliser de correcteur.
Écrire le mot FIN à la fin de votre composition.

Les calculatrices sont interdites.

Le sujet est composé de cinq parties, pouvant être traitées indépendamment.
Important : vous pouvez utiliser les fonctions des questions précédentes, même si vous ne les avez pas toutes implémentées.

Vous devez répondre directement sur le Document Réponse, soit à l'emplacement prévu pour la réponse lorsque celle-ci implique une rédaction, soit en complétant les différents programmes en langage Python.

Le sujet comporte :

le texte du sujet : 10 pages;
les Annexes : 3 pages;
le Document Réponse (DR) : 8 pages.

Seul le Document Réponse est à rendre dans son intégralité.

Gestion de Tests dans une entreprise

Une entreprise d'e-commerce vend des meubles tous identifiés par une référence et par un QR code

^1

. Tous les clients sont identifiés par leur numéro de sécurité sociale. Tous les achats s'effectuent à l'aide d'un numéro de carte de crédit. Cette entreprise met en œuvre différents tests afin d'éviter les erreurs de numéros de sécurité sociale, de numéros de carte de crédit ou de QR codes.

Partie I-Tests de code de sécurité sociale

En France, le numéro de sécurité sociale correspond au numéro d'inscription au répertoire national d'identification des personnes physiques (RNIPP). Il est formé du numéro d'inscription (NIR) à 13 chiffres et d'une clé de contrôle à 2 chiffres. Le NIR, créé à partir de l'état civil, est composé de la façon suivante :

Sexe (1 $^(er)$ chiffre);
Année de naissance (les deux chiffres suivants);
Mois de naissance (les deux chiffres suivants);
Lieu de naissance (les cinq chiffres ou caractères suivants - 2 chiffres $^2$ du code du département de naissance, suivis de 3 chiffres du code commune officiel de l'Insee $^3$ );
Numéro d'ordre permettant de distinguer les personnes nées au même lieu à la même période (les 3 chiffres suivants).
Les deux derniers chiffres, compris entre 01 et 97 , permettent de déterminer la clé, appelée aussi "clé de contrôle", qui permettra de contrôler l'exactitude du numéro de sécurité sociale.

Pour obtenir cette clé, on détermine tout d'abord, le reste de la division par 97 du nombre formé par les 13 premiers chiffres. La clé correspond au résultat de ce nombre retranché de 97.

Exemple : soit le numéro de sécurité sociale à 13 chiffres : "2 910175018 002". Le reste de la division de 2910175018002 par 97 est égal à 29. La clé est constituée du résultat : 97-29 = 68. Le numéro de sécurité sociale complet est donc : "2910175018002 68".

Dans cette partie, le numéro de sécurité sociale de 13 chiffres est une chaîne de caractères composée uniquement de chiffres avec des espaces de séparation entre les différents éléments constituant ce numéro. On ne prendra pas en compte le cas de la Corse.

Ne pas oublier qu'il est toujours possible de transformer un nombre entier en une chaîne de caractères composées de chiffres (fonction str) et réciproquement (fonction int), (annexe 3).

Q1. Écrire la fonction num_secu qui, à partir de la chaîne de caractères d'un numéro de sécurité sociale, donne le numéro sous la forme d'un entier. Le programme devra parcourir la chaîne de caractères représentant le numéro de sécurité sociale en supprimant les caractères d'espacement, puis la transformer en un nombre entier. Cette fonction a un paramètre de type string et retourne une valeur de type int.

Un QR code (Quick Response code) désigne un type de code-barres en deux dimensions, lequel se compose de modules noirs disposés dans un carré à fond blanc (voir figure 1).
Pour simplifier le problème, nous supposons que les deux départements corses 2 A et 2 B sont représentés par le code 20 comme avant 1976.
Institut national de la statistique et des études économiques.

Exemple:

>>> num_secu("2 91 01 75 018 002")
2910175018002

Q2. Écrire la fonction clef qui détermine la valeur de la clé d'un numéro de sécurité sociale. Cette fonction a un paramètre de type int et retourne un élément de type int.

Exemple :

>>>clef(2910175018002)

68
Q3. Écrire la fonction num_secu_complet qui détermine le numéro complet de sécurité sociale. Cette fonction a un paramètre de type int et retourne un élément de type int.
Exemple :

>>>num_secu_complet(2910175018002)
291017501800268

Q4. Écrire la fonction test_num_secu qui détermine si un numéro de sécurité sociale est correct. Cette fonction a un paramètre de type string et retourne un élément de type bool.

Exemples:

>>>test_num_secu('2 91 01 75 018 002 68')
True
>>>test_num_secu('2 91 01 75 018 002 93')
False

Partie II - Test de numéro de carte de crédit

Pour savoir si un numéro de carte de crédit est valide, on utilise très souvent l'algorithme de Luhn

^4

. Comme pour le numéro de sécurité sociale, il y a une clé appelée somme de contrôle (checksum en anglais) qui fait partie du numéro d'une carte de crédit. Ce numéro est un entier composé de 16 chiffres. Le dernier chiffre est la clé qui permet de contrôler l'exactitude du numéro.

Le principe de l'algorithme de Luhn est le suivant. On commence toujours par le chiffre se trouvant le plus à droite. Ce chiffre sera le premier élément de la liste dites des "indices impairs". Puis on complète cette liste en prenant un chiffre sur deux du numéro de carte bancaire, toujours en le lisant de la droite vers la gauche.

Pour la liste des chiffres "d'indices pairs", on commence par le deuxième chiffre le plus à droite du numéro de la carte de crédit, on se déplace de la droite vers la gauche comme pour la liste précédente et on construit la liste, en prenant un chiffre sur deux. Pour les nombres de cette liste des indices pairs, on double tous les chiffres. Si un nombre est supérieur à 9 , on réalise la somme des deux chiffres qui le composent (exemple si on obtient 16, on additionne 1 et 6 pour avoir 7). Par conséquent, tous les nombres des deux listes sont

composés uniquement de chiffres compris entre 0 et 9 . On calcule alors la somme totale des chiffres de ces deux listes. Si cette somme est un multiple de 10, alors le numéro de la carte de crédit est valide.

Exemple : soit 4762 un nombre (on se limite à 4 chiffres mais le raisonnement est identique pour un nombre à 16 chiffres). Appliquons-lui la formule de Luhn. On commence par le chiffre 2, celui se trouvant le plus à droite. Le nombre 4762 se transforme en deux listes correspondant aux indices impairs et pairs soit [2, 7] et [6, 4]. Puis en deux autres listes, la liste des indices impairs inchangés [2,7] et la liste des indices pairs doublés [12, 8]. La somme des éléments de ces deux listes est égale à 20 car la liste des indices pairs

[12, 8]

se réduit en la liste

[3, 8]

du fait de la sommation des chiffres constituant le nombre 12. La somme des éléments des deux listes obtenues [2,7] et [3,8] est bien égale à 20. Ce résultat est un multiple de 10 , le nombre 4762 est donc correct au sens de l'algorithme de Luhn.

On aurait pu raisonner sur une seule liste et obtenir le même résultat. 4762 se transforme en la liste [8, 7, 12, 2] puis en la liste [8, 7, 3, 2] après réduction. La somme des chiffres

8 + 7 + 3 + 2

est égale à 20 .
Q5. Écrire une fonction num_en_liste qui transforme un nombre entier en une liste de chiffres. Cette fonction a un paramètre de type int et retourne un élément de type list.

Exemple:

num_en_liste(4532015112830465)
[4, 5, 3, 2, 0, 1, 5, 1, 1, 2, 8, 3, 0, 4, 6, 5]

Q6. Écrire une fonction tuple_pairs_impairs qui détermine un tuple représentant la liste des chiffres d'indice pair et la liste des chiffres d'indice impair d'un numéro de carte de crédit. Le chiffre le plus à droite de ce numéro est considéré comme le premier chiffre d'indice impair. Cette fonction a un paramètre de type int et retourne un tuple composé de deux éléments de type list.
Exemple :

tuple_pairs_impairs(4532015112830465)
([6, 0, 8, 1, 5, 0, 3, 4], [5, 4, 3, 2, 1, 1, 2, 5])

Q7. Écrire une fonction cree_dico qui, à partir d'un numéro de carte de crédit, crée un dictionnaire avec deux clés nommées 'pair' et 'impair'. La clé 'pair' est constituée de la liste des nombres d'indice pairs du numéro de la carte de crédit et la clé 'impair' de la liste des nombres d'indice impairs.

Exemple:

>>> cree_dico(4532015112830465)
{'pair': [6, 0, 8, 1, 5, 0, 3, 4], 'impair': [5, 4, 3, 2, 1, 1, 2, 5]}

Q8. Écrire une fonction traitement_nb_pairs qui multiplie par 2 tous les chiffres de la liste associée à la clé 'pair'. Si un chiffre est supérieur à 9 , il faut réaliser la somme des deux chiffres qui le composent. Cette fonction a un paramètre de type dictionnaire et retourne un dictionnaire.
Remarque : la partie correspondant à la clé 'impair' n'est pas modifiée par le traitement de cette fonction.

Exemple:

>>> un_dico=cree_dico(4532015112830465)
>>> traitement_nb_pairs(un_dico)
{'pair': [3, 0, 7, 2, 1, 0, 6, 8], 'impair': [5, 4, 3, 2, 1, 1, 2, 5]}

Q9. Écrire une fonction test_num_carte_credit qui utilise l'algorithme de Luhn pour savoir si un numéro de carte de crédit est correct. Vous devez utiliser la fonction traitement_nb_pair pour sa réalisation. Cette fonction a un paramètre de type int et retourne une valeur de type bool.

Exemple :

test_num_carte_credit(4532015112830465)
True

Partie III - Tests de QR code

Les QR codes ont été inventés en 1994, par Masahiro Hara, un ingénieur de l'entreprise japonaise Denso-Wave. Cette invention a permis d'assurer le référencement des pièces détachées dans les usines Toyota. Les QR codes sont constitués essentiellement de pixels noirs et blancs codés dans le format RGB (annexe 1). Cependant, il existe des QR codes bicolores mais avec un jeu de couleurs très contrastées. Les QR codes peuvent être partiellement raturés ou déchirés car un de leurs avantages est qu'ils peuvent accepter un certain taux d'erreurs, entre

7%

30%

suivant la version du QR code. Il existe 40 versions qui peuvent stocker entre 10 et 7089 caractères numériques. Nous nous restreignons ici à la version 1 qui utilise une matrice de

21^* 21

pixels pour sa représentation.

En fait sur la figure 1, l'image du QR code correspond à u ne m atrice de

420^* 420

pixels (programme P1), alors que la matrice initiale d'un QR code de version 1 ne compte que

21^* 21

pixels. Pour qu'un QR code soit plus visible, on a créé la notion de module qui correspond à un bloc de pixels identiques pour représenter un pixel du QR code initial. C'est un mécanisme de zoom pour que le QR code soit visible. Un module a une taille de 2020 pixels. Chaque module représente globalement une valeur binaire : 1 pour le blanc et 0 pour le noir. Attention : ne pas confondre la taille d'un QR code (ici, 420420) avec la taille d'un module (ici, 2020 ) [la valeur 420 correspond à 2120]. Enfin, un QR code est constitué de différents éléments : des motifs de positionnement ( 3 blocs de

7 \times 7

pixels), des motifs de synchronisation (6 zones blanches de séparation et 11 pixels de couleur blanc et noir), des motifs de format d'information et une zone comprenant les données utilisateurs avec des motifs de correction (figure 2).

Dans la suite de cette partie, nous n'utiliserons que les QR codes de version 1.

Figure 1 －QR code version 1

Figure 2 －Organisation d＇un QR code

Q10．Écrire une fonction init qui réalise l＇initialisation d＇une liste de dimension

n

où chaque élément est également une liste de dimension

n

．Cette liste de listes représente ainsi une matrice de taille

n \times n

．Cette fonction a un paramètre de type int et retourne une liste de listes qui représente un QR code initialisé avec des valeurs 0.
Exemple ：

>>> init(4)
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

On donne le programme P1 suivant : (annexe 1 pour la description du module Gestion_QRCode).

P1
1 from Gestion_QRCode import *
2
3 img=open("./Image/ccinp.png")..........# Lecture de l'image
4 img.show().....................................# Affichage de l'image (figure 1)
5 largeur,hauteur=img.size..................# La taille de l'image (largeur, hauteur)
6 position = (largeur,hauteur) .............# Résultat : (420, 420)

Q11. Écrire la fonction charge_valeur qui a pour but de réduire les données de l'image dans une liste de listes de dimension 2121. Attention : l'image correspondant à un QR code représente une liste de listes de dimension 420420 dont on veut réduire tous les blocs constitués de 20*20 pixels à un seul pixel pour avoir à partir de l'image une liste de listes de dimension

21^* 21

. Ne pas oublier que tous les pixels d'un bloc sont identiques. Cette fonction a un paramètre de type image et retourne une liste de listes de triplets (couleur des pixels).
Indication : utiliser la fonction getpixel du module Python Gestion_QRCode (voir sa définition dans l'annexe 1).
On prend comme bloc de positionnement celui représenté dans la figure 3.

Figure 3 - Bloc de positionnement

Q12. Écrire une fonction cree_bloc qui crée un bloc de positionnement. Cette fonction, qui n'a pas de paramètre, retourne une liste de listes de dimension

7*7

.
Exemple :

    >>> cree_bloc()
[[0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 0],
    [0, 1, 0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0]]

Q13. Écrire une fonction test_bloc qui teste si un bloc de positionnement (rappel : il y en a trois) est bien représenté pixel par pixel dans un QR code. Cette fonction a 3 paramètres : les coordonnées

x

y

donnant la position du début d'un bloc de positionnement d'un QR code (toujours les coordonnées du pixel le plus haut et à gauche) et la liste de listes de dimension 21*21 associée au même QR code. Cette fonction retourne un booléen.
Remarque : on cherche à tester si un bloc de positionnement d'un QR code n'a pas subi une modification. Les coordonnées du pixel le plus haut et à gauche pour le premier bloc sont égales à

(0, 0)

, pour le second bloc à

(0, 14)

et pour le troisième bloc à ( 14,0 ).

Exemples:

test_bloc( 0,0 , mat1)
True

test_bloc(1,3, mat1)
False
Q14. On considère qu'un QR code est bien positionné lorsque ses 3 blocs de contrôle sont effectivement présents en haut à gauche, en haut à droite et en bas à gauche (comme sur la figure 1). Écrire une fonction test_QRcode qui permet de tester si un QR code est bien positionné. Cette fonction a pour paramètre une matrice de dimension 21 *21 et retourne un booléen.

Exemple :

test_QRcode(mat1)
True

Lors de la lecture d'un QR code par un appareil dédié (scanner, caméra ou autre) le processus de lecture permet de placer un QR code dans l'une des quatre positions possibles, comme illustré dans la figure 4. Cela dépend bien évidemment de l'orientation du QR code lors de sa lecture.

On se propose de faire tourner un QR Code par rotation successive de

90^\circ

afin qu'il puisse se trouver dans la bonne position comme celui de la figure 1.

Figure 4 - Les 4 positions possibles lors de la lecture d'un QR code

Q15.
Écrire une procédure

^5

tourHoraire qui réalise une rotation de

90^\circ

, dans le sens des aiguilles d'une montre, des 4 éléments du QR code. La fonction a trois paramètres, les coordonnées

x

y

d'un élément de la liste de listes et une liste de listes de dimension 21*21.

Exemple :

>>> tourHoraire(0,1, mat1)

On se limite à un exemple d'une liste de listes de dimension 4*4 pour expliquer le fonctionnement, mais ce serait la même chose pour une liste de listes de dimension 21 *21. Si on prend les 4 éléments (

b, h, o, i

) de la liste de listes table 1 de la figure 5 ,

b

doit se trouver, après une rotation de

90^\circ

, à la place de l'élément

h

, l'élément

h

à la place de l'élément

o

, l'élément

o

à la place de l'élément

i

et l'élément

i

à la place de l'élément

b

. Le résultat de la transformation est illustré dans la table 2 de la figure 5. Le mécanisme doit s'exécuter de la même manière sur les autres éléments de la table 2. Le résultat de la transformation finale est illustré dans la table 3 de la figure 5.

Table 1

a	i	c	d
e	f	g	b
o	j	k	l
m	n	h	p

Table 2

$m$	$i$	$e$	$a$
$n$	$j$	$f$	$b$
$o$	$k$	$g$	$c$
$p$	$l$	$h$	$d$

Table 3

Figure 5 - Simple rotation

Q16. Écrire la procédure rotationHoraire qui réalise la rotation de

90^\circ

d'un QR code. Cette procédure a un seul paramètre, une liste de listes de dimension

21^* 21

.
Par exemple, dans la figure 4 cette fonction réalisera la première rotation de

90^\circ

du QR code.

Q17. Connaissant les 4 positions possibles lors de la lecture d'un QR code par un appareil dédié, écrire la procédure QRcode_posi qui positionne correctement un QR code. Cette procédure a un seul paramètre, une liste de listes de dimension 21*21. Indication : utiliser les fonctions rotationHoraire et test_QRcode .

Partie IV - Gestion réseau

Cette entreprise possède de nombreux magasins dans le monde entier. Des serveurs ont été placés dans tous les pays et sont nommés par des lettres.

Les différentes informations envoyées dans le réseau circulent de serveur en serveur. Les serveurs sont représentés par des nœuds, figure 6, et plusieurs routes sont possibles entre chacun d'eux. Le poids associé aux arêtes correspond à la valeur du temps de transmission entre deux nœuds du graphe multiplié par un facteur correctif. L'entreprise souhaite optimiser les temps de transmission entre deux nœuds du réseau en utilisant l'algorithme de Dijkstra.

L'algorithme de Dijkstra permet de déterminer les plus courts chemins à partir d'un sommet unique

s \in S

vers les autres sommets d'un graphe pondéré orienté ou non

G = (S, A)

, avec

S

un ensemble de sommets et

A

un ensemble d'arêtes qui sont des paires de sommets. Toutes les arêtes de

G

sont de poids positif.

Figure 6 - Organisation des serveurs

Principe de l'algorithme de Dijkstra

Entrée :
    $G(S, A)$ : un graphe pondéré,
            $d$ : le sommet de départ à partir duquel on veut déterminer les plus courts chemins aux
                autres sommets,
            $P$ : construction d'un sous-graphe tel que la distance entre un sommet de $P$ depuis $d$ soit
                définie et soit un minimum dans le graphe $G$,
    Parent : tableau pour noter les sommets par où on passe. Parent est utilisé comme le tableau
                des précédents de chaque sommet, initialisé avec un élément n'appartenant pas à $S$,
            $M$ : tableau où les indices représentent les sommets du graphe : 0 désigne le sommet
                " $A$ ", 1 désigne le sommet " $B$ ", 2 désigne le sommet " $C$ ", etc...
                Les éléments de ce tableau sont corrigés au fur et à mesure de l'algorithme afin
                d'obtenir les distances les plus courtes du sommet de départ à un sommet du graphe.
Début:
        $\mathrm{P} \leftarrow \emptyset$
        $\mathrm{M}[\mathrm{d}] \leftarrow 0 \quad / /$ la distance de $d$ à lui-même est égale à 0
        $\mathrm{M}[\mathrm{s}] \leftarrow+\infty$ pour chacun des sommets du graphe autre que $d$
        Tant qu'il existe un sommet qui ne soit pas dans $P$
                Choisir un sommet $s$ hors de $P$ de plus petite distance $M[s]$
                Ajouter $s$ à $P$
                Pour chaque sommet $u$ hors de $P$ mais voisin de $s$
                    si M[u] > M[s] + poids(s,u)
                        $\mathrm{M}[\mathrm{u}]=\mathrm{M}[\mathrm{s}]+$ poids $(\mathrm{s}, \mathrm{u})$
                        Parent $[u]=s \quad / /$ le sommet $s$ est le prédécesseur du sommet $u$
                Fin du pour
        Fin tant que
Fin

En utilisant l'algorithme de Dijkstra, on souhaite déterminer tous les plus courts chemins, en terme de temps de communication, en partant du sommet

A

du graphe de la figure 6.

II est plus simple de réaliser l'exécution de l'algorithme de Dijkstra avec un tableau particulier que l'on nomme

M +

. Ce tableau est dans le

DR

. Une première colonne précise l'évolution des distances d'un sommet spécifique depuis le sommet de départ lors de l'exécution de l'algorithme. Chaque ligne correspond à une étape de l'algorithme. Chaque ligne donne les valeurs des distances courantes des sommets depuis le sommet de départ avec éventuellement une mise à jour si une distance est plus petite que celle déjà calculée.

Dans le tableau

M +

, l'élément

B(2_A)

correspond à la colonne choisie qui est

B

, à la valeur 2 du chemin et au sommet précédent

A

. Sur la ligne de l'élément

B(2_A)

on choisit la valeur (3) de la colonne

E

pour l'étape suivante.
Q18. Compléter les 3 lignes manquantes du tableau

M +

sur le

DR

.
Q19. Donner la valeur du plus court chemin entre "A" et "F". Expliquer comment on obtient cette valeur à l'aide du tableau

M +

. Expliciter le chemin le plus court trouvé pour aller de "

A

" à "

F

Partie V - Requêtes SQL

L'entreprise possède une base de données nommée Gestion_Entreprise constituée de trois tables : clients, produits et ventes. Les contenus de ces tables se trouvent en annexe 2.
La table "clients" est constituée de 5 champs :

id : de type INTEGER - clé primaire auto-incrémentée ;
num_secu : de type INTEGER - entier de 15 chiffres ;
nom : de type TEXT;
prenom : de type TEXT;
num_CB : de type INTEGER.

La table "produits" est constituée de 5 champs :

id : de type INTEGER - clé primaire auto-incrémentée ;
ref_produit : de type INTEGER ;
nom_produit : de type TEXT;
qrcode : de type TEXT;
prix : de type DECIMAL.

La table "ventes" est constituée de 3 champs :

date : de type TEXT ;
ref_produit : de type INTEGER ; - clé étrangère, pointe vers la clé primaire id de la table produits;
num_client : de type INTEGER; - clé étrangère, pointe vers la clé primaire id de la table clients.

Les dates dans cette table sont définies par une chaîne de 10 caractères suivant le format année-mois-jour. Exemple de dates : "2019-06-01", "2022-12-30".
Q20. Écrire, en SQL, la requête (1) qui permet d'obtenir le numéro de carte de crédit de toutes les personnes référencées dans la base de données de l'entreprise dont le numéro de sécurité sociale commence par 2. On utilisera le caractère "_" comme le séparateur des milliers. Par exemple 10000000 sera réécrit comme 10_000_000.

Q21. Écrire, en SQL, la requête (2) permettant d'obtenir le nom et le prénom de toutes les personnes ayant effectué un achat avec un résultat sans doublon.

Q22. Écrire, en SQL, la requête (3) qui permet d'obtenir les produits associés à chaque numéro de carte de crédit du client et qui ont été vendus entre le 1 juin 2020 et le 30 juillet 2020. On rappelle que SQL compare les variables de type TEXT grâce à l'ordre lexicographique : par exemple "13-06-1989 < 13-07-1999" est vrai.

Annexe 1

Module "Gestion_QRCode"

fonction Gestion_QRCode.open(fp)

Paramètre :

fp : nom de fichier (chaîne de caractères) représentant une image sous différents formats tels que PPM, PNG, JPEG, GIF, TIFF et BMP.

Retour :

retourne une variable qui est un descripteur d'image (un objet image).

Attention : la valeur retournée n'est en aucun cas une liste de listes ou une liste de listes similaire à celle de la bibliothèque Numpy.

Exemple :
img=Gestion_QRCode.open("uneImage.png")

fonction Gestion_QRCode.Show()

Retour :

retourne la valeur None. $^6$

Cette fonction affiche l'image dans n'importe quelle visionneuse d'images.

Exemple:

img.show()

attribut Gestion_QRCode.size

Permet de connaître la taille de l'image en pixels, le résultat est un tuple (largeur, hauteur).
Exemple :
print(img.size)

(360, 160) # soit largeur = 360 pixels et hauteur = 160 pixels

fonction Gestion_QRCode.getpixel(x,y)

Paramètres :

x : la coordonnée x du pixel référencé ;
y : la coordonnée y du pixel référencé.

Retour:

retourne les attributs de la couleur du pixel, au format RVB $^7$

La valeur retournée est un tuple (

r, v, b

) correspondant à la couleur du pixel : le plus souvent

(0, 0, 0)

pour un pixel noir et

(255, 255, 255)

pour un pixel blanc pour un QR code.

Exemple:
(r,v,b) = img.getpixel(100,30)

⋙(θ, θ, θ) #

pour un pixel noir
6. La valeur None est une valeur qui correspond à l'absence de valeur.
7. Le système RVB (Rouge, Vert, Bleu), ou en anglais RGB (Red, Green, Blue), permet de coder les couleurs en informatique. Un écran informatique est composé de pixels représentant une couleur au format RVB. La composante R est codée sur 8 bits de 0 à 255 en décimal. Il en va de même pour les composantes suivantes. Le codage des couleurs va du plus foncé au plus clair.

Annexe 2

Base de données "Gestion_Entreprise"

Le contenu des tables clients, produits et ventes de la base de données Gestion_Entreprise est donné ci-après.

Table "clients"

id	num_secu	nom	prenom	num_CB
1	286128817863441	Eldyn	Sophie	6767342589219928
2	298082934500890	Gomez	Maria	2324563490665454
3	298082934500896	Ruiza	Flor	9889454573204522
4	109086723487917	Kovitz	Boris	6789543778653678
5	175105642102321	Mottreff	Erwan	4745342178563217
6	189027511732543	Settin	Michel	7856432167453492
7	191017511318196	Valérie	Georges	8787564521392354
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

Table "produits"

id	ref_produit	nom_produit	qrcode	prix
1	27	Buffet chêne	$27.jpg$	320
2	102	Chaise rustique	$102.jpg$	65
3	453	Table ronde	$453.jpg$	75
4	756	Table ovale	$756.jpg$	120
5	921	Coffret Bali	$921.jpg$	170
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

Table "ventes"

date	ref_produit	num_client
2020-05-15	2	2
2020-06-17	3	1
2020-06-21	3	7
2020-07-19	4	5
2020-08-19	5	5
2020-09-05	4	6
$\dots$	$\dots$	$\dots$

Annexe 3

Rappels des syntaxes en Python

Définir une liste.

L = [1, 2, 3]; ⋙L[0]

Définir une liste de listes.

LL = [[1, 2], [3, 4], [5, 6], [7, 8]]

>>> LL[1] [3,4]

Ajouter un élément à la fin d'une liste.

L.append(5) LL.append([9, 10])

Convertir un nombre entier en une chaîne de caractères.

>>> str(12345) '12345'

Convertir une chaîne de caractères en un nombre entier.

Attention : si la chaîne de caractères contient un espace, l'appel de la fonction int provoque une erreur.

>>> int('12345') 12345

a//b

donne le quotient de la division euclidienne de

a

par

b

>>> 10//3 3

a%b

donne le reste de la division euclidienne de

a

par

b

>>> 10%3 1

Définir une chaîne de caractères.

mot='Python'

Longueur d'une chaîne.

len(mot)

Le slicing permet d'extraire des éléments d'une liste ou d'une chaîne.

si L = [6, 8, 5, 3, 7]; L[2 : 4] - - > [5, 3]; L[ : 3] - - > [6, 8, 5]; L[3 : ] - - > [3, 7]; L[ : 2] - - > [6, 5, 7]; L[2 : - 1] - - > [5, 3]; L[ - 1] - - > 7; mot[2 : 7] - - > ^' thon ^'

FIN

DOCUMENT RÉPONSE

Seul ce document est à rendre dans son intégralité.

Q1. Fonction num_secu

Q2. Fonction clef

Q3. Fonction num_secu_complet

Q4．test＿num＿secu

｜

Q5．Fonction num＿en＿liste

－

．

－

｜

－

｜

－

｜

－

｜

－

｜

－

0.1

－

－ 0.000

－

－ 0.0 .00

－

－

0.00 .0

－

0.00000

－

｜ 0.00

Q6．Fonction tuple＿pairs＿impairs

－

－

✓

－

｜

－

｜

－

｜

－

｜

－

｜

－

－

都鎄

✓

－

都讍

－

✓

－

✓

－

Q7. Fonction cree_dico

Q8. Fonction traitement_nb_pairs

	-	-	-	-	-	-	-	-	-	-	lo		-	-	-	-	\|	-	-	-	\|	-	-	-	.	-	-	-	-	\|	\| $◻$
-	-		-	-		-		-			-	-			-	-	-		-							-					-
	-




	$0.0 - 1000$
	0.00000

Q9. Fonction test_num_carte_credit

Q10. Fonction init

Q11. Fonction charge_valeur

Q12. Fonction cree_bloc

Q13. Fonction test_bloc

Q14. Fonction test_QRcode

Q15. Fonction tourHoraire

Q16. Fonction rotationHoraire

Q17. Fonction QRcode_posi

Q18．Compléter les 3 lignes manquantes du tableau

M +

	A	B	C	D	E	F
étape initiale	0	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
$A(0)$	－	2	$\infty$	（1）	$\infty$	$\infty$
$D(1_A)$	－	（2）	$\infty$	－	3	$\infty$
$B(2_A)$	－	－	5	－	（3）	7
$E(3_D)$

Q19．Donner et expliquer la valeur obtenue du plus court chemin entre＂

A

＂et＂

F

＂． Expliciter le chemin le plus court entre＂

A

＂et＂

F

＂．

⟶

類－

颣

－

類

，

－

，

－

｜

都

－

都

｜

－

｜

－

✓

－

✓

－

．

－

✓

－

✓

✓

Q20. Requête 1

Q21. Requête 2

Q22. Requête 3

1. L'algorithme de Luhn, ou code de Luhn, ou encore formule de Luhn est aussi connu comme l'algorithme "modulo 10".
1. Une procédure est une fonction qui retourne la valeur None mais cette valeur n'est pas destinée à être utilisée ou à être capturée.

Questions fréquentes

4 questions

Sur quels chapitres porte l'épreuve d'informatique commune CCINP TSI 2023 ?

Le sujet couvre la manipulation de listes et de chaînes, les dictionnaires, le parcours de graphe avec l'algorithme de Dijkstra et les requêtes SQL, en mobilisant surtout le programme de première année et quelques notions de seconde année.

Quelles erreurs le jury a-t-il le plus relevées ?

Le jury cite la manipulation des listes et du slicing, les confusions entre types int et str, la valeur retournée par une fonction, et la copie superficielle ou profonde de listes de listes.

L'algorithme de Dijkstra est-il au programme de la filière TSI ?

Non, il est hors programme de TSI, mais l'énoncé présentait tous les points nécessaires à sa compréhension.

Ce sujet est-il faisable avec le seul programme de première année ?

Le sujet fait très largement appel aux connaissances de première année, tout en intégrant de nouvelles notions du programme de seconde année comme les dictionnaires et les graphes.

Pas de description pour le moment

Commentaires• CCINP Informatique Commune TSI 2023

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...