Algorithme glouton vs Pile et File : ne confonds plus en NSI

Tu as déjà confondu un algorithme glouton avec une pile ou une file ? Pas de panique, c'est super courant en NSI. Pourtant, ces notions sont très différentes : les gloutons sont une stratégie algorithmique, tandis que les piles et files sont des structures de données. Dans cet article, on va démêler tout ça avec des exemples concrets en Python, des astuces pour le bac, et des exercices pour t'entraîner.

1. Qu'est-ce qu'un algorithme glouton ?

Un algorithme glouton (ou greedy) prend la meilleure décision locale à chaque étape, en espérant que cela mène à une solution globale optimale. Il ne revient jamais en arrière : il fait un choix définitif et continue. C'est un peu comme construire une tour en prenant la plus grosse pièce disponible à chaque instant, sans vérifier si une combinaison plus petite serait plus stable.

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. L'algorithme glouton prendra d'abord la plus grande pièce possible : 20, puis 10, puis 5, puis 2 (mais 37-20-10-5 = 2, donc une pièce de 2), total 4 pièces. C'est optimal ici. Mais ce n'est pas toujours le cas (ex: pièces 1, 3, 4 pour rendre 6 : glouton donne 4+1+1=3 pièces, alors que 3+3=2 pièces).

def rendu_glouton(somme, pieces):
    pieces.sort(reverse=True)
    rendu = []
    for p in pieces:
        while somme >= p:
            rendu.append(p)
            somme -= p
    return rendu

print(rendu_glouton(37, [1,2,5,10,20]))  # [20, 10, 5, 2]

2. Piles et files : des structures de données

Une pile (stack) fonctionne en LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré. Une file (queue) fonctionne en FIFO (First In, First Out) : le premier ajouté est le premier retiré. Elles ne sont pas des algorithmes, mais des outils pour organiser des données.

Pile en Python

pile = []
pile.append('a')  # empiler
pile.append('b')
element = pile.pop()  # dépile 'b'
print(pile)  # ['a']

File en Python (avec deque pour efficacité)

from collections import deque
file = deque()
file.append('a')  # enfiler
file.append('b')
element = file.popleft()  # défile 'a'
print(file)  # deque(['b'])

3. Points clés pour ne plus confondre

• Nature : glouton = stratégie (comment on résout un problème) ; pile/file = structure (comment on organise les données).
• Objectif : glouton cherche une solution optimale (parfois) ; pile/file gèrent l'ordre de traitement.
• Combinaison : un algorithme glouton peut utiliser une pile ou une file pour stocker des choix temporaires, mais ce n'est pas obligatoire.

4. Exemple concret : problème du sac à dos fractionnaire

Le problème du sac à dos fractionnaire (où on peut prendre des fractions d'objets) se résout par un algorithme glouton : on prend les objets avec le meilleur rapport valeur/poids. Ici, on n'utilise ni pile ni file, juste un tri et une boucle.

def sac_a_dos_glouton(objets, capacite):
    # objets : liste de tuples (valeur, poids)
    objets_tries = sorted(objets, key=lambda x: x[0]/x[1], reverse=True)
    valeur_totale = 0
    for val, poids in objets_tries:
        if capacite >= poids:
            valeur_totale += val
            capacite -= poids
        else:
            valeur_totale += val * (capacite / poids)
            break
    return valeur_totale

print(sac_a_dos_glouton([(60,10),(100,20),(120,30)], 50))  # 240.0

5. Cas d'usage des piles et files

Pile : vérification de parenthèses

def parentheses_correctes(expression):
    pile = []
    for c in expression:
        if c == '(':
            pile.append(c)
        elif c == ')':
            if not pile:
                return False
            pile.pop()
    return len(pile) == 0

print(parentheses_correctes('(())'))  # True

File : parcours en largeur (BFS) dans un graphe

from collections import deque

def bfs(graphe, depart):
    visites = set()
    file = deque([depart])
    while file:
        sommet = file.popleft()
        if sommet not in visites:
            visites.add(sommet)
            for voisin in graphe[sommet]:
                if voisin not in visites:
                    file.append(voisin)
    return visites

graphe = {0: [1,2], 1: [2], 2: [0,3], 3: [3]}
print(bfs(graphe, 2))  # {0,1,2,3}

6. Conseils pour le bac NSI

Au bac, on te demande souvent de choisir la structure de données adaptée et l'algorithme approprié. Voici comment t'y prendre :

• Si tu dois traiter des éléments dans l'ordre d'arrivée (premier arrivé, premier servi) → file.
• Si tu dois traiter en ordre inverse (dernier arrivé, premier servi) → pile.
• Si tu dois faire un choix local optimal sans revenir en arrière → algorithme glouton.
• Attention : un glouton peut utiliser une pile ou une file, mais ce n'est pas ce qui le définit.

Pour t'entraîner, consulte nos cours NSI et exercices dédiés. Tu y trouveras des sujets type bac et des corrections détaillées. Et si tu veux approfondir avec des fiches de révision, n'hésite pas à visiter nos fiches.

7. Conclusion

Les algorithmes gloutons et les structures de pile/file sont deux concepts fondamentaux mais distincts. Les premiers sont une méthode de résolution, les secondes des outils de stockage. En les pratiquant avec des exemples concrets, tu verras que la confusion disparaît vite. Continue de coder, et n'oublie pas : le bac NSI, c'est avant tout de la logique et de l'entraînement. Tu gères !

Pour aller plus loin, découvre aussi nos partenaires AlloBac et AlloLycée qui proposent des ressources complémentaires.