Algorithmique et structures de données I

Riadh Ben Messaoud

Université 7 novembre à Carthage

Faculté des Sciences Économiques et de Gestion de Nabeul

1ère année Licence Fondamentale IAG

1ère année Licence Appliquée IAG

Année universitaire
2009 – 2010

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 1 / 27

Syllabus du cours ...

Syllabus : http://eric.univ-lyon2.fr/~rbenmessaoud/
Objectif :
se familiariser avec les méthodes de résolution de problèmes avec l’outil informatique ;
apprendre les principes de l’algorithmique ;
acquérir un début de maı̂trise des techniques et langages de programmation.

Pré-requis : Connaissances générales en informatique utiles,

mais pas indispensables.
Organisation : 21 h de cours + 42 h de TD
Bibliographie :
Introduction à l’algorithmique, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
et Clifford Stein, Dunod, Paris, 2004.
Algorithmique Application en C, Jean-Michel Léry, Pearson Education, 2005.
Algorithmique et programmation en Java, Vincent Granet, Dunod, Paris, 2000.
Débuter en programmation, Greg Perry, CampusPress, 2003.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 2 / 27

Plan du cours

1 Introduction
2 Environnement algorithmique
3 Variables
4 Structures conditionnelles
5 Structures itératives
6 Tableaux
7 Sous-programmes
8 Mode de passage de paramètres

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 3 / 27

Variables
A quoi servent les variables ?

Dans un programme informatique, on a, en permanence, besoin de stocker

provisoirement des valeurs :
données issues du disque dur ;
données fournies par l’utilisateur (frappées au clavier) ;
résultats (intermédiaires ou définitifs) obtenus par le programme.

I Pour stocker une valeur au cours d’un programme, on utilise une variable.

Signification physique d’une variable

Dans la mémoire vive de l’ordinateur, physiquement, une variable correspond à
un emplacement de mémoire, repéré par une adresse binaire.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 4 / 27

Variables
Les types de variables

En employant une image

Une variable est un récipient, que l’ordinateur va repérer par une étiquette (un
nom). Pour avoir accès au contenu du récipient, il suffit de le désigner par son
étiquette.

Il existe plusieurs types de récipients !

I De la même manière, il existe plusieurs types de variables ...

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 5 / 27

Variables
Les types de variables

Important
Lorsqu’on déclare une variable, il ne suffit pas de créer un récipient (réserver
un emplacement mémoire). Il faut encore préciser ce que l’on voudra mettre
dedans, car de cela dépendent la taille et la nature du récipient.

Les types de variables les plus courants en algorithmique :

Type numérique
I Entier
I Réel
Type alphanumérique
I Chaı̂ne de caractères
Type booléen
I Booléen

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 6 / 27

Variables
Les types de variables

Type numérique :
I Entier :
ensemble des entiers relatifs Z ;
valeurs non décimales.
I Réel :
ensemble des nombres réels R ;
valeurs décimales.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 7 / 27

 Variables
Les types de variables

Exemple :

Algorithme Algo Exemple

Var : Prix HT : réel ; Nombre Mois : entier ;
Début
...
Prix HT ← 245,550 ‘Affectation d’une valeur réelle
Nombre Mois ← 12 ‘Affectation d’une valeur entière
...
Fin

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 8 / 27

Variables
Les types de variables

Type alphanumérique :
I Chaı̂ne de caractères :
stocke des caractères : des lettres, des signes de ponctuation, des
espaces, ou même des chiffres ;
le nombre maximal de caractères pouvant être stockés dans une
seule variable chaı̂ne de caractères dépend du langage utilisé ;
en pseudo-code (en algorithmique), une chaı̂ne de caractères est
toujours notée entre guillemets.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 9 / 27

 Variables
Les types de variables

Exemple :

Algorithme Algo Exemple

Var : Prix HT : réel ; Nombre Mois : entier ; Fournisseur : chaı̂ne ;
Début
...
Prix HT ← 245,550 ‘Affectation d’une valeur réelle
Nombre Mois ← 12 ‘Affectation d’une valeur entière
Fournisseur ← “Smith & Co” ‘Affectation d’une chaı̂ne de caractères
...
Fin

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 10 / 27

Variables
Les types de variables

Type booléen :
I Booléen :
stocke uniquement les valeurs logiques VRAI et FAUX ;
le type booléen indique la présence ou l’absence d’un caractère.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 11 / 27

 Variables
Les types de variables

Exemple :

Algorithme Algo Exemple

Var : Fournisseur : chaı̂ne ; Etranger : booléen ;
Début
...
Fournisseur ← “Smith & Co” ‘Affectation d’une chaı̂ne de caractères
Etranger ← VRAI ‘Affectation d’une valeur booléenne
...
Fin

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 12 / 27

Variables
L’instruction d’affectation

Qu’est ce qu’on peut faire avec une variable ?

Réponse
La seule chose qu’on peut faire avec une variable, c’est l’affecter, c’est-à-dire lui
attribuer une valeur.
I En reprenant l’image des récipients :

La variable ≈ Le récipient (la coupe de vin)

La valeur de la variable ≈ Le contenu du

récipient (le vin)

Convention
En pseudo-code, l’instruction d’affectation se note avec le signe ←

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 13 / 27

Variables
L’instruction d’affectation

Exemple :
Toto ← 24,5

On attribue la valeur 24,5 à la variable Toto.

I Cette affectation sous-entend que Toto est une variable de type réel ...
On ne peut pas affecter à Toto une variable de type alphanumérique ou
booléen.

On peut toujours verser dans une coupe de vin du sirop Maxilase,

sauf que ce n’est pas logique !
R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 14 / 27
Variables
L’instruction d’affectation

On peut affecter à une variable la valeur d’une autre variable.

Exemple :
Toto ← 24,5
Tutu ← Toto

I La valeur de Tutu est maintenant celle de Toto. Tutu contient donc la

valeur 24,5.
La valeur de Toto n’est pas modifiée.

Important
Une instruction d’affectation ne modifie que ce qui est situé à gauche de
l’affectation ←

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 15 / 27

Variables
L’instruction d’affectation

On peut affecter à une variable le résultat d’une opération en fonction

d’autres variables.
Exemple 1 :
Toto ← 24,5
Tutu ← Toto + 5,5

I La valeur de Tutu est maintenant égale à celle de Toto + 5,5. Tutu

contient donc la valeur 30.
La valeur de Toto n’est pas modifiée. Elle vaut toujours 24,5.

Exemple 2 :
Tutu ← Tutu + 3

I Si Tutu valait 30, il vaut maintenant 33.

La valeur de Tutu est modifiée, puisque Tutu est la variable située à
gauche de l’affectation.
R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 16 / 27
Variables
L’instruction d’affectation

Confusion possible entre le nom d’une variable et la valeur d’une variable !

Début
Riri ← “Loulou”
Fifi ← “Riri”
Fin
I Fifi contient la suite de caractères R - i - r - i.
I À la fin de l’algorithme, la variable Fifi est donc égale à “Riri”.

Début
Riri ← “Loulou”
Fifi ← Riri
Fin
I Riri, étant dépourvu de guillemets, n’est pas considéré comme une suite de
caractères, mais comme un nom de variable.
I À la fin de l’algorithme, la variable Fifi est donc égale à “Loulou”.
R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 17 / 27
Variables
L’instruction d’affectation

L’ordre des instructions joue un rôle essentiel dans le résultat final !

Var : A : entier ;
Début
A ← 34
A ← 12
Fin
I À la fin de l’algorithme, la variable A est égale à 12.

Var : A : entier ;
Début
A ← 12
A ← 34
Fin
I À la fin de l’algorithme, la variable A est égale à 34.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 18 / 27

Variables
Les expressions et les opérateurs

Une instruction d’affectation doit respecter trois conditions :

à gauche de l’affectation, on doit trouver un nom de variable, et
uniquement cela. Dans le cas contraire, il s’agit certainement d’une
erreur !
à droite de l’affectation, on doit trouver une expression ;
l’expression (située à droite de l’affectation) doit être du même type que la
variable (située à gauche de l’affectation).

Définition d’une expression

Une expression est un ensemble de valeurs, reliées par des opérateurs, et
équivalent à une seule valeur.

Exemple d’expressions de type numérique :

A←7
B←5+4
C ← 123 – 45 + 844
D ← Toto – 12 + 5 – Riri
R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 19 / 27
Variables
Les expressions et les opérateurs

Définition d’un opérateur

Un opérateur est un signe qui relie deux valeurs, pour produire un résultat.

Les opérateurs possibles dépendent du type des valeurs qui sont en jeu :

Opérateurs numériques
Opérateur alphanumérique
Opérateurs logiques

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 20 / 27

Variables
Les expressions et les opérateurs

Opérateurs numériques :
+ : l’addition ;
– : la soustraction ;
* : la multiplication ;
/ : la division ;
∧
: la puissance.

I On peut utiliser les parenthèses. La multiplication et la division ont

naturellement la priorité sur l’addition et la soustraction.
I Les parenthèses ne sont ainsi utiles que pour modifier cette priorité naturelle.
Exemple :
A ← 12 * 3 + 5
B ← (12 * 3) + 5 ‘A et B valent 41
C ← 12 * (3 + 5) ‘C vaut 12 * 8, soit 96

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 21 / 27

Variables
Les expressions et les opérateurs

Opérateur alphanumérique :
& : la concaténation.

I Cet opérateur permet de concaténer (agglomérer) deux chaı̂nes de

caractères.
Exemple :
A ← “Buvons”
B ← “ un coup”
C←A&B ‘C vaut “Buvons un coup”

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 22 / 27

Variables
Les expressions et les opérateurs

Opérateurs logiques :
ET : la conjonction ;
OU : la disjonction ;
NON : la négation.

I À garder sous le coude pour le moment. Nous y reviendrons une autre fois !

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 23 / 27

 Variables
La lecture et l’écriture

Algorithme Carre De Douze

Var : A : entier ;
Début
∧
A ← 12 2
Fin

1 Pour calculer le carré d’un autre nombre que 12, il faut réécrire le
programme.
2 L’utilisateur ne saura jamais le résultat. La machine le garde pour elle.

I Il existe des instructions pour permettre à la machine de dialoguer avec

l’utilisateur.
I Instruction de lecture et instruction d’écriture.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 24 / 27

Variables
La lecture et l’écriture

Instruction de lecture
Une instruction de lecture permet à l’utilisateur de rentrer des valeurs au
clavier pour qu’elles soient utilisées par le programme.

Exemple : pour que l’utilisateur entre une nouvelle valeur d’une variable Titi :

Lire (Titi)

Lire (“Donnez la valeur de Titi” ; Titi)

Remarque
Dès que le programme rencontre une instruction Lire, l’exécution s’interrompt
et attend la frappe d’une valeur au clavier.

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 25 / 27

Variables
La lecture et l’écriture

Instruction d’écriture
Une instruction d’écriture permet au programme de communiquer des valeurs
à l’utilisateur en les affichant à l’écran.

Exemple : pour que le programme affiche à l’utilisateur la valeur d’une variable

Toto :

Ecrire (“La valeur de Toto est :” ; Toto)

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 26 / 27

Plan du cours

1 Introduction
2 Environnement algorithmique
3 Variables
4 Structures conditionnelles
5 Structures itératives
6 Tableaux
7 Sous-programmes
8 Mode de passage de paramètres

R. Ben Messaoud (FSEGN) Algorithmique I 2009 – 2010 27 / 27