Optimisation du chargement de camions de livraison et gestion d'une base de données de livraisons
Afficher ou masquer la section
Le sujet est composé de deux parties indépendantes. La première étudie un problème d'optimisation du chargement de camions (variante du sac à dos) avec une méthode intuitive de tri par ratio puis une méthode récursive avec mémoïsation. La seconde porte sur une base de données de livraisons interrogée en SQL et sur un codage binaire d'identifiants clients.
1Partie I : optimisation du chargementpremière année et deuxième annéeRecherche d'une cargaison de poids maximal et de valeur maximale, d'abord par une méthode de tri intuitive puis par une méthode récursive avec mémoïsation.
2Partie II : données liées aux livraisonsRequêtes SQL sur une base de données à trois tables et codage binaire des identifiants clients.
Deux tiers des copies environ (moyenne ± écart-type)
Votre note sur 20 à ce sujet, en conditions de concours.
Source : document officiel du concours, épreuve du 5 mai 2021. 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
Manipulation des listes · Caractère non mutable des chaînes · Clé primaire de la table livraison
Afficher ou masquer la section
Le rapport relève des lacunes récurrentes sur les listes et les chaînes de caractères, ainsi que des questions de bases de données souvent traitées mais avec un manque de rigueur dans la syntaxe. Les correcteurs signalent aussi des copies peu lisibles et non soignées, ce qui a été pris en compte dans l'évaluation.
Les erreurs les plus sanctionnées
1
Manipulation des listesQ4, Q5
Le jury relève des erreurs récurrentes comme l'utilisation de L[i]=x pour une liste vide, L=L+x au lieu de L=L+[x], ou des problèmes d'indices lors du parcours de listes.
« utilisation de « L[i]=x » pour une liste vide »
2
Caractère non mutable des chaînesQ7, Q26
Le caractère non mutable d'une chaîne de caractères est peu connu des candidats, ce qui pose problème dans plusieurs questions.
3
Clé primaire de la table livraisonQ21
La notion de clé primaire n'est pas du tout acquise par une large majorité de candidats sur cette question.
« La notion de clé primaire n’est pas du tout acquise par une large majorité de »
4
Syntaxe SQLQ22, Q23, Q24
Des requêtes SQL pourtant simples sont mal maîtrisées, certains candidats tentant par exemple d'utiliser « SELECT date AND heure ».
« SELECT date AND heure »
5
Terminaison de la récursivitéQ14
La question sur le stop d'un appel récursif est jugée laborieuse alors que c'est une compétence attendue.
« Travailler le stop d’un appel récursif, en quelques mots, est une compétence attendue »
Ce qui a été bien réussi
Les questions Q2 et Q3 sont généralement bien traitées.
La question Q17, non triviale, est globalement réussie.
La question Q25, simple, est très bien réussie.
Conseils du jury
Soigner la présentation des copies et barrer proprement en cas d'erreur.
Se relire pour éviter les fautes d'orthographe.
Justifier soigneusement les complexités données plutôt que d'avancer des arguments approximatifs.
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.
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 deux parties indépendantes.
Le sujet comporte :
le texte du sujet : page 1 à page 6;
le Document Réponse : page 1 à page 11.
Le Document Réponse doit être rendu dans son intégralité.
Optimisation de rendement d'une entreprise de livraison
Une entreprise de livraison dispose de plusieurs locaux en France et chacun possède plusieurs camions de livraisons. Celle-ci souhaite optimiser le chargement de ses camions pour diminuer ses frais de fonctionnement.
Partie I - Optimisation du chargement
Chaque camion de l'entreprise peut charger une cargaison jusqu'à un poids maximal noté P_(max). L'entreprise dispose de différentes informations provenant de ses clients :
le poids de chaque produit p_i (chaque client propose un seul produit);
la valeur v_i associée au transport de chaque produit : c'est-à-dire l'argent gagné par l'entreprise si elle réalise le transport de ce produit.
En considérant que l'entreprise dispose de n clients, l'entreprise cherche donc à trouver une liste d'indices notée I contenue dans {1, …, n} telle que :
∑_(i ∈ I)p_i ≤ P_(max) (respect du poids maximal)
et
∑_(i ∈ I)v_i soit maximal (optimation du profit pour l'entreprise).
Dans toute la suite, les poids seront donnés en centaines de kilogrammes et les valeurs en centaines d'euros.
I. 1 - Un exemple
Dans cette sous-partie, on suppose que n = 4 et que P_(max) = 8 centaines de kilogrammes. On stocke alors les différentes informations dans trois listes :
Pr est la liste des produits proposés par les clients numérotés de 1 à 4 : Pr = [1, 2, 3, 4];
P est la liste des poids associés : P = [3, 2, 1, 4];
V est la liste des valeurs associées : V = [4, 3, 1, 9].
Par exemple, le produit 2 a un poids de deux centaines de kilogrammes et une valeur de trois centaines d'euros.
Les questions Q1, Q2 et Q3 se traitent à l'aide de calculs simples, à faire à la main.
Q1. Expliquer pourquoi une cargaison constituée d'un, de deux ou de quatre produits ne répond pas au problème posé, c'est-à-dire ne maximise pas le profit fait par l'entreprise en respectant la condition donnée sur le poids maximal.
Q2. Donner toutes les cargaisons de trois produits respectant le poids maximal. On donnera à chaque fois le profit fait par l'entreprise.
Q3. Quelle est la cargaison maximisant le profit de l'entreprise ? Que vaut le profit dans ce cas ?
I. 2 - Une méthode intuitive pour la résolution du problème
On garde les notations de la sous-partie précédente dans le cas général :
Pr est la liste des produits (numérotés de 1 à n inclus);
P = [p_1, …, p_n] est la liste des poids associés aux produits;
V = [v_1, …, v_n] est la liste des valeurs associées aux produits.
Q4. Définir une fonction ListeProduits ayant pour argument un entier naturel non nul n et renvoyant la liste Pr.
Une méthode intuitive pour tenter d'optimiser le profit de l'entreprise est la suivante : on calcule les ratios (v_i)/(p_i), puis on trie les objets par ordre décroissant suivant ces valeurs. Les produits sont alors classés par rentabilité : le premier produit devient le plus rentable " au poids " et ainsi de suite. On ajoute progressivement chaque produit dans la cargaison, dans cet ordre, sans dépasser la limite du poids maximal.
Q5. Définir une fonction Ratio ayant pour arguments deux listes P, V où P correspond à la liste des poids et V correspond à la liste des valeurs, renvoyant la liste des ratios (v_i)/(p_i).
La fonction suivante est associée à une méthode de tri :
def Tri(L):
,'' L est une liste de nombres réels ','
for i in range(1,len(L)):
x=L[i]
j=i
while j>0 and x<L[j-1]:
L[j]=L[j-1]
j=j-1
L[j]=x
return L
Q6. On exécute Tri(L) avec L = [3, 5, 2, 1]. Combien y a t-il d'itérations de la boucle for? Donner la valeur de L à la fin de chaque itération de la boucle for.
Q7. Ce tri fonctionnerait-t-il pour une chaîne de caractères dont chaque caractère est un entier? Justifier.
Q8. Quelle est la méthode de tri utilisée dans la fonction Tri ? Donner sa complexité (en nombre de comparaisons) dans le pire des cas et dans le meilleur des cas. On justifiera soigneusement les complexités données.
Q9. Définir une fonction Inverse ayant pour argument une liste de nombres réels L et renvoyant l'inverse de celle-ci. Par exemple, l'inverse de [1, 5, 3, 4] est [4, 3, 5, 1].
L'utilisation de L[ : − 1] n'est pas autorisée.
Q10. On souhaite trier une liste de poids P et une liste de valeurs V associées à une liste de produits en suivant l'ordre décroissant de la liste des ratios (v_i)/(p_i). Justifier que les fonctions Ratio, Tri et Inverse ne permettent pas de répondre simplement au problème posé.
Q11. Écrire, à l'aide des fonctions Ratio et Inverse, une fonction Tri2 ayant pour arguments une liste de poids P et une liste de valeurs V associées à une liste de produits. Cette fonction renverra les listes de poids et de valeurs triées par ordre décroissant de la liste des ratios.
Q12. Compléter la définition de la fonction Vmax ayant pour arguments les listes de poids P et de valeurs V et le poids maximal P_(max) du chargement et renvoyant la valeur maximale du profit de l'entreprise en suivant la méthode proposée.
Q13. On souhaite appliquer cette méthode en utilisant les listes de poids et de valeurs de la souspartie I.1. Donner la liste des ratios, les listes de poids et de valeurs obtenues à l'aide de la fonction Tri2 ainsi que le profit obtenu. Commenter le résultat.
I. 3 - Une méthode récursive
Nous gardons les notations du cas général de la sous-partie I. 2 : Pr, P et V. On considère pour simplifier que les poids des produits sont des entiers, ainsi que P_(max).
Nous introduisons une méthode récursive pour résoudre le problème d'optimisation :
pour chacun des produits, deux choix sont possibles : il fait partie de la cargaison ou non;
la récursivité s'effectuera sur la liste des indices de Pr : le premier appel de la fonction se fera en utilisant l'indice n, puis l'indice n − 1 et ainsi de suite jusqu'à l'indice 0 (correspondant au cas où il n'y a plus de produits);
pour i ∈ {0, 1, …, n} et ω ∈ {0, 1, …, P_(max)}, on note S(i, ω) la valeur maximale cumulée des produits que l'on peut placer dans un camion d'une capacité maximale (en poids) de ω avec la liste constituée des i premiers produits de Pr.
On pose alors la relation de récursivité suivante :
S(i, ω) = {0, si i = 0; S(i − 1, ω), si i > 0 et p_i > ω; max(S(i − 1, ω), v_i + S(i − 1, ω − p_i)), si i > 0 et p_i ≤ ω
Q14. Justifier les relations précédentes dans les trois cas.
Q15. Justifier la terminaison de l'algorithme associé à la relation de récursivité précédente, sachant que la première valeur donnée pour i sera n et la première valeur pour ω sera Pmax.
Q16. Définir une fonction Max ayant pour arguments deux réels et renvoyant le maximum parmi ces deux valeurs. Il est interdit d'utiliser la fonction max prédéfinie dans Python.
Q17. En vous basant sur la relation (3), compléter la définition de la fonction récursive recur ayant pour arguments les listes de poids et de valeurs P et V , un indice i, un poids ω, et renvoyant S(i, ω).
Q18. Donner une série d'instructions utilisant la fonction recur et permettant de déterminer le profit de la sous-partie I.1.
I. 4 - Amélioration de la méthode récursive
On souhaite améliorer la méthode récursive de la sous-partie I.3. Nous allons procéder en mémorisant des calculs déjà effectués. Voici le principe : nous allons stocker les valeurs S(i, ω) dans un tableau Memoire, de taille (n + 1) × (P_(max) + 1), initialisé au départ avec des éléments tous égaux à -1 .
Si la valeur de S(i, ω) a déjà été calculée, l'élément d'indice (i, ω) de ce tableau Memoire ne sera plus égal à -1 : on renverra donc directement la valeur. Sinon, on la calculera en suivant le principe de la sous-partie I. 3 et on la stockera dans le tableau avant de la renvoyer.
Nous faisons le choix de représenter les tableaux comme des listes de listes.
Q19. Donner l'instruction permettant de créer le tableau Memoire initialisé avec des coefficients égaux à -1 , en supposant Pmax et n connus.
Q20. Compléter la fonction recur2 en suivant le principe expliqué et permettant d'améliorer la fonction recur. La variable Memoire sera utilisée comme une variable globale.
Avec les données suivantes : − P = [5, 3, 3, 3]; − V = [4, 3, 1, 1];
P_(max) = 8;
Memoire un tableau de taille 5 × 9;
et en exécutant recur2 ( P, V, len (P), Pmax, Memoire), on obtient alors la valeur 7.
Partie II - Données liées aux livraisons conservées par l'entreprise
À chaque livraison, l'entreprise stocke des données relatives à celle-ci. L'entreprise dispose de 20 locaux, numérotés de 1 à 20 , disposant chacun d'un certain nombre de camions. Pour faciliter ses livraisons, l'entreprise découpe la France en 30 zones et associe à chaque local, trois zones possibles de livraisons.
Ces données sont enregistrées dans une base de données contenant trois tables :
La table livraison constituée des champs suivants :
date : date de la livraison au format "jj-mm-aaaa" (chaine de caractères);
heure : heure de la livraison au format : "hh-mm-ss" (chaine de caractères);
id_client : identifiant du client recevant la livraison (entier);
id_local: identifiant du local de l'entreprise (entier compris entre 1 et 20).
La table client constituée des champs suivants :
id : identifiant du client (entier);
zone : entier compris entre 1 et 30.
La table local constituée des champs suivants :
id : identifiant du local (entier compris entre 1 et 20);
zonel : entier;
zone2 : entier;
zone3 : entier.
Q21. Donner une clé primaire pour la table livraison.
Q22. Écrire une requête SQL permettant d'obtenir les identifiants des clients livrés le 10 janvier 2021.
Q23. Écrire une requête SQL permettant de récupérer les dates et les heures de toutes les livraisons ayant eu lieu dans la zone 5 le 2 mars 2021.
Q24. Écrire une requête SQL permettant de compter le nombre de livraisons effectuées le 3 février 2021 par des camions dont les locaux ne livrent que dans des zones possibles inférieures ou égales à dix.
Chaque identifiant de client est stocké par l'entreprise en codage binaire (avec 8 bits). Par exemple, 00010111 est associé au client dont l'identifiant est le numéro 23.
Q25. Donner le codage associé au client 39.
Afin de retrouver l'identifiant de chaque client à l'aide de son code binaire, la fonction suivante est proposée :
def Identifiant(Bin):
,''Bin est est une chaine de caractères
constituée de 0 et 1,''
S=0
for i in range(len(Bin)):
S=S+Bin[i]*2**(len(Bin)-i)
return S
Q26. Trouver les deux erreurs dans le code de la fonction précédente.
On suppose maintenant la fonction précédente corrigée. La ligne 6 pose un problème de complexité : à chaque itération de boucle, la puissance de 2 est recalculée entièrement.
Q27. Écrire une fonction Identifiant2, qui donne le même résultat que la fonction Identifiant avec une meilleure complexité. Le nombre de multiplications devra être linéaire suivant la longueur de Bin.
Q28. Si l'entreprise souhaite aussi stocker la zone de chaque client en codage binaire, donner le nombre de bits minimal nécessaire.
FIN
Document Réponse
Ce Document Réponse doit être rendu dans son intégralité.
Optimisation de rendement d'une entreprise de livraison
Q1
Q2
Q3
Cargaison maximisant le profit:
Profit maximal :
Q4
def ListeProduits(n) :
def Ratio(P,V) :
Q6
Nombre d'itérations de la boucle for :
Valeur de L après chaque itération :
Q7
Méthode de tri utilisée :
Complexité dans le pire des cas :
Complexité dans le meilleur des cas :
Justifications :
Sur quels chapitres porte le sujet d'informatique commune TSI 2021 du concours CCINP ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet d'informatique commune TSI 2021 du concours CCINP ?
+
Le sujet couvre la manipulation de listes et de chaînes de caractères, la complexité et la terminaison d'algorithmes, les tris, la récursivité, ainsi que les bases de données et le SQL.
Quelles erreurs le jury a-t-il le plus relevées sur ce sujet d'informatique TSI 2021 ?
+
Le jury relève surtout des erreurs de manipulation des listes (création, append, indices), une mauvaise connaissance du caractère non mutable des chaînes de caractères, et une syntaxe SQL souvent fautive.
Le sujet d'informatique commune CCINP TSI 2021 est-il accessible dès la première année ?
+
La partie I mobilise des notions de première année comme deuxième année (récursivité, tri), tandis que la partie II porte sur les bases de données, un thème également au programme de première année.
Pas de description pour le moment
Commentaires• CCINP Informatique Commune TSI 2021
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même année, CentraleCentrale Informatique Commune MP PC PSI TSI 2021Centrale · 2021Corrigé
.jpg)
