Piles et files vs algorithmes gloutons : ne plus confondre en NSI

Tu es en Terminale NSI et tu te mélanges parfois entre les piles, les files et les algorithmes gloutons ? Pas de panique ! Ces notions sont très différentes : les deux premières sont des structures de données, tandis que le troisième est une technique algorithmique. Dans cet article, on va clarifier tout ça avec des exemples concrets et du code Python. Prêt à ne plus jamais les confondre ?

Qu'est-ce qu'une structure de données ?

En informatique, une structure de données est une façon d'organiser et de stocker des données pour pouvoir les manipuler efficacement. Les listes, les dictionnaires, les arbres, les piles et les files en sont des exemples. Chaque structure a ses propres opérations et règles d'accès.

Pour bien comprendre, imagine une boîte où tu ranges des objets. Selon la boîte, tu ne peux pas toujours prendre l'objet que tu veux. Parfois tu ne peux prendre que le dernier posé, parfois le premier. C'est exactement ce que font les piles et les files !

La pile (stack) : dernier arrivé, premier sorti (LIFO)

Une pile fonctionne comme une pile d'assiettes : tu poses une assiette sur le dessus, et tu reprends toujours celle du dessus. C'est le principe LIFO (Last In, First Out). Les opérations principales sont :

• empiler (push) : ajouter un élément au sommet.
• dépiler (pop) : retirer l'élément du sommet.
• sommet (peek) : regarder l'élément du sommet sans le retirer.

En Python, on peut utiliser une liste pour implémenter une pile, avec append() pour empiler et pop() pour dépiler. Mais attention, en NSI, on privilégie souvent une classe pour bien montrer le concept.

class Pile:
    def __init__(self):
        self.elements = []

    def est_vide(self):
        return len(self.elements) == 0

    def empiler(self, x):
        self.elements.append(x)

    def depiler(self):
        if self.est_vide():
            raise IndexError("Pile vide")
        return self.elements.pop()

    def sommet(self):
        if self.est_vide():
            raise IndexError("Pile vide")
        return self.elements[-1]

# Exemple d'utilisation
p = Pile()
p.empiler(1)
p.empiler(2)
p.empiler(3)
print(p.depiler())  # affiche 3
print(p.sommet())   # affiche 2

La file (queue) : premier arrivé, premier sorti (FIFO)

Une file fonctionne comme une file d'attente au cinéma : le premier arrivé est servi en premier. C'est le principe FIFO (First In, First Out). Les opérations sont :

• enfiler (enqueue) : ajouter à la fin.
• défiler (dequeue) : retirer le premier élément.

En Python, on peut utiliser une liste, mais attention, retirer le premier élément avec pop(0) est coûteux. On préfère souvent utiliser la classe deque du module collections pour une efficacité optimale.

from collections import deque

class File:
    def __init__(self):
        self.elements = deque()

    def est_vide(self):
        return len(self.elements) == 0

    def enfiler(self, x):
        self.elements.append(x)

    def defiler(self):
        if self.est_vide():
            raise IndexError("File vide")
        return self.elements.popleft()

# Exemple
f = File()
f.enfiler("a")
f.enfiler("b")
print(f.defiler())  # affiche "a"
print(f.defiler())  # affiche "b"

Les algorithmes gloutons : une stratégie de résolution

Un algorithme glouton (greedy algorithm) est une méthode pour résoudre un problème d'optimisation. À chaque étape, il fait le choix qui semble le meilleur sur le moment, sans se soucier des conséquences futures. Il espère ainsi obtenir une solution globalement optimale, mais ce n'est pas toujours le cas.

On l'appelle "glouton" car il prend tout ce qu'il peut immédiatement, comme un enfant devant un paquet de bonbons !

Exemple classique : le rendu de monnaie

Supposons que tu doives rendre 37 centimes avec des pièces de 20, 10, 5, 2 et 1 centime. Un algorithme glouton choisirait :

1. 20 (reste 17)
2. 10 (reste 7)
3. 5 (reste 2)
4. 2 (reste 0)

Résultat : 4 pièces. C'est optimal ici. Mais ce n'est pas toujours le cas avec d'autres systèmes de pièces. Par exemple, avec des pièces de 1, 3 et 4, pour rendre 6, le glouton ferait 4 + 1 + 1 (3 pièces) alors que la solution optimale est 3 + 3 (2 pièces). C'est un contre-exemple important à connaître.

Pile ou file ? Algorithmes gloutons ? Le tableau pour t'y retrouver

Voici un tableau récapitulatif pour bien différencier :

• Pile : LIFO, on manipule le dernier arrivé. Utilisée pour les parenthèses, la récursivité, le backtracking.
• File : FIFO, on manipule le premier arrivé. Utilisée pour les files d'attente, le parcours en largeur d'un graphe.
• Algorithme glouton : ce n'est pas une structure, c'est une méthode. On choisit localement l'option optimale à chaque étape.

Pour ne pas les confondre, pose-toi la question : "Est-ce que je décris une façon de ranger des données ou une façon de prendre des décisions ?" Si c'est une façon de ranger, c'est une structure (pile ou file). Si c'est une façon de décider, c'est un algorithme.

Exemples concrets pour ancrer les notions

Pile : vérifier des parenthèses

Un grand classique : vérifier si une expression mathématique a des parenthèses bien équilibrées. On parcourt la chaîne, on empile chaque parenthèse ouvrante, et dès qu'on voit une fermante, on dépile. Si à la fin la pile est vide, c'est bon.

def parentheses_equilibrees(expression):
    p = Pile()  # notre classe définie plus haut
    for caractere in expression:
        if caractere == '(':
            p.empiler(caractere)
        elif caractere == ')':
            if p.est_vide():
                return False
            p.depiler()
    return p.est_vide()

print(parentheses_equilibrees("((1+2)*3)"))  # True
print(parentheses_equilibrees("((1+2)"))    # False

File : gestion d'une imprimante

Imagine une imprimante qui reçoit des travaux d'impression. Les travaux sont traités dans l'ordre d'arrivée : c'est une file. On enfiler un nouveau travail, et l'imprimante défile le premier travail.

travaux = File()
travaux.enfiler("document1.pdf")
travaux.enfiler("photo.jpg")
travaux.enfiler("rapport.docx")

while not travaux.est_vide():
    print("Impression de", travaux.defiler())

Algorithme glouton : le problème du sac à dos fractionnaire

On a un sac qui peut contenir 15 kg, et des objets avec leur poids et leur valeur. Si on peut prendre des fractions d'objets, l'algorithme glouton consiste à trier par rapport valeur/poids décroissant et à prendre le maximum possible de chaque objet. C'est optimal dans ce cas.

objets = [
    {"poids": 5, "valeur": 50},
    {"poids": 10, "valeur": 60},
    {"poids": 3, "valeur": 30}
]
capacite = 15

# Trier par valeur/poids décroissant
objets.sort(key=lambda x: x["valeur"]/x["poids"], reverse=True)

valeur_totale = 0
poids_utilise = 0
for objet in objets:
    if poids_utilise + objet["poids"] <= capacite:
        poids_utilise += objet["poids"]
        valeur_totale += objet["valeur"]
    else:
        reste = capacite - poids_utilise
        valeur_totale += objet["valeur"] * reste / objet["poids"]
        break

print("Valeur totale :", valeur_totale)

Cas d'usage et pièges à éviter

En NSI, on te demandera souvent de choisir la structure adaptée à un problème. Voici quelques pièges classiques :

• Confondre pile et file : vérifie l'ordre de sortie. Pile = LIFO, file = FIFO.
• Penser qu'un algorithme glouton donne toujours la solution optimale : c'est faux ! Il faut le prouver ou connaître un contre-exemple.
• Oublier de gérer les cas vides : toujours vérifier si la pile ou la file est vide avant de dépiler/défiler.

Comment réviser pour le bac ?

Pour le bac NSI, tu dois savoir implémenter une pile et une file en Python, et les utiliser dans des exercices. Tu dois aussi connaître le principe des algorithmes gloutons et savoir les appliquer sur des exemples classiques (rendu de monnaie, sac à dos, etc.).

Entraîne-toi avec des exercices sur la page d'exercices du site et consulte les fiches de révision. N'hésite pas non plus à revoir les cours complets pour approfondir.

Si tu as besoin d'aide supplémentaire, des ressources en ligne comme Allo Lycée peuvent t'accompagner.

Conclusion

Voilà, tu sais maintenant faire la différence entre les structures de données (piles et files) et les algorithmes gloutons. Retiens :

• Pile : LIFO, dernier arrivé premier sorti.
• File : FIFO, premier arrivé premier sorti.
• Glouton : stratégie de choix local optimal.

Continue à t'entraîner, et ces notions deviendront des automatismes. Tu vas y arriver !