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.
Le sujet est d’une durée de 3 h. Il est composé de 3 parties indépendantes.
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.
Chaque camion de l’entreprise peut charger une cargaison jusqu’à un poids maximal noté ${\tt Pmax}$. L’entreprise dispose de différentes informations provenant de ses clients:
transport de ce produit.
En considérant que l’entreprise dispose de ${\tt n}$ clients, l’entreprise cherche donc à trouver une liste d'indices notée ${\tt I}$ contenue dans ${\tt \{1, \dots,n\} }$ telle que:
Dans toute la suite, les poids seront donnés en centaines de kilogrammes et les valeurs en centaines d’euros.
On suppose que ${\tt n = 4}$ et que ${\tt Pmax = 8}$ centaines de kilogrammes. On stocke alors les différentes informations dans trois listes:
Par exemple, le produit 2 a un poids de deux centaines de kilogrammes et une valeur de trois centaines d’euros.
Q1. Donner toutes les cargaisons de trois produits respectant le poids maximal. On donnera à chaque fois le profit fait par l’entreprise.
Solution Q1. 1,2,3 donne un poids de 600 et un profit de 800.
2,3,4 donne un poids de 700 et un profit de 1300.
1,3,4 donne un poids de 800 et un profit de 1400.
1,2,4 ne respecte pas le poids maximal.
Q2. Quelle est la cargaison maximisant le profit de l’entreprise ? Que vaut le poids dans ce cas ?
Solution Q2. La cargaison 1,3,4 donne un profit de 1400 avec un poids de 800.
Gardons les notations de la sous-partie précédente, soit:
Q3. Définir une fonction ${\tt ListeProduits}$ ayant pour argument un entier naturel non nul ${\tt n}$ et qui retourne la liste ${\tt Pr}$.
#solution1
ListeProduits = [ k for k in range(1,n+1) ]
#solution2
ListeProduits = list(range(1,n+1)) # ListeProduits = range(1,n+1) ne donne pas une variable de type liste
#solution3
ListeProduits = []
for k in range(1,n+1):
ListeProduits.append(k)
#solution4
ListeProduits = []
for k in range(1,n+1):
ListeProduits = ListeProduits + [k]
Une méthode intuitive pour tenter d’optimiser le profit de l’entreprise est la suivante : on calcule les ratios ${\tt \displaystyle\frac{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.
Q4. Définir une fonction ${\tt Ratio}$ ayant pour arguments deux listes ${\tt P}$, ${\tt V}$ où ${\tt P}$ et ${\tt V}$ correspondent respectivement à la liste des poids et des valeurs, renvoyant la liste des ratios ${\tt \displaystyle\frac{v_i}{p_i}}$.
# solution1
def Ratio(P,V):
n = len(P)
liste = []
for k in range(n):
liste.append(V[k]/P[k])
return liste
# solution2
def Ratio(P,V):
n = len(P)
liste = [ V[k]/P[k] for k in range(n) ]
return liste
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
Q5. On exécute ${\tt Tri(L)}$ avec ${\tt L=[3, 5, 2, 1]}$. Combien y a-t-il d’itérations de la boucle ${\tt for}$?
Donner la valeur
de ${\tt L}$ à la fin de chaque itération de la boucle ${\tt for}$.
Solution Q5. Nombre d'itérations de la boucle ${\tt for}$: 3.
Après l'itération 1: ${\tt L=[3,5,2,1]}$
Après l'itération 2: ${\tt L=[2,3,5,1]}$
Après l'itération 3: ${\tt L=[1,2,3,5]}$
Q6. Ce tri fonctionnerait-t-il pour une chaîne de caractères dont chaque caractère est un entier ? Justifier.
Solution Q6. Oui grâce à l'ordre lexicographique.
Q7. Quelle est la méthode de tri utilisée dans la fonction ${\tt Tri}$? Donner sa complexité en nombre de comparaisons et en utilisant la notation de Landau dans le pire des cas. On justifiera soigneusement ces résultats.
Solution Q7. Méthode de tri utilisée: tri par insertion.
Complexité dans le pire des cas: ${\tt O(n^2)}$.
En effet on effectue n-1 passages dans la boucle for. Pour le i-ième passage, le pire des cas correspond à i passages dans la boucle while et on effectue alors 1 comparaison. Le nombre de comparaisons dans le pire des cas est donc:
$$\displaystyle \sum_{i=1}^{n-1}i=1+2+\dots+(n-1)=\frac{(n-1)n}{2}$$
Q8. Définir une fonction ${\tt Inverse}$ ayant pour argument une liste de nombres réels ${\tt L}$ et renvoyant l’inverse de
celle-ci.
Par exemple, l’inverse de ${\tt [1, 5, 3, 4]}$ est ${\tt [4, 3, 5, 1]}$.
La syntaxe ${\tt L[::-1]}$ n’est pas autorisée.
# solution itérative
def Inverse(L):
n = len(L)
L2 = []
for k in range(n):
L2.append(L[n-1-k])
return L2
# solution récursive
def Inverse(L):
if len(L) <= 1:
return L
else:
return Inverse(L[1:]) + [ L[0] ]
Q9. On souhaite trier une liste de poids ${\tt P}$ et une liste de valeurs ${\tt V}$ associées à une liste de produits en suivant l’ordre décroissant de la liste des ratios ${\tt \displaystyle\frac{v_i}{p_i}}$. Justifier que les fonctions ${\tt Ratio}$, ${\tt Tri}$ et ${\tt Inverse}$ ne permettent pas de répondre simplement au problème posé.
Solution Q9. La fonction ${\tt Tri}$ permet de trier la liste donnée par la fonction ${\tt Ratio}$. On inverse l'ordre avec la fonction ${\tt Inverse}$. Mais on n'a pas enregistré la correspondance entre les produits et les ratios donc on ne sait pas quel produit a le meilleur ratio.
Q10. Écrire, à l’aide des fonctions ${\tt Ratio}$ et ${\tt Inverse}$, une fonction ${\tt Tri2}$ ayant pour arguments une liste de
poids ${\tt P}$ et une liste de valeurs ${\tt V}$ associées à une liste de produits.
Cette fonction renverra 2 listes ; les listes des
poids et des valeurs triées par ordre décroissant de la liste des ratios.
La construction de cette fonction peut s’inspirer avantageusement de la fonction ${\tt Tri}$ rappelée à la question Q4.
def Tri2(P,V):
L = Ratio(P, V)
for i in range(1, len(L)):
x, y ,z = L[i], P[i], V[i]
j = i
while j > 0 and x < L[j-1]:
L[j], P[j], V[j] = L[j-1], P[j-1], V[j-1]
j = j-1
L[j], P[j], V[j] = x, y ,z
return Inverse(P), Inverse(V)
Q11. Ecrire une fonction ${\tt Vmax}$ qui a pour arguments les listes des poids ${\tt P}$, des valeurs ${\tt V}$ et le poids maximal ${\tt Pmax}$ du chargement et qui renvoie la valeur maximale du profit de l’entreprise en suivant la méthode intuitive proposée.
def Vmax(P, V, Pmax):
P2, V2 = Tri2(P, V)
SP = 0
SV = 0
i = 0
while SP + P2[i] <= Pmax: # on charge tant qu'on n'a pas atteint le poids max
SP = SP + P2[i]
SV = SV + V2[i]
i = i+1
return SV
Q12. On souhaite appliquer cette méthode en utilisant les listes des poids et des valeurs définies en I.1. Donner
la liste des ratios, les listes des poids et des valeurs obtenues à l’aide de la fonction ${\tt Tri2}$ ainsi que le profit obtenu.
La méthode intuitive proposée est-elle optimale ou sous-optimale ? Commenter et justifier votre réponse.
Solution Q12. Liste des ratios: ${\tt \displaystyle \left[\frac{4}{3},\frac{3}{2},1,\frac{9}{4}\right]}$
Liste des ratios dans l'ordre décroissant: ${\tt \displaystyle \left[\frac{9}{4},\frac{3}{2},\frac{4}{3},1\right]}$
Liste des poids correspondants: ${\tt \displaystyle \left[4,2,3,1\right]}$
Liste des valeurs correspondantes: ${\tt \displaystyle \left[9,3,4,1\right]}$
Le profit est de 12 en prenant les objets 2 et 3. Ce n'est pas le profit optimal d'après Q2.
Nous gardons les notations de la partie I.2 soit ${\tt Pr}$, ${\tt P}$ et ${\tt V}$. Afin de simplifier l’étude, considérons que les poids des
produits sont des entiers, ainsi que ${\tt Pmax}$.
Nous introduisons une méthode récursive pour résoudre ce problème d’optimisation:
l’indice ${\tt n}$, puis l’indice ${\tt n-1}$ et ainsi de suite jusqu’à l’indice 0 (correspondant au cas où il n’y a plus de produits),
l’on peut placer dans un camion d’une capacité maximale (en poids) de ${\tt\omega}$ avec la liste constituée des ${\tt i}$ premiers
produits de ${\tt Pr}$.
On pose alors la relation de récursivité suivante:
$${\tt S(i,\omega)=}\left\{\begin{array}{ll} {\tt 0}&{\tt \hbox{si }i=0}\\
{\tt S(i-1,\omega)}&{\tt \hbox{si }i>0\hbox{ et }p_i>\omega}\\
{\tt \max\big(S(i-1,\omega),v_i+S(i-1,\omega-p_i)\big)}&{\tt \hbox{si }i>0\hbox{ et }p_i\leq\omega}\end{array}\right.$$
Q13. Justifier les relations précédentes dans les trois cas.
Solution Q13.
Q14. Justifier la terminaison de l’algorithme associé à la relation de récursivité précédente, sachant que la première valeur donnée pour ${\tt i}$ sera ${\tt n}$ et la première valeur pour ${\tt \omega}$ sera ${\tt Pmax}$.
Solution Q14. L'algorithme s'arrête si ${\tt i=0}$. Pour ${\tt i}$ quelconque on appelle le même algorithme avec ${\tt i-1}$. En partant de ${\tt i=n}$ on fait donc ${\tt n}$ appels récursifs avant de tomber sur la close d'arrêt.
Q15. Définir une fonction ${\tt Max}$ ayant pour arguments deux réels et renvoyant le maximum parmi ces deux valeurs. Il est interdit d’utiliser la fonction ${\tt max}$ prédéfinie dans Python.
def Max(a, b):
if a>b:
return a
else:
return b
Q16. En vous basant sur la relation de récursivité donnée ci-dessus, compléter la définition de la fonction récursive recur ci-dessous ayant pour arguments les listes de poids et de valeurs ${\tt P}$ et ${\tt V}$, un indice ${\tt i}$, un poids ${\tt \omega}$, et renvoyant ${\tt S(i,\omega)}$.
def recur(P,V,i,w) :
if i==0:
return...................
if P[i-1]>w:
return recur(P,V,i-1,w)
else :
..................
def recur(P, V, i, w):
if i == 0:
return 0
if P[i-1] > w:
return recur(P, V, i-1, w)
else:
return Max( recur(P, V, i-1, w), V[i-1] + recur(P, V, i-1, w-P[i-1]) )
Q17. Donner une série d’instructions utilisant la fonction ${\tt recur}$ et permettant de déterminer le profit de la sous-partie I.1.
P = [3,2,1,4]
V = [4,3,1,9]
recur(P,V,4,8)
À 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.
Le client est identifié par un nombre codé en binaire sur 8 bits. Ainsi, le code ${\tt "00010111"}$ est associé au client dont
l’identifiant est le numéro 23.
Q18. Donner le codage associé au client 39.
Solution Q18. $39=32+4+2+1=2^5+2^2+2^1+2^0=$ $"0b100111"$
Afin de retrouver l’identifiant de chaque client à l’aide de son code binaire ${\tt Bin}$ typé ${\tt str}$, la fonction suivante est proposée :
1 def Identifiant(Bin):
2 '''Bin est est une chaine de caractères constituée de 0 et 1'''
3 S=0
4 for i in range(len(Bin)) :
5 S = S + Bin[i]*2**(len(Bin)-i)
6 return S
Q19. Trouver les deux erreurs dans le code de la fonction précédente.
Solution Q19.
S = S + int(Bin[i])*2**(len(Bin)-i-1)
On suppose maintenant la fonction précédente corrigée. La ligne 5 pose un problème de complexité : à chaque itération de boucle, la puissance de 2 est recalculée entièrement.
Q20. Écrire une fonction ${\tt Identifiant2}$, qui donne le même résultat que la fonction ${\tt Identifiant}$ avec une
meilleure complexité. Le nombre de multiplications devra être linéaire suivant la longueur de ${\tt Bin}$.
Chut, il faut connaître le schéma de Horner présenté en cours, ...
def Identifiant2(Bin):
S=0
p=1
for i in range(len(Bin)):
S=S+int(Bin[len(Bin)-i-1])*p
p=2*p
return S
Q21. Si l’entreprise souhaite aussi stocker la zone de chaque client en codage binaire, donner le nombre de bits minimal nécessaire.
Solution Q21. Il y a 30 zones. La plus petite puissance de 2 immédiatement supérieure est $32=2^5$ donc on a besoin de 5 bits minimum.
Le chargement une fois effectué, il s’agit ensuite de déterminer le trajet optimal qui minimise la distance parcourue.
Le graphe ci-dessous est le modèle du réseau routier des différents sites à livrer. Ses sommets représentent les lieux de livraison et les arêtes, les distances exprimées en kilomètres entre ces différents lieux.
Lorsque le livreur termine son parcours en D, il souhaite revenir en B le plus rapidement possible.
On rappelle l’algorithme de Dijkstra:
Q22. Déterminer ce plus court chemin en utilisant l’algorithme de Dijkstra. Compléter pour cela le document réponse DR1 en précisant les valeurs de ${\tt x}$, ${\tt D}$, ${\tt C}$, ${\tt Dist}$ et ${\tt Pred}$ à la fin de chaque itération de la boucle «tant que».
Q23. Quelle est la distance parcourue en km pour le trajet de retour ?