Exercice ALGORITHME GLOUTON : Planification avec un algorithme glouton
Un système à serveur unique (par exemple, une pompe à essence, un caissier dans une banque ou un processeur informatique) doit servir \( n \) clients. Chaque client \( i \) a un temps de service \( t_i \), connu à l'avance. Votre objectif est de minimiser le temps total passé par tous les clients dans le système, soit :
\[ T = \sum_{i=1}^{n} (\text{temps total passé dans le système par le client } i). \]
Minimiser \( T \) revient également à minimiser le temps d'attente moyen des clients.
Expliquez pourquoi l'ordre dans lequel les clients sont servis affecte le temps total \( T \).
Supposons que \( n = 3 \) avec \( t_1 = 5 \), \( t_2 = 10 \), \( t_3 = 3 \). Calculez \( T \) pour les six ordres possibles de service. Identifiez l'ordre optimal.
Un algorithme glouton est proposé :
À chaque étape, ajouter à la fin de l'ordre de service le client dont le temps de service est le plus court parmi ceux qui restent.
Expliquez pourquoi cet algorithme est logique pour minimiser \( T \).
Utilisez cet algorithme pour trouver l'ordre optimal pour les temps de service \( t_1 = 7 \), \( t_2 = 2 \), \( t_3 = 4 \), \( t_4 = 8 \). Calculez \( T \) pour cet ordre.
On démontre que cet algorithme est toujours optimal. En particulier :
Le temps total \( T \) peut être exprimé comme :
\[ T = \sum_{i=1}^{n} (n - i + 1) \cdot t_{k_i}, \]
où \( t_{k_i} \) est le temps de service du \( i^\text{ème} \) client servi.
Déduisez à partir de cette formule pourquoi il est préférable de servir les clients avec des temps de service plus courts en premier.
Montrez, à l'aide d'un contre-exemple, qu'un ordre non glouton peut être sous-optimal.
Écrivez un programme dans le langage de votre choix (Python, Java, ou autre) pour implémenter l'algorithme glouton. Votre programme doit :
Lire un tableau de \( n \) temps de service.
Afficher l'ordre optimal de service et le temps total \( T \).
Imaginez un système où certains clients ont des priorités (par exemple, un poids \( p_i \) pour chaque client). Proposez une extension de l'algorithme pour gérer ce cas et justifiez votre approche.
Si vous avez trouvé les exercices corriges sur la Complexité des Algorithmes & Structure de donnée de Mr JoëlYk intéressants et utiles, pourquoi ne pas les partager avec d'autres personnes qui pourraient également en bénéficier ? Partagez ce lien sur les réseaux sociaux ou envoyez-le à vos amis et collègues. Vous pourriez aider quelqu'un à améliorer ses compétences en programmation ou à trouver des solutions à des problèmes complexes. N'oubliez pas que la connaissance doit être partagée pour grandir. Merci pour votre soutien et votre partage !
Contact WhatsApp : +237 652027193| Réaliser Par Joël_Yk
