Cours | Exercices

Exercice 1

On cherche à sélectionner cinq nombres de la liste suivante en cherchant à avoir leur somme la plus grande possible (maximiser une grandeur) et en s'interdisant de choisir deux nombres voisins (contrainte).

15 - 4 - 20 - 17 - 11 - 8 - 11 - 16 - 7 - 14 - 2 - 7 - 5 - 17 - 19 - 18 - 4 - 5 - 13 - 8

Comme on souhaite avoir le plus grand résultat final, la stratégie gloutonne consiste à choisir à chaque étape le plus grand nombre possible dans les choix restants.

1. Appliquez cet algorithme glouton sur le tableau.
2. Vérifiez que $\{20, 18, 17, 16, 15\}$ est une autre solution possible.
3. Que dire de la solution gloutonne ?

Exercice 2 : le problème du voyageur

Un voyageur a ciblé plusieurs villes qu'il souhaite visiter. Il cherche un itinéraire passant par toutes ces villes et qui minimise la distance totale parcourue. Les villes peuvent être visitées dans n'importe quel ordre mais aucune ne doit être négligée, et le visiteur doit revenir à la fin à sa ville de départ.

Le voyageur part de Nancy et souhaite visiter Metz, Paris, Reims et Troyes, avant de retourner à Nancy.

Voici un tableau donnant les distances kilométriques entre chacune des ces villes.

1. Quelle est la stratégie gloutonne à mettre en oeuvre ?
2. Mettez en oeuvre cette stratégie et donnez la solution.
3. Calculez la distance totale pour le parcours Metz - Reims - Paris - Troyes (départ et arrivée à Nancy sous-entendus)
4. Que dire de la solution gloutonne ?

Exercice 3 : le problème du sac à dos

On rappelle qu'il y a plusieurs stratégies gloutonnes pour donner une solution à ce problème

• Stratégie 1 : prendre toujours l'objet de plus grande valeur n'excédant pas la capacité restante (il faut trier préalablement par valeur décroissante)
• Stratégie 2 : prendre toujours l'objet de plus faible masse (il faut trier préalablement par masse croissante)
• Stratégie 3 : prendre toujours l'objet de plus grand rapport $\frac{\text{valeur}}{\text{masse}}$ n'excédant pas la capacité restante (il faut trier préalablement par rapport $\frac{\text{valeur}}{\text{masse}}$ décroissant)

Exemple 1

Considérons les objets suivants et un sac de capacité maximale 2 kg.

objet	A	B	C
masse (kg)	1,5	2	0,3
valeur (€)	200	500	400
$\frac{\text{valeur}}{\text{masse}}$	133,33...	250	1333,33...

1. Appliquez chacune des stratégies à ce problème.
2. Quelle est la meilleure stratégie dans ce cas ?
3. Listez toutes les combinaisons possibles, puis celles respectant la contrainte et déduisez-en la solution optimale au problème. Comparez-la aux stratégies gloutonnes.

Exemple 2

Même questions mais avec un sac de capacité maximale 3,5 kg.

Exemple 3

On considère désormais les objets suivants et un sac de capacité maximale 5 kg.

Objet	Valeur (en milliers d'€)	Masse (en kg)
A	114	4.57
B	32	0.63
C	20	1.65
D	4	0.085
E	18	2.15
F	80	2.71
G	5	0.32

1. Appliquez chacune des stratégies à ce problème.
2. Quelle est la meilleure stratégie dans ce cas ?
3. Le sac $\{B, C, F\}$ est-il une solution au problème ? Quelle est sa valeur ? Que dire des solutions gloutonnes ?

Exercice 4

Vous visitez un parc d'attractions proposant des spectacles à différents horaires. Voici les horaires des différents spectacles :

spectacle	A	B	C	D	E	F	G	H	I	J
horaire	10h-11h	10h30-11h30	11h-12h30	11h30-12h	12h-13h	13h-15h	13h30-14h	14h-15h30	15h-16h	16h-17h30

Vous avez remarqué qu'il n'est pas possible d'assister à tous les spectacles puisque certains ont lieu à des moments communs. Vous souhaitez assister à un maximum de spectacles sur la journée. Quels spectacles devez-vous choisir ?

Voici deux stratégies gloutonnes possibles :

• Stratégie n°1 : choisir le spectacle dont l'heure de début arrive le plus tôt (parmi les spectacles dont l'heure de début est postérieure aux créneaux des spectacles déjà choisis). Cette stratégie est basée sur l'idée que moins on attend entre deux spectacles, plus on en verra.
• Stratégie n°2 : choisir le spectacle dont l'heure de fin arrive le plus tôt (parmi les spectacles dont l'heure de début est postérieure aux créneaux des spectacles déjà choisis). Cette stratégie est basée sur l'idée que plus un spectable finit tôt, plus il reste de temps pour en voir d'autres.

1. Appliquez ces deux stratégies au problème.
2. Laquelle donne la meilleure solution ?

Remarque : la deuxième stratégie gloutonne donne toujours la solution optimale à ce type de problème.

Exercice 5 : Plus beaucoup de place sur ta clé USB ?

Objectifs :

• implémenter un algorithme glouton pour trouver une solution à un problème
• implémenter l'algorithme de force brute pour déterminer la solution optimale et la comparer à la solution gloutonne

Introduction

Nous disposons d’une clé USB qui est déjà bien remplie et sur laquelle il ne reste que 5 Go de libre. Nous souhaitons copier sur cette clé des fichiers vidéos pour l’emporter en voyage. Chaque fichier a un poids et chaque vidéo a une durée. La durée n’est pas proportionnelle à la taille car les fichiers sont de format différents, certaines vidéos sont de grande qualité, d’autres sont très compressées. Le tableau qui suit présente les 7 fichiers disponibles avec les durées données en minutes.

Nom	Durée en min (valeur)	Poids
Vidéo A	114	4.57 Go
Vidéo B	32	630 Mo
Vidéo C	20	1.65 Go
Vidéo D	4	85 Mo
Vidéo E	18	2,15 Go
Vidéo F	80	2,71 Go
Vidéo G	5	320 Mo

Problème : Quelles vidéos copier sur la clé USB pour que la durée des vidéos soient la plus grande possible tout en ne dépassant pas 5 Go ?

Pour traiter cet exercice, cliquez ici pour accéder au notebook en ligne.

---

Références :

• Documents ressources du DIU EIL, Université de Nantes, C. JERMANN.
• Cours/exercices de J. DE VILLELE sur les algorithmes gloutons : lien vers son archive pour l'exercice 1
• Ressources Eduscol : Le problème du sac à dos pour l'exercice 5
• Numérique et Sciences Informatiques, 1re, T. BALABONSKI, S. CONCHON, J.-C. FILLIATRE, K. NGUYEN, éditions ELLIPSES : Site du livre pour l'idée de l'exercice 4

---

Germain BECKER, Lycée Mounier, ANGERS