La machine RAM nous a permis de définir formellement la notion d'algorithme et de complexité, malheureusement le prix à payer pour cette rigueur est une écriture très fastidieuse des algorithmes. Le troisième exemple d'algorithme du chapitre sur la machine RAM est particulièrement simple à décrire en français : soit
Le langage algorithmique que nous allons employer tout au long du cours est à la fois rudimentaire et très évolué. Deux raisons principales motivent l'utilisation d'un langage algorithmique plutôt qu'un langage de programmation (même si l'on peut trouver des analogies avec le Python par exemple).
La première est qu'il est en quelque sorte un plus grand commun dénominateur des langages de programmation, ce qui le rend à la fois universel et nécessairement simple compte tenu de leur diversité. Son apprentissage est quasi immédiat et sa proximité avec la langue naturelle permet également de décrire facilement les objets que l'on manipule. Par exemple, l'appartenance d'un objet
La seconde est qu'il évite de cumuler deux types de difficultés, celles qui concernent la conception et l'analyse d'un algorithme et celles qui sont spécifiques au langage de programmation utilisé. On peut par exemple avoir besoin de manipuler des listes dans l'écriture d'un algorithme sans que leur gestion soit un sujet d'étude en soit. Le langage Python dispose d'un arsenal à cet effet alors que le langage C demande un travail conséquent et fastidieux pour développer la structure de données ad hoc. C'est justement le rôle des tp de bien faire la part des choses et le travail d'implantation est une tâche à part entière.
Nous ne fournirons pas de grammaire formelle pour ce langage, à dessein. Ce qui pourrait apparaître comme un manque de rigueur nous permet en fait de nous affranchir à chaque fois que nécessaire, de difficultés qui ne sont pas au centre de l'algorithme étudié. Ainsi, si nous avons ponctuellement besoin d'une liste de
Ce pseudo-langage manipule des objets plus proches des modèles abstraits que des structures de données. Nous utiliserons par exemple librement les listes et les opérations usuelles sur les listes, sauf encore une fois, dans le cas où ces opérations sont le sujet d'étude de l'algorithme.
La description littérale d'un algorithme que nous allons faire tente de conserver les éléments clés que nous avons mis en évidence dans le schéma de l'introduction. On y trouve son nom suivi de la liste des données à traiter suivie du type du résultat final (la nature de l'ensemble d'arrivée).
1 ALGORITHME NomAlgorithme(liste_données):type_résultat2 DONNEES3 liste_données: types4 VARIABLES GLOBALES5 liste_variables_globales: types6 VARIABLES7 liste_variables: types8 DEBUT9 liste_instructions10 FIN
Par convention chaque terme des listes de données (sauf dans l'entête) occupe une ligne de l'algorithme (ou sont regroupés par type). Le mot réservé RENVOYER (ou RETOURNER) permet de renvoyer le résultat du calcul effectué par l'algorithme et par convention l'algorithme s'arrête. Comme pour la composition des applications, on peut parfaitement composer des algorithmes en considérant que la valeur renvoyée par un premier algorithme est l'entrée d'un second.
Comme pour les langages de programmation, le passage des variables est un passage par valeur, c'est-à-dire que lors de l'appel d'un algorithme, le contenu des variables d'appel est copié dans leurs paramètres respectifs, les variables d'appels ne sont donc pas modifiées par l'exécution de l'algorithme. On peut aussi faire opérer un algorithme directement sur la donnée qui lui est fournie en entrée, dans ce cas celle-ci est précédée du symbole @. C'est l'équivalent en langage pseudo-algorithmique du passage par adresse.
Si
Par défaut, un algorithme est exécuté séquentiellement, dans l'ordre de lecture des instructions qui le composent.
Si/Alors
1 SI condition ALORS2 bloc instructions3 FSI
Son fonctionnement consiste à exécuter la séquence des instructions du bloc uniquement si la condition est satisfaite. Le bloc d'instructions est indenté et est délimité par les mots réservés SI et FSI.
Si/Alors/Sinon
1 SI condition ALORS2 bloc instructions #13 SINON4 bloc instructions #25 FSI
Son fonctionnement consiste à exécuter exclusivement l'un des deux blocs d'instructions, le premier si la condition est satisfaite le second sinon. Les blocs d'instructions sont indentés et délimités par les mots réservés SI, SINON et FSI.
Tant que
Il s'agit de la rupture de séquence qui permet de réaliser des boucles:
Son fonctionnement consiste à vérifier que la condition est satisfaite avant d'exécuter les instructions du bloc et à recommencer au début du bloc tant qu'elle l'est. Si la condition n'est pas satisfaite, le programme continue après le bloc délimité par les mots réservés TQ et FTQ.1 TQ condition FAIRE2 bloc instructions3 FTQ
Nous désignerons indifférement par
L'algorithme suivant renvoie la somme des nombres entiers pairs contenus dans la liste d'entrée :
L'algorithme suivant prend en entrée un entier naturel1 ALGORITHME2 Additionner(L):réel3 DONNEES4 L: liste de nombres réels5 VARIABLES6 i: entier7 S: réel8 DEBUT9 i ← 110 S ← 011 TQ i ≤ #L FAIRE12 SI (2 | L[i]) ALORS13 S ← S + L[i]14 FSI15 i ← i + 116 FTQ17 RENVOYER S18 FIN
1 ALGORITHME PairOuImpair(n):entier2 DONNEES3 n: entier4 VARIABLES5 S: entier6 DEBUT7 SI (2 | n) ALORS8 S ← n / 29 SINON10 S ← 3 * n + 111 FSI12 RENVOYER S13 FIN
1 ALGORITHME Syracuse(u0):entier2 DONNEES3 u0: entier4 VARIABLES5 u: entier6 n: entier7 DEBUT8 U ← U09 n ← 010 TQ u > 1 FAIRE11 u ← PairOuImpair(u)12 n ← n + 113 FTQ14 RENVOYER n15 FIN
Cet algorithme ne respecte peut-être pas la condition d'arrêt imposée par notre définition d'un algorithme. En effet, il s'appuie sur une conjecture célèbre en mathématiques :
Dans les différents sujets, vous aurez parfois à manipuler le logiciel Gnuplot pour tracer des courbes représentatives de fonctions. Ce logiciel a été développé par gnu et les tracés se font à partir de commandes écrites dans un langage spécifique. À l'instar de Python, on exécute le script monscript.gp en lançant la commande gnuplot monscript.gp et on lance l'interprète de commande simplement grâce à gnuplot.
Par exemple, la commande plot sin(x) va ouvrir une fenêtre et tracer le graphe de la fonction réelle définie par
NB : La phrase devra être récupérée via la ligne de commande. Utilisez les paramètres de la fonction int main(int argc, char *argv[]).
On se propose d'étudier la suite de Syracuse. Les valeurs successives d'une suite de Syracuse
La suite de Syracuse de terme initial
On note