Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Devoir 8 Cette évaluation est destinée à vous entrainer et ne doit pas être env

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 i p qui est un nombre entier positif de kg et une utilité i u 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. uploads/Geographie/ devoir-8-nsi.pdf