ALGORITHME
Définition
nom masculin (d'Al-Khârezmi, médecin arabe).
Suite de raisonnements ou d'opérations qui fournit la
solution de certains problèmes.
Objectifs
Un algorithme sert à transmettre un savoir faire.
Il décrit les étapes à suivre pour réaliser un travail.
Il permet d'expliciter clairement les idées de solution
d'un problème indépendamment d'un langage de
programmation.
L'utilisateur d'un algorithme n'aura qu'à suivre toutes
les instructions, dans l'ordre pour arriver au résultat
que doit donner l'algorithme.
1
Algorithme
Le "langage algorithmique" que nous utilisons est un
compromis entre un langage naturel et un langage de
programmation.
Nous présentons les algorithmes comme une suite
d'instructions dans l'ordre des traitements. Ils sont toujours
accompagnés d'un lexique qui indique, pour chaque
variable, son type et son rôle.
Nous manipulerons les types couramment rencontrés
dans les langages de programmation : entier, réel,
booléen, caractère, chaîne, tableau et type composite. 2
Formalisme
Un algorithme doit être lisible et compréhensible par plusieurs
personnes.
Il doit donc suivre des règles. Il est composé d'une entête et d'un
corps.
L'entête comprend :
- Nom : le nom de l'algorithme
- Rôle : ce que fait l'algorithme
- Données : les données fournies à l'algorithme
- Résultat : ce que l'on obtient à la fin du traitement
- Principe : le principe utilisé dans l'algorithme
Le corps :
- il est délimité par les mots clés début et fin.
3
- il se termine par un lexique, décrivant les variables utilisées
Formalisme
Par convention, tous les identifiants de variables seront
notés en minuscule et auront un nom mnémonique
Il en va de même pour les fonctions, dont l'identifiant
doit être le plus explicite sur son rôle. Ce dernier peut être
une contraction de plusieurs mots, par
conséquent pour rendre la lecture plus facile, la
première lettre de chaque mot est mis en majuscule
(exemple : CalculerAireRectangle).
4
Formalisme
Exemple d'algorithme :
Nom : AddDeuxEntiers.
Rôle : additionner deux entier et mémoriser le résultat
Données : les valeurs à additionner.
Résultat : la somme des deux valeurs.
Principe : Additionner deux entiers a et b et mettre le résultat dans
c.
début
c←a+b
fin
Lexique :
a : entier 5
b : entier
c : entier
Les variables
Une variable est une entité qui contient une information, elle
possède :
un nom, on parle d’identifiant
une valeur
un type qui caractérise l’ensemble des valeurs que peut
prendre la variable
L’ensemble des variables est stocké dans la mémoire de
l’ordinateur
6
Les variables
Type de variable
entier pour manipuler des entiers
réel pour manipuler des nombres réels
booléen pour manipuler des valeurs booléennes
caractère pour manipuler des caractères alphabétiques
et numériques
chaîne pour manipuler des chaînes de caractères
permettant de représenter des mots ou des phrases. 7
Les variables
A un type donné, correspond un ensemble d'opérations
définies pour ce type.
Une variable est l'association d'un nom avec un type,
permettant de mémoriser une valeur de ce type.
8
Opérateur, opérande et expression
Un opérateur est un symbole d’opération qui permet d’agir
sur des variables ou de faire des “calculs”
Une opérande est une entité (variable, constante ou
expression) utilisée par un opérateur
Une expression est une combinaison d’opérateur(s) et
d’opérande(s), elle est évaluée durant l’exécution de
l’algorithme, et possède une valeur (son interprétation) et un
type
9
Opérateur, opérande et expression
Exemple dans a + b :
a est l’opérande gauche
+ est l’opérateur
b est l’opérande droite
a + b est appelé une expression
Si par exemple a vaut 2 et b 3, l’expression a + b vaut 5
Si par exemple a et b sont des entiers, l’expression a + b est un
entier
10
Les opérateurs
Un opérateur peut être unaire ou binaire :
Unaire s’il n’admet qu’une seule opérande, par exemple
l’opérateur non
Binaire s’il admet deux opérandes, par exemple
l’opérateur +
Un opérateur est associé à un type de donnée et ne peut être
utilisé qu’avec des variables, des constantes, ou des
expressions de ce type
Par exemple l’opérateur + ne peut être utilisé qu’avec les
types arithmétiques (naturel, entier et réel) ou (exclusif) le 11
type chaîne de caractères
Les opérateurs
On ne peut pas additionner un entier et un caractère
Toutefois exceptionnellement dans certains cas on accepte
d’utiliser un opérateur avec deux opérandes de types
différents, c’est par exemple le cas avec les types
arithmétiques (2 + 3.5)
La signification d’un opérateur peut changer en fonction
du type des opérandes
l’opérateur + avec des entiers aura pour sens l’addition,
2+3 vaut 5
avec des chaînes de caractères il aura pour sens la
concaténation "bonjour" + " tout le monde" vaut
"bonjour tout le monde"
12
Les opérateurs booléens
Pour les booléens nous avons les opérateurs non, et, ou, ouExclusif
Non
Et
13
Les opérateurs booléens
Ou
Ou exclusif
14
Les opérateurs booléens
Rappels sur la logique booléenne...
Valeurs possibles : Vrai ou Faux
Associativité des opérateurs et et ou
a et (b et c) = (a et b) et c
Commutativité des opérateurs et et ou
a et b = b et a
a ou b = b ou a
15
Les opérateurs booléens
Distributivité des opérateurs et et ou
a ou (b et c) = (a ou b) et (a ou c)
a et (b ou c) = (a et b) ou (a et c)
Involution (homographie réciproque)
(homos semblable et graphein écrire)
non non a = a
Loi de Morgan
non (a ou b) = non a et non b
non (a et b) = non a ou non b 16
Les opérateurs sur les numériques
On retrouve tout naturellemment +, -, *, /
Avec en plus pour les entiers div et mod, qui permettent
respectivement de calculer une division entière et le
reste de cette division,
par exemple :
11 div 2 vaut 5
11 mod 2 vaut 1
17
Les opérateurs sur les numériques
L’opérateur d’égalité :
C’est l’opérateur que l’on retrouve chez tous les types
simples qui permet de savoir si les deux opérandes sont
égales
Il est représenté par le caractère =
Le résultat d'une expression contenant cet opérateur est un
booléen
On a aussi l’opérateur d’inégalité : ≠
Et pour les types possédant un ordre les opérateurs de
comparaison 18
<, ≤, >, ≥
Priorités des opérateurs
Tout comme en arithmétique les opérateurs ont des
priorités
Par exemple * et / sont prioritaires sur + et -
Pour les booléens, la priorité des opérateurs est non, et,
ouExclusif et ou
Pour clarifier les choses (ou pour dans certains cas
supprimer toutes ambiguïtés) on peut utiliser des
parenthèses
19
Manipulation de variables
On ne peut faire que deux choses avec une variable :
1. Obtenir son contenu
Cela s’effectue simplement en nommant la variable
2. Affecter un (nouveau) contenu
Cela s’effectue en utilisant l’opérateur d’affectation
représenter par le symbole ←
La syntaxe de cet opérateur est :
identifiant de la variable ← expression
20
Manipulation de variables
Par exemple l’expression c ← a + b se comprend de la
façon suivante :
On prend la valeur contenue dans la variable a
On prend la valeur contenue dans la variable b
On additionne ces deux valeurs
On met ce résultat dans la variable c
Si c avait auparavant une valeur, cette dernière est perdue !
21
Les entrées / sorties
Un algorithme peut avoir des interactions avec l’utilisateur
Il peut afficher un résultat (du texte ou le contenu d’une
variable)
demander à l’utilisateur de saisir une information afin
de la stocker dans une variable
En tant qu’informaticien on raisonne en se mettant “à la
place de la machine”, donc :
22
Les entrées / sorties
Instruction d'écriture
L'instruction de restitution de résultats sur le périphérique de
sortie (en général l'écran) est :
écrire(liste d'expressions)
Cette instruction réalise simplement l'affichage des valeurs
des expressions décrites dans la liste.
Ces instructions peuvent être simplement des variables ayant
des valeurs ou même des nombres ou des commentaires écrits
sous forme de chaînes de caractères.
Exemple d'utilisation : écrire(x, y+2, "bonjour") 23
Les entrées / sorties
Instructions de lecture
L'instruction de prise de données sur le périphérique d'entrée
(en général le clavier) est :
variable <- lire()
L'exécution de cette instruction consiste à affecter une valeur
à la variable en prenant cette valeur sur le périphérique
d'entrée.
Avant l'exécution de cette instruction, la variable avait ou
n'avait pas de valeur. Après, elle a la valeur prise sur le 24
périphérique d'entrée.
Les entrées / sorties
Exemple
On désire écrire un algorithme qui lit sur l'entrée standard une
valeur représentant une somme d'argent et qui calcule et affiche le
nombre de billets de 100 Euros, 50 Euros et 10 Euros, et de pièces
de 2 Euros et 1 Euro qu'elle représente.
Nom : DécompSomme.
Rôle : Décomposition d'une somme
Données : la somme à décomposée.
Résultat : les nombres de billets et de pièces.
Principe : on commence par lire sur l'entrée standard l'entier qui
représente la somme d'argent et affecte la valeur à
une variable somme.
Pour obtenir la décomposition en nombre de billets
et de pièces de la somme d'argent, on procède par
25
divisions successives en conservant chaque fois le reste.
