Algorithmique impérative/Théorie

Qu'est ce qu'un algorithme impératif

Première approche

On peut faire le parallèle entre un algorithme et une recette de cuisine. La recette donne les indications nécessaires pour transformer, étape par étape, des ingrédients de départ en un plat prêt à servir. En suivant la recette, le cuisinier en transpose le texte en actions concrètes. Il en va de même pour l'algorithme : une fois qu'on l'a écrit, on le donne à l'ordinateur qui va le suivre étape par étape, cette fois-ci pour transformer des données de départ en données d'arrivée : les résultats.

Attention toutefois, ce parallèle donne une idée générale mais cache quelques subtilités. En effet, si le cuisinier peut faire deux choses en même temps (faire cuire quelque chose au four pendant qu'il épluche autre chose), l'ordinateur, lui, ne fait qu'une seule chose à la fois.

L'objectif de ce livre est donc d'apprendre à écrire des recettes qu'un ordinateur pourra comprendre. Cela implique le respect des règles d'un langage que nous allons apprendre. Nous pourrons ainsi écrire des recettes qui seront en fait des méthodes pour résoudre des problèmes ou calculer des résultats. L'ordinateur pourra alors suivre la recette et donner les résultats, après avoir effectué tous les calculs (fastidieux) à votre place. Un objectif concret est tout simplement de pouvoir assigner à un ordinateur une tâche trop rébarbative pour en débarrasser un humain.

Définition

Tout d'abord, un algorithme impératif est une séquence d'actions. C'est une séquence car les actions s'effectuent les unes après les autres et non en même temps.

Un algorithme a une fonction, un objectif. Pour cela, il transforme des entrées (aucune, une ou plusieurs) en sorties (une ou plusieurs) : vous lui entrez des données, il vous en sort d'autres.

Distinction algorithme / programme : de l'algorithme découle un programme informatique que l'on peut exécuter sur une machine. Le programme informatique est une traduction de l'algorithme dans un langage de programmation (par exemple Pascal). On peut créer plusieurs programmes informatiques différents à partir d'un même algorithme car chaque langage de programmation a ses particularités. On peut donc dire que l'algorithme est théorique, il est l'abstraction du programme informatique.

Par exemple, l'algorithme par lequel on entre deux nombres entiers et qui donne en sortie la somme de ces deux nombres a pour objectif de faciliter le calcul des sommes de deux nombres, opérations qui peuvent être fastidieuses à faire de tête pour un humain.

Il y a dans la vie courante de nombreux exemples d'algorithmes impératifs qui nous donnent des marches à suivre (mathématiques, recettes de cuisine, ...).

Un algorithme complet, pris ci-dessous comme exemple, donne une idée simple de ce qu'on pourra produire à la fin de l'étude de l'algorithmique impérative. Tous les concepts mis en œuvre dans cet algorithme sont expliqués plus loin, ne vous inquiétez donc pas si certains aspects vous échappent pour l'instant.

Cet algorithme calcule et affiche le périmètre, l'aire et le volume du cercle ou de la sphère dont le rayon est donné par l'utilisateur :

Algorithme cercle
Constantes
  pi = 3,1416
Lexique
  rayon     : réel (* le rayon donné par l'utilisateur *)
  périmètre : réel (* le périmètre du cercle *)
Début
  Afficher("Donner le rayon : ")
  Lire(rayon)
  périmètre ← 2 * pi * rayon
  Afficher("Le périmètre est de : ", périmètre)
  Afficher("L'aire du cercle est de ", pi * rayon²)
  Afficher("Le volume de la sphère est de ",(4/3) * pi * rayon³)
Fin

À la fin de l'apprentissage proposé dans ce livre, vous serez à même de créer ce genre d'algorithme et d'autres bien plus complexes.

Les types, les opérateurs et les expressions

Nous entrons maintenant dans le vif du sujet. Cette première partie est plutôt abstraite et une fois que vous l'aurez étudiée, peut entrainer une sensation de confusion sans application pratique concrète. À cet effet, vous trouverez en fin de document une partie « Ce qu'il faut retenir ». Lors de votre première lecture, n'essayez pas de comprendre mais plutôt d'admettre. Une seconde lecture vous permettra d'avoir une vue d'ensemble et de constater qu'en fait, tout se tient.

Première approche

Un type est la façon de comprendre la signification d'une donnée. Prenons la donnée 4 : elle peut être de type entier (de valeur 4 : 3+1), de type caractère (le caractère "4"), est-ce un réel... ?

Un opérateur transforme des données. Par exemple, la somme est un opérateur qui transforme des données en une autre donnée. Il convient de se demander sur quel(s) type(s) un opérateur fonctionne. Par exemple, la somme de deux données de type "entier" est de type "entier". On peut donc supposer que la somme de deux données de type "réel" sera de type "réel" (rassurez-vous : ce sera le cas). Qu'en est-il de la somme de deux données de type "caractère" et de la somme d'une donnée de type "réel" et d'une autre de type "entier" ?

Une expression est une combinaison d'opérateur et de données. Par exemple "4+3" est une expression comportant un opérateur et deux données de type "entier". Toutes les expressions ont une valeur, "4+3" a la valeur 7 ; 7 est une donnée de type "entier".

Nous avons donc trois notions différentes, mais liées entre elles par des règles que nous allons voir.

Spécification

Chaque type a donc son ensemble de valeurs possibles et des opérateurs qui lui sont propres. Par exemple, le type entier qui peut prendre des valeurs telles que 10 ou 12345...

Les opérateurs sont des fonctions mathématiques et à ce titre, ils ont un espace de départ et un espace d'arrivée. Cette propriété s'étend aux opérateurs puisque chaque opérateur à un ou plusieurs types de départ (fonction à une ou plusieurs variables) et un type d'arrivée.

Prenons la fonction mathématique « somme ». On pourrait noter : somme : ℕ² → ℕ : x,y → x+y. De la même façon, l'opérateur somme ajoute deux données de type "entier" et renvoie un "entier". Remarquez que "a+b" est une notation de somme(a,b).

Pour chaque opérateur que vous découvrez ou utilisez, demandez-vous toujours quels sont les types de départ et d'arrivée. Beaucoup d'erreurs sont dues à des opérateurs mal utilisés.

Une expression est donc une suite d'opérateurs et de données qui doit respecter les règles imposées par l'usage des opérateurs.

Dans notre cours nous allons introduire cinq types, les plus couramment utilisés en informatique :

• entier
• réel
• caractère
• chaîne de caractères
• booléen

Ce(s) dernier(s) vous est (sont) probablement étrangers : ne vous inquiétez pas, nous allons y revenir.

Les entiers et les réels

Voici deux types fidèles à leur définition mathématique.

Les opérateurs sur les entiers sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division entière. Un dernier opérateur est l'opérateur mod, donnant le reste de la division entière. Tous ces opérateurs prennent deux données de type "entier" pour en renvoyer une autre du même type. (Rappel : a = (a / b)*b + a mod b)

Les opérateurs sur les réels sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division. Tous ces opérateurs prennent deux données de type "réel" pour en renvoyer une autre du même type.

Il convient de se demander ce qu'il se passe quand on considère l'expression "a+b" avec a entier et b réel. Cela est censé ne jamais arriver. Néanmoins, on pourra considérer que l'entier se transforme en réel avant l'opération.

Les caractères et les chaînes de caractères

Un caractère est tout simplement une lettre, un chiffre ou un symbole : par exemple, "1", "a", "A", "|" sont des caractères.

Aucun opérateur n'existe sur les caractères, ayant un caractère pour résultat. Dans certains langages de programmation, il peut exister des opérateurs pour ajouter un caractère à une chaîne de caractères.

Une chaîne de caractères est une suite de caractères telle que décrite précédemment. "1", "1abc" (par exemple) sont des chaînes de caractères. À noter que "" est une chaîne de caractères (la seule comportant 0 caractère).

Il n'existe qu'un seul opérateur sur les chaînes. Il s'agit de l'opérateur de concaténation qu'on notera "+". La concaténation revient à mettre la seconde chaîne à la suite de la première.

Par exemple "abc"+"def" est équivalente a "abcdef". Remarquez que l'opérateur de concaténation, même s'il est noté "+", n'est pas commutatif comme l'est la somme, nous n'avons évidemment pas a+b=b+a.

Attention, par la suite, à ne pas confondre 1+2 qui est l'entier de valeur 3 avec "1"+"2" qui est la concaténation des chaînes "1" et "2" qui vaut "12" (et sûrement pas "3").

Il n'existe pas de convention pour désigner l'opérateur de concaténation. Nous pourrons également utiliser la notation ".".

Bien que cela ne doive pas arriver, nous pouvons considérer que l'opération de concaténation effectuée sur des caractères fonctionne et donne une chaîne de caractères.

Introduction à l'arithmétique booléenne

En informatique on introduit un nouveau type un peu moins familier : le booléen. Au même titre que les entiers ou les réels : un booléen peut prendre un ensemble de valeurs et possède ses propres opérateurs.

Il n'est donné ici que quelques explications (nécessaires et suffisantes pour la suite du cours) sur le booléen. Il existe cependant toute une algèbre permettant de travailler sur les booléens. Un complément essentiel de ce cours d'algorithmique impérative est l'étude de l'algèbre de Boole.

Première approche

En mathématiques, les entiers ont été invités pour dénombrer, les réels pour représenter les distances, les volumes, etc... Le booléen a également pour utilité de représenter le réel. Il sert à représenter la véracité, c'est à dire à déclarer si une chose est vraie ou fausse.

L'ensemble des valeurs possibles d'un booléen est de deux (!). Ces deux valeurs sont notées VRAI et FAUX.

Voici deux exemples comportant des informations représentées par des booléens :

Premier exemple : Supposons que E soit en ensemble qui contient les éléments a, b, c et d.

1. L'information cardinal de E est une information qui peut être représentée par un entier (ici 4).
2. L'information b appartient à E est une information qui peut être représentée par un booléen (ici VRAI).
3. L'information e appartient à E est une information qui peut être représentée par un booléen (ici FAUX).
4. L'information 'E comporte au moins 2 éléments est une information qui peut être représentée par un booléen (ici VRAI).

Second exemple : Prenons l'ascenseur d'un immeuble.

1. L'information nombre de personnes dans l'ascenseur peut être représentée par un entier.
2. L'information il y a au moins une personne dans l'ascenseur peut être représentée par un booléen.
3. L'information l'ascenseur est au premier étage peut être représentée par un booléen.
4. etc.

Vous voyez donc qu'un booléen peut servir à représenter une multitude d'informations différentes mais ne remplace pas les entiers, les réels ou tout autre type. Chaque type à un usage et il convient d'user du booléen a bon escient tout comme on ne représente pas une distance avec un entier ou un dénombrement avec un réel.

Opérateurs booléens

Au même titre que pour les autres types, il existe des opérateurs sur les booléen. Nous avons vu que la somme était un opérateur qui prenait deux entiers et renvoyait un résultat de type entier également. Il en va de même pour les booléen.

Opérateur	noté	Type des paramètres	Type du résultat	Valeur du résultat	Exemple	Remarque
négation	non ou ¬	un booléen	un booléen	Si VRAI alors FAUX. Si FAUX alors VRAI	non(VRAI) a pour résultat FAUX non(FAUX) a pour résultat VRAI	non() est une fonction mathématique dite réciproque : non(non(truc)) vaut truc.
conjonction	et	deux booléens	un booléen	Le résultat vaut VRAI seulement si les deux paramètres sont VRAI. FAUX sinon.	VRAI et VRAI a pour résultat VRAI VRAI et FAUX a pour résultat FAUX	On pourra aussi dire "Pour que le résultat soit VRAI il faut que tous les paramètres soient VRAI".
disjonction	ou	deux booléens	un booléen	Le résultat vaut VRAI si au moins un des deux paramètres est VRAI. FAUX si tous les paramètres sont FAUX	VRAI ou VRAI a pour résultat VRAI VRAI ou FAUX a pour résultat VRAI

Vous en serez déjà arrivé à ces conclusions : si b est un booléen,

• b et FAUX vaut FAUX quel que soit b
• b ou VRAI vaut VRAI quel que soit b

Ces opérateurs peuvent bien sûr former des expressions. Quelques exemples :

• non(non(FAUX)) vaut FAUX
• ((VRAI et FAUX) ou VRAI) vaut VRAI

La négation est prioritaire sur la conjonction. La conjonction est prioritaire sur la disjonction.

Tableau récapitulatif

Tableau récapitulatif des types et de leurs opérateurs

Type	Ensemble de valeurs	Opérateurs
Entier	ℕ	+ (somme), - (différence), * (multiplication), / (division entière)
Réel	ℝ	+ (somme), - (différence), * (multiplication), / (division)
Booléen	{VRAI ; FAUX}	¬ (négation), et (conjonction), ou (disjontion)
Caractère
Chaîne de caractères		Concaténation

Ce qu'il faut retenir

Ce chapitre est abstrait et ne donne rien de concret. N'apprenez pas par cœur, tout ceci se tient et est assez cohérent par rapport à ce que vous avez appris sur les mathématiques. Voici ce qui doit retenir votre attention :

• Retenez les noms des différents types et de leurs opérateurs en retenant bien quel opérateur fait quoi et avec quoi. Vous devriez pouvoir reconstruire de tête le tableau récapitulatif (encore une fois, vous ne devriez pas avoir à l'apprendre, vous devriez pouvoir le déduire des types).
• Retenez que les booléen, les caractères et les chaînes de caractères et leurs opérateurs fonctionnent exactement de la même façon que les entiers et les réels. Ce sont des types, qui ont un ensemble de valeurs possibles et des opérateurs spécifiques. On peut écrire des expressions à condition de respecter certaines règles.
• Essayez de voir un peu comment on manipule cette arithmétique booléenne qui, comme l'arithmétique entière, vous permet de calculer des expressions et d'en simplifier d'autres. Remarquez que cette arithmétique est plus simple puisque vous n'avez que deux valeurs possibles (c'est peu par rapport à l'infinité d'entiers...).
• Vous pouvez déjà faire les exercices sur ce chapitre. Si vous avez su les résoudre sans relire ce cours.

Les constantes, les variables

Dans un algorithme, il faut stocker les données à traiter. Certaines de ces données sont connues et ne varieront pas tout le long de l'algorithme : il s'agit des constantes. D'autres données peuvent être inconnues (elle seront fonction du choix de l'utilisateur, ou du temps...) ou susceptibles d'évoluer au cours de l'algorithme : il s'agit des variables.

Les variables

Toutes les variables ont un type. Dans chaque algorithme, toutes les variables et leurs types sont explicitées dans le lexique. On dit que la variable est déclarée.

D'un point de vue mathématique, la déclaration revient à l'expression "Soit ... un ...".

Le lexique est noté comme suit :

Variables
 identifiant_de_la_variable : type de la variable;
 ...

Un exemple

Variables
     n : entier
     1 : réel
 une réponse : booléen
 un nom de famille : chaîne de caractère

Dans cet exemple, nous avons cinq variables.

Du point de vue mathématique, on aurait pu énoncer "Soit n un entier", "Soit 1 un réel", "Soit vrai ou faux booléen", etc.

Les constantes

De la même façon, les constantes sont déclarées dans une partie Constantes de cette façon :

Constantes
  nom_de_la_constante = valeur

Un exemple

À priori, on peut considérer que PI ne risque pas de changer de valeur pendant un algorithme. On peut donc déclarer PI en tant que constante.

Constantes
  pi = 3.14
  ...

Une seule constante est déclarée.

Les instructions, les blocs d'instructions

Nous avons vu qu'un algorithme est une séquence d'instructions ; de quoi s'agit-il exactement ? Les instructions sont les actions devant être effectuées par l'algorithme. Elle peuvent requérir que l'on précise certaines informations.

Deux instructions de base

Voici expliquées deux instructions que l'on retrouvera très fréquemment dans des algorithmes. Il s'agit des instructions Afficher et Lire.

Afficher

Afficher permet d'afficher des données à l'écran et ainsi de communiquer avec l'utilisateur. Pour cette instruction, on doit préciser une expression qui sera évaluée avant d'être affichée.

Quelques exemples :

Afficher ("ceci est un exemple : on affiche une chaîne, sans utiliser de variables")

Ce programme affiche :

ceci est un exemple : on affiche une chaîne, sans utiliser de variables

Si l'algorithme contient

Constantes
  PI = 9

Le programme

Afficher(PI)

affiche

9

Lire

La fonction Lire permet de demander à l'utilisateur de fournir des informations. Chaque information donnée par l'utilisateur est stockée dans une variable (attention au type !). Vous précisez cette variable dans les parenthèses.

Un exemple : nous réalisons un algorithme qui demande à l'utilisateur d'entrer son âge. Tout d'abord il apparaîtra dans le lexique :

Lexique
  age : entier (* l'âge donné par l'utilisateur *)

Pour demander l'âge :

Lire(age)

Les blocs d'instructions

Souvent, l'exécution d'une seule instruction ne suffit pas pour faire un algorithme complet. Nous pouvons faire en sorte que plusieurs instructions soient considérées comme une seule. Pour cela, il faut créer un bloc d'instructions. Partout où l'on peut mettre une instruction, on peut mettre un bloc d'instructions.

Concrètement, on procède ainsi : les instructions sont séparées par un saut de ligne ou par ;. Le bloc d'instruction est précédé de Début et suivi de Fin.

Un exemple :

Début
  instruction1
  instruction2
  Afficher("Cet affichage est la troisième instruction")
  instruction4
Fin

Une autre notation, courante dans les langages de programmation, est plus courte. Les instructions formant un bloc sont entre { et }.

L'assignation

L'assignation est une instruction qui consiste à inscrire dans une variable une valeur calculée depuis une expression. Attention : la nouvelle valeur affectée « écrase » la précédente.

C'est donc la deuxième façon que nous apprenons de donner une valeur à une variable. La première était d'utiliser l'instruction Lire qui permet de demander la valeur à l'utilisateur. On peut dire que l'instruction Lire est une forme particulière d'affectation.

Pour effectuer une assignation, on utilise l'instruction Assigner. On précise entre parenthèses la variable affectée ainsi que l'expression de la valeur de l'affectation.

On pourra également noter l'affectation ← ou :=. Ce symbole peut être énoncé « prend pour valeur ». Attention toutefois à ne pas la noter = bien que certains langages utilisent cette notation. Ce serait un dangereux raccourci de pensée avec les mathématiques (voir la mise en garde ci-dessous).

Un exemple : voici notre lexique

Lexique
  n : entier

On assigne n :

Assigner(n, 12)

À partir de maintenant la variable n vaut 12. Ainsi, l'instruction

Afficher(n)

provoquera l'affichage suivant :

12

Dans la suite du cours, nous utiliserons la notation ←, moins lourde.

Mise en garde sur le parallèle avec les mathématiques

Au moment de l'affectation, la valeur affecté est évaluée, c'est-à-dire calculée, les constantes et les variables sont donc remplacées par leurs valeurs respectives.

Exemple : dans le lexique nous avons :

Lexique
  a,b,c : entiers

a←1
b←2
c←a+b (* équivaut à c←2+1 et à c←3 *)
afficher(c) (* affiche 3 *)
b←5
afficher(c) (* affiche toujours 3 et non 6 *)

c conserve sa valeur tant qu'elle n'a pas été affectée, le changement de la valeur de b n'affecte pas la valeur de c.

Certains seraient tentés de noter l'affectation avec l'opérateur "=", elle est d'ailleurs notée ainsi dans le langage de programmation C. C'est pourtant une erreur vis-à-vis du sens mathématique de ce symbole. En effet, cette expression :

x = x+1

est tout à fait correcte en informatique si on considère l'affectation notée ainsi ; cela revient à incrémenter x. Mais du point de vue mathématique c'est une aberration. Voyons cela en appliquant une résolution d'équation du premier degré :

$x=x+1$

par soustraction de x dans les deux membres :

$x-x=1$

donc

$0=1$

En revanche, l'affectation notée := est valide en mathématique comme en informatique. En prenant cette convention, tout le monde est content...

Les exécutions conditionnelles

Vous savez que les instructions s'exécutent les unes après les autres. C'est intéressant mais insuffisant pour élaborer des algorithmes complexes. En effet, nous pourrions avoir besoin d'exécuter certaines instructions seulement dans un certain contexte. Les structures permettant d'imposer la succession des instructions sont appelées structures de contrôles. L'exécution conditionnelle, que nous allons voir ici, est la plus simple de ces structures de contrôles.

SI...ALORS...

L'exécution conditionnelle permet de n'exécuter une instruction que si une certaine condition est remplie. La syntaxe est la suivante :

SI condition
  ALORS instruction
FINSI

• condition est une expression booléenne. L'instruction n'est exécutée que si cette l'expression booléenne est évaluée à VRAI. Si condition est évaluée à FAUX aucune instruction n'est exécutée. Dans les deux cas, le programme poursuit son exécution par ce qui se trouve après le FINSI.
• instruction est une instruction normale. Vous pouvez bien sûr exécuter plusieurs instructions : il suffit pour cela d'un bloc d'instructions.

Exemples

 SI FAUX
   ALORS Afficher("Cet affichage ne se produira jamais, la condition n'étant jamais VRAI")
 FINSI

Cet extrait d'algorithme n'a aucun intérêt. S'il est effacé du programme, on obtient un programme équivalent.

SI VRAI
  ALORS Afficher("Cet affichage se produit toujours")
FINSI

Cet extrait d'algorithme n'a aucun intérêt. Il aurait évidemment suffit d'écrire :

Afficher ("Cet affichage se produit toujours")

...SINON

Il est possible de préciser une instruction à exécuter si la condition n'est pas vérifiée, c'est-à-dire si elle est évaluée à FAUX. Il suffit pour cela d'ajouter une partie SINON entre ALORS et FINSI. Cette partie SINON n'est pas toujours utile, elle est donc facultative.

SI condition
  ALORS instruction
  SINON instruction
FINSI

Exemples

SI condition
  ALORS Afficher("La condition vaut VRAI")
  SINON Afficher("La condition vaut FAUX")
FINSI

Une équivalence utile

Remarquez que ces deux blocs conditionnels sont équivalents :

SI condition
  ALORS instruction_A
  SINON instruction_B
FINSI

SI non(condition)
  ALORS instruction_B
  SINON instruction_A
FINSI

Les structures itératives

Les structures de contrôle itératives permettent d'exécuter plusieurs fois de suite une ou plusieurs instructions. Il en existe trois distinctes.

Structure POUR

La structure POUR permet d'exécuter une instruction un nombre connu de fois. Voici la syntaxe :

POUR i DE deb A fin FAIRE
  instruction
FINPOUR

i est l'identifiant d'une variable (qui doit bien sûr être déclarée). deb et fin sont deux expressions de même type que i : ce sont les valeurs entre lesquelles i va parcourir l'ensemble des valeurs intermédiaires.

La structure s'exécute de la façon suivante :

1. i est affecté à la valeur de deb (i←deb)
2. si i est différent de fin alors on exécute instruction
3. incrémenter i (i←i+1)
4. revenir au point 2

Il est évident que pour que le programme fonctionne deb<fin.

Exemples

Dix itérations

Lexique
  i : entier
Début
  POUR i de 1 à 10 FAIRE
    Afficher(i);
  FINPOUR
FIN

Ce programme va afficher :

1
2
3
4
5
6
7
8
9
10

Structure TANTQUE

TANTQUE condition
  instruction
FINTANTQUE

condition est une expression booléenne, comme dans la structure SI condition ALORS...

Cette structure est exécutée comme suit :

1. si condition est vraie : exécuter instruction sinon, continuer après FINTANTQUE
2. reprendre au point 1

La boucle infinie

Il est possible grâce à cette structure de créer une boucle infinie :

TANTQUE VRAI
 instruction
FTQ

Une boucle POUR

Il est possible de simuler une boucle POUR à l'aide d'un TANTQUE

i←deb
TANTQUE i <= fin
  instruction
  i←i+1
FTQ

Structure REPETER

REPETER
  instruction
JUSQU'A condition

condition est une expression booléenne.

Cette structure s'exécute comme suit :

1. exécuter instruction
2. si condition est vrai : continuer au point 3 sinon, reprendre au point 1
3. exécuter ce qui suit le JUSQU'A

La boucle infinie

Il est possible grâce à cette structure de créer une boucle infinie :

REPETER
 instruction
JUSQU'A FAUX

Une boucle POUR

Il est possible de simuler une boucle POUR à l'aide d'un REPETER

i←deb
REPETER
  instuction
  i←i+1
JUSQU'A i=fin

Comment déterminer la structure à utiliser ?

Le choix de la structure de contrôle se fait en fonction du nombre d'itérations à effectuer :

• si le nombre d'itérations est déterminé à l'avance, une boucle POUR est la plus appropriée,
• sinon :
  • si la condition de boucle ne peut être évaluée avant la première itération, ou si au moins une itération doit être exécutée, la boucle REPETER est la plus appropriée,
  • sinon la boucle TANT QUE est la plus appropriée.

Les tableaux

Première approche

Le tableau est un nouveau type. Il contient un ensemble d'éléments indicés par des entiers ; on peut donc utiliser des variables tableaux.

Nous n'étudierons que les tableaux à une dimension également appelés vecteurs.

Spécification

Les tableaux sont déclarés comme suit :

Lexique
  tab : tableau DEBUT à FIN de TYPE

• tab est l'identifiant de la variable tableau
• DEBUT est un entier : l'indice du premier élément du tableau, généralement 0 ou 1.
• FIN est un entier : l'indice du dernier élément, cela peut être un entier fixé ou, plus intéressant, une constante déclarée.
• On a évidemment FIN > DEBUT
• TYPE est le type de chacun des éléments du tableau.

Par exemple, un tableau d'entiers de 10 cases

Lexique
  tab : tableau 1 à 10 de entier

On accède au i^ème du tableau comme suit

tab[i]

• i est un entier qui doit évidemment être compris entre DEBUT et FIN (précisés dans la déclaration de tab)
• la variable tab[i] est donc du type TYPE (précisé dans la déclaration de tab)

Utilisation

La tableau est utilisé lorsqu'il faut stocker des suites de variables de même rôle. Par exemple, les notes d'un groupe d'étudiants en algorithmique impérative.

La structure POUR se prête très bien au parcours d'un tableau. En supposant le tableau tab déclarer comme suit :

Lexique
  tab : tableau MIN à MAX de TYPE

Il suffit pour afficher ses éléments de

Pour i de MIN à MAX
  Afficher(tab[i])
FP

Les procédures et les fonctions

Première approche

Les procédures et les fonctions sont des sous-programmes qui permettent une réutilisation du code plus facile. En effet, si par exemple on code l'algorithme de calcul de T.V.A. et qu'on l'utilise à divers endroits du programme, plutôt que de recopier le code à chaque fois, il est préférable de créer un sous-programme de calcul. La recopie a toutefois les inconvénients suivants :

• La recopie du code s'accompagne souvent d'un changement des noms de variables, voire de la valeur de certains paramètres,
• Chaque copie du code augmente la taille des programmes source et compilé,
• La maintenance est plus difficile : s'il faut modifier l'algorithme, il faut modifier toutes les copies sans en oublier une seule.

L'utilisation d'un sous-programme évite tous ces problèmes :

• Les sous-programmes utilisent des variables locales et des paramètres formels, c'est-à-dire qu'on leur passe les valeurs (voire les variables, par adresse ou référence) qu'ils doivent utiliser.
• L'algorithme n'est codé qu'une seule fois, ce qui n'augmente pas la taille du programme.
• La maintenance est facilitée par le point précédent : s'il faut modifier l'algorithme, la modification n'a lieu qu'en un seul endroit.

Procédure et fonction : quelle différence ?

Une procédure traite les informations qu'on lui passe, mais ne retourne, en général, aucun résultat. En général, cette procédure a un effet de bord.

Une fonction traite les informations qu'on lui passe, et retourne un résultat. Si la fonction n'a aucun effet de bord, on peut la comparer à une fonction mathématique.

Effet de bord

un sous-programme avec effet de bord modifie l'état global de l'application. En général, appeler deux fois un même sous-programme avec effet de bord en lui passant les mêmes paramètres ne produit pas le même résultat.

Le type enregistrement

Première approche

L'enregistrement est une façon de créer un nouveau type, ou encore un méta-type, c'est-à-dire un type qui contient d'autres variables de types déjà définis.

Spécification

On déclare un nouveau type dans la partie Types comme suit :

identifiant_du_type = enregistrement
  identifiant_première_sous_valeur : type_de_la_première_sous_valeur
  identifiant_deuxième_sous_valeur : type_de_la_deuxième_sous_valeur
  ...
fin

on peut ensuite déclarer normalement les variables de ce nouveau type :

identifiant_variable : identifiant_du_type

Pour accéder à une sous-valeur de la variable, nous utiliserons l'expression :

identifiant_variable.identifiant_sous_valeur

Cette expression est du type de identifiant_sous_valeur.

Exemple

Supposons que nous voulions un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :

couple = enregistrement
  a : entier
  b : entier
fin

Supposons maintenant que nous avons le lexique suivant :

Lexique
  c : couple

Si nous assignons :

c.a ← 1
c.b ← 2
afficher(c.a) (* affichera 1 *)

Le projet sur les dates propose un travail complet sur le sujet.

Utilisation

Cela n'est pas obligatoire en algorithmique impérative, mais pour travailler sur un nouveau type , il convient de définir quelques fonctions élémentaires pour créer une variable à partir de ses sous-valeurs. Remarquez que les types de paramètres seront semblables aux types des sous-variables de nouveau type (exception faite dans le cas de sous-valeurs par défaut...).

Exemple

Pour reprendre notre exemple, nous pourrions créer une fonction :

fonction creerCouple(m, n : entiers)
(* créer un couple à partir de ses deux éléments *)
lexique
  NouveauCouple : couple
debut
  NouveauCouple.a ← m
  NouveauCouple.b ← n
  renvoyer NouveauCouple
fin

L'algorithme au final : vue d'ensemble

Au final, l'algorithme se compose de la façon suivante :

1. Algorithme suivi du nom de l'algorithme
2. De la déclaration des procédures et des fonctions
3. De la déclaration des constantes de l'algorithme principal
4. De la déclaration des variables de l'algorithme principal
5. De l'algorithme principal

Algorithme nom_de_l'algorithme
Fonction1(paramètre1 : type du paramètre 1 (* objet du paramètre1 *)
          paramètre2 : type du paramètre 1 (* objet du paramètre2 *))
         : type de la valeur de retour
Constantes locales de la Fonction1
  constante1 = valeur_de_la_constante1
  constante2 = valeur_de_la_constante2
  constante3 = valeur_de_la_constante3
Variables locales de la Fonction1
  variable1 : type_de_la_variable1
  variable2 : type_de_la_variable2
  variable3 : type_de_la_variable3
Début
  instruction1
  instruction2
  Retourner valeur
Fin

Procédure1(E|S|ES paramètre1 : type du paramètre 1 (* objet du paramètre1 *)
           E|S|ES paramètre1 : type du paramètre 2 (* objet du paramètre2 *)
           E|S|ES paramètre1 : type du paramètre 3 (* objet du paramètre3 *))
Constantes locales de la Procédure1
  constante1 = valeur_de_la_constante1
  constante2 = valeur_de_la_constante2
  constante3 = valeur_de_la_constante3
Variables locales de la Procédure1
  variable1 : type_de_la_variable1
  variable2 : type_de_la_variable2
  variable3 : type_de_la_variable3
Début
  instruction1
  instruction2
Fin

Constantes de l'algorithme principal
  constante1 = valeur_de_la_constante1
  constante2 = valeur_de_la_constante2
  constante3 = valeur_de_la_constante3

Variables de l'algorithme principal
  variable1 : type_de_la_variable1
  variable2 : type_de_la_variable2
  variable3 : type_de_la_variable3

Début
  instruction1
  instruction2
Fin

Exercices

Types, expressions et opérateurs

Questions théoriques

1. Citez des exemples de types
2. Donnez un opérateur polymorphe
3. Écrire un programme qui saisit trois nombres dans un ordre donné et les fait sortir dans l'ordre inverse d'entrée.

Solutions :

1. booléen, entier, réel, caractère, chaîne de caractères
2. + (polymorphe car fonctionne avec des entiers et des réels)

Types et valeurs

Donner le type des expressions suivantes et leur valeur

1. 0
2. 1+2
3. 0.0+1.0
4. "a"
5. "a"."b"="b"
6. "a"."b"

Donner le type de a et de l'expression :

1. a+1
2. a."b"
3. a=1.0

Solutions

1. entier : 0
2. entier : 3
3. réel : 1.0
4. caractère : "a"
5. booléen : FAUX
6. chaîne de caractères : "ab"

Questions avec la variable a :

1. entier ; a entier
2. chaîne de caractères : a caractère ou chaîne de caractères
3. booléen : a réel

Calcul booléen

Quelle est la valeur de ces expressions booléennes ?

1. non(VRAI)
2. VRAI et FAUX
3. FAUX ou FAUX
4. VRAI et VRAI
5. non(FAUX ou VRAI)
6. FAUX et ((VRAI et VRAI) ou (VRAI et (FAUX ou (VRAI et FAUX)))))
7. VRAI ou (VRAI et (FAUX ou ((FAUX et VRAI) ou VRAI)))

a et b sont des booléens, simplifier les expressions :

1. non(non(a))
2. non(non(non(b)))
3. faux ou a
4. faux et a
5. vrai et a
6. vrai ou a
7. a et non(a)
8. a ou non(a)
9. non(a=b) et (a=b)

Solutions

1. FAUX
2. FAUX
3. FAUX
4. VRAI
5. FAUX
6. Il suffit de lire "FAUX et ..." au début de l'expression pour savoir tout de suite le résultat. Quel que soit ce qu'il y avait après le et cela aurait été FAUX.
7. De même, il suffit de lire "VRAI ou ..." au début de l'expression pour savoir tout de suite le résultat : peu importe ce qu'il y a après le ou, cela aurait été VRAI
8. ...

Simplifications :

1. a
2. non(b)
3. a
4. faux
5. a
6. vrai
7. faux
8. vrai
9. faux

Condition

Donner un extrait d'algorithme équivalent à celui-ci sans utiliser de sinon :

si condition
  alors instruction1
  sinon instruction2

Solution

si condition
  alors instruction1
finsi
si non(condition)
  alors instruction2
finsi

Boucles

13 à 47

Donner une boucle qui affiche les entiers de 13 à 47

Solution:

Pour i de 13 à 37
  Afficher(i)
FP

de 5 en 5

Donner une boucle affichant les entiers de 5 en 5 et de 5 à 100

Solutions :

i←0
Répéter
  i←i+5
  afficher(i)
Jusqu'à i=100

i←5
Répéter
  afficher(i)
  i←i+5
Jusqu'à i=105

pour i de 5 à 100
  si i mod 5 = 0 alors afficher i
fp

pour i de 1 à 20
  afficher(5*i)
fp

Remarque : ces algorithmes fonctionnent tous mais certains sont plus efficaces que d'autres. Cette réflexion est laissée au lecteur.

Tableaux

Selon la déclaration suivante

tab : tableau 0 à 10 de T

Combien le tableau a-t-il d'éléments ? 9, 10, 11 ?

Le tableau contient 11 éléments.

Procédures et fonctions

Écrire des fonctions en procédures, des procédures en fonctions.