Fascicule du Cours :

Algorithmique et Structures de Données

Fiche module

Niveau ciblé 1ère année du cycle ingénieur

Nature de l’enseignement Cours intégré

Description du module
Ce module est constitué de deux volets : un premier volet qui s’intéresse à l’algorithmique et un
deuxième qui se focalise sur la programmation. Le premier volet est lui-même constitué de deux
parties. La première couvre l’algorithmique de base et est enseignée en parallèle avec la partie
programmation. La deuxième quant à elle s’intéresse à des notions d’algorithmique plus
avancées englobant les structures de données séquentielles et arborescentes.
Objectifs du module
Les objectifs du volet Algorithmique de ce module sont essentiellement les suivants :
 Expliquer aux étudiants l’importance d’avoir des connaissances solides en algorithmique, le
lien entre l’algorithmique et la programmation ainsi que les règles d’écriture d’un
algorithme ;
 Etudier, assimiler et maîtriser les notions de base nécessaires pour la résolution de tout
problème d’algorithmique ;
 Introduire et expliquer la notion de Types Abstraits de Données en insistant sur leur intérêt
ainsi que la manière de les définir ;
 Utiliser la démarche de définition de TAD pour introduire les types : « Liste », « Pile » et
« File » permettant l’organisation séquentielle de données aussi bien que les « Arbres
Binaires » et les « Arbres Binaires de Recherche » permettant l’organisation arborescente de
données ;
 Proposer, comparer et mettre en œuvre les différentes représentations permettant
d’implémenter les TAD déjà introduits.

Les objectifs du volet Programmation de ce module sont essentiellement les suivants :

 Expliquer brièvement l’histoire du langage C et souligner ses caractéristiques principales en
tant que langage compilé ;
 Introduire de façon progressive les notions de base de la programmation C ;
 Insister sur les notions délicates du langage telles que les pointeurs et le passage par adresse ;
 Apprendre aux étudiants à programmer en C en organisant des séances de TP et en leur
proposant des travaux à rendre ;
 Créer des bibliothèques implémentant les TAD vus dans le volet Algorithmique.

Evaluation du module
L’évaluation est constituée d’un ou de plusieurs tests, de travaux pratiques à rendre, d’un devoir
surveillé et d’un examen.
Sommaire

éférences bibliographiques du cours ASD

MALGOUYRES, Rémy, ZROUR, Rita, et FESCHET, Fabien. Initiation à l’algorithmique

et à la programmation en C-3e éd. : Cours avec 129 exercices corrigés. Dunod, 2014.

CORMEN, Thomas H., LEISERSON, Charles Eric, RIVEST, Ronald L., et al. Introduction
à l’algorithmique. Dunod, 1997.

COURTIN, Jacques, KOWARSKI, Irène. Initiation à l'algorithmique et aux structures de

donnéesVolume 2. Dunod, 1997.

COURTIN, Jacques, KOWARSKI, Irène. Initiation à l'algorithmique et aux structures de

donnéesVolume 1. Dunod, 1994.

FROIDEVAUX, Christine, GAUDEL, Marie-Claude, et SORIA, Michele. Types de données et

algorithmes. Ediscience International, 1993.

BEN RHOUMA, Kamel. Cours Algorithmique et Structures de Données. ENSI, 2007.

ALGORITHMIQUE DE BASE
 CHAPITRE I – LES OBJETS SIMPLES ET LES OPERATIONS
DE BASE
1. Définition
L’origine du mot algorithme découle du nom latinisé du mathématicien perse du 9ème
siècle « Abu Ja’far Mohammed Ibn MûsâAl-Khowâ-rismî ».
Le terme algorithme admet, depuis longtemps, plusieurs définitions qui convergent. Froidevaux
et al. définissent ce concept comme étant [Froidevaux et al., 1993]:
« La composition d’un ensemble fini d’étapes, chaque étape étant formée d’un nombre fini
d’opérations dont chacune est :
 Définie de façon rigoureuse et non ambigüe ;
 Effective c’est-à-dire pouvant être réalisée par une machine. »

Tout algorithme est donc caractérisé par [Courtin et al., 1994] :

 Un ensemble d’opérations à exécuter.
 Un ordre d’exécution de ces différentes opérations dicté par la logique d’enchaînement et
conditionné par les structures mises en œuvre.
 Un début et une fin.
Le domaine qui étudie les algorithmes est désigné par : « algorithmique ».

2. Structure d’un algorithme

Algorithme <nom de l’algorithme>
CONST
<nom_de_la_constante = valeur>
TYPE
<liste des structures>
VAR
<nom-variable> : <type-variable>
FONC
<liste des fonctions>
PROC
<liste des procédures>
DEBUT
<corps de l’algorithme : ensemble des instructions – une instruction par ligne>
FIN

_____________________________________________________________________________________
Préparé par Raoudha CHEBIL Page 1
Chapitre I Les objets simples et les opérations de base
Dans ce qui suit, nous présentons un exemple d’algorithme :
Supposons qu’on veut calculer la moyenne des notes d’un élève dans une matière donnée et
qu’on dispose de 3 notes : N1, N2 et N3.
Algorithme Moyenne
CONST
c1=2
c2=3
c3=4
VAR
Moyenne, N1, N2, N3 : réel
DEBUT
Ecrire( Donnez les trois notes dans l’ordre)
Lire (N1,N2,N3)
Moyenne  (N1*c1+N2*c2+N3*c3)/( c1+ c2 + c3)
Ecrire ( La moyenne est : , Moyenne)
FIN

3. Types de données
Dès que l’on a besoin de stocker une information au cours d’un algorithme, on utilise
une variable.
a. Types de base
i. Booléen
Valeurs : Vrai, Faux.
Opérations
 Opérations relationnelles (Faux < Vrai)
 Opérations logiques : négation (non), conjonction (et ), disjonction (ou)

A B Non A A et B A ou B
V V F V V
V F F F V
F V V F V
F F V F F

_____________________________________________________________________________________
Préparé par Raoudha CHEBIL Page 2
Chapitre I Les objets simples et les opérations de base

ii. Caractère
Valeurs : c’est un ensemble fini de symboles totalement ordonnés. Un code ASCII est associé à
chaque caractère.
Opérations
 Opérations relationnelles par exemple : ‘a’<’b’ ; ‘a’>’A’
 Concaténation
iii. Entier
Valeurs : c’est un sous ensemble de Z. Il s’agit d’une représentation en machine des entiers
relatifs.
Opérations
 Opérations relationnelles : = ; < ; > ; ≤ ; ≥ ; <>
 Opérations arithmétiques : +, -, *, /
 DIV : division entière
 MOD : reste de la division entière
 PUISSANCE
iv. Réel
Valeurs : un sous ensemble de R. Il s’agit d’une représentation en machine des réels.
Opérations
 Opérations relationnelles : = ; < ; > ; ≤ ; ≥ ; <>
 Opérations arithmétiques : +, -, *, /
 Puissance
 Autres opérations comme cos, sin…
Outre les types définis ci-dessus ; il est possible de définir de nouveaux types comme suit.

b. Type scalaire énuméré

Le type scalaire énuméré permet de représenter un ensemble ordonné et fini de valeurs désignées
par des identificateurs.
Définition et déclaration
Type nom_type = (val1,…, valk)
Une variable de type énuméré prendra une des valeurs figurant entre parenthèses.

_____________________________________________________________________________________
Préparé par Raoudha CHEBIL Page 3
Chapitre I Les objets simples et les opérations de base
Exemple :
Type
t_couleur = (blanc, bleu, rouge)
Var
cl : t_couleur
cl blanc

Opérations
 Opérations relationnelles
 Ord( ) : rang dans le domaine.
 Succ( ) : successeur dans le domaine
 Pred( ) : prédécesseur dans le domaine
 Inc (v,n) : incrémenter v de n
Exemples : ord(bleu)=1, succ(bleu)=rouge, pred(bleu)= blanc.

c. Type intervalle
Le type intervalle permet de restreindre le groupe de valeurs d’un type scalaire (entier, réel,
booléen, caractère ou type énuméré).
Définition du type :
Type nom_intervalle = borne_inf…borne_sup
Avec borne_inf<borne_sup.
Les opérations que nous pouvons effectuer sont celles du type des variables contenues dans
l’intervalle.
Exp :
Type
T_chiffre=0..9
T_majuscule=’A’..’Z’

4. Opérations de base
Dans un schéma séquentiel, on distingue deux types d’instructions :
 Des instructions simples, élémentaires permettant de faire un traitement ;
 Des instructions permettant de commander le déroulement de l’exécution, appelées structures
de contrôle.
a. Affectation

_____________________________________________________________________________________
Préparé par Raoudha CHEBIL Page 4
Chapitre I Les objets simples et les opérations de base
Le rôle de cette instruction est de placer une valeur dans une variable (associer une valeur à une
variable).
<nom variable><expression>
<expression> : constante | variable | expression
La variable et l’expression doivent être de même type ou de types compatibles (Exp : il est
possible d’affecter un entier à une variable réelle).

Exemple
Test()
var
i,j : entier

Debut
i 10
j 20
i 2*j
Fin

b. Lecture
L’utilisateur introduit des valeurs qui seront affectées à des variables réservées par le
programmeur. L’utilisateur doit respecter le type des éléments à introduire.
Lire (< liste variables >)
<liste variables > : <variable1>, … <variable n>
Exemple
Var
i : entier
j : réel
Debut
Lire(i,j)
Fin
c. Ecriture
Cette instruction permet aussi bien l’affichage d’un texte que l’affichage des valeurs d’une liste
de variables (une ou plusieurs).
Ecrire (<texte>)
Exemple
_____________________________________________________________________________________
Préparé par Raoudha CHEBIL Page 5
Chapitre I Les objets simples et les opérations de base
Var
i, j : entier
Debut
Ecrire (“Bonjour”)
Lire (i, j)
i i*j
Ecrire (i)
Fin

Remarque
On peut regrouper dans la syntaxe de l’instruction Ecrire, la liste des variables et le texte. Par
exemple : Ecrire ("La valeur de i est", i, " la valeur de j est ", j)

5. Algorithmique et programmation
La mise en œuvre d’un algorithme consiste en l’écriture des opérations qui le composent dans un
langage de programmation et constitue alors la brique de base d’un programme informatique.
Un algorithme exprime les instructions permettant de résoudre un problème donné
indépendamment des langages de programmation. Lors du passage de l’algorithmique à la
programmation, le travail revient à résoudre des problèmes de syntaxe, ou de types d’instructions
propres à ce langage.
Afin d’écrire un algorithme, on se base généralement sur une série de conventions désignée par
« pseudo-code », qui est comparable à un langage de programmation dont on aurait évacué la
plupart des problèmes de syntaxe. Puisqu’il est purement conventionnel, ce pseudo-code peut
varier légèrement d’une référence à une autre.
Pour être compréhensible, un algorithme doit être présenté de manière lisible ; il ne doit pas être
trop long, ce qui nécessite parfois de le décomposer en modules. Certaines formes de
programmation telles que les branchements sont à éviter ; par contre la récursivité permet une
expression concise des algorithmes et facilite leur analyse.

6. LES STRUCTURES DE CONTROLE

1. Structures conditionnelles
a. Schéma conditionnel à simple choix (Si – Alors – Fsi)
i. Syntaxe

Si <condition> alors
<Traitement>
Fsi

_____________________________________________________________________________________
Préparé par Raoudha CHEBIL Page 6
Chapitre II Les structures de contrôle

<condition> : expression à résultat booléen

<traitement> : suite d’instructions
Fsi : Fin si
ii. Sémantique

Si <condition> est vraie alors on exécute le bloc <traitement> et on continue en séquence à

l’instruction qui suit <Fsi>.
Si <condition> est fausse, on continue en séquence avec l’instruction qui suit immédiatement
<Fsi> .
b. Schéma conditionnel à double choix (Si – Alors – Sinon - Fsi)
i. Syntaxe
Si <condition> alors
<Traitement 1>
Sinon
<Traitement 2>
Fsi
ii. Sémantique

Si <condition> est vraie alors on exécute le bloc <traitement 1> et on continue en séquence à
l’instruction qui suit <Fsi>.
Si <condition> est fausse, on exécute les instructions du bloc <traitement 2> et on passe à
l’instruction qui suit immédiatement <Fsi>.
c. Schéma conditionnel à choix multiple
i. Syntaxe
Selon<v>
<v1> : <Traitement 1>
<v2> : < Traitement 2>
<vn> : < Traitement n>
Sinon : <Traitement >
Fin selon
ii. Sémantique

<Traitement > : suite d’instructions

<v> : identificateur d’une variable de type scalaire.
<vi> : une valeur ou une liste composée d’une suite de valeurs (Exp : 2, 5, 8) ou d’une fourchette (Exp :
0..9). Les valeurs contenues dans les <vi> doivent être de même type que <v>.
Lorsque <v> = <vi> on exécute le traitement correspondant et on passe à l’instruction qui suit
immédiatement Finselon.
Le bloc <sinon> est facultatif.

13
Chapitre II Les structures de contrôle

Remarque
L’instruction selon peut être ramenée à un enchaînement de « Si » imbriquées.
Exemple d’utilisation
Exp( )
Var
k, x : entier
Debut

x0
lire(k)
Selon k

5 : x  x+6

6..10 : x  x+18

11, 12, 13 : x  x-5

Sinon
x1
Fin selon
Fin

2. Structures itératives
Les structures itératives sont des instructions qui permettent de répéter l’exécution d’une même
séquence d’instructions un nombre fini de fois.
On distingue deux types de répétitions :
 L’itération : quand on connait le nombre de fois que l’on va répéter une instruction ou
une séquence d’instructions.
 La répétition conditionnelle : quand la poursuite d’une répétition dépend d’une
condition à résultat booléen.

8
Chapitre II Les structures de contrôle

a. Boucle « Pour »
Pour <compteur>de<valeur initiale>à<valeur finale>pas<incrément>faire
<Traitement>
Fpour
<compteur> : l’identificateur d’une variable de type scalaire.
<valeur initiale>, <valeur finale>, <incrément> : une variable de même type que le compteur ou
une constante de même type que le compteur ou une expression dont le résultat est de même type
que le compteur.
<Traitement> : une ou plusieurs instructions quelconques.
Exemple :
var
i, j, n : entier
Debut
n5
j1
Pour i de j à n pas (2) faire
Ecrire(i)
Fpour
Fin
Remarques
Il est interdit de modifier : <compteur>, <valeur initiale>, <valeur finale> et <incrément>.
 <valeur initiale> <= <valeur finale> Ssi <incrément>>0
 <valeur initiale> >= <valeur finale> Ssi <incrément><0
 <incrément> ne doit jamais être nul.

Lorsque la valeur de <incrément> n’est pas précisée elle est considérée comme étant égale à 1.
L’instruction Pour est utilisée lorsque le nombre d’itérations est connu.
b. Boucle « Tant que »

Tant que<condition>faire
<Traitement>
Fin tant que

_____________________________________________________________________________________
Préparé par Raoudha CHEBIL Page 9
Chapitre I Rappel et conventions syntaxiques

<condition> : expression à résultat booléen

<Traitement> : un ensemble d’instructions telles qu’il existe au moins une instruction modifiant
la condition.

Exercice
Ecrire un algorithme permettant de saisir une suite d’entiers positifs ou nuls se terminant par une
valeur négative, de faire la somme de ces entiers et de l’afficher.
c. Boucle « Répéter »

Répéter
<Traitement>
Jusqu’à <condition>
Remarque
Cette instruction ne peut être utilisée que si on est sûrs que le traitement est exécuté au moins
une fois.
La boucle précédente peut être remplacée par la boucle suivante :
Tant que non <condition> faire
<Traitement>
FTQ

13
Chapitre I Rappel et conventions syntaxiques

7. Décomposition modulaire
1. Introduction
Lors de la conception d’un programme résolvant un problème général, il est nécessaire de
décomposer le problème en différents sous-problèmes moins complexes à résoudre.
Ces différents sous-problèmes peuvent être résolus grâce à des modules ou sous-programmes.
L’utilisation des sous-programmes présente de nombreux avantages. Nous citons :
 La possibilité de réutilisation ;
 La facilité de la résolution de problèmes en ne s’intéressant qu’à l’écriture d’un module à
la fois ;
 La factorisation du code : les sous-programmes permettent de ne pas répéter plusieurs
fois une même séquence d’instructions au sein de l’algorithme.
En algorithmique, il existe deux types de sous-programmes :
 Les procédures
 Les fonctions
Lors de la conception d’un programme deux aspects apparaissent :
 La définition de la procédure ou de la fonction ;
 L’appel de la procédure ou de la fonction dans le programme.
Une fois explicité (l'algorithme défini), un sous programme peut être utilisé dans d'autres
programmes ou sous-programmes. Le (sous-) programme qui utilise un sous-programme est
désigné par (sous-) programme appelant.

2. Procédures
a. Déclaration
Procédure<Nom procédure> (<Liste-paramètres>)
var
<variables-locales>
Début
<Traitement>
Fin
<Nom procédure> : identificateur

<Liste-paramètres> : <par1> : <Type1>, <par2> :<Type2>,……,<par n> : <Type n>

<par i> : identificateurs de variables

<variables-locales> :<var1> : <Type1>

<var2> : <Type2>

14
Chapitre I Rappel et conventions syntaxiques

Une variable définie dans un sous-programme est appelée variable locale. La portée d'une
variable locale est uniquement le sous-programme qui la déclare.

<Traitement> : liste des instructions de la procédure

b. Appel de procédure
Un appel de procédure se fait de la façon suivante :

<Nom procédure> (<Liste-paramètres>)

<Liste-paramètres> : <par1>, <par2>,……,<par n>

<par i> =identificateurs de variables ou constante ou expression.

c. Exemple de procédure
Algo Exp1

Var

A, B : entier

Procédure AfficheMax(X :entier, Y :entier)

Début
si (X>Y)
alors ecrire(X)
sinon
ecrire (Y)
fsi
Fin

Début (Algorithme principal : algorithme appelant)

Ecrire(« Donnez deux entiers »)

Lire(A,B)

AfficheMax(A,B)

Fin

15
Chapitre I Rappel et conventions syntaxiques

3. Fonctions
a. Déclaration
Fonction<Nom fonction> (<Liste-paramètres>) : <type>
var

<variables-locales>
Début

<Traitement>

<Nom fonction> <variable>

Fin

<Nom fonction> : identificateur

<Liste-paramètres> : <par1> : <Type1>, <par2> :<Type2>,……,<par n> : <Type n>

<par i> : identificateurs de variables

<type> : type de retour de la fonction

<variables-locales> :<vari> : <Typei>

<Traitement> : liste des instructions de la fonction

<variable> : variable de même type que la fonction ou de type compatible.

b. Appel de fonction
Une fonction est utilisée dans une instruction :

 Dans la partie droite d’une affectation (y f(x))

 Dans une expression (arithmétique ou logique selon le type de la fonction)
(y f(x)+2)
 Comme paramètre d’une procédure ou d’une fonction P(f(x)), f(f(x)).
c. Exemple de fonction

16
Chapitre I Rappel et conventions syntaxiques

Algo Max
Var
A, B, C : entier
Fonction Max(X, Y : entier) : entier
Var
W : entier
Début
Si (X>Y) alors
W X
Sinon
W Y
Fsi
Max W
Fin
Début (Algorithme principal : algorithme appelant)

Ecrire (« Donner deux entiers »)

Lire (A, B)

C Max(A, B)

Ecrire (« Le maximum est : », C)

Fin

4. Transmission des données

a. Les types de paramètres
P. effectif P. formel
Appelant Appelé

Programme : Donnée Procédure

Procédure ou
Résultat
ou Fonction
Fonction Données-Résultats

Lors de l’utilisation des sous-programmes, une transmission de données et de résultats est mise
en jeu. On distingue :

17
Chapitre I Rappel et conventions syntaxiques

 Les paramètres formels : utilisés dans la définition de la fonction ou procédure. Ce sont

des variables qui peuvent prendre plusieurs valeurs.
 Les paramètres effectifs : ce sont les paramètres utilisés de façon effective dans un appel de
fonction ou de procédure (ce sont les valeurs qu’on utilisera pour effectuer les calculs dans
la fonction ou procédure)
Le nombre de paramètres effectifs doit être égal au nombre de paramètres formels.

Le paramètre effectif doit avoir le même type ou un type compatible avec le paramètre formel
correspondant.

La correspondance entre paramètres effectifs et paramètres formels se fait dans l’ordre de leur
apparition dans les deux listes.

b. Les modes de passage de paramètres

Il existe 3 modes de passage de paramètres :

 Donnée : dans ce mode de passage, le paramètre doit porter une valeur significative avant
l’exécution, il est nécessaire aux calculs effectués dans le sous-programme mais il ne sera
pas modifié par celui-ci. C'est le seul mode de passage de paramètre qui admet l'utilisation
d'une constante. Ce mode de passage est exprimé par le mot clé : Don
 Résultat : dans ce mode de passage, le paramètre est destiné à recevoir un résultat. Les
instructions du sous-programme affectent obligatoirement une valeur à ce paramètre qui n’a
pas nécessairement une valeur significative avant l’exécution. Par contre, après l’exécution
du sous-programme, il doit comporter une valeur significative. Ce mode de passage de
paramètre est exprimé par le mot clé : Res
 Donnée-résultat : dans ce mode de passage, le paramètre est utilisé dans les calculs faits
dans le sous-programme. Il est en même temps utilisé pour recevoir un résultat. Il doit donc
avoir une valeur significative avant et après exécution. Ce mode de passage de paramètre est
exprimé par le mot clé : DonRes
Exemples :

1/
Procédure AfficheMax (X :entier, Y :entier)
Utilisation : AfficheMax (A,B)
Les paramètres formels sont : X et Y.
Les paramètres effectifs sont : A et B.
X et Y sont des paramètres données. Donc on déclarera la procédure AfficheMax comme suit :

18
Chapitre I Rappel et conventions syntaxiques

Procédure AfficheMax (Don X , Y :entier)

2/
Fonction Max(X, Y : entier) : entier
Utilisation : C Max(A, B)
Les paramètres formels sont : X et Y.
Les paramètres effectifs sont : A et B.
X et Y sont des paramètres données. Donc on déclarera la fonction Max comme suit :
Fonction Max(Don X, Y : entier) : entier

3/
Soit la procédure Permute qui permute deux entiers X et Y.
Procédure Permute (DonRes X, Y :entier)

19