L'algorithme

Résumé du document

Ce chapitre étudie la démarche algorithmique qui part de l'analyse d'un problème pour déterminer un algorithme qui résoud ce problème de manière effective. La première étape importante est celle d'écrire (ou de décrire) l'algorithme. Celui-ci peut-être vu, dans de nombreux cas, comme une procédure de calcul que doit effectuer un ordinateur abstrait. L'étape suivante consiste à rendre l'algorithme opérationnel en le traduisant dans un langage de programmation approprié et directement exploitable par ordinateur. Des exemples simples illustreront la diversité des problèmes qui relèvent de méthodes algorithmiques.

Un algorithme est un ensemble fini de règles opératoires (procédures de calcul, instructions) bien définies ayant pour but la résolution d'un problème. La solution représentée par l'algorithme doit pouvoir, normalement, être implémentée dans un langage de programmation pour être traitée par ordinateur (machine à calcul).
L'analyse du problème à résoudre, étape préliminaire dans la réalisation de l'algorithme, doit permettre tout d'abord d'identifier les données d'entrée de l'algorithme ainsi que les données de sortie qui fournissent la solution du problème.

Extraits

[...] τm est ´gal ` l'identit´). Montrer que cette d´composition n'est pas e a e e n´cessairement unique mais que pour toute d´composition de σ en produit de transpositions, la parit´ du e e e nombre de ces transpositions est constante (s'il elle est paire, la permutation est dite paire, sinon, elle est dite impaire). Ecrire en d´tail un algorithme qui d´compose une permutation quelconque de En en un produit d'au plus e e n 1 transpositions. Donner un exemple de permutation de En qui s'´crit comme produit de n 1 transpositions et pas moins e (penser ` une permutation “circulaire”). [...]

[...] Les valeurs e e e sont les ´l´ments ` trier. L'introduction de permet d'´viter que la variable j ne prenne ee a e des valeurs inf´rieures ` 1. Dans le pseudo-code de l'algorithme, cette condition est implicite e a puisque n'a pas de sens CTES DEUG MIAS ALGORITHMIQUE (UV 2I5) Chapitre 1. La notion d'algorithme Exercice 1.17 Appliquer le tri par insertion sur la liste L = [ en donnant toutes les configurations successives de L qui apparaissent au cours de l'algorithme TRI INSERTION(L). [...]

[...] ` e * + a b + b x * y c Figure 3 : arbre d'une expression alg´brique. e Une m´thode pour ´valuer l'expression consiste ` passer successivement du plus grand e e a niveau au niveau inf´rieur, ramenant le calcul a un arbre de profondeur moindre. Ce passage e ` s'obtient en effectuant l'op´ration indiqu´e sur le nœud int´rieur qui sont p`res des feuilles ; e e e e elle correspond a un groupement par parenth`ses dans l'expression alg´brique. [...]

[...] e D´monstration. La preuve se fait par induction sur k. Si k = alors b n'est pas nul mais e a mod b l'est puisqu'il n'y a qu'un appel a pgcdR. D'o` a > b 1 = f1 = f ce qui prouve ` u le lemme pour k = 1. Supposons-le d´montr´ pour k 1 1. On a toujours b > 0 et le e e premier appel r´cursif remplace a par b et b par a mod b. [...]

[...] Si n = celle-ci est banale. Si n = c'est tout aussi simple. Pour n = la solution s'obtient assez vite et il n'y a pas beaucoup de choix : on commence par d´placer les deux disques du haut sur le piquet 2 avec e les d´placements de piquet a piquet selon la s´quence 1 2. Le piquet 1 ne e ` e contient plus que le grand disque, d'o` son d´placement 1 puis on d´place la tour du u e e piquet 2 sur le piquet Figure Tour de Hano¨ cas n = 3 : d´placements de ı, e trois disques, du piquet 1 vers le piquet 3. [...]