Scribd
Importer
117 vues2 pages

Algorithmes Gloutons en Programmation Avancée

Ce document présente trois exercices sur les algorithmes gloutons. Le premier concerne le choix de nombres pour maximiser leur somme tout en respectant une contrainte. Le deuxième porte sur le choix de vidéos à copier sur une clé USB en fonction de leur durée et taille pour maximiser la durée totale sous une contrainte de taille. Le troisième exercice consiste à choisir des spectacles à voir dans un parc en fonction de leurs horaires pour en voir un maximum.

Transféré par

Thiziri Bouakache
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
117 vues2 pages

Algorithmes Gloutons en Programmation Avancée

Ce document présente trois exercices sur les algorithmes gloutons. Le premier concerne le choix de nombres pour maximiser leur somme tout en respectant une contrainte. Le deuxième porte sur le choix de vidéos à copier sur une clé USB en fonction de leur durée et taille pour maximiser la durée totale sous une contrainte de taille. Le troisième exercice consiste à choisir des spectacles à voir dans un parc en fonction de leurs horaires pour en voir un maximum.

Transféré par

Thiziri Bouakache
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université de Bejaia Niveau : Master 1 MI

Faculté des Sciences Exactes Module : Programmation Avancée


Département D’Informatique Année d’étude 2022/2023

Série de TD n°4
Les algorithmes gloutons

Un algorithme glouton permet d'apporter une solution à un problème d'optimisation


(maximiser ou minimiser une grandeur) tout en respectant certaines contraintes.

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 la liste de nombres ci-dessus.
2. Vérifiez que {20,18,17,16,15} est une autre solution possible.
3. Que dire de la solution gloutonne ?
4. Ecrire l'algorithme glouton.

Exercice 2.

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 minutes 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

1. Quelle est la valeur que l'on cherche à maximiser/minimiser ? Quelle est la


contrainte ?
2. Quel problème reconnaissez-vous ici ?

1
Université de Bejaia Niveau : Master 1 MI
Faculté des Sciences Exactes Module : Programmation Avancée
Département D’Informatique Année d’étude 2022/2023

3. Donner l'algorithme glouton

Exercice 3.

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- 10h30- 11h- 11h30- 12h- 13h- 13h30- 14h- 15h- 16h-
11h 11h30 12h30 12h 13h 15h 14h 15h30 16h 17h30

On remarque 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
spectacle 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 ?

Vous aimerez peut-être aussi