Formation algorithmique, tutoriel & guide de travaux pratiques en pdf.

Nommer un algorithme

Donner un nom à un algorithme est essentiel si on veut pouvoir l’utiliser à l’intérieur d’un autre algorithme. Si par exemple on veut décrire un algorithme qui utilise le tri par bulles, on pourrait réécrire le tri par bulles, ou bien juste utiliser son nom. Tribulle(C) : 1. n←longueur(C) 2. fini←0 3. tant que fini = 0 faire : 4. fini←1 5. pour i←1 à n faire : 6. si C[i] > C[i+1] faire : 7. temp←C[i] 8. C[i]←C[i+1] 9. C[i+1]←temp 10. fini←0 Dans le nom de l’algorithme on indique aussi quelles sont les données d’entrée, ou paramètres, de l’algorithme. Dans ce cas est le tableau à trier. Ici C est le paramètre formel. Pour symboliser l’exécution de l’algorithme, on écrit son nom, et on remplace les paramètres formels avec la donnée sur la quelle on veut exécuter l’algorithme. Si on veut lancer le tri par bulle sur un tableau spécique D on écrit Tribulle(D). Le nombre de pas exécutés pas cet appel correspond au nombre de pas de l’algorithme correspondant. On pourrait aussi être plus exible et spécier quelles parties du tableau on veut trier. On peut vouloir trier le tableau entre la case j et la case k. Tribulle(C,j,k) : 1. fini←0 2. tant que fini = 0 faire : 3. fini←1 4. pour i←j à k faire : 5. si C[i] > C[i+1] faire : 6. temp←C[i] 7. C[i]←C[i+1] 8. C[i+1]←temp 9. fini←0 Attention : cet algorithme est correct sous la condition que k ≤ longueur(C), car sinon C[i] n’a pas de sens pour i > n. Pour trier entièrement le tableau D, il faudrait exécuter Tribulle(D,1,longueur(D)). Parfois un algorithme est censé renvoyer un résultat, sous forme d’un nombre. Dans ce cas on peutaectercenombreàunevariable,oulerenvoyerultérieurement.Considéronsl’algorithme pour trouver la maximum d’un tableau. On ajoute le même niveau de exibilité que pour le tri par bulles, c’est à dire on met les limites parmi les paramètres. c ° Daniele Varacca <varacca@pps.jussieu.fr> 2008

RÉCURSION 

Max(C,j,k) : 1. temp = 0 2. pour i←1 à n faire : 3. si C[i] > temp faire : 4. temp←C[i] 5. renvoie temp Maintenant on peut aecter la valeur renvoyée par cet algorithme : m←Max(D,1,longueur(D)) Onpeututiliserlesnomsmêmepourdesalgorithmestrèssimples,pourfaciliterladescription d’algorithmespluscomplexes.Parexemple,onpeutdécrireunsimplealgorithmepourcalculer le maximum entre deux nombres. Cela nous sera utile par la suite. Max2(n,m) 1. si n > m renvoie n 2. sinon renvoie m On note que ici ce n’est pas question de temps d’exécution : pour tous paramètre le temps d’exécution est le même.
Dans les exemples ci-dessus, donner un nom à un algorithme est quelque chose de pratique, mais pas strictement nécessaire. On pourrait toujours remplacer l’appel à un algorithme par sa description. Pourtant les noms nous permettent aussi de faire appel à un algorithme dans sa propre dénition. Un algorithme qui fait appel à soi même est dit récursif. Voyons un exemple : SansFin(n) 1. m← SansFin(n+1) 2. renvoie m Ici l’algorithme SansFin(0),pour renvoyer son résultat, appelle l’algorithme SansFin(1) qui, pour renvoyer son résultat, appelle l’algorithme SansFin(2) qui, pour renvoyer son résultat, appelle l’algorithme SansFin(3) qui, pour renvoyer son résultat, appelle l’algorithme SansFin(4) qui,… C’est clair que l’algorithme ne se termine pas. Quel est donc l’intérêt d’un algorithme récursif s’il ne termine pas? Le fait que un algorithme peut s’appeler ne veut pas dire qu’il doit s’appeler. La terminaison d’un algorithme récursif dépend des cas de base : les cas où un algorithme ne fait pas appel à soi même mais termine directement. Pour mieux comprendre, on considère un algorithme récursif pour chercher le maximum dans un tableau. Cet algorithme compare le premier élément d’un tableau avec le maximum du reste du tableau, et renvoie le plus grand des deux. c ° Daniele Varacca <varacca@pps.jussieu.fr> 2008
Maxrec(C,i,j) 1. si i≥j 2. renvoie C[j] 3. sinon 4. maxtmp←Maxrec(C,i+1,j) 5. renvoie Max2(C[i],maxtmp) Pour trouver le max du tableau, on doit exécuter Maxrec(C,1,longueur(C)). Quel est le temps d’exécution de cet algorithme? On suppose que le temps soit un fonction T(n), où n est la taille de la partie du tableau dans la quelle on cherche, c’est-à-dire n = longueur(C)−i + 1. Pour exécuter Maxrec, on exécute un nombre xé de pas disons k1, puis on exécute Maxrec sur un partie plus petite du tableau, puis on exécute Max2, qui consiste en un nombre axé de pas, disons k2. Sauf dans le cas où n = 1, en ce cas on exécute un nombre axé de pas, disons h. On a donc : T(n) =½k1 +k2 +T(n−1) si n > 1 h sinon Quelle est la solution de cette équation? On verra plus tard une méthode générale pour résoudre ce genre d’équations. Ici on observe que on pourrait montre par induction queT(n) = h+(n−1)(k1 +k2). Il s’agit donc d’un temps linéaire : T(n)∈Θ(n).