Ecole Nationale des Sciences Appliquées de Tétouan

Algorithmique

Pr. Oussama ELHAJJAMY

Email : [email protected]
2019/2020

09/06/2019 Oussama ELHAJJAMY 1

 CHAPITRE I
Notion d'Algorithme et de Programme
Notion d'Algorithme et de Programme

• Algorithmique

Le terme algorithme vient du nom du mathématicien arabe Al-Khawarizmi (820

après J.C.)

Un algorithme est un ensemble d'actions (ou d'instructions) séquentielles et

logiquement ordonnées, permettant de transformer des données en entrée
(Inputs) en données de sorties (outputs ou les résultats), afin de résoudre un
problème.

Une fois l'algorithme est écrit (avec n'importe quelle langues : français, anglais,
arabe, etc.), il sera transformé, après avoir choisi un langage de programmation,
en un programme code source qui sera compilé (traduit) et exécuté par
l'ordinateur.

09/06/2019 Oussama ELHAJJAMY 3

Notion d'Algorithme et de Programme

• Etapes de réalisation d’un programme

Enoncé du problème
Spécification
Cahier des charges
Analyse
Algorithme
Traduction en langage
Programme source
Compilation
Programme exécutable
Tests et modifications
Version finale et résultats

La réalisation de programmes passe par l’écriture d’algorithmes

 D’où l’intérêt de l’Algorithmique

09/06/2019 Oussama ELHAJJAMY 4

Notion d'Algorithme et de Programme

• Données : Entrées-Sorties

Données

Données d’Entrée Données

(Inputs) Données de Sortie Intermédiaires
(Outputs)
Les données que Les données utilisées
l’utilisateur doit Les données que par l’algorithme pour
fournir à l’algorithme l’algorithme doit le traitement lié au
montrer à l’utilisateur problème
(Solution du problème)

09/06/2019 Oussama ELHAJJAMY 5

 Notion d'Algorithme et de Programme

• Vue Globale d’un Algorithme

Données d’Entrée Instructions
(Inputs) des entrées

Traitements Données
Algorithme (Instructions) Intermédiaires
Données + Instructions

Données de Sortie Instructions

(Outputs) dess orties

09/06/2019 Oussama ELHAJJAMY 6

Notion d'Algorithme et de Programme

• Structure d’un Algorithme

Algorithme
Données + Instructions

Entête Déclarations Corps (Instructions)

Permet d’identifier La parties des

On déclare toutes les
l’algorithme avec un instructions (Entrées,
données (Variables et
nom unique Traitements et
Constantes)
(Identificateur) Sorties)

09/06/2019 Oussama ELHAJJAMY 7

Notion d'Algorithme et de Programme

• Structure d’un Algorithme

Modèle d’écriture d’un Algorithme

Algorithme <ident_Algo>
<Déclarations>
Début
<instructions>
Fin

09/06/2019 Oussama ELHAJJAMY 8

Notion d'Algorithme et de Programme

• Structure d’un Algorithme

Exemple :
Algorithme Max_Deux_Nbre
Variables A, B : entier
Début
Lire(A)
Lire(B)
Si (B < A)
Ecrire("A est plus grand que B")
Sinon
Ecrire("B est plus grand que A")
Fin Si
Fin

09/06/2019 Oussama ELHAJJAMY 9

Notion d'Algorithme et de Programme

• Données : Variables & Constantes

Une donnée représente une information liée à un élément du problème traité par
l’algorithme.
Sert à stocker la valeur d’une donnée.
Variable Désigne en fait un emplacement mémoire
dont le contenu peut changer au cours d’un
programme

Données

C’est un objet contenant une valeur fixe (ne

Constante peut jamais être modifié).

09/06/2019 Oussama ELHAJJAMY 10

Notion d'Algorithme et de Programme

• Données : Identificateur
Chaque donnée (Variable ou Constante) manipulée par un algorithme est
désignées par un nom unique appelé IDENTIFICATEUR.
Identificateur : est soumis à quelques règles qui varient selon le langage, mais en
général:
 Un nom doit commencer par une lettre alphabétique
exemple valide: A1 exemple invalide: 1A
 doit être constitué uniquement de lettres, de chiffres et du soulignement _
(Eviter les caractères de ponctuation et les espaces)
valides: ENSA2019, ENSA_2019 invalides: ENSA 2019, ENSA;2019
 doit être différent des mots réservés du langage (par exemple en Java: int,
float, else, switch, case, default, for, main, return, …)
 La longueur du nom doit être inférieure à la taille maximale spécifiée par le
langage utilisé

09/06/2019 Oussama ELHAJJAMY 11

Notion d'Algorithme et de Programme

• Données : Identificateur

Conseil: pour la lisibilité du code choisir des noms significatifs qui décrivent les
données manipulées
exemples: TotalVentes2004, Prix_TTC, Prix_HT

Remarque :
Même l’algorithme lui-même possède un nom unique (identificateur)
Un identificateur est affecté à un seul objet . On peut jamais utiliser le même
identificateur pour deux variables ou constantes différentes .

09/06/2019 Oussama ELHAJJAMY 12

Notion d'Algorithme et de Programme

• Types des variables

Le type d’une variable détermine l’ensemble des valeurs qu’elle peut prendre, les
types offerts par la plus part des langages sont:
• Type numérique (entier ou réel)
– Byte (codé sur 1octet): de 0 à 255
– Entier court (codé sur 2 octets) : -32 768 à 32 767
– Entier long (codé sur 4 ou 8 octets)
– Réel simple précision (codé sur 4 octets)
– Réel double précision (codé sur 8 octets)
• Type logique ou booléen: deux valeurs VRAI ou FAUX

• Type caractère: lettres majuscules, minuscules, chiffres, symboles, …

exemples: ’A’, ’a’, ’1’, ’?’, …
• Type chaîne de caractère: toute suite de caractères,
exemples: " Nom, Prénom", "code postale: 1000", …

09/06/2019 Oussama ELHAJJAMY 13

Notion d'Algorithme et de Programme

• Déclaration des variables

 toute variable utilisée dans un programme doit avoir fait l’objet d’une
déclaration préalable
 En pseudo-code, on va adopter la forme suivante pour la déclaration de
variables
Variables liste d'identificateurs : type
• Exemple:
Variables i, j,k : entier
x, y : réel
OK: booléen
ch1, ch2 : chaîne de caractères

09/06/2019 Oussama ELHAJJAMY 14

Notion d'Algorithme et de Programme

• Types d’instructions
 Pour les entrées , on utilise l’instruction de lecture.
 Pour les sorties, on utilise l’instructions d’écriture.
 Pour les traitements, plusieurs Instructions :
 L’instruction d’affectation
 L’instruction de tests (conditionnelles )
 Les instructions de boucles (de répétition)
 Les instructions de sauts (ou de branchements)
Remarques
 Les instructions des entrées de sorties et d’affectation sont séquentielles. Leurs
exécution permet automatiquement de passer à l’instruction suivante
 Les instructions de tests de boucles et sauts ne sont pas séquentielles

09/06/2019 Oussama ELHAJJAMY 15

Notion d'Algorithme et de Programme

• Les instructions d'entrées-sorties: lecture et écriture

Les instructions de lecture et d'écriture permettent à la machine de

communiquer avec l'utilisateur

La lecture permet d'entrer des donnés à partir du clavier

– En pseudo-code, on note: lire (var)

la machine met la valeur entrée au clavier
dans la zone mémoire nommée var

– Remarque: Le programme s'arrête lorsqu'il rencontre une instruction

Lire et ne se poursuit qu'après la frappe d’une valeur au clavier et de la
touche Entrée

09/06/2019 Oussama ELHAJJAMY 16

Notion d'Algorithme et de Programme

• Les instructions d'entrées-sorties: lecture et écriture

L'écriture permet d'afficher des résultats (valeur fixe, valeur d’une variable ou
une valeur calculé) à l'écran (ou de les écrire dans un fichier)

– En pseudo-code, on note: écrire (var | val_fixe | expr)

la machine affiche le contenu de la
zone mémoire var

– Conseil: Avant de lire une variable, il est fortement conseillé d’écrire des
messages à l’écran, afin de prévenir l’utilisateur de ce qu’il doit frapper

09/06/2019 Oussama ELHAJJAMY 17

Notion d'Algorithme et de Programme

• Les instructions d'entrées-sorties: lecture et écriture

Exemple 1: Ecrire un algorithme qui demande un nombre entier à l'utilisateur,

puis qui calcule et affiche le double de ce nombre
Algorithme Calcul_double
variables A, B : entier
Début
écrire("entrer le nombre ")
lire(A)
B ← 2*A
écrire("le double de ", A, "est :", B)
Fin

09/06/2019 Oussama ELHAJJAMY 18

Notion d'Algorithme et de Programme

• Les instructions d'entrées-sorties: lecture et écriture

Exemple 2: Ecrire un algorithme qui vous demande de saisir votre nom puis
votre prénom et qui affiche ensuite votre nom complet
Algorithme AffichageNomComplet
variables Nom, Prenom, Nom_Complet : chaîne de caractères
Début
écrire("entrez votre nom")
lire(Nom)
écrire("entrez votre prénom")
lire(Prenom)
Nom_Complet ← Nom & Prenom
écrire("Votre nom complet est : ", Nom_Complet)
Fin

09/06/2019 Oussama ELHAJJAMY 19

Notion d'Algorithme et de Programme

• L’instruction d’affectation
L’affectation consiste à attribuer une valeur à une variable (ça consiste en fait à remplir
où à modifier le contenu d'une zone mémoire)
En pseudo-code, l'affectation se note avec le signe ←
Var← e: attribue la valeur de e à la variable Var

- e peut être une valeur, une autre variable ou une expression

- Var et e doivent être de même type ou de types compatibles
- l’affectation ne modifie que ce qui est à gauche de la flèche

• Ex valides: i ←1 j ←i k ←i+j
x ←10.3 OK ←FAUX ch1 ←"SMI"
ch2 ←ch1 x ←4 x ←j
(voir la déclaration des variables dans le transparent précédent)
• non valides: i ←10.3 OK ←"2AP" j ←x
09/06/2019 Oussama ELHAJJAMY 20
Notion d'Algorithme et de Programme

• L’instruction d’affectation

Quelques remarques
• Beaucoup de langages de programmation (C/C++, Java, …) utilisent le signe
égal = pour l’affectation ←. Attention aux confusions:

– l'affectation n'est pas commutative : A=B est différente de B=A

– l'affectation est différente d'une équation mathématique :

• A=A+1 a un sens en langages de programmation

• A+1=2 n'est pas possible en langages de programmation et n'est pas
équivalente à A=1

• Certains langages donnent des valeurs par défaut aux variables déclarées. Pour
éviter tout problème il est préférable d'initialiser les variables déclarées
09/06/2019 Oussama ELHAJJAMY 21
Notion d'Algorithme et de Programme

• L’instruction d’affectation

Exemple 1:
Donnez les valeurs des variables A, B et C après exécution des instructions
suivantes ?
Variables A, B, C: Entier
Début
A←3
B←7
A←B
B ← A+5
C←A+B
C←B–A
Fin

09/06/2019 Oussama ELHAJJAMY 22

Notion d'Algorithme et de Programme

• L’instruction d’affectation

Exemple 2:
Donnez les valeurs des variables A et B après exécution des instructions
suivantes ?
Variables A, B : Entier
Début
A←1
B←2
A←B
B←A
Fin
Les deux dernières instructions permettent-elles d’échanger les valeurs de A et B ?

09/06/2019 Oussama ELHAJJAMY 23

Notion d'Algorithme et de Programme

• L’instruction d’affectation

Exercice simple sur l'affectation :

Ecrire un algorithme permettant d’échanger les valeurs de deux variables A et B

09/06/2019 Oussama ELHAJJAMY 24

Notion d'Algorithme et de Programme

• Expressions et opérateurs

Une expression peut être une valeur, une variable ou une opération constituée
de variables reliées par des opérateurs
exemples: 1, b, a*2, a+ 3*b-c, …

L'évaluation de l'expression fournit une valeur unique qui est le résultat de

l'opération.

Les opérateurs dépendent du type de l'opération, ils peuvent être :

– des opérateurs arithmétiques: +, -, *, /, % (modulo), ^ (puissance)
– des opérateurs logiques: NON, OU, ET
– des opérateurs relationnels: =, , <, >, <=, >=
– des opérateurs sur les chaînes: & (concaténation)
Une expression est évaluée de gauche à droite mais en tenant compte de priorités
09/06/2019 Oussama ELHAJJAMY 25
Notion d'Algorithme et de Programme

• Priorité des opérateurs

Pour les opérateurs arithmétiques donnés ci-dessus, l'ordre de priorité est le

suivant (du plus prioritaire au moins prioritaire) :

– ^ : (élévation à la puissance)
– * , / (multiplication, division)
– % (modulo)
– + , - (addition, soustraction)
exemple: 2+3*7 vaut 23

En cas de besoin (ou de doute), on utilise les parenthèses pour indiquer les
opérations à effectuer en priorité
exemple: (2 + 3) * 7 vaut 35

09/06/2019 Oussama ELHAJJAMY 26

Notion d'Algorithme et de Programme

• Tests: instructions conditionnelles

• Les instructions conditionnelles servent à n'exécuter une instruction ou une

séquence d'instructions que si une condition est vérifiée
• On utilisera la forme suivante: Si condition alors
instruction ou suite d'instructions1
Sinon
instruction ou suite d'instructions2
Finsi
– la condition ne peut être que vraie ou fausse
– si la condition est vraie, se sont les instructions1 qui seront exécutées
– si la condition est fausse, se sont les instructions2 qui seront exécutées
– la condition peut être une condition simple ou une condition composée de
plusieurs conditions
09/06/2019 Oussama ELHAJJAMY 27
Notion d'Algorithme et de Programme

• Tests: instructions conditionnelles

La partie Sinon n'est pas obligatoire, quand elle n'existe pas et que la condition est
fausse, aucun traitement n'est réalisé

On utilisera dans ce cas la forme simplifiée suivante:

Si condition alors
instruction ou suite d'instructions1
Finsi

09/06/2019 Oussama ELHAJJAMY 28

Notion d'Algorithme et de Programme

• Tests: instructions conditionnelles

Exemple (version1):
Algorithme AffichageValeurAbsolue
Variable x : réel
Début Ecrire (" Entrez un réel : “)
Lire (x)
Si (x < 0) alors
Ecrire ("la valeur absolue de ", x, "est:",-x)
Sinon
Ecrire ("la valeur absolue de ", x, "est:",x)
Finsi
Fin

09/06/2019 Oussama ELHAJJAMY 29

Notion d'Algorithme et de Programme

• Tests: instructions conditionnelles

Exemple (version 2):
Algorithme AffichageValeurAbsolue
Variable x,y : réel
Début
Ecrire (" Entrez un réel : “)
Lire (x)
y← x
Si (x < 0) alors
y ← -x
Finsi
Ecrire ("la valeur absolue de ", x, "est:",y)
Fin

09/06/2019 Oussama ELHAJJAMY 30

Notion d'Algorithme et de Programme

• Tests: instructions conditionnelles

Exemple 3:
Ecrire un algorithme qui demande un nombre entier à l'utilisateur, puis qui teste
et affiche s'il est divisible par 3
Algorithme Divsible_par3
Variable n : entier
Début
Ecrire (" Entrez un entier : ")
Lire (n)
Si (n%3=0) alors
Ecrire (n," est divisible par 3")
Sinon
Ecrire (n," n'est pas divisible par 3")
Finsi
Fin

09/06/2019 Oussama ELHAJJAMY 31

Notion d'Algorithme et de Programme

• Conditions composées

Une condition composée est une condition formée de plusieurs conditions

simples reliées par des opérateurs logiques:
ET, OU, OU exclusif (XOR) et NON
Exemples :
x compris entre 2 et 6 : (x > 2) ET (x < 6)
n divisible par 3 ou par 2 : (n%3=0) OU (n%2=0)
deux valeurs et deux seulement sont identiques parmi a, b et c :
(a=b) XOR (a=c) XOR (b=c)

09/06/2019 Oussama ELHAJJAMY 32

Notion d'Algorithme et de Programme

• Conditions composées
C1 C2 C1 ET C2 C1 C2 C1 OU C2
VRAI VRAI VRAI VRAI VRAI VRAI
VRAI FAUX FAUX VRAI FAUX VRAI
FAUX VRAI FAUX FAUX VRAI VRAI
FAUX FAUX FAUX FAUX FAUX FAUX

C1 C2 C1 XOR C2 C1 NON C1
VRAI VRAI FAUX VRAI FAUX
VRAI FAUX VRAI FAUX VRAI
FAUX VRAI VRAI
FAUX FAUX FAUX

09/06/2019 Oussama ELHAJJAMY 33

Notion d'Algorithme et de Programme

• Tests imbriqués
Les tests peuvent avoir un degré quelconque d'imbrications
Si condition1 alors
Si condition2 alors
instructionsA
Sinon
instructionsB
Finsi
Sinon
Si condition3 alors
instructionsC
Finsi
Finsi

09/06/2019 Oussama ELHAJJAMY 34

Notion d'Algorithme et de Programme

• Tests imbriqués
Exemple (version 1) :
Algorithme test_Nombre
Variable n : entier
Début
Ecrire ("entrez un nombre : ")
Lire (n)
Si (n < 0) alors
Ecrire ("Ce nombre est négatif")
Sinon
Si (n = 0) alors
Ecrire ("Ce nombre est nul")
Sinon
Ecrire ("Ce nombre est positif")
Finsi
Finsi
Fin
09/06/2019 Oussama ELHAJJAMY 35
Notion d'Algorithme et de Programme

• Tests imbriqués
Exemple (version 2) :
Algorithme test_Nombre
Variable n : entier
Début Remarque : dans la version 2 on fait trois
Ecrire ("entrez un nombre : ") tests systématiquement alors que dans la
Lire (n) version 1, si le nombre est négatif on ne
Si (n < 0) alors fait qu'un seul test
Ecrire ("Ce nombre est négatif")
Finsi
Si (n = 0) alors
Ecrire ("Ce nombre est nul") Conseil : utiliser les tests imbriqués pour
Finsi limiter le nombre de tests et placer
Si (n > 0) alors d'abord les conditions les plus probables
Ecrire ("Ce nombre est positif")
Finsi
Fin

09/06/2019 Oussama ELHAJJAMY 36

Notion d'Algorithme et de Programme

• Instructions itératives: les boucles

Dans certaine situation. On est amener à répéter l’exécution d’une ou plusieurs

instructions.

Algorithme Exemple1

Début
Ecrire(1)
Ecrire(2)
Ecrire(3)
Ecrire(4)
Ecrire(5)
Fin

Ecrire un algorithme qui affiche les nombres de 1 à 10000 ?

09/06/2019 Oussama ELHAJJAMY 37

Notion d'Algorithme et de Programme

• Instructions itératives: les boucles

Les boucles servent à répéter l'exécution d'un groupe d'instructions un certain

nombre de fois
On distingue trois sortes de boucles en langages de programmation :
 Les boucles tant que : on y répète des instructions tant qu'une certaine
condition est réalisée
 Les boucles de répéter – jusqu’à : on y répète des instructions jusqu'à ce
qu'une certaine condition soit réalisée
 Les boucles pour ou avec compteur : on y répète des instructions en faisant
évoluer un compteur (variable particulière) entre une valeur initiale et une
valeur finale

09/06/2019 Oussama ELHAJJAMY 38

Notion d'Algorithme et de Programme

• Les boucles Pour

L’instruction de boucle pour permet de répéter l’exécution d’un bloc

d’instructions. Elle utilise un compteur d’itération, une valeur initiale et une valeur
finale du compteur. Le compteur est incrémenté automatiquement.

Pour compteur allant de initiale à finale Faire

instructions
FinPour i ←initiale

i n'a pas atteint finale Vrai instructions i ← i + pas

Faux

09/06/2019 Oussama ELHAJJAMY 39

Notion d'Algorithme et de Programme

• Les boucles Pour

Remarque : le nombre d'itérations dans une boucle Pour est connu avant le début
de la boucle

Compteur est une variable de type entier (ou caractère). Elle doit être déclarée

Pas est un entier qui peut être positif ou négatif. Pas peut ne pas être mentionné,
car par défaut sa valeur est égal à 1. Dans ce cas, le nombre d'itérations est égal à
finale - initiale+ 1

Initiale et finale peuvent être des valeurs, des variables définies avant le début de
la boucle ou des expressions de même type que compteur

09/06/2019 Oussama ELHAJJAMY 40

Notion d'Algorithme et de Programme

• Les boucles Pour

1) La valeur initiale est affectée à la variable compteur

2) On compare la valeur du compteur et la valeur de finale :
a) Si la valeur du compteur est > à la valeur finale dans le cas d'un pas positif
(ou si compteur est < à finale pour un pas négatif), on sort de la boucle et
on continue avec l'instruction qui suit FinPour
b) Si compteur est <= à finale dans le cas d'un pas positif (ou si compteur est
>= à finale pour un pas négatif), instructions seront exécutées
i. Ensuite, la valeur de compteur est incrémentée de la valeur du pas si
pas est positif (ou décrémenté si pas est négatif)
ii. On recommence l'étape 2 : La comparaison entre compteur et finale
est de nouveau effectuée, et ainsi de suite …

09/06/2019 Oussama ELHAJJAMY 41

Notion d'Algorithme et de Programme

• Les boucles Pour

Exemple :
Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul
Variables x, puiss : réel
n, i : entier
Début
Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss ← 1
Pour i allant de 1 à n Faire
puiss← puiss*x
FinPour
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin
09/06/2019 Oussama ELHAJJAMY 42
Notion d'Algorithme et de Programme

• Les boucles Pour

Exemple :
Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul
(version 2 avec un pas négatif)
Variables x, puiss : réel
n, i : entier
Début
Ecrire (" Entrez respectivement les valeurs de x et n ")
Lire (x, n)
puiss ← 1
Pour i allant de n à 1 (par pas -1 ) Faire
puiss← puiss*x
FinPour
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin

09/06/2019 Oussama ELHAJJAMY 43

Notion d'Algorithme et de Programme

• Les boucles Pour

Il faut éviter de modifier la valeur du compteur (et de finale) à l'intérieur de la

boucle. En effet, une telle action :
 perturbe le nombre d'itérations prévu par la boucle Pour
 rend difficile la lecture de l'algorithme
 présente le risque d'aboutir à une boucle infinie

Exemple : Pour i allant de 1 à 5 Faire

i ← i -1
écrire(" i = ", i)
FinPour

09/06/2019 Oussama ELHAJJAMY 44

Notion d'Algorithme et de Programme

• Les boucles Pour

Quant-est-ce que nous utiliserons l’instruction de boucle pour?

Dans toute formule mathématique qui utilise un ou plusieurs indices. Comme par
exemple les sommes, les vecteurs, les matrices … .
Exemple :
S = 1/2 + 2/3 + 3/4 + ……… + n/(n+1)
T[1]  1*2 T[2]  2*3 T[1]  3*4 T[1]  4*5

En générale, si le nombre d’itérations (de répétitions) est connu (par exemple Nb).
On peut utiliser la boucle Pour.

09/06/2019 Oussama ELHAJJAMY 45

Notion d'Algorithme et de Programme

• Les boucles Tant que

TantQue (condition)
instructions condition Vrai instructions

FinTantQue
Faux

• la condition (dite condition de contrôle de la boucle) est évaluée avant chaque

itération
• si la condition est vraie, on exécute instructions (corps de la boucle), puis, on
retourne tester la condition. Si elle est encore vraie, on répète l'exécution, …
• si la condition est fausse, on sort de la boucle et on exécute l'instruction qui
est après FinTantQue

09/06/2019 Oussama ELHAJJAMY 46

Notion d'Algorithme et de Programme

• Les boucles Tant que

Le nombre d'itérations dans une boucle TantQue n'est pas connu au moment
d'entrée dans la boucle. Il dépend de l'évolution de la valeur de condition
Une des instructions du corps de la boucle doit absolument changer la valeur de
condition de vrai à faux (après un certain nombre d'itérations), sinon le
programme tourne infiniment
Attention aux boucles infinies
Exemple de boucle infinie :
i←2
TantQue (i > 0) Faire
i ← i+1 (attention aux erreurs de frappe : + au lieu de -)
FinTantQue

09/06/2019 Oussama ELHAJJAMY 47

Notion d'Algorithme et de Programme

• Les boucles Tant que

Exemple (version 1) :
Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à
N dépasse strictement 100
Algorithme Somme_Entier-Inf100
Variables som, i : entier
Début
i←0
som← 0
TantQue (som <=100) Faire
i ← i+1
som ← som+i
FinTantQue
Ecrire (" La valeur cherchée est N= ", i)
Fin

09/06/2019 Oussama ELHAJJAMY 48

Notion d'Algorithme et de Programme

• Les boucles Tant que

Exemple (version 2) :
Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à
N dépasse strictement 100
Algorithme Somme_Entier-Inf100
Variables som, i : entier
Début
som ← 0
i←1
TantQue (som <=100)
som ← som + i
i ← i+1
FinTantQue
Ecrire (" La valeur cherchée est N= ", i-1)
Fin

09/06/2019 Oussama ELHAJJAMY 49

Notion d'Algorithme et de Programme

• Les boucles Tant que

Quant-est-ce que nous utiliserons l’instruction de boucle TantQue?

 Dans tous les cas où la boucle Pour est appliquée, nous pouvons utiliser la
boucle TantQue.
 Si la boucle dépend d’une condition compliquée (expression booléenne avec
opérateurs logiques par exemple : a <> 0 et b <= n).
 Il faut s’assurer de l’initialisation de la condition et s’assurer qu’il y a une
instruction qui rend la condition fausse après un certain nombre d’itérations.

09/06/2019 Oussama ELHAJJAMY 50

Notion d'Algorithme et de Programme

• Lien entre pour et TantQue

La boucle Pour est un cas particulier de Tant Que (cas où le nombre d'itérations
est connu et fixé) . Tout ce qu'on peut écrire avec Pour peut être remplacé avec
TantQue (la réciproque est fausse)

Pour compteur allant de initiale à finale par pas valeur du pas

instructions

FinPour
peut être remplacé par : compteur ← initiale
(cas d'un pas positif) TantQue compteur <= finale
instructions
compteur ← compteur+pas
FinTantQue

09/06/2019 Oussama ELHAJJAMY 51

Notion d'Algorithme et de Programme

• Lien entre pour et TantQue

Exemple: Calcul de x à la puissance n où x est un réel non nul et n un entier positif
ou nul (version avec TantQue)
Variables x, puiss : réel
n, i : entier
Debut
Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss ← 1
i←1
TantQue (i<=n)
puiss← puiss*x
i ← i+1
FinTantQue
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin
09/06/2019 Oussama ELHAJJAMY 52
Notion d'Algorithme et de Programme

• Boucles imbriquées

Les instructions d'une boucle peuvent être des instructions itératives. Dans ce cas,
on aboutit à des boucles imbriquées

Exemple: Exécution
Pour i allant de 1 à 5 Faire OX
Pour j allant de 1 à i OOX
écrire("O") OOOX
FinPour OOOOX
écrire("X") OOOOOX
FinPour

09/06/2019 Oussama ELHAJJAMY 53

Notion d'Algorithme et de Programme

• Les boucles Répéter … jusqu’à …

instructions
Répéter

instructions
Faux
Jusqu'à condition condition

Vrai
L’instruction de boucle Répéter permet de répéter l’exécution d’une bloc
d’instructions. A chaque itération une expression booléenne (condition) est
réévaluée :
Si l’expression est True, donc on arrête la boucle et on exécute l’instruction qui
vient après Répéter.
Si l’expression est False, on continue la boucle en exécutant l’itération suivante.

09/06/2019 Oussama ELHAJJAMY 54

Notion d'Algorithme et de Programme

• Les boucles Répéter … jusqu’à …

Exemple : Un algorithme qui détermine le premier nombre entier N tel que la
somme de 1 à N dépasse strictement 100 (version avec répéter jusqu'à)
Variables som, i : entier
Debut
som ← 0
i←0
Répéter
i ← i+1
som ← som+i
Jusqu'à ( som > 100)
Ecrire (" La valeur cherchée est N= ", i)
Fin

09/06/2019 Oussama ELHAJJAMY 55

Notion d'Algorithme et de Programme

• Les boucles Répéter … jusqu’à …

Quant-est-ce que nous utiliserons l’instruction de boucle Répéter?

 Dans tous les cas où la boucle Pour est appliquée, nous pouvons utiliser la
boucle Répéter.
 Si la boucle dépend d’une condition compliquée (expression booléenne avec
opérateur logiques par exemple: a<>0 et b<=n).
 En général, si la première itération est réalisée sans condition. On peut utiliser
l’instruction Répéter au lieu de l’instruction TantQue.

09/06/2019 Oussama ELHAJJAMY 56

Notion d'Algorithme et de Programme

• Choix d'un type de boucle

Si on peut déterminer le nombre d'itérations avant l'exécution de la boucle, il est

plus naturel d'utiliser la boucle Pour

S'il n'est pas possible de connaître le nombre d'itérations avant l'exécution de la

boucle, on fera appel à l'une des boucles TantQue ou répéter jusqu'à

Pour le choix entre TantQue et répéter jusqu'à :

 Si on doit tester la condition de contrôle avant de commencer les instructions
de la boucle, on utilisera TantQue
 Si la valeur de la condition de contrôle dépend d'une première exécution des
instructions de la boucle, on utilisera répéter jusqu'à

09/06/2019 Oussama ELHAJJAMY 57

CHAPITRE II
Les Tableaux
Les tableaux

• Exemple introductif
Supposons qu'on veut conserver les notes d'une classe de 200 étudiants pour
extraire quelques informations. Par exemple : le nombre d'étudiants ayant une
note supérieure à 10.
Le seul moyen dont nous disposons actuellement consiste à déclarer 200
variables, par exemple N1, …, N200. Après 200 instructions lire, on doit écrire 200
instructions Si pour faire le calcul.
nbre ← 0
Si (N1 >10) alors nbre ←nbre+1 FinSi
….
Si (N200>10) alors nbre ←nbre+1 FinSi
c'est lourd à écrire
Heureusement, les langages de programmation offrent la possibilité de rassembler toutes
ces variables dans une seule structure de donnée appelée tableau

09/06/2019 Oussama ELHAJJAMY 59

Les tableaux

• Définition

 Type Tableau permet au programme d’allouer (de réserver) un espace

mémoire (dans la RAM) pour stocker N valeurs de même type.

 Un tableau est un ensemble de variables.

 Chaque variable du tableau représente un élément de ce dernier.

 Ces éléments (cases du tableau) sont accessibles par un (ou plusieurs)

indice(s).

 Un indice permet d'indiquer la position d'un élément donné au sein du tableau

et de déterminer sa valeur

09/06/2019 Oussama ELHAJJAMY 60

Les tableaux

• Définition

Tableaux à 1 dimension (Vecteurs)

Pour traiter les problèmes nécessitant une
représentation vectorielle des données.
On utilise un seul indice pour accéder à une
Tableaux valeur du Vecteur

Tableaux à 2 dimension (Matrices)

Problèmes nécessitant une représentation
matricielle des données.
On utilise un deux indices pour accéder à
une valeur de la matrice

09/06/2019 Oussama ELHAJJAMY 61

Les tableaux

• Tableaux à une dimension : Syntaxe & sémantique

 La déclaration d'un tableau s'effectue en précisant le type de ses éléments et

sa dimension (le nombre de ses éléments).
En pseudo code :
variables tableau identificateur[dimension] : type
Exemple :
variables tableau notes[200] : réel

On peut définir des tableaux de tous types : tableaux d'entiers, de réels, de

caractères, de booléens, de chaînes de caractères.

09/06/2019 Oussama ELHAJJAMY 62

Les tableaux

• Tableaux à une dimension :

Taille maximale
RAM Taille à utiliser du valeur
pour le tableau

1 2 3 n 49 50
T = t1 t2 t3 ………. tn …….. t49 t50

Si on veut mettre la valeur (-15) dans la casa N°3 du tableau T :

T[3]  -15

09/06/2019 Oussama ELHAJJAMY 63

Les tableaux

• Tableaux à une dimension : remarques

 L'accès à un élément du tableau se fait au moyen de l'indice. Par exemple, notes[i]
donne la valeur de l'élément i du tableau notes.
 Selon les langages, le premier indice du tableau est soit 0, soit 1. Le plus souvent c'est 0
(c'est ce qu'on va adopter en pseudo-code). Dans ce cas, notes[i] désigne l'élément i+1
du tableau notes .
 Il est possible de déclarer un tableau sans préciser au départ sa dimension. Cette
précision est faite ultérieurement.
 Par exemple, quand on déclare un tableau comme paramètre d'une procédure, on peut
ne préciser sa dimension qu'au moment de l'appel.
 En tous cas, un tableau est inutilisable tant qu’on n’a pas précisé le nombre de ses
éléments .
 Un grand avantage des tableaux est qu'on peut traiter les données qui y sont stockées
de façon simple en utilisant des boucles.

09/06/2019 Oussama ELHAJJAMY 64

Les tableaux

• Tableaux à une dimension : Exemple

La déclaration Pour le calcul du nombre d'étudiants ayant une note supérieure à
10 avec les tableaux, on peut écrire :
Variables i, nbre : entier
tableau notes[200] : réel
Début
nbre ← 0
Pour i allant de 0 à 199
Si (notes[i] >10) alors
nbre ←nbre+1
FinSi
FinPour
écrire ("le nombre de notes supérieures à 10 est : ", nbre)
Fin

09/06/2019 Oussama ELHAJJAMY 65

Les tableaux

• Tableaux à une dimension : Lecture

Lire(n)
Pour i allant de 1 à n faire
Lire(T[i])
FinPour

Remarques :
• La variable i (le compteur de la boucle pour) sert comme indice pour accéder
au ième , élément du tableau T.
• Le premier élément est T[1], le deuxième élément est T[2], … et le ième élément
est T[i].
• Pour i allant de 1 à n faire lire(T[i]) permet la lecture des cases T[1], T[2], … et
T[n].

09/06/2019 Oussama ELHAJJAMY 66

Les tableaux

• Tableaux à une dimension : Ecriture

Pour i allant de 1 à n faire

Ecrire(T[i])
FinPour

09/06/2019 Oussama ELHAJJAMY 67

Les tableaux

• Tableaux à une dimension : Lecture & Ecriture

Exemple :
Algorithme Tableau_lec_ecr
Variables Tableau T[50] : réel
n, i : entier
Début
Lire(n)
Pour i allant de 1 à n faire
Lire(T[i])
FinPour
Pour i allant de 1 à n faire
Ecrire(T[i])
FinPour

09/06/2019 Oussama ELHAJJAMY 68

Les tableaux

• Tableaux à une dimension : Ecriture

La plus part des langages offrent une fonction longueur qui donne la dimension
du tableau. Les procédures Saisie et Affiche peuvent être réécrites comme suit :
Algorithme Tableau_lec_ecr
Variables Tableau T[50] : réel
i : entier
Début
Pour i allant de 1 à longueur(T) faire
Lire(T[i])
FinPour
Pour i allant de 1 à longueur(T) faire
Ecrire(T[i])
FinPour

09/06/2019 Oussama ELHAJJAMY 69

Les tableaux

• Tableaux à une dimension : Problèmes classiques

 Somme et la moyenne des éléments d’un tableau.
 Inverser les éléments d’un tableau (le résultat dans un autre tableau, ou dans
le même tableau).
 La recherche de l’élément minimum (et/ou maximum) dans un tableau et leurs
positions (leurs indices)
 Trier les éléments d’un tableau (Ordre croissant ou décroissant)
 La recherche d’un élément dans un tableau
 La somme et produit cartésien de deux vecteurs
 Ajouter une même valeur à tous les éléments d’un vecteur.

09/06/2019 Oussama ELHAJJAMY 70

Les tableaux

• Tableaux à deux dimensions : Syntaxe & sémantique

Les langages de programmation permettent de déclarer des tableaux dans
lesquels les valeurs sont repérées par deux indices. Ceci est utile par exemple
pour représenter des matrices.
En pseudo code :
variables tableau identificateur[dimension1] [dimension2] : type
Exemple : une matrice A de 3 lignes et 4 colonnes dont les éléments sont réels
variables tableau A[3][4] : réel
A[i][j] permet d'accéder à l’élément de la matrice qui se trouve à l’intersection de
la ligne i et de la colonne j

09/06/2019 Oussama ELHAJJAMY 71

Les tableaux

• Tableaux à deux dimensions : lecture d'une matrice

Exemple : Algorithme qui permet de saisir les éléments d'une matrice :

lire(n,m)
Pour i allant de 1 à n faire
Pour j allant de 1 à m faire
lire (A[i][j])
FinPour
FinPour

09/06/2019 Oussama ELHAJJAMY 72

Les tableaux

• Tableaux à deux dimensions : Ecriture d'une matrice

Exemple : Algorithme qui permet d’afficher les éléments d'une matrice :

Pour i allant de 1 à n faire

Pour j allant de 1 à m faire
écrire ("A[",i, "] [",j,"]=", A[i][j])
FinPour
FinPour

09/06/2019 Oussama ELHAJJAMY 73

Les tableaux

• Tableaux à deux dimensions

Exemple : Algorithme qui calcule la somme de deux matrices

Algorithme Somme2Matrice
Variables tableau A[10][10] : réel
tableau B[10][10] : réel
tableau C[10][10] : réel
i,j ,n,m: entier
Début
lire(n,m)
Pour i allant de 1 à n faire
Pour j allant de 1 à m faire
C[i][j] ← A[i][j]+B[i][j]
FinPour
FinPour
Fin
09/06/2019 Oussama ELHAJJAMY 74
Les tableaux

• Tableaux à deux dimensions : Problèmes classiques

 Somme et la moyenne des éléments d’une matrice.

 Somme et la moyenne de chaque ligne et/ou de chaque colonne.
 Somme et Moyenne de la ligne N° i (ou de la colonne N° j).
 La recherche de l’élément minimum (et/ou maximum) dans une matrice et
leurs positions (leurs indices de ligne et de colonne).
 Tri d’une matrice (Ordre croissant ou décroissant).
 La recherche d’une valeur dans une matrice.
 La somme et le produit de deux matrices réelles.
 Ajouter une même valeur à tous les éléments d’une matrice.

09/06/2019 Oussama ELHAJJAMY 75

Les tableaux

• Tableaux : Algorithmes de recherche

Recherche d’un élément dans un tableau :

 Recherche séquentielle
 Recherche dichotomique

09/06/2019 Oussama ELHAJJAMY 76

Les tableaux

• Tableaux : Algorithme de recherche séquentielle

Le principe consiste à consulter les éléments de la liste et les comparer un à un

avec l’élément recherché, du début jusqu’à trouver l’élément ou arriver à la fin de
la liste. Ceci est réalisé à l’aide d’une structure itérative.

Exemples :
 Recherche d’un nom dans une liste de noms.
 Recherche d’un nombre dans une liste de nombres.

09/06/2019 Oussama ELHAJJAMY 77

Les tableaux

• Tableaux : Algorithme de recherche séquentielle

Recherche de la valeur x dans un tableau T de N éléments :
Variables i: entier, Trouvé : booléen
Début
i←0 , Trouvé ← Faux
TantQue (i < N) ET (Trouvé=Faux)
Si (T[i]=x) alors
Trouvé ← Vrai
Sinon
i←i+1
FinSi
FinTantQue
Si Trouvé=vrai alors
écrire ("x appartient au tableau")
Sinon
écrire ("x n'appartient pas au tableau")
FinSi
Fin
09/06/2019 Oussama ELHAJJAMY 78
Les tableaux

• Tableaux : Algorithme de recherche séquentielle

Une fonction Recherche qui retourne un booléen pour indiquer si une valeur x
appartient à un tableau T de dimension N.
x , N et T sont des paramètres de la fonction

Fonction Recherche(x : réel, N: entier, tableau T : réel ) : booléen

Variable i: entier
Pour i allant de 0 à N-1
Si (T[i]=x) alors
retourne (Vrai)
FinSi
FinPour
retourne (Faux)
FinFonction

09/06/2019 Oussama ELHAJJAMY 79

Les tableaux

• Tableaux : Algorithme de recherche séquentielle

Avantages :
 Très simple à réaliser.
 Le tri de la liste n’est pas obligatoire.

Inconvénients :
 Pour des listes trop importantes la recherche devient trop lente.

09/06/2019 Oussama ELHAJJAMY 80

Les tableaux

• Tableaux : Algorithme de recherche séquentielle

 Pour évaluer l’efficacité et la rapidité d'un algorithme, on calcule sa complexité.

 Mesurer la complexité revient à quantifier le temps d'exécution et l'espace
mémoire nécessaire.
 Le temps d'exécution est proportionnel au nombre des opérations effectuées.
Pour mesurer la complexité en temps, on met en évidence certaines
opérations fondamentales, puis on les compte.
 Le nombre d'opérations dépend généralement du nombre de données à
traiter. Ainsi, la complexité est une fonction de la taille des données. On
s'intéresse souvent à son ordre de grandeur asymptotique.
 En général, on s'intéresse à la complexité dans le pire des cas et à la
complexité moyenne.

09/06/2019 Oussama ELHAJJAMY 81

Les tableaux

• Tableaux : Algorithme de recherche séquentielle

 Pour évaluer l’efficacité de l'algorithme de recherche séquentielle, on va calculer

sa complexité dans le pire des cas. Pour cela on va compter le nombre de tests
effectués
 Le pire des cas pour cet algorithme correspond au cas où x n'est pas dans le
tableau T
 Si x n’est pas dans le tableau, on effectue 3N tests : on répète N fois les tests (i < N),
(Trouvé=Faux) et (T[i]=x)
 La complexité dans le pire des cas est d'ordre N, (on note O(N))
 Pour un ordinateur qui effectue 106 tests par seconde on a :
N 103 106 109
temps 1 ms 1s 16 min 40 s

09/06/2019 Oussama ELHAJJAMY 82

Les tableaux

• Tableaux : Algorithme de recherche dichotomique

Dans le cas où le tableau est ordonné, on peut améliorer l'efficacité de la

recherche en utilisant la méthode de recherche dichotomique

Principe : diviser par 2 le nombre d'éléments dans lesquels on cherche la valeur x

à chaque étape de la recherche. Pour cela on compare x avec T[milieu] :

 Si x < T[milieu], il suffit de chercher x dans la 1ère moitié du tableau entre

(T[0] et T[milieu-1])

 Si x > T[milieu], il suffit de chercher x dans la 2ème moitié du tableau entre

(T[milieu+1] et T[N-1])

09/06/2019 Oussama ELHAJJAMY 83

Les tableaux

• Tableaux : Algorithme de recherche dichotomique

• Considérons le tableau T :
5 6 11 16 18 19 25 28 30

• Si la valeur cherché est 20 alors les indices inf, sup et milieu vont évoluer
comme suit :
Inf 1 5 6
Sup 9 9 6
milieu 5 7 6

• Si la valeur cherché est 10 alors les indices inf, sup et milieu vont évoluer
comme suit :
Inf 1 1 3
Sup 9 4 4
milieu 5 2 3

09/06/2019 Oussama ELHAJJAMY 84

Les tableaux

• Tableaux : Algorithme de recherche dichotomique

inf←1 , sup←N, Trouvé ← Faux
TantQue (inf <=sup) ET (Trouvé=Faux)
milieu←(inf+sup)div2
Si (x=T[milieu]) alors
Trouvé ← Vrai
SinonSi (x>T[milieu]) alors
inf←milieu+1
Sinon
sup←milieu-1
FinSi
FinSi
FinTantQue
Si Trouvé=vrai alors écrire ("x appartient au tableau")
Sinon écrire ("x n'appartient pas au tableau")
FinSi
09/06/2019 Oussama ELHAJJAMY 85
Les tableaux

• Tableaux : Algorithme de recherche dichotomique

Avantages :
 Très rapide surtout pour les listes trop importantes.

Inconvénients :
 La liste doit être triée.

09/06/2019 Oussama ELHAJJAMY 86

Les tableaux

• Tableaux : Algorithme de recherche dichotomique

 La complexité dans le pire des cas est d'ordre log2N

 L'écart de performances entre la recherche séquentielle et la recherche
dichotomique est considérable pour les grandes valeurs de N
 Exemple: au lieu de N=1milion ≈220 opérations à effectuer avec une recherche
séquentielle il suffit de 20 opérations avec une recherche dichotomique.

09/06/2019 Oussama ELHAJJAMY 87

Les tableaux

• Tableaux : Tri d'un tableau

Le tri consiste à ordonner les éléments du tableau dans l’ordre croissant ou

décroissant.
Il existe plusieurs algorithmes connus pour trier les éléments d’un tableau :
 Le tri par sélection.
 Le tri par insertion.
 Le tri rapide.
 Le tri à bulles.

09/06/2019 Oussama ELHAJJAMY 88

Les tableaux

• Tri par sélection

Principe : à l'étape i, on sélectionne le plus petit élément parmi les (n-i+1)
éléments du tableau les plus à droite. On l'échange ensuite avec l'élément i du
tableau.
Exemple : 9 4 1 7 3
Étape 1: on cherche le plus petit parmi les 5 éléments du tableau. On l’identifie en
troisième position, et on l’échange alors avec l’élément 1 :
1 4 9 7 3
Étape 2: on cherche le plus petit élément, mais cette fois à partir du deuxième
élément. On le trouve en dernière position, on l'échange avec le deuxième:
1 3 9 7 4

Étape 3: 1 3 4 7 9
09/06/2019 Oussama ELHAJJAMY 89
Les tableaux

• Tri par sélection

Pour i allant de 1 à N-1
posMin ← i
Pour j allant de i + 1 à N-1
Si T[j] <T[posMin] alors
posMin ← j
Finsi
FinPour
temp ← T[posMin]
T[posMin] ← T[i]
T[i] ← temp
FinPour

09/06/2019 Oussama ELHAJJAMY 90

Les tableaux

• Tri par sélection

 Quel que soit l'ordre du tableau initial, le nombre de tests et d'échanges reste
le même
 On effectue N-1 tests pour trouver le premier élément du tableau trié, N-2
tests pour le deuxième, et ainsi de suite. Soit : (N-1)+(N-2)+…+1 = N(N-1)/2 On
effectue en plus (N-1) échanges.
 La complexité du tri par sélection est d'ordre N² à la fois dans le meilleur des
cas, en moyenne et dans le pire des cas
 Pour un ordinateur qui effectue 103 tests par seconde on a :
N 103 106 109
temps 1s 11,5 jours 32000 ans

09/06/2019 Oussama ELHAJJAMY 91

Les tableaux

• Tri par insertion

Principe : Insérer le i-ème élément à sa place parmi ceux qui précèdent :
Pour T[i] d’indice i (par exemple i=4), on suppose que les i-1 premiers éléménts
sont triés.
1. Commencer par sauvegarder T[i] dans une autre variable TMP
2. Trouver où l’élément doit être insérer dans la partie du tableau commençant
Position
de i à i-1 d’insertion

1 2 3 4 5 6
3 18 26 12 90 40
TEMP
Partie Partie pas
12
triée i=4 encore triée

09/06/2019 Oussama ELHAJJAMY 92

Les tableaux

• Tri par insertion

Principe : Insérer le i-ème élément à sa place parmi ceux qui précèdent :
Pour T[i] d’indice i (par exemple i=4), on suppose que les i-1 premiers éléménts
sont triés.
3. Décaler les éléments afin de pouvoir effectuer l’insertion

Position
d’insertion

1 2 3 4 5 6
3 18 18 26 90 40
TEMP
Partie Partie pas
12
triée i=4 encore triée

09/06/2019 Oussama ELHAJJAMY 93

Les tableaux

• Tri par insertion

Principe : Insérer le i-ème élément à sa place parmi ceux qui précèdent :
Pour T[i] d’indice i (par exemple i=4), on suppose que les i-1 premiers éléménts
sont triés.
4. Insérer l’élément à partir de TEMP dans la position d’insertion.
Remarque : En pratique l’étape 2 et 3 se font au même temps.
Position
d’insertion

1 2 3 4 5 6
3 12 18 26 90 40
TEMP
Partie Partie pas
12
triée i=4 encore triée

09/06/2019 Oussama ELHAJJAMY 94

Les tableaux

• Tri par insertion

Pour i allant de 2 à N faire
Tmp ← T[i]
j←i
Tantque (j > 1) and (T[j-1] > Tmp) faire
T[j] ← T[j-1]
j ← j-1
FinTantque
T[j] ← Tmp
FinPour

09/06/2019 Oussama ELHAJJAMY 95

Les tableaux

• Tri par insertion

 Dans le pire des cas le nombre de comparaisons "Tantque Tab[j-1] > Tmp faire"
est une valeur qui ne dépend que de la longueur i de la partie (a1, a2, ... , ai)
déjà rangée. Il y a donc au pire i comparaisons pour chaque i variant de 2 à n :
 La complexité au pire en nombre de comparaison est donc égale à la somme
des n termes suivants (i = 2, i = 3,.... i = n)
 C = 2 + 3 + 4 +...+ n = n(n+1)/2 -1 comparaisons au maximum. (c'est la somme
des n premiers entiers moins 1).
 La complexité au pire en nombre de comparaison est de de l'ordre de n², que
l'on écrit O(n²).

09/06/2019 Oussama ELHAJJAMY 96

Les tableaux

• Tri rapide
Principe : Le tri rapide est un tri récursif basé sur l'approche "diviser pour régner",
(consiste à décomposer un problème d'une taille donnée à des sous problèmes
similaires mais de taille inférieure faciles à résoudre)
Description du tri rapide :
1. On considère un élément du tableau qu'on appelle pivot.
2. On partitionne le tableau en 2 sous tableaux : les éléments inférieurs ou
égaux à pivot et les éléments supérieurs à pivot. on peut placer ainsi la valeur
du pivot à sa place définitive entre les deux sous tableaux.
3. On répète récursivement ce partitionnement sur chacun des sous tableaux
crées jusqu'à ce qu'ils soient réduits à un à un seul élément.

09/06/2019 Oussama ELHAJJAMY 97

Les tableaux

• Tri rapide
Procédure TriRapide(tableau T : réel par adresse, p,r: entier par valeur)
variable q: entier
Si p <r alors
Partition(T,p,r,q)
TriRapide(T,p,q-1)
TriRapide(T,q+1,r)
FinSi
Fin Procédure
A chaque étape de récursivité on partitionne un tableau T[p..r] en deux sous
tableaux T[p..q-1] et T[q+1..r] tel que chaque élément de T[p..q-1] soit inférieur
ou égal à chaque élément de A[q+1..r] . L'indice q est calculé pendant la
procédure de partitionnement

09/06/2019 Oussama ELHAJJAMY 98

Les tableaux

• Tri rapide
Procédure Partition(tableau T : réel par adresse, p,r: entier par valeur,
q: entier par adresse )
Variables i, j: entier
pivot: réel
pivot← T[p], i←p+1, j ← r
TantQue (i<=j)
TantQue (i<=r et T[i] <=pivot) i ← i+1 FinTantQue
TantQue (j>=p et T[j] >pivot ) j ← j-1 FinTantQue
Si i <j alors
Echanger(T[i], T[j]), i ← i+1, j ← j-1
FinSi
FinTantQue
Echanger(T[j], T[p])
q←j
Fin Procédure
09/06/2019 Oussama ELHAJJAMY 99
Les tableaux

• Tri rapide

 La complexité du tri rapide dans le pire des cas est en O(N²)

 La complexité du tri rapide en moyenne est en O(N log N)
 Le choix du pivot influence largement les performances du tri rapide
 Le pire des cas correspond au cas où le pivot est à chaque choix le plus petit
élément du tableau (tableau déjà trié)
 différentes versions du tri rapide sont proposés dans la littérature pour rendre
le pire des cas le plus improbable possible, ce qui rend cette méthode la plus
rapide en moyenne parmi toutes celles utilisées

09/06/2019 Oussama ELHAJJAMY 100

 CHAPITRE III
Fonctions et Procédures
 Fonctions et Procédures

• Exemple introductif
{Calculer n!}
Cn k = n! / (k! * (n-k)!)
nf  1
Algorithme Calcule_Combinaison Pour i allant de 2 à n faire
Variables n, k, c : entier nf  nf*i
nf, kf, nkf : entier Fin Pour
Début
{Entrées} {Calculer k!}
Lire (n, k) kf  1
{Traitement} Pour i allant de 2 à k faire
{trt 1} kf  kf*i
{trt 2} Fin Pour
{trt 3}
{Calculer (n-k)!}
c  nf/(kf*nkf)
nkf  1
{Sorties}
Pour i allant de 2 à (n-k) faire
Ecrire (c)
nkf  nkf*i
Fin
Fin Pour

09/06/2019 Oussama ELHAJJAMY 102

Fonctions et Procédures

• Exemple introductif

Problèmes :
Presque le même code a été répété 3 fois : Calcul du factoriel (Les données
uniquement qui changent)
{Calculer n!} {Calculer k!} {Calculer (n-k)!}
nf  1 kf  1 nkf  1
Pour i allant de 2 à n faire Pour i allant de 2 à k faire Pour i allant de 2 à (n-k) faire
nf  nf*i kf  kf*i nkf  nkf*i
Fin Pour Fin Pour Fin Pour

Comment écrire le code du factoriel une seule fois et l’exécuter autant de fois
qu’on veut ?
Solution : Sous-Programme

09/06/2019 Oussama ELHAJJAMY 103

Fonctions et Procédures

• Sous-Programme :

Un Sous-Programme est une séquence d’instructions qui possède un nom unique

(identificateur). Il a plusieurs intérêt :
 permet de "factoriser" les programmes, càd de mettre en commun les
parties qui se répètent

 permet une structuration et une meilleure lisibilité des programmes.

 facilite la maintenance du code (il suffit de modifier une seule fois).

 peut éventuellement être réutilisé dans d'autres programmes.

09/06/2019 Oussama ELHAJJAMY 104

Fonctions et Procédures

• Sous-Programme :

Données d’Entrées
(Paramètres)
Défini dans un programme
plus grand (Souvent c’est
le programme principal)

Sous-Programme Déclaration
Appel

Les procédures
Les fonctions
Données de sorties
(Paramètres)

09/06/2019 Oussama ELHAJJAMY 105

Fonctions et Procédures

• Structure du Programme principal :

Entête
Nom du programme (identificateur).

Déclaration
Programme
Constantes, Types, Variables, Etiquètes
Principal

Corps du programme (Instructions)

Lecture, Ecriture
Affectation
Structures de contrôle (si, pour, tant que,
répéter … )
Appel au sous programme

09/06/2019 Oussama ELHAJJAMY 106

Fonctions et Procédures

• Structure d’un sous-Programme :

Entête
Nom, paramètres (formels).

Déclaration
Sous-Programme Constantes, Types, Variables, Etiquètes, Sous-
programmes (à éviter)

Corps du programme (Instructions)

Lecture, Ecriture (à éviter)
Affectation
Structures de contrôle (si, pour, tant que,
répéter … )
Appel au sous programme

09/06/2019 Oussama ELHAJJAMY 107

Fonctions et Procédures

• Appel à un sous-Programme :
Programme
Principal Sous-
Données Programme
-Constante Données
-Variables -Paramètres
Instructions -Constante
Instruction1 -Variables
Instruction2 Instructions
Instruction3 Instruction1
……. Instruction2
……. …….
Instruction N-i …….
……. Instruction M
Instruction N

09/06/2019 Oussama ELHAJJAMY 108

Fonctions et Procédures

• Appel à un sous-Programme :
Programme
Principal Sous-
Données Programme
-Constante Données Données
-Variables Globales -Paramètres
Paramètre et
Instructions -Constante Données Locales
Instruction1 -Variables
Instruction2 Instructions
Instruction3 Instruction1
……. Instruction2
……. …….
Appel à SP …….
……. Instruction M
Instruction N

09/06/2019 Oussama ELHAJJAMY 109

Fonctions et Procédures

• Appel à un Sous-Programme :

Remarque
 Lors d’appel à un sous-programme, c’est possible de transmettre des données :
paramètres en entrée.

 Lorsque l’exécution du sous-programme est terminée, c’est possible de

retourner des données (résultats) : paramètres en sorties.

 Le programme principal attend toujours la fin d’exécution du sous-programme.

 Le sous-programme possède éventuellement des données locales.

09/06/2019 Oussama ELHAJJAMY 110

Fonctions et Procédures

• Appel à un Sous-Programme :

Remarques :
 Les sous-programme possède éventuellement des données locales.

 Les sous-programme peut accéder aux données du programme principal

(données globales – Pratique déconseillée à éviter  Autonomie du S.P).

 Le sous-programme, dans une bonne pratique, utilise uniquement les données

locales ainsi que ses paramètres (entrée/sortie)  S.P Autonome.

 Il y a deux types de paramètres : paramètres d’entrées (les valeurs à

transmettre au S.P) et paramètre de sorties (les résultats à récupérer).

09/06/2019 Oussama ELHAJJAMY 111

Fonctions et Procédures

• Fonctions: Déclaration

Le rôle d'une fonction en programmation est similaire à celui d'une fonction en

mathématique : elle retourne un résultat à partir des valeurs des paramètres.
Une fonction s'écrit en dehors du programme principal sous la forme :
Fonction nom_fonction (paramètres et leurs types) : type_fonction
Instructions constituant le corps de la fonction
retourne …
FinFonction
• Pour le choix d'un nom de fonction il faut respecter les mêmes règles que
celles pour les noms de variables
• type_fonction est le type du résultat retourné
• L'instruction retourne sert à retourner la valeur du résultat

09/06/2019 Oussama ELHAJJAMY 112

Fonctions et Procédures

• Appel à une fonction

L'appel à une fonction, se fait dans le programme principale ou dans une autre
fonction par une instruction indiquant le nom de la fonction :

Paramètres formels Paramètres effectifs

Fonction exemple_fct (p1:type, Algorithme exempleAppelFonction

p2:type, …, pn:type) :typeFonction Début
… exemple_fct (vp1, vp2, …, vpn)
FinFonction …
Fin

09/06/2019 Oussama ELHAJJAMY 113

Fonctions et Procédures

• Fonctions

Remarques

 Eviter d’utiliser les données (variables/constantes) globales dans une fonction.

La fonction doit être autonome.

 Utiliser uniquement les paramètres pour communiquer avec une fonction.

 Eviter de faire les lectures (et éventuellement) les écritures à l’intérieur d’une
fonction.

09/06/2019 Oussama ELHAJJAMY 114

Fonctions et Procédures

• Fonctions: Exemples

La fonction SommeCarré suivante calcule la somme des carrées de deux réels x et

y:
Fonction SommeCarre (x : réel, y: réel ) : réel
variable z : réel
z ←x^2+y^2
retourne (z)
FinFonction

La fonction Pair suivante détermine si un nombre est pair :

Fonction Pair (n : entier ) : booléen
retourne (n%2=0)
FinFonction

09/06/2019 Oussama ELHAJJAMY 115

Fonctions et Procédures

• Procédure: Déclaration

Dans certains cas, on peut avoir besoin de répéter une tache dans plusieurs
endroits du programme, mais que dans cette tache on ne calcule pas de résultats
ou qu'on calcule plusieurs résultats à la fois.
Dans ces cas on ne peut pas utiliser une fonction, on utilise une procédure.
Une procédure est un sous-programme semblable à une fonction mais qui ne
retourne rien.
Une procédure s'écrit en dehors du programme principal sous la forme :
Procédure nom_procédure (paramètres et leurs types)
Instructions constituant le corps de la procédure
FinProcédure
• Remarque : une procédure peut ne pas avoir de paramètres.

09/06/2019 Oussama ELHAJJAMY 117

Fonctions et Procédures

• Appel d'une procédure

L'appel d'une procédure, se fait dans le programme principale ou dans une autre
procédure par une instruction indiquant le nom de la procédure :

Paramètres formels Paramètres effectifs

Procédure exemple_proc (p1:type, Algorithme exepmleAppelProcédure

p2:type, …, pn:type) Début
… exemple_proc (vp1, vp2, …, vpn)
FinProcédure …
Fin

09/06/2019 Oussama ELHAJJAMY 118

Fonctions et Procédures

• Appel d'une procédure

Remarques :
 contrairement à l'appel d'une fonction, on ne peut pas affecter la procédure
appelée ou l'utiliser dans une expression. L'appel d'une procédure est une
instruction autonome.

 Le nombre des paramètres effectifs et le même que les paramètres formels.

 Chaque paramètre effectif doit être du même type (ou type homogène) que le
paramètre formel correspondant.

09/06/2019 Oussama ELHAJJAMY 119

Fonctions et Procédures

• Paramètres d’une procédure

 Les paramètres servent à échanger des données entre le programme

principale (ou la procédure appelante) et la procédure appelée.

 Les paramètres placés dans la déclaration d'une procédure sont appelés

paramètres formels. Ces paramètres peuvent prendre toutes les valeurs
possibles mais ils sont abstraits (n'existent pas réellement).

 Les paramètres placés dans l'appel d'une procédure sont appelés paramètres
effectifs. ils contiennent les valeurs pour effectuer le traitement.

 Le nombre de paramètres effectifs doit être égal au nombre de paramètres

formels. L'ordre et le type des paramètres doivent correspondre.

09/06/2019 Oussama ELHAJJAMY 120

Fonctions et Procédures

• Transmission des paramètres

Il existe deux modes de transmission de paramètres dans les langages de

programmation :
 La transmission par valeur : les valeurs des paramètres effectifs sont affectées aux
paramètres formels correspondants au moment de l'appel de la procédure. Dans ce
mode le paramètre effectif ne subit aucune modification
 La transmission par adresse (ou par référence) : les adresses des paramètres effectifs
sont transmises à la procédure appelante. Dans ce mode, le paramètre effectif subit les
mêmes modifications que le paramètre formel lors de l'exécution de la procédure
Remarque : le paramètre effectif doit être une variable (et non une valeur)
lorsqu'il s'agit d'une transmission par adresse
En pseudo-code, on va préciser explicitement le mode de transmission dans la
déclaration de la procédure

09/06/2019 Oussama ELHAJJAMY 121

Fonctions et Procédures

• Transmission des paramètres : Exemple

Procédure incrementer1 (x : entier par valeur, y : entier par adresse)
x ← x+1
y ← y+1
FinProcédure

Algorithme Test_incrementer1
variables n, m : entier
Début
n←3
m←3
incrementer1(n, m) résultat :
écrire (" n= ", n, " et m= ", m) n=3 et m=4
Fin

Remarque : l'instruction x ← x+1 n'a pas de sens avec un passage par valeur

09/06/2019 Oussama ELHAJJAMY 122

Fonctions et Procédures

• Transmission par valeur, par adresse : exemples

Procédure qui calcule la somme et le produit de deux entiers :

Procédure SommeProduit (x,y: entier par valeur, som, prod : entier par adresse)
som ← x+y
prod ← x*y
FinProcédure
Procédure qui échange le contenu de deux variabales :
Procédure Echange (x : réel par adresse, y : réel par adresse)
variables z : réel
z←x
x←y
y←z
FinProcédure
09/06/2019 Oussama ELHAJJAMY 123
Fonctions et Procédures

• Variables locales et globales

 On peut manipuler 2 types de variables dans un module (procédure ou

fonction) : des variables locales et des variables globales. Elles se distinguent
par ce qu'on appelle leur portée (leur "champ de définition", leur "durée de
vie")

 Une variable locale n'est connue qu'à l'intérieur du module ou elle a été
définie. Elle est créée à l'appel du module et détruite à la fin de son exécution

 Une variable globale est connue par l'ensemble des modules et le programme
principale. Elle est définie durant toute l’application et peut être utilisée et
modifiée par les différents modules du programme

09/06/2019 Oussama ELHAJJAMY 124

Fonctions et Procédures

• Variables locales et globales

 La manière de distinguer la déclaration des variables locales et globales diffère

selon le langage
– En général, les variables déclarées à l'intérieur d'une fonction ou procédure
sont considérées comme variables locales

 En pseudo-code, on va adopter cette règle pour les variables locales et on

déclarera les variables globales dans le programme principale

 Conseil : Il faut utiliser autant que possible des variables locales plutôt que des
variables globales. Ceci permet d'économiser la mémoire et d'assurer
l'indépendance de la procédure ou de la fonction

09/06/2019 Oussama ELHAJJAMY 125

Fonctions et Procédures

• Fonctions récursives

 Un module (fonction ou procédure) peut s'appeler lui-même: on dit que c'est

un module récursif
 Tout module récursif doit posséder un cas limite (cas trivial) qui arrête la
récursivité
Exemple : Calcul du factorielle
Fonction fact (n : entier ) : entier
Si (n=0) alors
retourne (1)
Sinon
retourne (n*fact(n-1))
Finsi
FinFonction

09/06/2019 Oussama ELHAJJAMY 126

Fonctions et Procédures

• Fonctions récursives

Ecrivez une fonction itérative qui calcule le terme n de la suite de Fibonacci:

Fonction Fib (n : entier ) : entier
Variables i, AvantDernier, Dernier, Nouveau : entier
Si (n=1 OU n=0) alors retourne (1)
Finsi
AvantDernier ←1, Dernier ←1
Pour i allant de 2 à n
Nouveau← Dernier+ AvantDernier
AvantDernier ←Dernier
Dernier ←Nouveau
FinPour
retourne (Nouveau)
FinFonction
Remarque: la solution récursive est plus facile à écrire
09/06/2019 Oussama ELHAJJAMY 127
Fonctions et Procédures

• Fonctions récursives

Ecrivez une fonction récursive qui calcule le terme n de la suite de Fibonacci :

Fonction Fib (n : entier ) : entier
Variable res : entier
Si (n=1 OU n=0) alors
res ←1
Sinon
res ← Fib(n-1)+Fib(n-2)
Finsi
retourne (res)
FinFonction

09/06/2019 Oussama ELHAJJAMY 128

Fonctions et Procédures

• Procédures récursives

Une procédure récursive qui permet d'afficher la valeur binaire d'un entier n

Procédure binaire (n : entier )

Si (n<>0) alors
binaire (n/2)
écrire (n % 2)
Finsi
FinProcédure

09/06/2019 Oussama ELHAJJAMY 129