# 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 :
À 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.
* L'information cardinal de E est une information qui peut être représentée par un entier (ici 4).
* L'information b appartient à E est une information qui peut être représentée par un booléen (ici VRAI).
* L'information e appartient à E est une information qui peut être représentée par un booléen (ici FAUX).
* 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.
* L'information nombre de personnes dans l'ascenseur peut être représentée par un entier.
* L'information il y a au moins une personne dans l'ascenseur peut être représentée par un booléen.
* L'information l'ascenseur est au premier étage peut être représentée par un booléen.
* 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 :

### Un exemple

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 :

### 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.
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 :
Ce programme affiche :
Si l'algorithme contient
Le programme
affiche

### 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 :
Pour demander l'âge :

## 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 :
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
On assigne n :
À partir de maintenant la variable n vaut 12. Ainsi, l'instruction
provoquera l'affichage suivant :
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 :
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 :
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 :
* 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

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

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

### Exemples
## Une équivalence utile

Remarquez que ces deux blocs conditionnels sont équivalents :

# 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 :
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 :
* i est affecté à la valeur de deb (i←deb)
* si i est différent de fin alors on exécute instruction
* incrémenter i (i←i+1)
* revenir au point 2
Il est évident que pour que le programme fonctionne deb<fin.

### Exemples
#### Dix itérations

Ce programme va afficher :

## Structure TANTQUE

condition est une expression booléenne, comme dans la structure SI condition ALORS...
Cette structure est exécutée comme suit :
* si condition est vraie : exécuter instruction sinon, continuer après FINTANTQUE
* reprendre au point 1

### La boucle infinie

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

### Une boucle POUR

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

### Exemples
## Structure REPETER

condition est une expression booléenne.
Cette structure s'exécute comme suit :
* exécuter instruction
* si condition est vrai : continuer au point 3 sinon, reprendre au point 1
* exécuter ce qui suit le JUSQU'A

### La boucle infinie

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

### Une boucle POUR

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

### Exemples
## 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 :
* 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
On accède au ième du tableau comme suit
* 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 :
Il suffit pour afficher ses éléments de

# 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 :
on peut ensuite déclarer normalement les variables de ce nouveau type :
Pour accéder à une sous-valeur de la variable, nous utiliserons l'expression :
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 :
Supposons maintenant que nous avons le lexique suivant :
Si nous assignons :
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 :

# L'algorithme au final : vue d'ensemble

Au final, l'algorithme se compose de la façon suivante :
* Algorithme suivi du nom de l'algorithme
* De la déclaration des procédures et des fonctions
* De la déclaration des constantes de l'algorithme principal
* De la déclaration des variables de l'algorithme principal
* De l'algorithme principal

# Exercices
## Types, expressions et opérateurs
### Questions théoriques

* Citez des exemples de types
* Donnez un opérateur polymorphe
* Écrire un programme qui saisit trois nombres dans un ordre donné et les fait sortir dans l'ordre inverse d'entrée.
Solutions :
* booléen, entier, réel, caractère, chaîne de caractères
* + (polymorphe car fonctionne avec des entiers et des réels)

### Types et valeurs

Donner le type des expressions suivantes et leur valeur
* 0
* 1+2
* 0.0+1.0
* "a"
* "a"."b"="b"
* "a"."b"
Donner le type de a et de l'expression :
* a+1
* a."b"
* a=1.0

#### Solutions

* entier : 0
* entier : 3
* réel : 1.0
* caractère : "a"
* booléen : FAUX
* chaîne de caractères : "ab"
Questions avec la variable a :
* entier ; a entier
* chaîne de caractères : a caractère ou chaîne de caractères
* booléen : a réel

### Calcul booléen

Quelle est la valeur de ces expressions booléennes ?
* non(VRAI)
* VRAI et FAUX
* FAUX ou FAUX
* VRAI et VRAI
* non(FAUX ou VRAI)
* FAUX et ((VRAI et VRAI) ou (VRAI et (FAUX ou (VRAI et FAUX)))))
* VRAI ou (VRAI et (FAUX ou ((FAUX et VRAI) ou VRAI)))
a et b sont des booléens, simplifier les expressions :
* non(non(a))
* non(non(non(b)))
* faux ou a
* faux et a
* vrai et a
* vrai ou a
* a et non(a)
* a ou non(a)
* non(a=b) et (a=b)

#### Solutions

* FAUX
* FAUX
* FAUX
* VRAI
* FAUX
* 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.
* 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
Simplifications :
* a
* non(b)
* a
* faux
* a
* vrai
* faux
* vrai
* faux

## Condition

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

### Solution
## Boucles
### 13 à 47

Donner une boucle qui affiche les entiers de 13 à 47
Solution:

### de 5 en 5

Donner une boucle affichant les entiers de 5 en 5 et de 5 à 100
Solutions :
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
Le tableau contient 11 éléments.

## Procédures et fonctions

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