Fiche d'exercices : Algorithmes Gloutons
Introduction 🦊
Comprendre le problème du rendu de monnaie
Le problème du rendu de monnaie consiste à rendre une somme donnée avec le minimum de pièces possible.
Exemple : Pour rendre 67 centimes avec les pièces [50, 20, 10, 5, 2, 1], l'algorithme glouton donne :
- 1 pièce de 50c → reste 17c
- 1 pièce de 10c → reste 7c
- 1 pièce de 5c → reste 2c
- 1 pièce de 2c → reste 0c
Total : 4 pièces
Facile 🌟
Algorithme de rendu de monnaie simple
Écrire une fonction rendu_monnaie(somme, pieces) qui :
- Prend en paramètres la somme à rendre et la liste des pièces disponibles (triée par ordre décroissant)
- Utilise l'algorithme glouton pour rendre la monnaie
- Retourne la liste des pièces utilisées
Exemple :
pieces = [50, 20, 10, 5, 2, 1]
print(rendu_monnaie(67, pieces)) # [50, 10, 5, 2]def rendu_monnaie(somme, pieces):
resultat = []
for piece in pieces:
while somme >= piece:
resultat.append(piece)
somme -= piece
return resultat
# Test
pieces = [50, 20, 10, 5, 2, 1]
print(rendu_monnaie(67, pieces)) # [50, 10, 5, 2]Intermédiaire 🔥
Rendu de monnaie avec comptage
Écrire une fonction rendu_monnaie_detaille(somme, pieces) qui :
- Retourne un dictionnaire avec le nombre de chaque pièce utilisée
- Affiche le détail du rendu de monnaie
Exemple :
pieces = [50, 20, 10, 5, 2, 1]
resultat = rendu_monnaie_detaille(67, pieces)
# Affiche : "1 pièce(s) de 50, 1 pièce(s) de 10, 1 pièce(s) de 5, 1 pièce(s) de 2"
# Retourne : {50: 1, 10: 1, 5: 1, 2: 1}def rendu_monnaie_detaille(somme, pieces):
resultat = {}
details = []
for piece in pieces:
nb_pieces = somme // piece
if nb_pieces > 0:
resultat[piece] = nb_pieces
details.append(f"{nb_pieces} pièce(s) de {piece}")
somme -= nb_pieces * piece
print(", ".join(details))
return resultat
# Test
pieces = [50, 20, 10, 5, 2, 1]
resultat = rendu_monnaie_detaille(67, pieces)
print(resultat) # {50: 1, 10: 1, 5: 1, 2: 1}Difficile 🚀
Vérification de l'optimalité
L'algorithme glouton ne donne pas toujours la solution optimale. Considérons un système de pièces [4, 3, 1].
Question : Pour rendre 6 unités :
- Que donne l'algorithme glouton ?
- Quelle est la solution optimale ?
Écrire une fonction test_optimalite(somme, pieces) qui compare l'algorithme glouton avec une solution par force brute pour vérifier l'optimalité.
def rendu_glouton(somme, pieces):
resultat = []
for piece in pieces:
while somme >= piece:
resultat.append(piece)
somme -= piece
return resultat
def test_optimalite(somme, pieces):
# Solution gloutonne
solution_gloutonne = rendu_glouton(somme, pieces)
nb_pieces_glouton = len(solution_gloutonne)
print(f"Algorithme glouton pour {somme} : {solution_gloutonne}")
print(f"Nombre de pièces : {nb_pieces_glouton}")
# Pour 6 avec [4, 3, 1] :
# Glouton : [4, 1, 1] = 3 pièces
# Optimal : [3, 3] = 2 pièces
if pieces == [4, 3, 1] and somme == 6:
print("Solution optimale : [3, 3] = 2 pièces")
print("L'algorithme glouton n'est pas optimal ici !")
return solution_gloutonne
# Test
pieces = [4, 3, 1]
test_optimalite(6, pieces)Projet 🎯
Simulateur de caisse automatique
Créer un programme complet qui simule une caisse automatique :
- Demander le prix d'un article et l'argent donné
- Calculer la monnaie à rendre
- Afficher le détail des pièces et billets à rendre
- Gérer les cas d'erreur (argent insuffisant)
Système monétaire : [500, 200, 100, 50, 20, 10, 5, 2, 1] (en centimes)
def caisse_automatique():
# Système monétaire français en centimes
pieces_billets = [500, 200, 100, 50, 20, 10, 5, 2, 1]
noms = ["5€", "2€", "1€", "50c", "20c", "10c", "5c", "2c", "1c"]
print("=== CAISSE AUTOMATIQUE ===")
try:
prix = float(input("Prix de l'article (en €) : "))
argent_donne = float(input("Argent donné (en €) : "))
# Conversion en centimes pour éviter les erreurs de virgule flottante
prix_centimes = int(prix * 100)
argent_centimes = int(argent_donne * 100)
if argent_centimes < prix_centimes:
print("Erreur : Argent insuffisant !")
return
monnaie = argent_centimes - prix_centimes
if monnaie == 0:
print("Pas de monnaie à rendre.")
return
print(f"\nMonnaie à rendre : {monnaie/100:.2f}€")
print("Détail :")
for i, valeur in enumerate(pieces_billets):
nb = monnaie // valeur
if nb > 0:
print(f" {nb} x {noms[i]}")
monnaie -= nb * valeur
except ValueError:
print("Erreur : Veuillez entrer des nombres valides.")
# Lancer le simulateur
caisse_automatique()Introduction 🦊
Comprendre le problème du sac à dos
Le problème du sac à dos consiste à sélectionner des objets pour maximiser la valeur totale sans dépasser la capacité du sac.
Exemple : Sac de capacité 15kg avec les objets :
| Objet | Masse | Valeur | Rapport V/M |
|---|---|---|---|
| A | 6kg | 12€ | 2.0 |
| B | 8kg | 20€ | 2.5 |
| C | 4kg | 6€ | 1.5 |
Facile 🌟
Sac à dos par masse (objets les plus légers)
Écrire une fonction sac_a_dos_masse(capacite, objets) qui :
- Prend en paramètres la capacité maximale du sac et une liste de tuples (masse, valeur)
- Utilise la stratégie du choix par masse (objets les plus légers d'abord)
- Retourne un tuple (objets_selectionnes, valeur_totale)
Exemple :
objets = [(2, 3), (3, 4), (4, 5), (5, 6)] # (masse, valeur)
print(sac_a_dos_masse(10, objets))def sac_a_dos_masse(capacite, objets):
# Trier par masse croissante
objets_tries = sorted(objets, key=lambda x: x[0])
objets_selectionnes = []
valeur_totale = 0
capacite_restante = capacite
for masse, valeur in objets_tries:
if masse <= capacite_restante:
objets_selectionnes.append((masse, valeur))
valeur_totale += valeur
capacite_restante -= masse
return (objets_selectionnes, valeur_totale)
# Test
objets = [(2, 3), (3, 4), (4, 5), (5, 6)]
resultat = sac_a_dos_masse(10, objets)
print(f"Objets sélectionnés : {resultat[0]}")
print(f"Valeur totale : {resultat[1]}")Facile 🌟
Sac à dos par valeur (objets les plus précieux)
Écrire une fonction sac_a_dos_valeur(capacite, objets) qui :
- Prend en paramètres la capacité maximale du sac et une liste de tuples (masse, valeur)
- Utilise la stratégie du choix par valeur (objets les plus précieux d'abord)
- Retourne un tuple (objets_selectionnes, valeur_totale)
def sac_a_dos_valeur(capacite, objets):
# Trier par valeur décroissante
objets_tries = sorted(objets, key=lambda x: x[1], reverse=True)
objets_selectionnes = []
valeur_totale = 0
capacite_restante = capacite
for masse, valeur in objets_tries:
if masse <= capacite_restante:
objets_selectionnes.append((masse, valeur))
valeur_totale += valeur
capacite_restante -= masse
return (objets_selectionnes, valeur_totale)
# Test
objets = [(2, 3), (3, 4), (4, 5), (5, 6)]
resultat = sac_a_dos_valeur(10, objets)
print(f"Objets sélectionnés : {resultat[0]}")
print(f"Valeur totale : {resultat[1]}")Intermédiaire 🔥
Sac à dos par rapport valeur/masse
Écrire une fonction sac_a_dos_rapport(capacite, objets) qui :
- Utilise la stratégie du choix par rapport valeur/masse (efficacité)
- Calcule le rapport valeur/masse pour chaque objet
- Sélectionne les objets par ordre décroissant de ce rapport
- Retourne un tuple (objets_selectionnes, valeur_totale)
def sac_a_dos_rapport(capacite, objets):
# Calculer le rapport valeur/masse et trier par ordre décroissant
objets_avec_rapport = [(masse, valeur, valeur/masse) for masse, valeur in objets]
objets_tries = sorted(objets_avec_rapport, key=lambda x: x[2], reverse=True)
objets_selectionnes = []
valeur_totale = 0
capacite_restante = capacite
for masse, valeur, rapport in objets_tries:
if masse <= capacite_restante:
objets_selectionnes.append((masse, valeur))
valeur_totale += valeur
capacite_restante -= masse
return (objets_selectionnes, valeur_totale)
# Test
objets = [(2, 3), (3, 4), (4, 5), (5, 6)]
resultat = sac_a_dos_rapport(10, objets)
print(f"Objets sélectionnés : {resultat[0]}")
print(f"Valeur totale : {resultat[1]}")Intermédiaire 🔥
Analyse comparative des stratégies
Soit un sac à dos de capacité 15 kg et les objets suivants :
| Objet | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Masse | 6 | 8 | 4 | 10 | 7 |
| Valeur | 12 | 20 | 6 | 18 | 15 |
Questions :
- Appliquer l'algorithme glouton en utilisant la stratégie par masse.
- Appliquer l'algorithme glouton en utilisant la stratégie par valeur.
- Appliquer l'algorithme glouton en utilisant la stratégie par rapport valeur/masse.
- Quelle stratégie donne les meilleurs résultats ?
# Données de l'exercice
objets = [(6, 12), (8, 20), (4, 6), (10, 18), (7, 15)] # (masse, valeur)
capacite = 15
print("=== ANALYSE COMPARATIVE DES STRATÉGIES ===")
print(f"Capacité du sac : {capacite} kg")
print(f"Objets disponibles : {objets}")
print()
# 1. Stratégie par masse
print("1. Stratégie par masse (objets les plus légers) :")
resultat_masse = sac_a_dos_masse(capacite, objets)
print(f" Objets sélectionnés : {resultat_masse[0]}")
print(f" Valeur totale : {resultat_masse[1]}")
print()
# 2. Stratégie par valeur
print("2. Stratégie par valeur (objets les plus précieux) :")
resultat_valeur = sac_a_dos_valeur(capacite, objets)
print(f" Objets sélectionnés : {resultat_valeur[0]}")
print(f" Valeur totale : {resultat_valeur[1]}")
print()
# 3. Stratégie par rapport
print("3. Stratégie par rapport valeur/masse :")
resultat_rapport = sac_a_dos_rapport(capacite, objets)
print(f" Objets sélectionnés : {resultat_rapport[0]}")
print(f" Valeur totale : {resultat_rapport[1]}")
print()
# 4. Comparaison
print("4. Comparaison des résultats :")
strategies = [
("Masse", resultat_masse[1]),
("Valeur", resultat_valeur[1]),
("Rapport V/M", resultat_rapport[1])
]
meilleure = max(strategies, key=lambda x: x[1])
print(f" Meilleure stratégie : {meilleure[0]} avec une valeur de {meilleure[1]}")Difficile 🚀
Optimisation et limites de l'algorithme glouton
L'algorithme glouton pour le sac à dos ne garantit pas toujours la solution optimale.
Exemple problématique : Capacité 10kg, objets [(6, 10), (5, 8), (5, 8)]
- Algorithme glouton par valeur : prend (6, 10) puis ne peut plus rien ajouter → valeur = 10
- Solution optimale : prend (5, 8) et (5, 8) → valeur = 16
Créer une fonction qui teste différents cas et identifie quand l'algorithme glouton échoue.
def test_limites_glouton():
print("=== TEST DES LIMITES DE L'ALGORITHME GLOUTON ===")
# Cas problématique 1
print("\nCas 1 : Capacité 10kg, objets [(6, 10), (5, 8), (5, 8)]")
objets1 = [(6, 10), (5, 8), (5, 8)]
capacite1 = 10
# Stratégie par valeur (problématique)
resultat_valeur = sac_a_dos_valeur(capacite1, objets1)
print(f"Glouton par valeur : {resultat_valeur[0]}, valeur = {resultat_valeur[1]}")
# Solution optimale (force brute simple)
print("Solution optimale : [(5, 8), (5, 8)], valeur = 16")
print("→ L'algorithme glouton échoue !")
# Cas problématique 2
print("\nCas 2 : Capacité 15kg, objets [(10, 10), (6, 6), (6, 6)]")
objets2 = [(10, 10), (6, 6), (6, 6)]
capacite2 = 15
resultat_valeur2 = sac_a_dos_valeur(capacite2, objets2)
print(f"Glouton par valeur : {resultat_valeur2[0]}, valeur = {resultat_valeur2[1]}")
print("Solution optimale : [(6, 6), (6, 6)], valeur = 12")
if resultat_valeur2[1] >= 12:
print("→ L'algorithme glouton fonctionne bien ici")
else:
print("→ L'algorithme glouton échoue !")
print("\nConclusion : L'algorithme glouton est rapide mais pas toujours optimal.")
print("Pour une solution optimale, il faut utiliser la programmation dynamique.")
# Lancer le test
test_limites_glouton()Introduction 🦊
Comprendre la planification de tâches
Le problème de la planification de tâches consiste à ordonnancer des tâches pour minimiser le retard total ou maximiser le nombre de tâches terminées à temps.
Exemple : 4 tâches avec leurs durées et échéances :
| Tâche | Durée | Échéance |
|---|---|---|
| A | 3h | 6h |
| B | 2h | 8h |
| C | 1h | 9h |
| D | 4h | 9h |
Stratégie gloutonne : Trier les tâches par échéance croissante (EDD - Earliest Due Date).
Facile 🌟
Planification par échéance (EDD)
Écrire une fonction planification_echeance(taches) qui :
- Prend en paramètre une liste de tuples (nom, duree, echeance)
- Utilise la stratégie EDD (Earliest Due Date)
- Retourne l'ordre d'exécution des tâches
Exemple :
taches = [("A", 3, 6), ("B", 2, 8), ("C", 1, 9), ("D", 4, 9)]
print(planification_echeance(taches))def planification_echeance(taches):
# Trier par échéance croissante (EDD)
taches_triees = sorted(taches, key=lambda x: x[2])
ordre_execution = []
temps_actuel = 0
for nom, duree, echeance in taches_triees:
ordre_execution.append({
'nom': nom,
'debut': temps_actuel,
'fin': temps_actuel + duree,
'echeance': echeance,
'retard': max(0, temps_actuel + duree - echeance)
})
temps_actuel += duree
return ordre_execution
# Test
taches = [("A", 3, 6), ("B", 2, 8), ("C", 1, 9), ("D", 4, 9)]
resultat = planification_echeance(taches)
print("Ordre d'exécution (stratégie EDD) :")
for tache in resultat:
print(f"Tâche {tache['nom']} : {tache['debut']}h → {tache['fin']}h (échéance: {tache['echeance']}h, retard: {tache['retard']}h)")Facile 🌟
Planification par durée (SPT)
Écrire une fonction planification_duree(taches) qui :
- Utilise la stratégie SPT (Shortest Processing Time)
- Trie les tâches par durée croissante
- Calcule le temps de completion moyen
def planification_duree(taches):
# Trier par durée croissante (SPT)
taches_triees = sorted(taches, key=lambda x: x[1])
ordre_execution = []
temps_actuel = 0
temps_completion_total = 0
for nom, duree, echeance in taches_triees:
temps_completion = temps_actuel + duree
temps_completion_total += temps_completion
ordre_execution.append({
'nom': nom,
'debut': temps_actuel,
'fin': temps_completion,
'echeance': echeance,
'retard': max(0, temps_completion - echeance)
})
temps_actuel += duree
temps_completion_moyen = temps_completion_total / len(taches)
return ordre_execution, temps_completion_moyen
# Test
taches = [("A", 3, 6), ("B", 2, 8), ("C", 1, 9), ("D", 4, 9)]
resultat, temps_moyen = planification_duree(taches)
print("Ordre d'exécution (stratégie SPT) :")
for tache in resultat:
print(f"Tâche {tache['nom']} : {tache['debut']}h → {tache['fin']}h (échéance: {tache['echeance']}h, retard: {tache['retard']}h)")
print(f"\nTemps de completion moyen : {temps_moyen:.1f}h")Intermédiaire 🔥
Comparaison des stratégies de planification
Soit les tâches suivantes :
| Tâche | T1 | T2 | T3 | T4 | T5 |
|---|---|---|---|---|---|
| Durée | 4h | 2h | 6h | 3h | 1h |
| Échéance | 8h | 4h | 12h | 6h | 3h |
Questions :
- Appliquer la stratégie EDD (par échéance)
- Appliquer la stratégie SPT (par durée)
- Calculer le retard total pour chaque stratégie
- Quelle stratégie minimise le retard total ?
# Données de l'exercice
taches = [("T1", 4, 8), ("T2", 2, 4), ("T3", 6, 12), ("T4", 3, 6), ("T5", 1, 3)]
print("=== COMPARAISON DES STRATÉGIES DE PLANIFICATION ===")
print(f"Tâches : {taches}")
print()
# 1. Stratégie EDD
print("1. Stratégie EDD (Earliest Due Date) :")
resultat_edd = planification_echeance(taches)
retard_total_edd = sum(tache['retard'] for tache in resultat_edd)
print(" Ordre : ", [tache['nom'] for tache in resultat_edd])
for tache in resultat_edd:
print(f" {tache['nom']} : {tache['debut']}h → {tache['fin']}h (retard: {tache['retard']}h)")
print(f" Retard total : {retard_total_edd}h")
print()
# 2. Stratégie SPT
print("2. Stratégie SPT (Shortest Processing Time) :")
resultat_spt, temps_moyen = planification_duree(taches)
retard_total_spt = sum(tache['retard'] for tache in resultat_spt)
print(" Ordre : ", [tache['nom'] for tache in resultat_spt])
for tache in resultat_spt:
print(f" {tache['nom']} : {tache['debut']}h → {tache['fin']}h (retard: {tache['retard']}h)")
print(f" Retard total : {retard_total_spt}h")
print(f" Temps completion moyen : {temps_moyen:.1f}h")
print()
# 3. Comparaison
print("3. Comparaison des résultats :")
print(f" EDD - Retard total : {retard_total_edd}h")
print(f" SPT - Retard total : {retard_total_spt}h")
if retard_total_edd < retard_total_spt:
print(" → EDD minimise mieux le retard total")
elif retard_total_spt < retard_total_edd:
print(" → SPT minimise mieux le retard total")
else:
print(" → Les deux stratégies donnent le même retard total")Intermédiaire 🔥
Planification avec priorités
Créer une fonction planification_priorite(taches) qui :
- Prend en paramètre une liste de tuples (nom, duree, echeance, priorite)
- Utilise un système de score combinant échéance et priorité
- Score = priorité / échéance (plus le score est élevé, plus urgent)
- Retourne l'ordre d'exécution optimisé
Exemple : Priorité de 1 (faible) à 5 (critique)
def planification_priorite(taches):
# Calculer le score d'urgence : priorité / échéance
taches_avec_score = []
for nom, duree, echeance, priorite in taches:
score = priorite / echeance
taches_avec_score.append((nom, duree, echeance, priorite, score))
# Trier par score décroissant (plus urgent en premier)
taches_triees = sorted(taches_avec_score, key=lambda x: x[4], reverse=True)
ordre_execution = []
temps_actuel = 0
for nom, duree, echeance, priorite, score in taches_triees:
ordre_execution.append({
'nom': nom,
'debut': temps_actuel,
'fin': temps_actuel + duree,
'echeance': echeance,
'priorite': priorite,
'score': score,
'retard': max(0, temps_actuel + duree - echeance)
})
temps_actuel += duree
return ordre_execution
# Test
taches = [
("Rapport", 3, 8, 4), # (nom, durée, échéance, priorité)
("Email", 1, 2, 2),
("Présentation", 4, 10, 5),
("Réunion", 2, 6, 3),
("Documentation", 2, 12, 1)
]
resultat = planification_priorite(taches)
print("Planification avec priorités :")
print("Ordre d'exécution (par score d'urgence) :")
for tache in resultat:
print(f"{tache['nom']} : {tache['debut']}h → {tache['fin']}h")
print(f" Priorité: {tache['priorite']}, Échéance: {tache['echeance']}h, Score: {tache['score']:.2f}")
print(f" Retard: {tache['retard']}h")
print()Difficile 🚀
Optimisation multi-critères
Créer un système de planification avancé qui :
- Combine plusieurs critères : durée, échéance, priorité, coût de retard
- Utilise une fonction de score pondérée
- Permet d'ajuster les poids selon le contexte
- Compare les résultats avec les stratégies simples
Formule : Score = (w1×priorité + w2×(1/durée) + w3×(1/échéance) + w4×coût_retard)
def planification_multi_criteres(taches, poids=(0.3, 0.2, 0.3, 0.2)):
"""
Planification multi-critères avec pondération
poids = (w_priorite, w_duree, w_echeance, w_cout_retard)
"""
w_priorite, w_duree, w_echeance, w_cout_retard = poids
taches_avec_score = []
for nom, duree, echeance, priorite, cout_retard in taches:
# Normalisation des critères (plus c'est élevé, plus c'est urgent)
score_priorite = priorite # 1-5
score_duree = 1 / duree if duree > 0 else 0 # Favorise les tâches courtes
score_echeance = 1 / echeance if echeance > 0 else 0 # Favorise les échéances proches
score_cout = cout_retard # Coût du retard
# Score pondéré
score_total = (w_priorite * score_priorite +
w_duree * score_duree * 10 + # Facteur 10 pour équilibrer
w_echeance * score_echeance * 100 + # Facteur 100 pour équilibrer
w_cout_retard * score_cout)
taches_avec_score.append((nom, duree, echeance, priorite, cout_retard, score_total))
# Trier par score décroissant
taches_triees = sorted(taches_avec_score, key=lambda x: x[5], reverse=True)
ordre_execution = []
temps_actuel = 0
cout_total_retard = 0
for nom, duree, echeance, priorite, cout_retard, score in taches_triees:
fin_tache = temps_actuel + duree
retard = max(0, fin_tache - echeance)
cout_retard_reel = retard * cout_retard if retard > 0 else 0
cout_total_retard += cout_retard_reel
ordre_execution.append({
'nom': nom,
'debut': temps_actuel,
'fin': fin_tache,
'echeance': echeance,
'priorite': priorite,
'retard': retard,
'cout_retard': cout_retard_reel,
'score': score
})
temps_actuel += duree
return ordre_execution, cout_total_retard
# Test avec données complexes
taches_complexes = [
# (nom, durée, échéance, priorité, coût_retard_par_heure)
("Projet_A", 5, 10, 5, 50),
("Maintenance", 2, 6, 2, 10),
("Formation", 3, 15, 3, 5),
("Urgence", 1, 3, 5, 100),
("Routine", 4, 20, 1, 2)
]
print("=== PLANIFICATION MULTI-CRITÈRES ===")
# Test avec différents poids
configs = [
((0.4, 0.2, 0.2, 0.2), "Priorité élevée"),
((0.2, 0.4, 0.2, 0.2), "Durée courte"),
((0.2, 0.2, 0.4, 0.2), "Échéance proche"),
((0.2, 0.2, 0.2, 0.4), "Coût de retard")
]
for poids, description in configs:
print(f"\n--- Configuration : {description} ---")
resultat, cout_total = planification_multi_criteres(taches_complexes, poids)
print("Ordre d'exécution :")
for tache in resultat:
print(f" {tache['nom']} : {tache['debut']}h → {tache['fin']}h")
print(f" Retard: {tache['retard']}h, Coût: {tache['cout_retard']:.0f}€")
print(f"Coût total de retard : {cout_total:.0f}€")Projet 🎯
Simulateur de planification de tâches
Créer un simulateur complet qui :
- Permet de saisir des tâches avec tous leurs attributs
- Propose plusieurs stratégies de planification
- Affiche un planning visuel (diagramme de Gantt textuel)
- Compare les performances de chaque stratégie
- Génère un rapport d'analyse
Fonctionnalités : Interface interactive, visualisation, export des résultats
class SimulateurPlanification:
def __init__(self):
self.taches = []
self.strategies = {
'EDD': self.planification_edd,
'SPT': self.planification_spt,
'Priorité': self.planification_priorite,
'Multi-critères': self.planification_multi
}
def ajouter_tache(self, nom, duree, echeance, priorite=1, cout_retard=0):
self.taches.append({
'nom': nom,
'duree': duree,
'echeance': echeance,
'priorite': priorite,
'cout_retard': cout_retard
})
def planification_edd(self):
return sorted(self.taches, key=lambda x: x['echeance'])
def planification_spt(self):
return sorted(self.taches, key=lambda x: x['duree'])
def planification_priorite(self):
return sorted(self.taches, key=lambda x: x['priorite'], reverse=True)
def planification_multi(self):
taches_scorees = []
for tache in self.taches:
score = (tache['priorite'] * 0.3 +
(1/tache['duree']) * 2 +
(1/tache['echeance']) * 10 +
tache['cout_retard'] * 0.1)
taches_scorees.append((tache, score))
return [t[0] for t in sorted(taches_scorees, key=lambda x: x[1], reverse=True)]
def calculer_metriques(self, ordre):
temps_actuel = 0
retard_total = 0
cout_total = 0
taches_a_temps = 0
for tache in ordre:
fin = temps_actuel + tache['duree']
retard = max(0, fin - tache['echeance'])
if retard == 0:
taches_a_temps += 1
retard_total += retard
cout_total += retard * tache['cout_retard']
temps_actuel = fin
return {
'retard_total': retard_total,
'cout_total': cout_total,
'taches_a_temps': taches_a_temps,
'duree_totale': temps_actuel,
'taux_reussite': taches_a_temps / len(ordre) * 100
}
def afficher_gantt(self, ordre, nom_strategie):
print(f"\n=== DIAGRAMME DE GANTT - {nom_strategie} ===")
temps_actuel = 0
for tache in ordre:
fin = temps_actuel + tache['duree']
retard = max(0, fin - tache['echeance'])
# Barre de progression textuelle
barre = "█" * tache['duree']
statut = "⚠️" if retard > 0 else "✅"
print(f"{tache['nom']:12} |{temps_actuel:2}h {barre:10} {fin:2}h| {statut} (échéance: {tache['echeance']}h)")
temps_actuel = fin
def comparer_strategies(self):
print("\n" + "="*60)
print(" COMPARAISON DES STRATÉGIES")
print("="*60)
resultats = {}
for nom, strategie in self.strategies.items():
ordre = strategie()
metriques = self.calculer_metriques(ordre)
resultats[nom] = metriques
self.afficher_gantt(ordre, nom)
print(f"\nMétriques pour {nom} :")
print(f" Retard total: {metriques['retard_total']}h")
print(f" Coût total: {metriques['cout_total']:.0f}€")
print(f" Tâches à temps: {metriques['taches_a_temps']}/{len(self.taches)}")
print(f" Taux de réussite: {metriques['taux_reussite']:.1f}%")
print(f" Durée totale: {metriques['duree_totale']}h")
# Recommandation
print("\n" + "="*60)
print(" RECOMMANDATION")
print("="*60)
meilleure_retard = min(resultats.items(), key=lambda x: x[1]['retard_total'])
meilleure_cout = min(resultats.items(), key=lambda x: x[1]['cout_total'])
meilleur_taux = max(resultats.items(), key=lambda x: x[1]['taux_reussite'])
print(f"Meilleure pour minimiser le retard: {meilleure_retard[0]}")
print(f"Meilleure pour minimiser les coûts: {meilleure_cout[0]}")
print(f"Meilleure pour le taux de réussite: {meilleur_taux[0]}")
# Exemple d'utilisation
simulateur = SimulateurPlanification()
# Ajouter des tâches
simulateur.ajouter_tache("Développement", 8, 12, 4, 25)
simulateur.ajouter_tache("Tests", 3, 10, 3, 15)
simulateur.ajouter_tache("Documentation", 2, 15, 2, 5)
simulateur.ajouter_tache("Déploiement", 1, 8, 5, 50)
simulateur.ajouter_tache("Formation", 4, 20, 1, 10)
# Lancer la comparaison
simulateur.comparer_strategies()