Pseudo langage algorithmique

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éralsation 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 qui le décrivent :
  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. 
ALGORITHME NomAlgorithme(liste_données):type_résultat
DONNEES
   liste_données: types
VARIABLES GLOBALES
   liste_variables_globales: types
VARIABLES
   liste_variables: types
DEBUT
   liste_instructions
FIN
Format général d'un pseudo-algorithme.

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.

Affectation et structures de contrôle

Affectation

L'affectation est une instruction qui attribue une valeur à une variable. Quand on réalise une affectation, on dit que l'on instancie la variable. Une variable est toujours indéfinie avant sa première affectation appelée initialisation. Si \(x\) est une variable et \(y\) une valeur, on écrit cette instruction : \[ 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\).

Par défaut, un algorithme est exécuté séquentiellement, dans l'ordre de lecture des instructions qui le composent.

Une structure de contrôle désigne toute commande qui contrôle l'ordre dans lequel les instructions seront exécutées. Toute instruction qui modifie l'ordre d'exécution d'un algorithme s'appelle une rupture de séquence.

Ruptures de séquence

Si/Alors

SI condition ALORS
   bloc instructions
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

SI condition ALORS
    bloc instructions #1
SINON
    bloc instructions #2
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: 
TQ condition FAIRE
    bloc instructions
FTQ
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.

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 \(\ab{a}{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 : 

ALGORITHME 
Additionner(L):réel
donnees
   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
L'algorithme suivant prend en entrée un entier naturel \(n\) et renvoie l'entier \(n/2\) si \(n\) est pair et \(3n+1\) s'il est impair: 
ALGORITHME PairOuImpair(n):entier
donnees
   n: entier
variables
   S: entier
debut
   SI (2 | n) alors
      S ← n / 2
   SINON 
      S ← 3 * n + 1
   FSI
   RENVOYER S
fin
La suite de Syracuse est une suite récurrente d'entiers de premier terme \(u_0\) arbitraire et définie par : \begin{equation}\label{def:syracuse} u_{n+1}:=\begin{cases} u_n/2,&\quad\text{si}\ u_n\ \text{est pair.}\\ 3u_n+1,&\quad\text{si}\ u_n\ \text{est impair.}\\ \end{cases} \end{equation}
L'algorithme suivant calcule les valeurs successives de la suite de Syracuse à partir du terme initial \(u_0\) qui constitue l'entrée de l'algorithme. L'algorithme s'arrête dès que le terme calculé est égal à 1 et renvoie donc la plus petite valeur \(n\) telle que \(u_n=1\): 
ALGORITHME Syracuse(u0):entier
donnees
   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 :

Quelle que soit la valeur initiale \(u_0 \gt 0\) de la suite de Syracuse \((\ref{def:syracuse}),\) il existe un entier naturel \(n\) tel que \(u_n=1\).

Cette conjecture a été vérifiée pour toutes les valeurs \(u_0<5\times2^{60}\) et vous pouvez le vérifier ici même pour tout terme initial \(u_0\) inférieur à un million. Pour \(u_0=\), le plus petit entier \(n\) tel que \(u_n=1\) est \(n=\,\) En imaginant que les valeurs successives de cette suite codent les dif­fé­ren­tes altitudes d'un avion durant un vol, la valeur \(n\) coderait le temps de vol, la valeur 1 représentant le plancher des vaches.

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.

Définissez un nouveau type tbool basé sur un type énuméré enum avec les deux valeurs true et false.
Écrivez une fonction tbool EstPalindrome(char *phrase) qui détermine si une chaîne de caractères est un palindrome (les espaces dans la chaîne ne doivent pas être pris en compte).

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 \((u_n)_{n\in\N^*}\) déterminées par le terme initial \(u_0,\) sont interprétées comme les altitudes d'un vol en avion partant de l'altitude \(u_0,\) la fin du vol correspondant à l'altitude \(u_n=1\). Toutes les fonctions sont à écrire en langage C.

La suite de Syracuse de terme initial \(u_0:=u\) est qualifiée de vol \(u\). On note \(t(u)\) le temps de vol de \(u,\) c'est-à-dire \[ t(u):=\min\{n\in\N\such (u_0=u)\wedge(u_n=1)\}. \]

On note \(p(u)\) le plafond du vol \(u,\) c'est-à-dire l'altitude maximale atteinte durant ce vol : \[ p(u):=\max\{u_i\such i\in\ab{0}{t(u)}\}. \]

(1) Écrivez une fonction uint Syracuse(uint n) qui renvoie la valeur \(n/2\) si \(n\) est pair et la valeur \(3n+1\) si \(n\) est impair.

(2) Écrivez une fonction void Vol(uint u, uint *temps, uint *plafond, tbool afficher) qui calcule \(t(u)\) et \(p(u)\). Si le paramètre affiche est vrai, alors la fonction doit afficher tous les couples \((n,u_n)\) pour \(n\in\ab{0}{t(u)}\) (un couple par ligne uniquement séparés par un espace). Quelle est la durée et l'altitude maximale du vol qui commence à l'altitude \(u_0:=27\) ? Même question pour le vol qui commence à l'altitude \(u_0=4\,563\,281\).

(3) Écrivez une fonction void GenererGraphes(uint n, const char *datat, const char *datap) qui crée deux fichiers dont les noms sont en paramètres, et qui contiennent les graphes partiels des deux fonctions \(t\) et \(p\) respectivement pour \(u\in\ab{1}{n}\).

(4) Tracez les graphes de ces deux fonctions dans la même fenêtre avec Gnuplot pour différentes valeurs de \(n\). Indication⁥: commande plot "datat.txt" with lines, "datap.txt" with lines.