COURS ALGORITHMIQUE

ANNÉE UNIVERSITAIRE 2021/2022

PR. BASSMA JIOUDI

 O RG A N I S AT I O N D U C O U R S
• Introduction
• L'algorithmique
• Caractéristiques des algorithmes: Les variables, les constantes et les types de base
• Les instructions simples
• L’instruction d’affectation
• L’instruction de lecture
• L’instruction d’écriture
• Les instructions conditionnelles (les alternatives)
• Structure d’un test: Forme simple & Forme complète
• Tests imbriqués
 O RG A N I S AT I O N D U C O U R S
• Les instructions itératives (les boucles)
• L’instruction « Pour »
• L’instruction « Tant que… faire »
• L’instruction « Répéter… jusqu’à »
• Les tableaux
• Tableaux à une seule dimension
• Tableaux à deux dimensions
• Les enregistrements (structures)
• Les fonctions et les procédures
• Les pointeurs
 INTRODUCTION AUX ALGORITHMES

• Contexte
• « Informatique » est un concept (1962 par Philippe Dreyfus) pour caractériser
le traitement automatique de l’information: « information automatique ».

• Ce terme a été accepté par l’Académie française en avril 1966, et

l’informatique devient officiellement la science du traitement automatique de
l’information, où l’information est considérée comme le support des
connaissances humaines et des communications dans les domaines techniques,
économiques et sociaux.
 INTRODUCTION AUX ALGORITHMES

• Notions élémentaires
• Informatique : la science du traitement automatique de l’information. Elle traite de
deux aspects complémentaires :
o Programmes ou logiciels (software) qui décrivent un traitement à réaliser,
o Machines ou le matériel (hardware) qui exécute ce traitement.
 INTRODUCTION AUX ALGORITHMES

Algorithme
• Un algorithme est une suite ordonnée d’instructions qui indique la démarche à
suivre pour résoudre un problème ou effectuer une tâche. Le mot algorithme vient
du nom latinisé du mathématicien perse AlKhawarizmi « le père de l'algèbre ».

• Exemple : Appel téléphonique

a. Ouvrir son téléphone,

b. Chercher/Composer le numéro du destinataire,
c. Appuyer sur le bouton « Appel ». Muhammad Ibn Mūsā al-
Khuwārizmī (~780-850)
 INTRODUCTION AUX ALGORITHMES

L'algorithmique
• La science des algorithmes. Elle s’intéresse à l’art de
construire des algorithmes ainsi qu’à déterminer leur
validité, leur robustesse, leur réutilisabilité, leur complexité
ou leur efficacité.

Décrire La démarche de résolution du problème

Traduire un algorithme dans un langage « compréhensible » par l’ordinateur

Exécution automatiquement
Etapes de développement
 INTRODUCTION AUX ALGORITHMES
• L'algorithmique
Exemple : Calcul de la moyenne d’un étudiant
Supposons qu’on doit calculer la moyenne d’un étudiant pour un ensemble de
matières.

Principe du traitement automatisé

 INTRODUCTION AUX ALGORITHMES
L'algorithmique
Exemple : Calcul de la moyenne d’un étudiant
1. Définir le nombre des matières concernées ainsi que les notes et les coefficients ;
2. Réaliser les opérations suivantes :
• Multiplier chaque note d’une matière par son coefficient,
• Calculer la somme des résultats des multiplications,
• Diviser la somme obtenue par le total des coefficients,
3. Afficher le la moyenne de l’étudiant (résultat final).
 INTRODUCTION AUX ALGORITHMES

• Caractéristiques des algorithmes:

✓ Structure générale:
Un algorithme se compose généralement de deux parties :
• Partie déclarative (entête de l’algorithme): contient généralement les
déclarations (des constantes, des variables, etc.)
• Partie corps de l’algorithme : constituée d’une ou plusieurs séquences
d’instructions faisant appel à des opérations de base à exécuter par
l’ordinateur.
 INTRODUCTION AUX ALGORITHMES

• Caractéristiques des algorithmes:

✓ Structure générale:
Syntaxe:
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les variables et les constantes:
L’élément unitaire de stockage de l’information est
appelé bit (0 ou 1).
Dans la mémoire de l’ordinateur, les données sont
manipulées par groupes de 8 bits (octets), ou plus
(mots de 16, 32, 64 bits,…).
Une case mémoire est donc appelée mot et pour
que l’unité centrale puisse stocker une information
et la retrouver dans la mémoire, chaque mot est
repéré par une adresse. Organisation de la mémoire
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les variables et les constantes:
La variable (Var): Une case mémoire destiné à contenir des valeurs de type défini au
préalable (nombres, caractères, chaînes de caractères,…). Elle possède un nom, un
type, et un contenu qui peut être modifié au cours de l’exécution de l’algorithme.
La constante (Cost): Sa valeur reste inchangée tout au long du déroulement (exécution)
de l’algorithme.
Syntaxe :
Var nom_variable : type ;
Const nom_constante = valeur ;
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les variables et les constantes:
La variable (Var): Une case mémoire destiné à contenir des valeurs de type défini au
préalable (nombres, caractères, chaînes de caractères,…). Elle possède un nom, un
type, et un contenu qui peut être modifié au cours de l’exécution de l’algorithme.
La constante (Cost): Sa valeur reste inchangée tout au long du déroulement (exécution)
de l’algorithme.
Un identificateur (un nom attribué à la variable ou
Syntaxe : à la constante: lettres et de chiffres sans espaces
Var nom_variable : type ;
Un type : qui définit la nature et la taille de la
Const nom_constante = valeur ; variable
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les types de base:
Le type d’une variable définit l’ensemble des valeurs que peut prendre la variable, ainsi
que l’ensemble des opérations que l’on peut appliquer sur cette variable.
i. Type entier
C’est un type numérique représentant l’ensemble des entiers relatifs, tels que: -9, 0, 1,
31, …. Les opérations permises sur ce type sont : +, - , *, div (division entière) et mod
(modulo ou reste de la division entière). Le mot clé est : entier.
Exemple : Var x : entier ;
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les types de base:
ii. Type réel
C’est un type numérique aussi représentant l’ensemble des nombres réels, tels que : 0.25,
-1.33, 2.5 e+10,… . Les opérations permises sur ce type sont : +, -, * et /.
Le mot clé est : réel.
Exemple : Var y : réel ;
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les types de base:
iii. Type caractère
Ce type représente tous les caractères alphanumériques tels que : ′a′, ′A′, ′3′, ′%′, ′ ′, …
Les opérations supportées par ce type sont : =, ≠, <, <=, >, >=.
Le mot clé est : caractère.
Exemple : Var a : caractère ;
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les types de base:
iv. Type booléen
Ce type est utilisé dans la logique pour représenter les deux valeurs : vrai et faux.
Les opérations prises en charge sont : NON, ET, OU.
Le mot clé est : booléen.
Exemple : Var b : booléen ;
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les types de base:
iv. Chaîne de caractères
Ce type représente les mots et les phrases tels que "Algorithmique", "Cours", etc. Le mot
clé utilisé est : chaîne.
Exemple : Var c : chaîne ;
 INTRODUCTION AUX ALGORITHMES
• Caractéristiques des algorithmes:
✓ Les types de base:
Exemple :
Var x, y : entier ;
z, w : réel ;
lettre : caractère ;
nom : chaîne ;
Etat : booléen ;
Const n = 100 ;
arobase = ′@′ ;
mot = "bonjour" ;
 LES INSTRUCTIONS

Les algorithmes comportent généralement deux types d’instructions :

o Les instructions simples : qui permettent la manipulation des variables telles
que l’affectation, la lecture et l’écriture.
o Les instructions de contrôle : qui précisent l’enchainement chronologique des
instructions simples. C’est en particulier le cas des instructions conditionnelles ou
les tests.
 LES INSTRUCTIONS SIMPLES

• L’instruction d’affectation
Permet d’assigner une valeur à une variable selon la syntaxe suivante :
variable ← expression ;
Une instruction d’affectation est exécutée comme suit :
- évaluation de l’expression située à droite de l’instruction, et
- affectation du résultat à la variable située à gauche de l’instruction.
 LES INSTRUCTIONS SIMPLES

• L’instruction d’affectation
L’expression peut être :
• Une variable ( v ← x )
• Une expression arithmétique ( e ← x + y )
• Une expression logique ( d ← a ou b )
Remarque :
Une constante ne figure jamais à gauche d’une instruction d’affectation.
Exemple d’instruction fausse : Const z = 1 ; z ← 2 ; « Faux »
 LES INSTRUCTIONS SIMPLES
• L’instruction d’affectation
Remarque :
• Après une affectation, l’ancien contenu d’une variable est substitué (écrasé) par le nouveau
contenu.
Exemple : Var a : entier ;
a←1;
a←2;
• Après la deuxième affectation, la valeur de a est devenue 2 (la valeur 1 est écrasée).
Une instruction d’affectation doit se faire entre deux types compatibles.
Exemple : Var x, y : entier ; z : réel ; a, b : caractère ;
 LES INSTRUCTIONS SIMPLES
• L’instruction d’affectation
Symbole Signification
Symbole Signification
Les opérateurs arithmétiques (par ordre de priorité)
Les opérateurs de comparaison ou relationnels
^ ou ** Puissance
> , >= supérieur et supérieur ou égal
* , / , mod Multiplication, Division et Modulo
< , <= inférieur et inférieur ou égal
+,- Addition et Soustraction
= , ≠ (ou < >) égal et différent
Les opérateurs logiques ou booléens
Les opérateurs logiques ou booléens
NON Non logique (négation)
NON ET négation de conjonction
ET Et logique (conjonction)
NON OU négation de disjonction
OU Ou logique (disjonction)

Les expressions logiques peuvent être composées des opérateurs logiques et/ou relationnels.
Par exemple, (A<20) ET (B>=10) est Vrai si A est inférieur à 20 et B est égal ou supérieur à 10, et faux sinon.
 LES INSTRUCTIONS SIMPLES

• L’instruction de lecture
Cette instruction permet de lire des valeurs en entrée (input) et les affecter aux variables
stockées dans la mémoire. Les valeurs affectées sont souvent des données introduites à
partir d’un périphérique d’entrée tel que le clavier.
Syntaxe :
Lire (var1, var2,…) ;
Exemple :
Lire(x) : lit et stocke une valeur donnée
dans la case mémoire associée à x.
Lire(x, y) : lit et stocke deux valeurs, la
première dans x et la deuxième dans y.
 LES INSTRUCTIONS SIMPLES

• L’instruction d’écriture
Cette instruction permet d’écrire en sortie (output) les données résultant d’un traitement
effectué par l’algorithme (valeur, texte, …) en les affichant par exemple sur un
périphérique de sortie tel que l’écran.
Syntaxe :
Ecrire (var1, var2, expr1, expr2, …) ;
Exemple :
Calculez et affichez la moyenne:
l’utilisateur introduit 10 pour x et 20
pour y alors l’affichage sera : La
moyenne est : 15
LES INSTRUCTIONS SIMPLES

Exercices:
1. Ecrire un algorithme qui lit le prix HT d’un article, le nombre d’articles et le taux
de TVA, et qui fournit le prix total TTC correspondant.
 LES INSTRUCTIONS CONDITIONNELLES
( L E S A LT E R N AT I V E S )
• Structure d’un test
Il existe deux formes de test : forme simple (ou réduite) et forme complète.
✓ Forme simple
Une action, qui correspond à une ou plusieurs instructions, est exécuté si une
condition est vérifiée. Sinon l’algorithme passe directement au bloc d’instruction qui
suit immédiatement le bloc conditionnel.
Syntaxe :
Si (condition) Alors
instruction(s) ; // action
Finsi
 LES INSTRUCTIONS CONDITIONNELLES
( L E S A LT E R N AT I V E S )
• Structure d’un test
✓ Forme complète
Cette forme permet de choisir entre deux actions selon qu’une condition est
vérifiée ou non.
Syntaxe :
Si (condition) Alors
instruction(s) 1 ; // action1
Sinon instruction(s) 2 ; // action2
Finsi
 LES INSTRUCTIONS CONDITIONNELLES
( L E S A LT E R N AT I V E S )
• Tests imbriqués
La forme complète permet de choisir entre plusieurs actions en imbriquant des formes
simples.
Syntaxe :
Si (condition1) Alors instruction(s) 1 ;
Sinon Si (condition2) Alors instruction(s) 2 ;
Sinon Si (condition3) Alors instruction(s) 3 ;
…
Sinon instruction(s) N ;
FinSi
FinSi
FinSi
FinSi
 LES INSTRUCTIONS CONDITIONNELLES
( L E S A LT E R N AT I V E S )
• Tests imbriqués
l’utilisation de tests imbriqués permet de :
✓ Simplifier le (pseudo-) code : moins de conditions (simples ou composées).
Un algorithme (ou programme) plus simple et plus lisible.
✓ Optimiser le temps d’exécution : dans le cas où la première condition est
vérifiée, l’algorithme passe directement à la fin, sans tester le reste qui est
forcément faux.
Un algorithme (ou programme) plus performant à l’exécution.
 LES INSTRUCTIONS CONDITIONNELLES
( L E S A LT E R N AT I V E S )
• Tests imbriqués
Exemple : Etat de l’eau
Dans les conditions normales de température et de pression, l’eau est sous forme
de glace si la température est inférieure ou égale à 0° C, sous forme de liquide si
la température est comprise entre 0° C et 100° C et sous forme de vapeur au-
delà de 100° C. Ecrivons l’algorithme qui permet de vérifier l’état de l’eau selon
sa température.
 LES INSTRUCTIONS CONDITIONNELLES
( L E S A LT E R N AT I V E S )
• Les choix multiples
Il existe une autre variante d’instructions conditionnelles qui permet d’effectuer des actions
différentes suivant les différentes valeurs que peut avoir une variable.
Syntaxe :
Selon (variable)
valeur1 : instruction(s) 1 ;
valeur2 : instruction(s) 2 ;
…
valeurN : instruction(s) N ;
défaut : instruction(s) par défaut;
FinSelon ;
 LES INSTRUCTIONS CONDITIONNELLES
( L E S A LT E R N AT I V E S )

• Les choix multiples

Dans la structure de test à choix multiples :

o L’action peut être une suite d’instructions ;

o La valeur est une constante de même type que la variable ;

o La partie « défaut » est exécutée si aucun des autres cas n’est vérifié ;

o L’exécution des différents cas (y compris le cas par défaut) est exclusive:
l’exécution d’un seul cas provoque la sortie de cette structure.
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
Une boucle (ou itération) est une instruction de contrôle qui permet de répéter
plusieurs fois un ensemble d’instructions. Généralement, deux cas sont distingués :
• Le nombre de répétitions est connu.
• Le nombre des répétitions est inconnu ou variable.
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
L’instruction « Pour »
Cette structure possède un indice (compteur) de contrôle d’itérations caractérisé
par :
• une valeur initiale,
• une valeur finale,
• un pas de variation.
Syntaxe :
Pour indice de début à fin Pas valeur_du_pas
instruction(s) ;
FinPour
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
Exemple : un compteur croissant/décroissant
Les deux algorithmes suivants comptent de 1 à N et de N à 1
respectivement.
Algorithme compteur_croissant ; Algorithme compteur_decroissant ;
Var i : entier ; Var i : entier ;
Const N=100 ; Const N=100 ;
Début Début
Pour i de 1 à N /* par défaut le pas = 1 */ Pour i de N à 1 /* par défaut le pas = -1 */
Ecrire (i); Ecrire (i);
FinPour FinPour
Fin Fin
Résultat d’exécution : 1,2, 3, … , 99, 100 Résultat d’exécution : 100, 99, 98, … , 2, 1
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
L’instruction « Tant que… faire »
Cette instruction permet de tester une condition et répéter le traitement
associé tant que cette condition est vérifiée.
Syntaxe:
Tant que condition faire
instruction(s) ;
FinTq
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
L’instruction « Répéter… jusqu’à »
Dans cette instruction, un traitement est exécuté au moins une fois puis sa
répétition se poursuit jusqu’à ce que la condition soit vérifiée.
Syntaxe:
Répéter
instruction(s) ;
Jusqu’à (condition) ;
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
Exemple :
Soit l’algorithme suivant :
Var n, p : entier ;
Début
Le bloc de la boucle qu’il faut
Répéter
répéter jusqu’à ce que la condition
Ecrire ("Donner un nombre :") ;
(n=0) soit vérifiée
Lire (n) ;
p ← n*n ; Ecrire (p);
Jusqu’à (n=0)
Ecrire ("Fin de l’algorithme") ; condition d’arrêt
Fin
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
La notion du compteur
Un compteur est une variable associée à la boucle dont la valeur est
incrémentée de un à chaque itération. Elle sert à compter le nombre
d’itérations (répétitions) de la boucle.
Initialisation
du compteur
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
La notion d’accumulation
Elle est utilisée notamment pour calculer la somme d’un ensemble de valeurs.
L’instruction correspondante se présente ainsi :
variable ← variable + valeur ;
Exemple : calcul de la somme de n valeurs données par l’utilisateur
 L E S I N S T RU C T I O N S I T É R AT I V E S ( L E S
BOUCLES)
Les boucles imbriquées
Les boucles peuvent être imbriquées les unes dans les autres. Deux ou
plusieurs boucles imbriquées peuvent être aussi les mêmes ou différentes.
Exemple :
Pour i de 1 à 2 Boucle 1
Écrire ("i = ", i) ; Boucle 2
Pour j de 1 à 3 boucle 1
Écrire ("j = ", j) ; boucle 2
Finpour
Finpour