Algorithmique ii - 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 évolué. Deux raisons principales motivent l'utilisation d'un langage algorithmique plutôt qu'un lan­ga­ge de programmation.

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 comme un manque de rigueur nous permet en fait de nous affranchir à chaque fois que nécessaire, de difficultés qui ne relèvent pas de la nature de l'algorithme étudié. Ainsi, si nous avons ponc­tuel­le­ment 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 tente de conserver les éléments clés que nous avons mis en évidence dans l'introduction. Le nom de l'algorithme est suivi de la liste des données à traiter (la variable \(x\)) et suivi du type du résultat final (la nature de l'ensemble d'arrivée). Son écriture est constituée de 4 blocs consécutifs:

  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

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. 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 @.

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
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 \([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
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:
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
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\):
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 :

[Syracuse] Quelle que soit la valeur initiale \(u_0 > 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.

Écrivez un programme Python pour l'algorithme Syracuse. Tracez avec gnuplot la courbe des temps de vol de cette suite, c'est-à-dire le graphe de la fonction \(\nu:{\mathbf N}\setminus\{0\}\rightarrow{\mathbf N}\) définie par \[\nu(u_0):=\min\{n\in{\mathbf N}\ |\ u_n=1\}.\]

Quel est la durée du vol et l'altitude maximale atteinte si le vol commence à l'altitude \(u_0=4.563.281\) ?