Introduction

La machine RAM nous a permis de définir formellement la notion d'algorithme et de complexité, mal­heu­reu­se­ment 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 \(T\) une liste de \(n\) valeurs sur un ensemble to­ta­le­ment ordonné. Pour toutes les valeurs \(i\) allant de \(1\) à \(n-1\), on échange les valeurs \(T[i]\) et \(T[i+1]\) si \(T[i]>T[i+1]\). Le programme correspondant sur la machine RAM est bien plus complexe à rédiger ! Pour des raisons d'efficacité, les algorithmes seront décrits dans un pseudo-langage algorithmique plus proche de la langue naturelle.

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 lan­ga­ge 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 \(x\) à un ensemble \(E\) s'écrira très classiquement \(x\in E\).

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 com­me un manque de rigueur nous permet en fait de nous affranchir à chaque fois que nécessaire, de dif­ficultés qui ne sont pas au centre de l'algorithme étudié. Ainsi, si nous avons ponctuellement besoin d'une liste de \(n\) entiers compris entre \(1\) et \(K\) choisis aléatoirement sans que la génération de cette liste ne soit la question centrale de l'algorithme étudié, nous nous autoriserons à employer ponctuellement un algorithme auxilaire ALEA(1,K) sans même le définir. La liberté ainsi gagnée permet de nous concentrer sur la nature du problème à résoudre plutôt que sur des questions annexes qui peuvent nécessiter à elles seules une étude détaillée, la génération d'une bonne séquence pseu­do-aléatoire en faisant partie.

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.

Description générale d'un 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). Les variables utilisées par un algorithme sont déclinées en plusieurs classes repertoriées dans les trois premiers des quatre blocs décrivant l'algorithme :

1. Les données : également appelées paramètres, il s'agit des quantités que l'algorithme doit traiter. C'est la variable \(x\) de notre fonction vue comme un \(k\)-uplet s'il y a \(k\) paramètres. Chaque élément de la liste est accompagné de son type (entier, réel, liste, etc. autrement dit les ensembles dont le produit cartésien est l'ensemble de départ de la fonction).
2. Les variables globales : on indique les variables que l'algorithme peut manipuler et qui ont été définies au préalable. On indique leurs types et on les distingue des données de l'algorithme.
3. Les variables locales : on indique les variables et leurs types qui vont être utilisées dans l'algorithme et dont la durée de vie n'excède pas l'exécution de l'algorithme par opposition aux variables globales, on les distingue des données de l'algorithme.
4. Le corps de l'algorithme : encadré par les mots réservés DEBUT et FIN, il contient la séquence des instructions à exécuter.

NomAlgorithme(liste_données):type_résultat
Données
   liste_données: types
variables globales
   liste_variables_globales: types
variables
   liste_variables: types
debut
   liste_instructions
fin

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.

Affectation et structures de contrôle

Affectation

L'affectation est vue ici comme une instruction qui a pour but d'attribuer une valeur à une variable (on parle aussi d'instanciation de la variable). Une variable contient toujours une valeur, dite indéfinie avant la première affectation. C'est le rôle de l'initialisation de ne pas laisser de variables indéfinies dans un algorithme. Si \(x\) est une variable et \(y\) une valeur, on écrit cette affectation ainsi: \[x\leftarrow y\] que l'on lit \(x\) reçoit la valeur \(y\). Si \(y\) est une variable, alors on interprète \(x\leftarrow y\) comme l'affectation de la valeur de la variable \(y\) à \(x\). Plus généralement, on peut placer à droite du symbole d'affectation une expression arithmétique ou logique et dans ce cas, c'est le résultat de l'évaluation de cette expression qui est affecté à \(x\). Par exemple, soit \(y\) une variable dont la valeur est 3, l'affectation \(x\leftarrow 2(y + 1)\) donne la valeur 8 à \(x\).

Une structure de contrôle désigne toute commande qui contrôle l'ordre dans lequel les instructions seront executées. Par défaut, les instructions du corps de l'algorithme sont exécutées sé­quen­tiel­lement dans l'ordre de lecture sauf quand il s'agit de l'une des trois instructions de rupture de séquence si/alors, si/sinon et tant que:

Si/Alors

SI condition ALORS
    bloc instructions
FSI

Si/Alors/Sinon

SI condition ALORS
    bloc instructions #1
SINON
    bloc instructions #2
FSI

Tant que
Il s'agit de la rupture de séquence qui permet de réaliser des boucles:

TQ condition faire
    bloc instructions
FTQ

Quelques notations pour les modèles de données

Nous désignerons indifférement par \(u_i\) ou \(u[i]\) le \(i\)ème élément d'une structure \(u\) de type énuméré (modèle liste, suite, mot, ensemble, tableau, etc.). Dans le même esprit si \(u\) est une structure de type énuméré, nous noterons \(u[a\!:\!b]\) la sous-structure de \(u\) dont les termes sont ceux dont les indices appartiennent à l'intervalle entier \([a,b]:=\{i\in{\mathbf N}\ |\ a\leq i\leq b\}\). Selon les situations et pour simplifier les écritures nous commencerons l'indexation de ces structures par 0 ou par 1, en le précisant bien entendu.

Quelques exemples

L'algorithme suivant renvoie la somme des nombres entiers pairs contenus dans la liste d'entrée :

Additionner(L):réel
Entrée
   L: liste de nombres réels
variables
   i: entier
   S: réel
debut
   i ← 1
   S ← 0
   TQ i ≤ #L faire
       SI (2 | L[i]) alors
          S ← S + L[i]
       FSI 
       i ← i + 1
   FTQ
   RENVOYER S
fin

PairOuImpair(n):entier
données
   n: entier
variables
   S: entier
debut
   SI (2 | n) alors
      S ← n / 2
   SINON 
      S ← 3 * n + 1
   FSI
   RENVOYER S
fin

Syracuse(u0):entier
données
   u0: entier
variables
   u: entier
   n: entier
debut
   u ← u0
   n ← 0
   TQ u > 1 faire
      u ← PairOuImpair(u)
      n ← n + 1
   FTQ
   RENVOYER n
fin

Cet algorithme ne respecte peut-être pas la condition d'arrêt imposée par notre définition d'un al­go­ri­thme. En effet, il s'appuie sur une conjecture célèbre en mathématiques appelée conjecture de Sy­ra­cu­se :

Travaux pratiques

Dans les différents sujets, vous aurez parfois à utiliser l'utilitaire 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 \(x\mapsto \sin x\). Pour tracer un nouveau graphe dans la même fenêtre, il suffit d'utiliser replot au lieu de plot. On peut également tracer un graphe à partir d'un fichier texte contenant un couple de valeurs par ligne, avec plot "mongraphe.txt". Comme toujours, pour en savoir plus, rtfm.