Introduction

Dans le monde de l'informatique et des mathématiques, la résolution de problèmes complexes nécessite souvent des approches algorithmique efficaces. Parmi ces approches, les algorithmes gloutons et la méthode de diviser pour régner se distinguent par leur simplicité et leur efficacité. Ce cours vous permettra de comprendre ces deux techniques, leurs applications et comment les utiliser pour résoudre des problèmes concrets.

Algorithmes gloutons

Les algorithmes gloutons, ou "greedy algorithms" en anglais, sont des algorithmes qui prennent des décisions optimales à chaque étape avec l'espoir que ces choix mèneront à une solution globale optimale.

Principe des algorithmes gloutons

Le principe fondamental des algorithmes gloutons repose sur le fait qu'à chaque étape, on choisit la meilleure option disponible sans se soucier des conséquences futures. Cela signifie que l'algorithme fait des choix locaux optimaux dans l'espoir de trouver une solution globale optimale.

#### Exemple concret : Problème du rendu de monnaie
Considérons le problème du rendu de monnaie. Supposons que vous devez rendre 1,30 € avec des pièces de 1 €, 0,50 €, 0,20 €, 0,10 € et 0,05 €. Un algorithme glouton consisterait à rendre d'abord la plus grande pièce possible, puis de continuer avec la plus grande pièce restante jusqu'à ce que le montant soit atteint. Ainsi, vous rendriez 1 € + 0,20 € + 0,10 € + 0,05 € = 1,35 €.

Montant à rendre	Pièces utilisées
------------------	------------------
1,30 €	1 €, 0,20 €, 0,10 €, 0,05 €

Limites des algorithmes gloutons

Bien que les algorithmes gloutons soient souvent efficaces, ils ne garantissent pas toujours une solution optimale. Par exemple, dans le cas de certaines combinaisons de pièces, un algorithme glouton pourrait donner un rendu moins optimal.

Diviser pour régner