Utilisateur:Regards sur sciences/agreg/leçons/12. Stratégies algorithmiques (dont glouton, diviser pour régner, programmation dynamique, retour sur trace).
programmation glouton[modifier | modifier le wikicode]
Un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l'espoir d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Dans les cas où l'algorithme ne fournit pas systématiquement la solution optimale, il est appelé une heuristique gloutonne. L'illustration ci-contre montre un cas où ce principe est mis en échec.
diviser pour régner[modifier | modifier le wikicode]
En informatique, diviser pour régner (du latin « Divide ut imperes », divide and conquer en anglais) est une technique algorithmique consistant à :
- Diviser : découper un problème initial en sous-problèmes ;
- Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
- Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
Cette technique fournit des algorithmes efficaces pour de nombreux problèmes, comme la recherche d'un élément dans un tableau trié (recherche dichotomique), le tri (tri fusion, tri rapide), la multiplication de grands nombres (algorithme de Karatsuba) ou la transformation de Fourier discrète (transformation de Fourier rapide).
Exemples[modifier | modifier le wikicode]
La table suivante donne des exemples d'algorithmes en donnant les trois étapes (diviser, régner, combiner).
| Diviser | Régner | Combiner | |
|---|---|---|---|
| Recherche dichotomique | Pour chercher x dans le tableau trié T[1, .. n],
|
- | - |
| Tri fusion | on découpe le tableau T[1, .. n] à trier en deux sous-tableaux T[1, .. n/2] et T[n/2 +1,..n] | on trie les deux sous-tableaux T[1, .. n/2] et T[n/2 +1,..n] (récursivement, ou on ne fait rien s'ils sont de taille 1) | on calcule une permutation triée du tableau initial en fusionnant les deux sous-tableaux triés T[1, .. n/2] et T[n/2 +1,..n]. |
| Tri rapide | on choisit un élément du tableau au hasard qui sera 'pivot' et on permute tous les éléments de manière à placer à gauche du pivot les éléments qui lui sont inférieurs, et à droite ceux qui lui sont supérieurs | on trie les deux moitiés de part et d'autre du pivot. | - |
programmation dynamique[modifier | modifier le wikicode]
En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman1. À l'époque, le terme « programmation » signifie planification et ordonnancement1. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type, comme la conduite et l'optimisation de procédés chimiques, ou la gestion de stocks1.
Illustrons la programmation dynamique sur le calcul du nème terme de la suite de Fibonacci, parfois utilisé comme exemple introductif dans un cours sur la programmation dynamique.
La suite de Fibonacci est définie par F0 = 0, F1 = 1 et Fn = Fn-1 + Fn-2. La programmation dynamique s'appuie sur le principe d'optimalité de Bellman : une solution optimale d'un problème s'obtient en combinant des solutions optimales à des sous-problèmes. Sur l'exemple de la suite de Fibonacci, la solution Fn s'obtient en additionnant Fn-1 et Fn-2.
La méthode de programmation dynamique, comme la méthode Diviser pour régner, résout des problèmes en combinant des solutions de sous-problèmes. Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial. La méthode diviser-pour-régner est inefficace si on doit résoudre plusieurs fois le même sous-problème. Par exemple, l'algorithme suivant est inefficace :
fonction fibonacci(n)
si n = 0 ou n = 1
retourner n
sinon
retourner fibonacci(n-1) + fibonacci(n-2)
Le graphe de dépendance montré sur la droite n'est pas un Arbre_(théorie_des_graphes)|arbre : cela illustre que les sous-problèmes se chevauchent. Par exemple, pour calculer F5, nous avons besoin de F3 et F4. Mais pour calculer F4, nous avons besoin de F2 et F3. Ainsi, F3 est utile à la fois pour le calcul de F4 et pour le calcul de F5. La programmation dynamique consiste alors à stocker les valeurs des sous-problèmes pour éviter les recalculs. Il existe alors deux méthodes pour calculer effectivement une solution : la méthode ascendante et la méthode descendante. Dans la méthode ascendante, on commence par calculer des solutions pour les sous-problèmes les plus petits, puis, de proche en proche, on calcule les solutions des problèmes en utilisant le principe d'optimalité et on mémorise les résultats dans un tableau F[.]. Par exemple :
fonction fibonacci(n)
F[0] = 0
F[1] = 1
pour tout i de 2 à n
F[i] := F[i-1] + F[i-2]
retourner F[n]
Dans la méthode descendante, on écrit un algorithme récursif mais on utilise la mémoïsation pour ne pas résoudre plusieurs fois le même problème, c'est-à-dire que l'on stocke dans un tableau F[.] les résultats des appels récursifs :
fonction fibonacci(n)
si F[n] n'est pas défini
si n = 0 ou n = 1
F[n] := n
sinon
F[n] := fibonacci(n-1) + fibonacci(n-2)
retourner F[n]
La programmation dynamique est utilisée pour résoudre des problèmes d'optimisation. La conception d’un algorithme de programmation dynamique est typiquement découpée en quatre étapes
- Caractériser la structure d’une solution optimale.
- Définir (souvent de manière récursive) la valeur d’une solution optimale.
- Calculer la valeur d’une solution optimale.
- Construire une solution optimale à partir des informations calculées.
La dernière étape est utile pour calculer une solution optimale, et pas seulement la valeur optimale. Un problème d'optimisation peut avoir de nombreuses solutions. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale. Une telle solution optimale au problème n'est pas forcément unique, c'est sa valeur qui l'est.
retour sur trace[modifier | modifier le wikicode]
Le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour résoudre des problèmes algorithmiques, notamment de satisfaction de contraintes (optimisation ou décision). Ces algorithmes permettent de tester systématiquement l'ensemble des affectations potentielles du problème. Ils consistent à sélectionner une variable du problème, et pour chaque affectation possible de cette variable, à tester récursivement si une solution valide peut-être construite à partir de cette affectation partielle. Si aucune solution n'est trouvée, la méthode abandonne et revient sur les affectations qui auraient été faites précédemment (d'où le nom de retour sur trace).
En d'autres termes, le retour sur trace est un parcours en profondeur sur l'arbre de décision du problème.