Devoir 8 Nsi

Devoir 8
Cette évaluation est destinée à vous entrainer et ne doit pas être envoyée à la correction
Veuillez réaliser ce devoir après avoir étudié la séquence 10.
Durée : 2h00
Exercice 1 (10 points)

Voici l’implémentation d’une fonction maximum.
def maximum(liste, iDebut, iFin):
""" Renvoie, s'il existe, le maximum d'une liste liste
en cherchant parmi les éléments d'indice compris
entre iDebut et iFin
"""
if iDebut == iFin:
return liste[iDebut]
iMilieu = (iDebut + iFin ) // 2
x = maximum(liste, iDebut, iMilieu)
y = maximum(liste , iMilieu + 1, iFin)
return x if x > y else y
1. Que se passe-t-il si on appelle cette fonction avec une liste vide comme argument ?
Dans la suite du devoir, on suppose que la fonction maximum n’est jamais appelée sur une liste vide.
2.
a) À quoi voit-on que cette fonction est récursive ? Vous citerez les lignes pertinentes.
b) Quels sont les cas d’arrêt de cette fonction ? Que renvoie-t-elle dans ces cas ? Vous donnerez
un exemple d’appel de cette fonction où l’algorithme rencontre immédiatement un tel cas.
3. On execute
print(maximum([10, 92, 29, 31, 4, 9, 75, 22, 13],0, 8)).
c) Reproduire et compléter l’arbre des appels récursifs de la fonction maximum en faisant

apparaître les valeurs des paramètres iDebut et iFin à chaque appel.
d) On insère juste avant la ligne if iDebut == iFin: une ligne avec l’instruction suivante :
print(iDebut, iFin)
Quels sont les six premiers affichages obtenus lorsqu’on exécute

print(maximum([10, 92, 29, 31, 4, 9, 75, 22, 13],0, 8)) ?
4. En vous inspirant de la fonction maximum(liste, iDebut, iFin), implémentez une fonction minimum(liste,
iDebut, iFin) qui renvoie, s’il existe, le minimum de la liste fournie en examinant les éléments dont les
indices vont de iDebut à iFin.
Exercice 2 (10 points)

Cet exercice a pour but d’étudier la résolution du problème du sac à dos. En Première, vous avez vu
une résolution approchée de ce problème. Le but de ce devoir est d’aborder un nouvel algorithme qui
donne une solution optimale.
On suppose avoir n objets objet 1, … , objet n . Chaque objet i a un poids pi qui est un nombre entier
positif de kg et une utilité ui qui est mesurée elle aussi par un nombre entier positif.
Il n’y a pas de possibilité de prendre plusieurs fois le même objet.
On dispose d’autre part d’un sac à dos ayant une certaine capacité en poids.
Le problème du sac à dos est de chosir quels objets mettre dans le sac de manière à ce que la somme
des utilités des objets soit maximale, tout ayant un poids total au plus égal à la capacité supportée par
le sac à dos.
Pour tout le devoir, on suppose avoir une liste de quatre objets

mesObjets = [objet1, objet2, objet3, objet4]
chaque objet étant donné par un couple (poids, utilité)

objet1 = (1, 12) # l'objet 1 pèse 1 kg et a une utilité de 12. Etc.
objet2 = (3, 75)
objet3 = (3, 72)
objet4 = (5, 130)
Enfin, on dispose d’un sac à dos de capacité capaSac = 6 (kg).
Partie A - Algorithme glouton

Dans cette partie, aucune programmation n’est nécessaire.
1. On applique strictement l’algorithme glouton suivant :
• Calculer le rapport utilité/poids de chaque objet.

• Tant qu’on ne dépasse pas la capacité du sac :
− Mettre dans le sac les objets dans l’ordre du meilleur rapport utilité/poids
a) Détailler l’exécution de cet algorithme sur nos 4 objets.

b) Quel est alors le poids atteint par le sac ?
c) Quelle est l’utilité totale atteinte ?
2. En faisant un autre choix d’objets, montrez que l’agorithme glouton n’est pas optimal.
Partie B - Algorithme menant à une solution optimale
Dans cette partie on étudie l’implémentation d’un algortihme donnant dans tous les cas une solution
optimale au problème du sac à dos.
On définit la fonction sacados ci-dessous.

def sacados(listeobjets, poidsmaxi):
"""
listeobjets : liste de couples (poids, utilité)
poidsmaxi : capacité en poids du sac à dos
"""
print(listeobjets, poidsmaxi)
if not listeobjets or poidsmaxi <= 0:
# not listeobjets signifie : listeobjets est vide
return 0
if listeobjets[-1][0] <= poidsmaxi :

v1 = sacados(listeobjets[:-1], poidsmaxi)
v2 = sacados(listeobjets[:-1] \
, poidsmaxi - listeobjets[-1][0]) \
+ listeobjets[-1][1]
return max(v1, v2)
else:
return sacados(listeobjets[:-1], poidsmaxi)
L’exécution de print(sacados(mesObjets, capaSac)) donne l’affichage suivant :
[[1, 12], [3, 75], [3, 72], [5, 130]] 6
[[1, 12], [3, 75], [3, 72]] 6
[[1, 12], [3, 75]] 6
[[1, 12]] 6
[] 6
[] 5
[[1, 12]] 3
[] 3
[] 2
[[1, 12], [3, 75]] 3
[[1, 12]] 3
[] 3
[] 2
[[1, 12]] 0
[[1, 12], [3, 75], [3, 72]] 1
[[1, 12], [3, 75]] 1
[[1, 12]] 1
[] 1
[] 0
147
1. On compte 19 lignes affichées avant le résultat 147 Que déduire de ce nombre 19 ?
2. Comment interpréter le nombre 147 qui termine l’affichage pour notre problème ?
Partie C - Programmation dynamique

L’algorithme de la partie B ne dit pas quels choix faire pour parvenir au choix optimal. On va utiliser la
technique de la mémoïsation pour
• obtenir la répartition optimale

• améliorer les performances de l’algorithme
Dans cette partie, on utilise un dictionnaire V et la fonction suivante.

# amélioration avec mémoïsation
#
V = dict() # V est un dictionnaire vide
#
# V sera formé d'entrées dont
# - la clé est le couple (i,j)
# où i est un nombre maximum d'objets, à prendre depuis le premier
# où j est une capacité en kg
# - la valeur est l'utilité atteinte
# Ainsi V[i,j] représente l'utilité optimale
# obtenue avec seulement les i premiers objets et une capacité de j kg.
def memoSacados(listeobjets, poidsmaxi):
k = (len(listeobjets), poidsmaxi) # k est une clé pour le dictionnaire V
if not k in V: # si la clé est absente
if not listeobjets or poidsmaxi <= 0 :
V[k] = 0
elif listeobjets[-1][0] <= poidsmaxi:
v1 = memoSacados(listeobjets[:-1], poidsmaxi)
v2 = memoSacados(listeobjets[:-1] \
, poidsmaxi - listeobjets[-1][0])\
+ listeobjets[-1][1]
V[k] = max(v1, v2)
else:
V[k] = memoSacados(listeobjets[:-1], poidsmaxi)
return V[k] # dans tous les cas, y compris clé déjà présente
1. L’exécution de
utiliteOptimale = memoSacados(mesObjets, capaSac)

print(utiliteOptimale)
print(V)
donne
147
{(0, 6): 0,
(0, 5): 0,
(1, 6): 12,
(0, 3): 0,
(0, 2): 0,
(1, 3): 12,
(2, 6): 87,
(1, 0): 0,
(2, 3): 75,
(3, 6): 147,
(0, 1): 0,
(0, 0): 0,
(1, 1): 12,
(2, 1): 12,
(3, 1): 12,
(4, 6): 147}
Comment interpréter par exemple (2,6): 87 pour notre problème de sac à dos ?
2. On trouve le nombre 147 à deux endroits de cet affichage. Qu’en déduire sur le choix final de l’objet 4 ?
3. Pour obtenir la liste des objets à prendre, on produit le code ci-dessous.
# Qu'a-t-on pris ?
#
i = len(mesObjets)
j = capaSac
while i > 0:
if V[i, j] > V[i - 1, j]: # Si on a pris l'objet_i
# /!\ objets numérotés à partir de zéro
# dans mesObjets
print(f"On a pris l'objet n°{i}"
+ f" qui pèse {mesObjets[i-1][0]} kg"
+ f" et qui vaut {mesObjets[i-1][1]}.")
j = j - mesObjets[i-1][0]
i = i - 1
Quel est l’affichage obtenu par l’exécution de celui-ci ? Quel est donc finalement le choix optimal pour
notre problème ?
Vous pouvez répondre à cette question en exécutant ce code, ou « à la main » à partir des valeurs de V.

Devoir 8 Nsi

Transféré par

Droits d'auteur :

Formats disponibles

Devoir 8 Nsi

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Devoir 8 Nsi

Transféré par

Droits d'auteur :

Formats disponibles

Devoir 8

Veuillez réaliser ce devoir après avoir étudié la séquence 10.

Exercice 1 (10 points)

print(maximum([10, 92, 29, 31, 4, 9, 75, 22, 13],0, 8)).

c) Reproduire et compléter l’arbre des appels récursifs de la fonction maximum en faisant

Quels sont les six premiers affichages obtenus lorsqu’on exécute

Exercice 2 (10 points)

Il n’y a pas de possibilité de prendre plusieurs fois le même objet.

Pour tout le devoir, on suppose avoir une liste de quatre objets

chaque objet étant donné par un couple (poids, utilité)

Enfin, on dispose d’un sac à dos de capacité capaSac = 6 (kg).

Partie A - Algorithme glouton

1. On applique strictement l’algorithme glouton suivant :

• Calculer le rapport utilité/poids de chaque objet.

a) Détailler l’exécution de cet algorithme sur nos 4 objets.

Partie B - Algorithme menant à une solution optimale

On définit la fonction sacados ci-dessous.

if listeobjets[-1][0] <= poidsmaxi :

1. On compte 19 lignes affichées avant le résultat 147 Que déduire de ce nombre 19 ?

Partie C - Programmation dynamique

• obtenir la répartition optimale

Dans cette partie, on utilise un dictionnaire V et la fonction suivante.

utiliteOptimale = memoSacados(mesObjets, capaSac)

Vous aimerez peut-être aussi