Mines Informatique MP-PC-PSI 2025

A2025 ­ INFO COMMUNE

ÉCOLE NATIONALE DES PONTS et CHAUSSÉES,
ISAE-SUPAERO, ENSTA PARIS,
TÉLÉCOM PARIS, MINES PARIS,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT ATLANTIQUE, ENSAE PARIS,
CHIMIE PARISTECH - PSL.
Concours Mines-Télécom,
Concours Centrale-Supélec (Cycle International).
CONCOURS 2025
ÉPREUVE D'INFORMATIQUE COMMUNE
Durée de l'épreuve : 2 heures
L'usage de la calculatrice ou de tout dispositif électronique est interdit.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE COMMUNE
Cette épreuve est commune aux candidats des filières MP, PC et PSI.
L'énoncé de cette épreuve comporte 14 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur 
d'énoncé, il le
signale sur sa copie et poursuit sa composition en expliquant les raisons des 
initiatives qu'il est
amené à prendre.

.
Les sujets sont la propriété du GIP CCMP. Ils sont publiés sous les termes de 
la licence
Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de 
Modification 3.0 France.
Tout autre usage est soumis à une autorisation préalable du Concours commun 
Mines Ponts.

Autour du sac à dos

Introduction

Le problème du sac à dos, noté également KP (knapsack problem), est un problème
d'optimisation combinatoire. Il modélise une situation analogue à celle du 
remplissage d'un
sac à dos ne pouvant pas supporter plus d'un certain poids, avec tout ou partie 
d'un ensemble
donné d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac 
à dos doivent
maximiser la valeur totale (le profit), avec la contrainte de ne pas dépasser 
le poids maximum
admissible (la quantité totale de ressources disponibles).
D'un point de vue mathématique, la formulation du problème du sac à dos est la 
suivante :
Maximiser le profit total P =

n°1
X

p i x i sous la contrainte

i =0

n°1
X
i =0

r i xi  b

où
· n est le nombre d'objets candidats,
· i est l'entier caractérisant l'objet (i 2 J0, n ° 1K),
· p i est le profit (ou valeur) associé à l'objet i ,
· x i est la variable de décision associée à l'objet i : x i = 1 si l'objet i 
est sélectionné et
x i = 0 sinon,
· r i est la quantité de ressources consommée par l'objet i (ou poids de 
l'objet i ),
· b est la quantité totale de ressources disponibles (ou poids total).

On ne considère que des cas où chaque ressource r i , chaque profit p i et la 
quantité de
ressources disponibles b, sont des entiers.
On fait aussi l'hypothèse que 8i 2 J0, n ° 1K, r i  b.

Dans le problème du sac à dos multidimensionnel, noté MKP, on considère 
plusieurs sacs
à dos ayant chacun un poids maximum admissible. L'objectif est alors de 
maximiser la valeur
totale des objets contenus dans l'ensemble des sacs à dos.
Les applications pratiques sont nombreuses : transport de marchandises, découpe 
de
matériaux, gestion de portefeuilles financiers, allocation de tâches à des 
systèmes multiprocesseurs, ...

1 Base de données - Exemple de fret maritime de conteneurs
On donne les tables NAVIRES et CONTENEURS suivantes :
· NAVIRES(idN,evp,portDepN,dateDep,portDestN)
· idN : clé primaire, identifiant du navire (type entier, non nul)
· evp : capacité en équivalent conteneurs de longueur 20 pieds (type entier)
· portDepN : port de départ (type chaîne de caractères)
· dateDep : date de départ (type date)
· portDestN : port de destination (type chaîne de caractères)
1

idN
12
2
5
8
...

evp
1500
16000
500
23000
...

portDepN
"Marseille"
"Valence"
"Le Havre"
"Hongkong"
...

dateDep
2025-06-23
2025-06-18
2025-10-06
2025-07-02
...

portDestN
"Hambourg"
"Algésiras"
"Rotterdam"
"Shanghai"
...

· CONTENEURS(idC,idN,taille,portDepC,dateDisp,portDestC,val)
· idC : clé primaire, identifiant du conteneur (type entier)
· idN : identifiant du navire attribué (type entier, valeur 0 si non encore 
attribué).
· taille : longueur du conteneur, 20 ou 40 pieds (type entier). La hauteur et 
la profondeur sont identiques.
· portDepC : port de départ (type chaîne de caractères)
· dateDisp : date de mise à disposition (type date)
· portDestC : port de destination (type chaîne de caractères)
· val : tarification, valeur entière de 1 à 5 par ordre croissant de profit 
pour l'entreprise
(type entier)
idC
103
218
5
885
...

idN
12
12
0
8
...

taille
20
40
40
20
...

portDepC
"Marseille"
"Marseille"
"Le Havre"
"Hongkong"
...

dateDisp
2025-08-08
2025-07-08
2025-10-01
2025-07-01
...

portDestC
"Hambourg"
"Valence"
"Shangai"
"Barcelone"
...

val
2
1
5
1
...

Pour les deux questions qui suivent, on demande d'écrire les requêtes en 
langage SQL.
On notera que pour les valeurs d'attributs de type date (format AAAA-MM-JJ), 
les relations
d'ordre (<, , >, , =, 6=) sont autorisées. Par exemple, 2025-07-02 < 2025-10-03. o Q1 ­ Écrire une requête permettant de retourner la liste des identifiants de conteneurs et leur ratio tarification/longueur trié par ordre décroissant, partant de Marseille et devant aller à Barcelone, avec une mise à disposition avant le 01/01/2025. o Q2 ­ Écrire une requête permettant de retourner les identifiants de navire et leur nombre respectif de conteneurs attribués. 2 Structure de données pour l'espace des objets On demande d'utiliser exclusivement le langage Python pour toute la suite du sujet. On implémente l'espace des objets i (i 2 J0, n ° 1K) avec une structure informatique obj de type liste de taille n. La valeur de obj[i] est un tuple (ri,pi) où ri et pi sont les valeurs respectives des paramètres r i et p i de l'objet i . Par exemple, (10,5) permet de définir pour un objet étiqueté 3 les paramètres r 3 = 10 et p 3 = 5. Une solution au problème du sac à dos S = [x 0 , x 1 , ..., x n°1 ], est implémentée par une liste Python. On rappelle que x i = 1 si l'objet i est sélectionné et x i = 0 sinon. 2 Pour les deux questions qui suivent, la fonction python sum ne sera pas utilisée. o Q3 ­ Écrire une fonction profit(obj:[(int)],S:[int])->int prenant en argument
une liste obj et une liste S, et retournant la valeur du profit P.
o Q4 ­ Écrire une fonction contrainte(obj:[(int)],S:[int],b:int)->bool prenant
en argument une liste obj, une liste S et un nombre b, et retournant le booléen 
True si la
contrainte de ressources du problème du sac à dos est respectée, False dans le 
cas contraire.

3 Structure de données pour l'espace des solutions
On choisit de modéliser l'espace des solutions au problème du sac à dos avec un 
arbre
n°1
X
binaire (figure 1). On ne s'intéresse pas pour le moment au respect de la 
contrainte
r i x i  b.
i =0

0

1

1

2

a

2

b

c

2

e

d

2

f

g

h

Figure 1 ­ Arbre binaire et espace des solutions pour le cas particulier où n = 
3
À chaque noeud, deux choix sont possibles :
-- Fils gauche : l'objet i (i 2 J0, n ° 1K) est sélectionné (x i = 1).
-- Fils droit : l'objet i (i 2 J0, n ° 1K) n'est pas sélectionné (x i = 0).
Au niveau le plus élevé (la racine), le choix se porte sur l'objet 0. Au niveau 
immédiatement
inférieur, le choix se fait sur l'objet 1, et ainsi de suite ... jusqu'à 
l'objet n ° 1.
Au niveau le plus bas, sont définies les feuilles (sans successeur). À chacune 
d'entre-elles
correspond une solution du type S = [x 0 , x 1 , ..., x n°1 ] décrivant les 
choix effectués le long du
chemin menant de la racine à la feuille considérée.

o Q5 ­ Sur l'exemple de la figure 1 où n = 3, à quoi est égale la liste S pour 
les feuilles b et c ?
o Q6 ­ Donner le nombre de feuilles de l'arbre binaire en fonction du nombre 
d'objets n.
Indiquer en la justifiant la complexité temporelle en fonction du nombre 
d'objets n d'un
algorithme de résolution du problème du sac à dos de type "force brute" qui 
envisagerait
toutes les combinaisons possibles de sélection d'objets.
Lorsque le nombre d'objets n devient grand, un parcours de toutes les solutions 
n'est pas
possible en un temps raisonnable.
3

4 Résolution approchée par un algorithme glouton
On envisage une stratégie gloutonne pour la résolution du problème du sac à 
dos. Lorsque
le choix de sélectionner un objet est fait, il ne sera plus remis en question. 
Les étapes sont les
suivantes :

1) On construit la liste Lqi qui contient pour chaque objet i 2 J0, n ° 1K le 
rapport profit
sur ressource consommée q i = p i /r i . En parallèle, on construit la liste 
Li, telle qu'initialement Li[i] vaut i . La liste Li est telle que Li[j] ( j 2 
J0, n ° 1K) donne l'indice
dans la liste obj de l'objet décrit par le rapport situé en position j dans Lqi.
2) On trie la liste Lqi par ordre décroissant et on modifie simultanément la 
liste Li de
sorte que 8 j 2 J0, n ° 2K, Lqi [Li [ j ]]  Lqi [Li [ j + 1]].
3) En partant de la quantité totale de ressources disponibles b, on sélectionne 
l'objet i de
rapport q i le plus grand possible tel que r i  b.

4) On met à jour la quantité de ressources disponibles b = b ° r i et on 
réitère le processus à partir de 3) jusqu'à ce qu'il ne soit plus possible de 
sélectionner un objet
supplémentaire.

o Q7 ­ On prend le cas particulier où obj=[(2,3),(1,4),(4,4)] et b=5. Expliquer 
quelle
liste S est construite par la stratégie gloutonne précédente.
Le code incomplet de la fonction construitLi(obj:[(int)])->[int] qui prend en
argument la liste obj et qui retourne la liste Li définie précédemment, est 
donné ci-après. Cet
algorithme correspond aux étapes 1 et 2 décrites en introduction de la 
stratégie gloutonne.

def construitLi(obj):
Lqi=[]
3
Li=[]
4
for i in range(len(obj)):
5
Lqi.append(.........)
6
Li.append(i)
7
for i in range (1,len(Lqi)):
8
x=Lqi[i]
9
j=i
10
while j>0 and Lqi[j-1]int donnée en page suivante,
implémente un algorithme de programmation dynamique itératif.

5

def KPprogDynamique(obj,b):
2
T=[]
3
n=len(obj)
4
for k in range(n+1):
5
L=[]
6
for r in range(b+1):
7
L.append(0)
8
T.append(L)
9
for i in range(n):
10
for r in range(b+1):
11
if obj[i][0]<=r: 12 T[i+1][r]=max(T[i][r],T[i][r-obj[i][0]]+obj[i][1]) 13 else: 14 T[i+1][r]=T[i][r] 15 return T[n][b] 1 o Q12 ­ On reprend le cas particulier où obj=[(2,3),(1,4),(4,4)] et b=5. Donner sans justifications les valeurs du tableau T à l'issue de l'exécution des lignes 2 à 8. Puis, à la fin de chacune des trois itérations de la boucle for en ligne 9, donner la valeur de T[i+1]. Préciser ce que retourner la fonction KPprogDynamique(obj,b) et à quoi correspond cette valeur. o Q13 ­ Déterminer en la justifiant la complexité asymptotique temporelle de la fonction KPprogDynamique(obj,b). On conserve les 14 premières lignes de la fonction proposée précédemment. On complète avec les lignes de code suivantes afin de retourner la solution S sous la forme S=[x0,x1,...] et la valeur de T[n][b]. def KPprogDynamique(obj,b): # 3 #Lignes 2 à 14 précédentes conservées 4 # 5 S=n*[0] 6 k=n-1 7 r=b 8 while r>0 and k>=0 and T[k+1][r]!=0:
9
while k>0 and T[k+1][r]==T[k][r]:
10
k-=1
11
S[k]=1
12
r=r-obj[k][0]
13
k-=1
14
return S,T[n][b]
1
2

o Q14 ­ Donner les valeurs des variables S, k et r après chaque itération de la 
boucle while
en ligne 8. Indiquer en justifiant si la complexité asymptotique temporelle de 
la fonction
KPprogDynamique(obj,b) est ainsi modifiée.

6

6 Résolution exacte par un algorithme PSE
Un algorithme par séparation et évaluation (PSE) ou branch and bound permet 
d'éliminer
de l'arbre des solutions, les branches qui ne peuvent pas contenir la solution 
optimale. Cet
"élagage" de l'arbre permet d'éviter l'exploration complète de celui-ci.
On applique dans un premier temps un algorithme glouton afin d'avoir en un temps
raisonnable une solution approchée de la solution optimale dont le profit est 
noté P mi n .
La reformulation du problème initial est donc :
Maximiser le profit total P =

n°1
X

p i x i sous les contraintes

i =0

n°1
X
i =0

r i x i  b et P > P mi n .

L'arbre binaire des solutions arbreSol est implémenté par une structure 
récursive (figure
2). Chaque noeud est lui-même un arbre binaire qui construit niveau par niveau 
une solution.
On modélise chacun par un dictionnaire possédant trois clés de type str :
· 'S' : le vecteur courant solution :
· arbresol['S']=[ ] pour la racine de l'arbre (liste vide),
· arbresol['S']=[x 0 , x 1 , ..., x k°1 ] à la profondeur k (k 2 J1, n K),
· 'g' : le noeud "fils" de gauche,
· 'd' : le noeud "fils" de droite.
À la profondeur k = n,
· arbresol['S']=[x 0 , x 1 , .., x n°1 ] : le vecteur est une solution,
· arbresol['g']={} : le noeud "fils" de gauche est un dictionnaire vide,
· arbresol['d']={} : le noeud "fils" de droite est un dictionnaire vide.
[]

[1]

[1,1]

[1,1,1]

{}

[0]

[1,0]

[1,1,0]

{}

{}

{}

Figure 2 ­ Arbre binaire partiel pour n = 3 avec les valeurs de arbresol['S'] à 
chaque noeud

La fonction récursive construireArbreBinaire(a:dict,n:int) permet, en page 
suivante, de construire un tel arbre.

7

def construireArbreBinaire(a,n):
2
if n==0:return a
3
else:
4
filsGauche={'S':a['S']+[1],'g':{},'d':{}}
5
filsDroit={'S':a['S']+[0],'g':{},'d':{}}
6
a['g']=filsGauche
7
a['d']=filsDroit
8
construireArbreBinaire(filsGauche,n-1)
9
construireArbreBinaire(filsDroit,n-1)
1

Par exemple, le code suivant permet de construire un arbre des solutions pour n 
= 3 :

arbreSol={'S':[],'g':{},'d':{}}
2 construireArbreBinaire(arbreSol,3)
1

o Q15 ­ Écrire une fonction estFeuille(a:dict)->bool qui prend en argument un 
arbre
a et qui retourne le booléen True si a est une feuille, False dans la cas 
contraire.

Le profit P mi n obtenu par un algorithme glouton est stocké dans la variable 
globale Pmin.

o Q16 ­ Écrire une fonction possible(obj:[(int)],Sk:[int],b:int)->bool qui prend
en argument la liste des objets obj, une liste Sk valeur d'une solution 
courante d'un noeud de
niveau k 2 J1, n K (len(Sk)=k) et la quantité de ressources disponibles b. La 
fonction retourne
le booléen True s'il est utile de poursuivre l'exploration des noeuds 
inférieurs. La fonction
retourne False dans le cas contraire. On s'assure ici que :

-- la condition de ressources est satisfaite : on utilise pour cela la fonction
contrainte(obj:[(int)],S:[int],b:int)->bool avec un vecteur solution S de
longueur n égal à la liste Sk complétée par des 0. On vérifie ainsi dans un 
premier
temps que le simple ajout de l'objet à la profondeur k (k 2 J1, n K) ne 
consomme pas
trop de ressources disponibles,
-- il est possible de trouver une meilleure solution que l'algorithme glouton : 
on utilise
la fonction profit(obj:[(int)],S:[int])->int avec un vecteur solution S égal
à la liste Sk complétée par des 1 en une liste de longueur n pour simuler le 
profit
maximal de la branche avec l'ajout de tous les objets non encore traités à la 
profondeur
k (k 2 J1, n K).

On adopte un algorithme récursif KPforceBrute(arbre:dict,obj:[(int)],b:int),
de résolution optimale par « force brute » du problème du sac à dos. Le code 
Python est donné
en page suivante.
La variable Pmin est réactualisée s'il existe une solution meilleure que celle 
trouvée par
une stratégie gloutonne et la solution optimale correspondante est alors mise à 
jour dans la
variable globale Sol.

8

def KPforceBrute(arbre,obj,b):
2
global Pmin,Sol
3
if estFeuille(arbre) :
4
if contrainte(obj,arbre['S'],b):
5
P=profit(obj,arbre['S'])
6
if P>Pmin:
7
Pmin=P
8
Sol=arbre['S']
9
else:
10
KPforceBrute(arbre['g'],obj,b)
11
KPforceBrute(arbre['d'],obj,b)
1

On souhaite à la fois :
-- "élaguer" les branches de l'arbre des solutions qui ne peuvent pas contenir 
de solution
de profit supérieur à la valeur P mi n obtenue par un algorithme glouton, et
-- "élaguer" les branches de l'arbre des solutions qui dépassent la ressource 
maximale b.

o Q17 ­ Le nom de la fonction KPforceBrute(arbre:dict,obj:[(int)],b:int) est
modifié en KPpse(arbre:dict,obj:[(int)],b:int). Cette fonction prend en argument
l'arbre des solutions arbre, la liste des objets obj et un nombre ressources b. 
Elle affecte
aux variables globales Pmin et Sol respectivement la valeur du profit maximal 
et le vecteur
solution correspondant, conformément à l'algorithme PSE. Réécrire le code 
Python à partir
de la ligne 9 (autant de lignes supplémentaires que nécessaire). Ne pas 
réécrire les autres
lignes.

7 Résolution approchée par colonie de fourmis (ACO)
Principe de la méthode

L'optimisation par colonies de fourmis (ACO : ants colony optimization) est une 
méthode
inspirée du comportement de fourmis lorsque celles-ci sont à la recherche de 
nourriture.
Le choix pour une fourmi artificielle k 2 J0, nb Ant s ° 1K de sélectionner un 
objet plutôt
qu'un autre afin d'élaborer une solution S k , se fait avec une loi de 
probabilité qui évolue au
cours des itérations.
Les fourmis artificielles déposent des traces de phéromone sur les objets 
sélectionnés
dans chacune des solutions S k élaborées, en fonction du profit engendré. La 
probabilité de
sélectionner un objet contenu dans une solution de profit important sera 
augmentée.
Elles élaborent alors de nouvelles solutions relativement aux traces de 
phéromone précédemment déposées.
De plus, ces traces subissent une loi d'évaporation au cours des itérations.
Intuitivement, cette communication indirecte fournit une information sur la 
qualité des
solutions envisagées, afin d'attirer les fourmis vers les zones potentiellement 
intéressantes de
l'espace des solutions.
On adopte alors la stratégie générique suivante :
1) Initialisation
a) Initialiser les traces de phéromone ø(o i )  ømax pour chaque objet o i (i 2 
J0, n °1K)
b) Initialiser la meilleure solution S bestO f Al l  ; et le profit P bestO f 
Al l  0
9

2) Processus itératif de nb i t itérations (nb i t : valeur entière définie 
afin d'obtenir une
solution approchée de qualité en un temps d'exécution raisonnable).
Tant que le nombre d'itérations nb i t n'est pas atteint, faire :
a) Initialiser les solutions S = {S 0 , S 1 , ..., S nb Ant s °1 }/S k  ;, k 2 
J0, nb Ant s ° 1K.
b) Pour chaque fourmi k 2 J0, nb Ant s ° 1K, construire une solution S k comme 
suit :

i. Choisir aléatoirement un premier objet o 0 2 J0, n ° 1K avec une loi 
uniforme.
ii. S k  {o 0 } et la quantité de ressources disponibles b est mise à jour.
iii. cand i d at s  {o i 2 J0, n ° 1K/o i 6= o 0 et respect de la contrainte 
maximale de
ressources}.
iv. Tant que cand i d at s 6= ;, faire :
-- Choisir un objet o i 2 c and i d at s avec la probabilité
pr ob(o i ) = P

(ø(o i ))Æ (¥(o i ))Ø
Æ
Ø
o j 2c and i d at s (ø(o j )) (¥(o j ))

La probabilité de choisir un objet pr ob(o i ) est définie avec un facteur 
phéromonal ø(o i ) et un facteur heuristique ¥(o i ).
Le facteur heuristique ¥(o i ) doit permettre de choisir les objets les plus
«intéressants» de part leurs caractéristiques intrinsèques. Il est défini par un
ratio profit p i /ressource r i tel que :
¥(o i ) = b £

pi
ri

P
avec b = b ° oi 2S k r i , la quantité restante de la ressource lorsque la
fourmi construit la solution S k .

La quantité de ressources disponibles b est réactualisée après chaque ajout
d'objet dans la solution S k .
-- Enlever de cand i d at s chaque objet qui viole des contraintes de 
ressources.
c) Mettre à jour les traces de phéromone ø(o i ) en fonction des solutions S k 
et S bestO f Al l
i. Toutes les traces de phéromone sont diminuées afin de simuler l'évaporation.
On multiplie chaque composant phéromonal par un coefficient réel de persistance 
 2 [0, 1].
ii. On détermine la meilleure fourmi k max du cycle courant de la boucle «Tant 
que
le nombre d'itérations nb i t ...». C'est celle qui a trouvé la solution S max 
2 S =
{S 0 , S 1 , ..., S nb Ant s °1 }, c'est-à-dire la solution ayant le profit 
maximal P (S max ) =
P max trouvé durant le cycle courant.
iii. On met à jour la meilleure solution S bestO f Al l ainsi que le meilleur 
profit
P bestO f Al l = P (S bestO f Al l ) trouvé depuis le début de l'exécution du 
processus itératif (y compris le cycle courant).
iv. La meilleure fourmi k max du cycle courant dépose de la phéromone.
La quantité déposée est égale à : 1/(1 + P bestO f Al l ° P max ).

Cette quantité de phéromone est ajoutée sur chacun des composants phéromonaux 
ø(o i ) de S max , c'est-à-dire correspondant aux objets o i sélectionnés dans
S max .
10

v. Si une trace de phéromone est inférieure à ømi n alors la mettre à ømi n .
vi. Si une trace de phéromone est supérieure à ømax alors la mettre à ømax .

Implémentation de l'algorithme

Afin qu'une fourmi artificielle k puisse choisir un objet o i 2 c and i d at s 
au cours de la
construction d'une solution S k , on implémente l'ensemble des c and i d at s 
avec une liste
candidats d'indices i 2 J0, n ° 1K représentant la position dans la liste obj 
des objets oi
compatibles avec la quantité de ressources disponibles b.
De plus, on utilise un dictionnaire prob tel qu'à la clé i (indice de l'objet o 
i ) correspond la
valeur de la probabilité pr ob(o i ) (comprise en 0 et 1).
Les deux paramètres Æ et Ø sont définis dans deux variables globales. Par 
exemple,
alpha=2 et beta=5.
La liste T de taille n contient les facteurs phéromonaux associés aux objets 
ø(o i ) (o i 2
J0, n ° 1K).
La quantité de ressources disponibles est stockée dans la variable b.
Les paramètres , ømax et ømi n sont définis dans des variables globales. À 
titre d'exemple,
rho=0.8, Tmax=6 et Tmin=0.01.
La liste S contient les listes S[k] des solutions S k (k 2 J0, nb Ant s ° 1K) 
construites par
chacune des fourmis artificielles lors d'une itération de l'algorithme.
On rappelle que chaque solution est de la forme S k = [x 0 , x 1 , .., x n°1 ] 
avec x i 2 {0, 1} (i 2
J0, n ° 1K).
La meilleure de toutes les solutions construites depuis le début de l'exécution 
de l'algorithme et le profit associé, sont stockés dans les variables globales 
respectives SbestOfAll et
PbestOfAll.
On donne ci-après le code incomplet de la fonction
mettreAjourTetSolution(obj:[(int)],T:[float],S:[[int]]), qui prend en argument
la liste des objets obj, la liste des facteurs phéromonaux T et la liste des 
solutions S, et qui met
à jour la liste des facteurs phéromonaux T, la meilleure solution SbestOfAll et 
le meilleur profit PbestOfAll. Cette fonction ne retourne rien et correspond à 
l'item 2)c) de la description
de l'algorithme.

def mettreAjourTetSolution(obj,T,S):
global SbestOfAll,PbestOffAll
3
# 2)c)i.
4
# Utiliser le nombre de lignes nécessaires
5
...............................
6
# 2)c)ii.
7
#Utiliser le nombre de lignes nécessaires
8
...............................
9
# 2)c)iii.
10
if Pmax>PbestOfAll:
11
PbestOfAll=Pmax
12
SbestOfAll=S[kmax]
13
# 2)c)iv.v.vi.
14
#Utiliser le nombre de lignes nécessaires
15
...............................
1
2

11

o Q18 ­ Proposer le code Python complet des lignes 4 et plus de la partie 
2)c)i. de la fonction
ci-dessus.

o Q19 ­ Proposer le code Python complet des lignes 7 et plus de la partie 
2)c)ii.
o Q20 ­ Proposer le code Python complet des lignes 14 et plus de la partie 
2)c)iv.v.vi.
La fonction randint(a,b) de la bibliothèque random a été importée. Elle permet 
de
retourner de manière aléatoire un entier x/a  x  b.
La fonction miseAjourCandidats(obj:[(int)],candidats:[int],b:int) a déjà été
implémentée. Elle permet de supprimer de la liste candidats tous les objets de 
la liste obj
ne respectant pas la contrainte de ressource b. (item 2)b)iii.).
La fonction L.remove(x) appliquée à une liste L permet de retirer un élément x 
de la
liste.
On donne ci-après le code incomplet qui permet de trouver une solution au 
problème
posé en appliquant un algorithme par colonie de fourmis.

#1)a)
2 n=len(obj)
3 T=[Tmax for i in range(n)]
4 #1)b)
5 PbestOfAll=0
6 SbestOfAll=n*[0]
7 #2)
8 for it in range(nbit):
9
#2)a)
10
S=[n*[0] for i in range(nbAnts)]
11
#2)b)
12
for k in range(nbAnts):
13
b2=b
14
#2)b)i.
15
................
16
#2)b)ii.
17
................
18
................
19
#2)b)iii.
20
candidats=[i for i in range(n) if i!=o0]
21
miseAjourCandidats(obj,candidats,b2)
22
#2)b)iv.
23
while b2>0 and candidats!=[ ]:
24
#Utiliser le nombre de lignes nécessaires
25
...............................
26
mettreAjourTetSolution(obj,T,S)
1

o Q21 ­ On donne le nom de variable o0 (o zéro) pour l'indice de l'objet 
choisi. Proposer le
code Python complet des lignes 15, 17 et 18, définies ci-dessus.

12

On propose ci-dessous l'ébauche d'une fonction

construitProb(obj:[(int)],candidats:[int],b:int,T:[float])->{int:float},
qui prend en argument la liste des objets obj, la liste des indices candidats, 
l'entier b et
la liste T, et qui retourne le dictionnaire prob des valeurs de probabilité 
associées à chacun
des objets o i 2 cand i d at s. Cette fonction participe à la réalisation des 
tâches décrites à l'item
2)b)iv. de la description de l'algorithme.

def construitProb(obj,candidats,b,T):
m=len(candidats)
3
prob=..........
4
for i in range(m):
5
oi=..........
6
..........
7
s=sum(prob.values())
8
for i in range(m):
9
oi=..........
10
..........
11
return prob
1
2

o Q22 ­ Proposer le code Python complet des lignes 3, 5, 6, 9 et 10.
On dispose d'une fonction

choixCandidat(candidats:[int],prob:{int:float})->int,
qui prend en argument la liste candidats et le dictionnaire prob, et qui 
retourne l'indice
du candidat sélectionné. Cette fonction participe à la réalisation des tâches 
décrites à l'item
2)b)iv. de la description de l'algorithme.

o Q23 ­ Proposer le code Python complet des lignes 24 et plus, définies en page 
précédente.

8 Analyse des résultats
On réalise une simulation avec 20 objets ayant chacun une quantité de 
ressources consommées comprise entre 1 et 100, et un profit respectif compris 
entre 1 et 100.
La quantité de ressources disponibles a été fixée à 200.
Les résultats sont affichés pour chaque méthode avec le format :
-- Nom de la méthode : temps d'exécution en secondes
-- Solution, profit maximum
-- Liste T pour l'algorithme ACO.
1
2

Force brute : 1.275291500001913
[0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] , 567

3
4
5

Glouton : 2.300000051036477e-05
[0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] , 548

6
7
8

PSE : 0.026752800011308864
[0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] , 567

9

13

Programmation dynamique : 0.00085039998521097
11 [0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] , 567

10

12

ACO avec nbAnts=5 et nbit=1 : 0.00029949998133815825
14 [0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] , 548
15 Liste T :
[4.800..., 5.800..., 4.800..., 4.800..., 5.800..., ...]

13

16

ACO avec nbAnts=5 et nbit=5 : 0.0012731999740935862
[0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] , 567
19 Liste T :
[1.966..., 2.967..., 1.966..., 1.966..., 4.767..., ...]

17

18

20

ACO avec nbAnts=5 et nbit=50 : 0.011390200001187623
22 [0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] , 567
23 Liste T :
[0.01, 0.065..., 0.01, 0.01, 3.799..., ...]

21

o Q24 ­ Commenter les résultats quant aux critères de performance (temps 
d'exécution et
qualité de la solution proposée). Commenter les résultats obtenus par 
l'algorithme ACO en
précisant sur quels paramètres de la méthode on peut jouer, et quelles sont les 
conséquences
sur les performances.

Fin du problème

14