Cours Algorithmique Niveau 2 PDF

Ministère de l’Enseignement Supérieur, de la Recherche Scientifique et de la Technologie
Direction Générale des Etudes Technologiques
Institut Supérieur des Etudes Technologiques de Beja
Département TECHNOLOGIES DE l’INFORMATIQUE
Matière :
Algorithmiques & structures de données
Mots-clés du Support
Algorithme, les Fonctions, les Procédures, la Récursivité, les Enregistrements, les
Pointeurs, Structure de données, Structures de données linéaires, les Fichiers, les Listes, les
Piles, les Files, Structures de données ramifiées, les Arbres, les Graphes, Parcours en
largeur, Parcours en Profondeur, Algorithmes de Recherche, le Tri, les Algorithmes de tri,
la complexité, etc.
Support de cours adressé aux étudiants du réseau ISETs et aux autres

étudiants de niveaux équivalents.
Réalisé par le groupe Unité d’Enseignement Programmation2:

ARFAOUI Olfa LANDOLSI Yosra
Bn KHADIJA Maali LARIBI Fatma
El KAMEL Ali MENSI Ali (coordinateur

du groupe)
JENDOUBI Karim
TAYACHI Ahlem
ème
Année universitaire : 2 Semestre 2008-2009
Equipe UE Programmation 2 Page 1

Table des matières
CHAPITRE 1 LA RECURSIVITE ........................................................................... 8
CHAPITRE 2 LES ENREGISTREMENTS.............................................................17
CHAPITRE 3 LES POINTEURS ...........................................................................23
CHAPITRE 4 LES LISTES ...................................................................................33
CHAPITRE5 LES PILES ET LES FILES .............................................................41
CHAPITRE 6 LES ARBRES ET LES GRAPHES .................................................48
CHAPITRE 7 LES ALGORITHMES RECURSIFS DE RECHERCHE ...................60
CHAPITRE 8 LES ALGORITHMES DE TRI .........................................................69
CHAPITRE 9 LA COMPLEXITE DES ALGORITHMES........................................79
Equipe UE Programmation 2 Page 2

ISET Béja Cours Algorithmique 2
Fiche de Présentation
ALGORITHMIQUE 2 ET STRUCTURES DE DONNEES
Spécialité : Technologies de l’informatique

Population : Etudiants de réseau ISETs.
Niveau : semestre2
crédits : 45 heures par semestre
Charges horaires : 3 Heures par semaine sur 15 semaines
Nature cours : Cours Intégrés
Pré-requis : Informatique de base & Algorithmique1
Langue : Français
Objectifs du cours
 Fournir aux étudiants des bases rigoureuses en algorithmique, en insistant sur l'aspect
scientifique de la discipline.
 Initier les concepts de récursivité, de Pointeur, de la gestion dynamique de la mémoire, de la
complexité d’un algorithme, etc.
 Présenter les structures de données typiques, à savoir les listes, les piles, les files, les arbres et
les graphes, ainsi que les algorithmes de traitement qui leur sont associés.
 Exploiter les caractéristiques de ces structures pour appliquer des algorithmes de recherche
récursifs.
 Formuler les algorithmes de quelques types de tri à savoir le tri par tas, le tri par insertion…
 Comprendre la notion de complexité et apprendre la méthode d’estimation de la complexité
des algorithmes.
 Stimuler la créativité des étudiants en les incitant à exploiter les solutions vues au cours pour
en élaborer de nouvelles.
Cours 1 : Récursivité 3
Evaluation
 Contrôle continu : il est compté comme 38% de la note finale du candidat et regroupe les notes
suivantes :
 La note de mini projet : chaque candidat est appelé à participer avec un autre binôme
dans un mini projet. Chaque deux binômes sont appelés à présenter leur travail à la fin
du semestre.
 Les notes de tests : un nombre variable de tests au cours des séances de cours.
 Une note pour l’assiduité des candidats
 La note du devoir surveillé : un examen partielle possible de le faire à partir de la
cinquième semaine de cours.
 Examen Final : il s’agit d’un examen de synthèse qui aura lieu à la fin du semestre. Cet
examen est compté comme 62% de la note finale du candidat.
Moyens Pédagogiques
 Support de cours papier.
 Support de cours numérique.
 Série de travaux dirigés : à la fin de chaque chapitre on doit avoir une série d’exercices.
 Sujets d’examens antérieurs.
Répartition horaire des cours

Suite à une réunion des membres de l’équipe de l’unité d’enseignement Programmation2, et en
tenant compte des prédictions de l’avancement au niveau des travaux pratiques du module Atelier
Programmation2 associés aux notions de cours de ce module , la répartition des chapitres est fixée selon
le tableau suivant.
N° Titre Semaine(s) Responsable(s)
1 La récursivité S1-S2 Karim Jendoubi
2 Les enregistrements S3 Karim Jendoubi et

Ali Mensi
3 Les pointeurs S4 Olfa Arfaoui
4 Les listes S5 Ali Mensi
5 Les piles et les files S6-S7 Yosra Landolsi
6 Les arbres et les graphes S8-S9 Fatma Laribi
Les algorithmes récursifs de

7 S10-S11 Ahlem Tayachi
recherche
8 Les algorithmes de tri S12-S13 Maali Ben Khadija
La complexité des
9 S14 Ali El kamel
algorithmes
Répartition horaire des cours
Le programme est planifié sur 14 semaines seulement. Nous avons décidé de laisser une dernière
semaine pour remédier les problèmes de décalage. Si tout va bien, cette semaine sera réservée pour une
révision à l’examen final.
Supports et Références Bibliographiques
[1] Le Langage C, Christian Bac, 24 février 2004.
[2] Algorithmique et Bases de la Programmation, Hamrouni M. Kamel, Année : 2004-05.
[3] Algorithmique – Niveau 1, Belhassen GUETTAT, 1er Semestre 2003-2004.
[4] Introduction au langage C norme iso / ansi , Bernard Cassagne, 2.1 de juin 1998
[5] Introduction à l'informatique et programmation en langage C, Jean Fruitet, 1999.
[6] Initiation au Langage C Niveau 1, M . Berthomier Eric, Version 1.1 du 13 Mars 2000
[7] Brian W. Kernighan, Dennis M. Ritchie Programmieren in C, 2. Ausgabe, ANSI-C Carl

Hanser Verlag, 1990.
[8] Autoformation, Le Langage C, Joelle Maillefert.
[9] Support de cours : Programmation C – II, Niveau 2 Par BEN ROMDHAN Mourad
[10] Claude Delannoy Exercices en Langage C Edition EYROLLES, 1992.
[11] The C programming language , Second Edition Dennis Ritchie & Brian W. Kernighan,
Edition PRENTICE HALL Informatique, 1988.
[12] Le langage C, Dominique GALLAND, Édition DUNOD Informatique, 1989.
Chapitre 1 La récursivité
1- Rappel : Les procédures

1.1 Définition
Une procédure est un sous algorithme réalisant un traitement sur une partie des données d’un
algorithme principal. Elle permet de décomposer un algorithme en sous algorithmes ou modules plus
simples et donc de simplifier la lecture et le suivi d’un algorithme. Une procédure est définie avant le
code de l’algorithme principal puis elle est appelée par son nom suivi de ses paramètres s’ils existent.
1.2 Syntaxe
Remarque :
 nomP est le nom de la procédure.

 type est un type de donnée simple ou composé.
 P1 … Pn sont les paramètres de la procédure.
 Une procédure peut être appelée à partir de l’algorithme principal ou d’une autre procédure.
1.3 Schéma d’exécution

L’appel de la procédure se fait en utilisant son nom suivi de ses paramètres séparés par des virgules et entourés
par des parenthèses. Quand on appelle une procédure le contrôle se trouve automatiquement transféré au début
de la procédure. Quand toutes les instructions de la procédure ont été exécutées le contrôle retourne à
l’instruction qui suit immédiatement l’instruction d’appel de la procédure.
Exemple :
Fig : schéma d’exécution d’un programme
2- Les variables et les paramètres

2.1 Variable locale
Une variable est dite locale si elle est définie dans la partie de déclaration des variables propre à la
procédure. Elle n’est accessible que dans la procédure où elle a été définie. Dans l’exemple précédent X1
est une variable locale à la procédure proc.
2.2 Variable globale
Une variable est dite globale si elle est définie au niveau de l’algorithme principal qui appelle la
procédure c’est à dire une variable utilisée par la procédure et qui n’est pas déclarée dans cette procédure.
Une variable globale peut être utilisée n’importe où, à l’intérieur ou à l’extérieur d’une procédure. On
parle donc de sa visibilité : on dit qu’elle est visible par l’algorithme principal et par toutes les autres
procédures utilisées. Dans l’exemple précédent V1 est une variable globale.
L’échange d’information entre la procédure et l’algorithme peut se faire à travers les variables
globales. Cette méthode peut changer le contenu de la variable à l’intérieur de la procédure ce qui peut
affecter l’exécution de l’algorithme principal. Pour résoudre ce problème on fait recours à l’emploie des
paramètres qui offrent une meilleur approche pour l’échange d’information entre la procédure et le
l’algorithme principal. Le transfert d’une donnée se fait entre un paramètre effectif et un paramètre
formel.
2.3 Paramètre formel
Un paramètre formel est un paramètre défini dans la déclaration de la procédure c'est-à-dire dans
l’entête de procédure. Dans l’exemple précédent P1 est un paramètre formel à la procédure proc.
2.4 Paramètre effectif
Un paramètre effectif est un paramètre utilisé pendant l’appel de la procédure. Dans l’exemple
précédent V1 est un paramètre effectif pour la procédure proc. Lors de l’appel de la procédure et avant de
commencer son exécution les paramètres formels sont initialisés par les valeurs des paramètres effectifs.
Ainsi dans l’exemple précédent P1 est initialisé avec la valeur de V1.
2.5 Exemple
A, B: 2 paramètres effectifs
x, y: 2 paramètre formels
A, B : variables globales
m: variable locale
3- Passage des paramètres

3.1 Passage des paramètres par valeur
Le mode de transfert de paramètre entre l’algorithme appelant et la procédure appelé définit un moyen
d’échange de donnée entre eux. Dans le passage des paramètres par valeur qui représente le 1 er mode, les
paramètres formels de la procédure reçoivent les valeurs des paramètres effectifs, ainsi avant l’exécution
de la procédure, ses paramètres formels sont initialisés avec les valeurs des paramètres effectifs. Tout
changement des paramètres formels dans la procédure ne change pas les valeurs des paramètres effectifs
associés. Dans l’exemple précédent le mode de passage des paramètres pour la procédure max est par
valeur, les paramètres formels sont x et y, ils sont initialisés par les valeurs de A et B.
3.2 Passage des paramètres par variable

Contrairement au mode de passage des paramètres par valeur, dans le mode de passage des paramètres
par variable toute modification dans la valeur du paramètre formel passé par variable, implique une
modification de la valeur du paramètre effectif correspondant. Ainsi ce 2 ème mode est plus général que le
1er il prend les caractéristiques du 1er et ajoute la possibilité de modifier les variables de l’algorithme
appelant à partir de la procédure.
Pour définir un passage de paramètre par variable on ajoute le mot clé « var » dans la définition des
paramètres de la procédure avant les paramètres pour lesquels on veut définir ce mode.
Un paramètre passé par variable ne peut être qu’une variable il ne peut pas être une constante ou une
expression.
3.3 Exemple
4- Les fonctions
Nous présentons dans ce paragraphe le concept des fonctions. Pour ce la, nous donnons la définition et la
syntaxe d’une fonction et nous terminons par un exemple illustratif de l’utilisation des fonctions.
4.1 Définition
La fonction possède la même définition que la procédure mais avec seulement 2 différences. D’abord
une fonction possède une valeur de retour. Ensuite la fonction est utilisée dans l’algorithme principal
comme une variable contrairement à la procédure qui est utilisé comme une instruction.
4.2 Syntaxe
Remarque :
 Le type de la fonction doit être le même que le type de la variable vf utilisé dans l’algorithme principal pour
recevoir la valeur de retour de la fonction.
4.3 Exemple
5- Algorithmes récursifs
5.1 Définition récursive
Une définition récursive est définie en fonction d'un objet ou d'une action de même nature mais de
complexité moindre.
Par exemple, on peut définir le factoriel d'un nombre « n » positif de deux manières:
 définition non récursive (ou itérative):

n ! = n * n-1 * ... 2 * 1
 définition récursive:
On remarque qu’une définition récursive est composée de deux parties: une partie strictement
récursive et une partie non récursive (base) servant de point de départ à l'utilisation de la définition
récursive.
5.2 Fonctions récursives
5.2.1 Définition
Comme pour les définitions récursives, les fonctions récursives sont des fonctions qui sont appelées
depuis leur propre corps de fonction, soit directement soit indirectement, à travers une ou plusieurs
fonctions relais. Si la fonction P appelle directement P, on dit que la récursivité est directe. Si P appelle
une fonction P1, qui appelle une fonction P2 et qui enfin appelle P, on dit qu'il s'agit d'une récursivité
indirecte.
Si la fonction P appelle dans son propre corps la fonction P, il est logique de penser que l’exécution ne
s'arrêtera jamais. Il est donc primordial qu'une des branches de la fonction P permette de stopper la
récursivité.
5.2.2 Exemple
On veut calculer la somme des n premiers entiers positifs. Une définition récursive de cette somme
serait:
Ce qui se traduit par la fonction récursive suivante:
Il est clair que sans le test « Si (n = 1) » cette fonction ne s'arrêterait jamais.
5.2.3 Exécution d’une fonction récursive

Supposant qu'on appelle la fonction somme (4). Puisque 4 ≠ 1, cette fonction va s'appeler elle-même avec la
valeur 3 (somme (3)). Ce nouvel appel se termine en renvoyant une valeur (dans cet exemple la valeur retournée
est 6 = 3 + 2 + 1). Cette valeur sera ajoutée à la valeur 4 et l'appel de somme (4) retournera la valeur 10 (4 + 6).
L'appel somme (3) suivra le même processus et appellera somme (2) qui lui-même appellera à somme (1) qui
retourne 1.
5.2.4 Variables locales et paramètres des fonctions récursives

Lorsqu'une fonction récursive définit des variables locales, un exemplaire de chacune d'entre elles est créé à
chaque appel récursif de la fonction.
Dans notre exemple somme (4), la variable locale m est créée 4 fois. Ces variables sont détruites au fur et à
mesure que l'on quitte la fonction comme toute variable locale d'une fonction.
Il en est de même des paramètres des fonctions.
Chapitre 2 Les enregistrements
1- Les types de base

Toute variable utilisée dans un algorithme doit avoir un type qui caractérise l’ensemble de valeurs qu’elle peut
prendre dans cet algorithme, ce type peut être un type de base (prédéfini) ou un type composé qui est défini par
l’utilisateur.
Les types de base se divisent en 2 catégories : les types simples et les types complexes. Ils sont tous des types
prédéfinis, c'est-à-dire des types définis par le langage de programmation.
1.1 Types simples

Les types simples qui peuvent être utilisés pour représenter les variables d’un algorithme sont :
 Entier : ce type représente toute variable qui peut prendre des valeurs entières positives ou négatives. Pour
utiliser ce type, on utilise le mot clé « entier ».
 Reel : ce type représente toute variable qui peut prendre des valeurs réelles. Pour utiliser ce type, on utilise le
mot clé « reel »
 Caractere : ce type représente toute variable qui peut prendre tout caractère qu’on peut saisir avec un clavier
standard. Pour utiliser ce type, on utilise le mot clé « caractere »
 Booleen : ce type représente toute variable à deux valeurs VRAI ou FAUX. Pour utiliser ce type, on utilise le
mot clé « booleen »
1.2 Types complexes

Les types simples servent pour définir les types complexes qui permettent de représenter des structures de
données plus compliqués. Les types complexes les plus utilisés sont :
 Tableau :
o Une variable de type Tableau est formée par l’union de plusieurs cases mémoires. Chacune des cases
contient le même type.
o la déclaration d’un tableau se fait comme suit : « nom : Tableau [i_deb .. i_fin] de type ».
o i_deb et i_fin représentent l’indice de début et l’indice de fin du tableau.
 Chaîne de caractères :
o C’est la concaténation de plusieurs caractères qui finie par le marqueur de fin de la chaîne. C’est ainsi un
tableau de caractères qui contient comme dernier caractère un caractère spécial pour représenter le
marqueur de fin de la chaîne.
Cours2 : Enregistrements Page 17

o La déclaration d’une chaîne de caractères se fait comme suit : « nom : chaine [ Max ] »
o Max est le nombre maximum de caractères dans la chaîne.
2- Définition d’un enregistrement

2.1 Utilité
Contrairement aux types de base les types composés sont défini par l’utilisateur. Les types de bases servent
pour définir de nouveaux types composés. Ces nouveaux types servent pour représenter des structures de
données plus complexes qu’on ne peut pas représenter par les types de bases.
Par exemple si on veut représenter les données relatives à une personne telle que le nom et l’âge dans une seule
variable ou une seule structure de donnée, on ne peut pas faire ça avec les types de bases et particulièrement
avec les tableaux. On peut utiliser un nouveau type appelé enregistrement qui contient 2 champs, un pour
représenter le nom de type chaîne de caractère et le 2ème pour représenter l’age de type entier. On remarque
qu’on ne peut pas représenter la personne par un tableau car elle est formée de 2 types différents.
Ainsi on définit le type personne par un enregistrement comme suit :
2.2 Définition
L’enregistrement est une structure de données (ou un type) composée, qui est formé par plusieurs autres
structures de données de nature différentes. Il permet ainsi de les regrouper dans une seule structure de
données.
2.3 Syntaxe
Avec :
Nom : représente le nom de l’enregistrement.

Champs 1…N : les noms des champs qui constituent l’enregistrement.
Type : est le type de chaque champ.
2.4 Représentation
Les enregistrements sont représentés en mémoire sous forme de suite de zones contiguës qui servent chacune à
représenter les différents champs, ces zones sont de taille différentes puisque chaque champ a un type différent.
Par exemple l’enregistrement personne sera représenter en mémoire comme suit :
3- Utilisation d’un enregistrement
3.1 Déclaration
La déclaration d’un enregistrement se fait comme étant un nouveau type définit par l’utilisateur dans
l’algorithme, il doit être déclaré dans la partie Type avant d’être utilisé comme type de variable dans la partie Var.
3.2 Accès
L’enregistrement qui est une structure de données composée de plusieurs champs n’est pas accessible dans sa
totalité, donc pour faire un accès à un enregistrement on accède à tous les champs un par un. Et pour utiliser un
champ, on écrit le nom de la variable de type enregistrement suivi de « point » suivi du champ auquel on veut
accéder : Nom_enregistrement.champ_desire
3.3 Exemple
On veut écrire un algorithme qui lit le nom, le prénom et la moyenne générale d’un étudiant puis il affiche si cet
étudiant a réussi ou non selon que sa moyenne est >= 10 ou non. Utiliser un enregistrement pour représenter
l’étudiant.

4- Les types abstraits

Les enregistrements permettent de représenter des structures de données complexes et formées par des
types non homogènes. Mais ils ne présentent pas une abstraction au niveau des structures de données de
l’algorithme. Pour résoudre ce problème on fait recours à une généralisation du type enregistrement par
les types abstraits. Ce qui donne une indépendance vis-à-vis d’une implémentation particulière et les
données sont considérées d’une manière abstraite.
4.1 Définition
Un type abstrait permet de représenter les données, les opérations faites sur ces données et les
propriétés de ces opérations, dans une même structure de données.
4.2 Exemple
Si on veut représenter un Compte Bancaire par un type abstrait il sera composé des données et des
opérations concernant les Comptes Bancaires :
 Les données seront :
 Une variable pour représenter le numéro du compte
 Une variable pour représenter le solde
 Une variable pour représenter le nom du propriétaire
 Les opérations sur les comptes bancaires:
 Une fonction pour créer un nouveau compte
 Une fonction pour consulter un compte
 Une procédure pour débiter un compte
 Une procédure pour créditer un compte
 Les propriétés des opérations :
 Pour débiter il faut que le solde soit positif
 Seuls les salariés peuvent créer des comptes.
4.3Signature d’un type abstrait

La signature d’un type abstrait de données est définie par :
 Les noms des types utilisés pour représenter les données (réels, entiers, …).
 Les noms des opérations et leurs profils.
La signature décrit la syntaxe du type abstrait mais elle ne le définie pas réellement.

Ainsi pour l’exemple précédent la signature est :
 Les types des données :
 entier
 reel
 chaîne [20]
 les opérations et leurs profils :
 Creer_compte : chaine[20]  entier
 Consulter _compte : entier  reel
 Debiter : entier * reel
 Crediter : entier * reel


Chapitre 3 Les pointeurs
1 Introduction
Le but de cette partie est de gérer un ensemble fini d’éléments dont le nombre varie au cours de
l’exécution du programme. Les éléments de cet ensemble peuvent être de différentes sortes : nombres
entiers ou réels, chaînes de caractères ou des objets informatiques plus complexes comme des
identificateurs de processus ou les expressions arithmétiques.
On ne s’intéressera pas aux éléments de l’ensemble en question mais aux opérations que l’on effectue sur
cet ensemble. Cette gestion des ensembles doit, pour être efficace, répondre à deux critères parfois
contradictoires : un minimum d’espace mémoire utilisé et un minimum d’instructions élémentaires pour
réaliser une opération.
2 Les variables dynamiques

Comme son nom le laisse supposer, une variable dynamique va "bouger", en d'autres termes, sa taille est
variable tout au long du programme. On ne peut pas savoir à l'avance quelle place elle occupera en
mémoire, pire même, elle ne va pas occuper la même place tout au long du déroulement du programme!
Jusqu’ici, nous avons utilisé des variables dites « statiques »
Une variable est caractérisée par les propriétés suivantes :
 Elle est déclarée en tête du bloc où elle est utilisée

 Elle occupe un espace mémoire dont la taille est fixée dès le début pour qu’on y place ses valeurs
 L’accès à la valeur se fait par le nom de la variable
Au contraire, une variable dynamique est caractérisée par les propriétés suivantes :
 Elle peut être créée et détruite au cours de l’exécution du bloc dans lequel elle est déclarée
 L’espace mémoire rendu libre peut être récupéré
 L’accès à la valeur se fait par un pointeur
3 Les pointeurs
Prenons par exemple un tableau qui contient l'ensemble des livres d'une bibliothèque: ce nombre de livres
ne sera pas fixe, puisqu'on peut ajouter de nouveau ouvrages, et en supprimer également.
Cours 3 : Pointeurs Page 23

On ne va donc pas pouvoir utiliser une déclaration classique à l'aide d'un type, nous allons avoir recours à
une autre variable, c’est le pointeur, qui contiendra l'adresse de la variable dynamique, qui nous permettra
donc d'accéder à l'endroit où se trouve la variable, d'en lire le contenu, de l'effacer, ou de la modifier.
3.1 Définition
Un pointeur est une variable statique dont les valeurs sont des adresses. Une variable dynamique pointée
par P sera noté P^.
Comme nous l'avons vu, un pointeur est une variable qui permet de stocker une adresse, il est donc
nécessaire de comprendre ce qu'est une adresse.
3.1.1 La notion d’adresse

Lorsque l'on exécute un programme, celui-ci est stocké en mémoire, cela signifie que d'une part le code à
exécuter est stocké, mais aussi que chaque variable que l'on a défini a une zone mémoire qui lui est
réservée, et la taille de cette zone correspond au type de variable que l'on a déclaré.
En réalité la mémoire est constituée de plein de petites cases de 8 bits (un octet). Une variable, selon son
type (donc sa taille), va ainsi occuper une ou plusieurs de ces cases (une variable de type char occupera
une seule case, tandis qu'une variable de type long occupera 4 cases consécutives).
Chacune de ces « cases » (appelées blocs) est identifiée par un numéro. Ce numéro s'appelle adresse.
On peut donc accéder à une variable de 2 façons :
 grâce à son nom

 grâce à l'adresse du premier bloc alloué à la variable
Il suffit donc de stocker l'adresse de la variable dans un pointeur (il est prévu pour cela) afin de pouvoir
accéder à celle-ci (on dit que l'on « pointe vers la variable »).
Le schéma ci-dessus montre par exemple par quel mécanisme il est possible de faire pointer une variable
(de type pointeur) vers une autre. Ici le pointeur stocké à l'adresse 24 pointe vers une variable stockée à
l'adresse 253 (les valeurs sont bien évidemment arbitraires).

3.1.2 Intérêt des pointeurs

Les pointeurs ont un grand nombre d'intérêts :
 Ils permettent de manipuler de façon simple des données importantes (au lieu de passer à une
fonction un élément très grand en taille, on pourra par exemple lui fournir un pointeur vers cet
élément).
 Les tableaux ne permettent de stocker qu'un nombre fixé d'éléments de même type. En stockant
des pointeurs dans les cases d'un tableau, il sera possible de stocker des éléments de taille diverse,
et même de rajouter des éléments au tableau en cours d'utilisation (c'est la notion de tableau
dynamique qui est très étroitement liée à celle de pointeur).
 Il est possible de créer des structures chaînées.
3.2 Déclaration d’une variable pointé

Le type de la variable pointée est appelé type de base. La déclaration d’une variable de type pointeur a
pour effet la réservation d’une case mémoire qui va contenir l’adresse de la variable pointé.
Exemple :
La variable pointeur P a pour valeur l’adresse « 43 ». Elle pointe sur l’espace mémoire « P^ » à l’adresse
43 dont le contenu est le caractère « T ».
On déclare un pointeur en précédant son type de base par le caractère « ^ ». Par exemple pour déclarer un
pointeur appelé P sur une variable de type caractère on écrit : P : ^ caractere
3.3 Création d’une variable pointé
3.3.1 Pointeur vers un seul élément

La déclaration d’une variable de type pointeur a pour effet la réservation d’une case mémoire qui
va contenir l’adresse de la variable pointé. Par exemple si on déclare 2 pointeurs Pe et Pf le 1 er vers une
variable de type entier et le 2ème vers une variable de type réel ceci implique la création de deux variables
qui contiennent respectivement l’adresse d’un entier et l’adresse d’un réel comme suit :

Pour utiliser la variable pointée il faut d’abord la créer, ce qui a pour effet de réserver un bloc en
mémoire capable de stocker la valeur de cette variable.
Par exemple pour créer la variable pointé par Pe on écrit : Allouer (Pe), et pour créer la variable pointé
par Pf on écrit : Allouer (Pf).
On remarque que la taille de la variable pointé par Pf est plus grande que la taille de la variable pointé par
Pe puisque la 1ère va contenir la valeur d’un entier et la 2ème va contenir la valeur d’un réel.
L’instruction Allouer (P) :
 Réserve un bloc mémoire de la taille adéquate pour contenir la valeur de la variable pointée par P.
 Récupère l’adresse de ce bloc et la met dans la variable P.
Exemple :

3.3.2 Pointeur vers un tableau d’éléments

On utilise l’instruction Allouer (T, N) pour créer un tableau dynamique de N cases. T doit être déclaré
comme un pointeur sur le type des éléments du tableau. Dans le cas particulier où les éléments du tableau
sont des caractères on dit qu’on a fait une allocation dynamique pour une chaîne de caractères.
L’instruction Allouer (T, N) :
 Réserve un bloc mémoire pour contenir un tableau de N cases.

 Récupère l’adresse de la 1ère case de ce tableau et la met dans la variable T.
Exemple :
3.4 Utilisation d’une variable pointé
3.4.1 Syntaxe
Pour accéder à la variable pointé par un pointeur appelé P on utilise l’opérateur ^. Donc « P^ » désigne la
variable pointée par P.
3.4.2 Exemple
L’algorithme suivant stocke la valeur 10 dans une variable de type pointeur.

3.5.1 Syntaxe
Lorsqu’une variable pointée n’a plus d’utilité, il est possible de la supprimer et de rendre disponible
l’espace mémoire qu’elle occupe. L’instruction qui réalise cette tache est « Liberer ».
Si on a déclaré un pointeur appelé P, l’instruction : « Liberer (P) » supprime la variable pointé par P et
libère l’espace mémoire occupé par cette variable. Par contre la variable pointeur « P » n’est pas
supprimée mais son contenu n’est plus l’adresse de la variable pointé mais une adresse non significative.
3.5.2 Exemple
L’exemple suivant montre l’effet de l’instruction « Liberer » sur la mémoire.
Remarque : l’utilisation de la variable pointé après l’instruction Liberer provoque une erreur.
3.5 Opérations sur les pointeurs
3.5.1 Initialisation
Pour initialiser un pointeur on peut lui affecte une valeur constante appelé « Nil », cette constante n’est
pas une valeur d’une adresse mémoire, mais elle signifie que le pointeur ne pointe sur rien.
Ainsi si on déclare un pointeur P vers un entier il sera initialisé comme suit : P  Nil
Et on le représente par le schéma suivant :
On peut aussi initialiser un pointeur à partir d’un autre pointeur comme le montre l’exemple suivant :

Supposons qu’on soit dans la situation initiale illustrée par la figure a :
Figure a
Si l’instruction : PQ est exécutée, nous passerons à la nouvelle situation illustrée par la figure b.
Dans ce cas, on a : P^ = Q^ = « Sousse »
Et si l’on modifie la valeur de Q^, P^ sera également modifie et restera égal à Q^.
Figure b
Par contre, si l’instruction : P^Q^ est exécutée. On passe à la nouvelle situation illustrée par la figure
c.
Figure c
Dans ce cas, on a également P^ = Q^ = « Sousse »
Mais si l’on modifie la valeur de Q^, P^ ne sera pas modifié.
3.5.2 Affectation d’un pointeur à un autre

Il ne faut pas confondre entre les opérations sur les pointeurs avec les opérations sur les variables pointées

Le contenu d’une variable pointeur peut être recopié dans une autre variable pointeur grâce à l’instruction
d’affectation, à condition que les 2 pointeurs soient de même sous type.
Soient 2 pointeurs P1 et P2 qui pointent vers le même sous-type par exemple entier. On peut écrire :
« P1  P2 » : cela a pour effet de copier l’adresse contenu dans P2 dans le pointeur P1.
Donc P1 et P2 vont pointer vers la même variable.
3.5.3 L’opérateur d’adresse

L’opérateur d’adresse permet de récupérer l’adresse en mémoire d’une variable il se note « &». Comme
le pointeur contient l’adresse d’une variable pointeur on peut utiliser l’opérateur d’adresse pour affecter à
un pointeur l’adresse d’une autre variable et ainsi il va pointer vers cette nouvelle variable. La syntaxe est
la suivante : « pointeur  & variable »
Exemple :

3.5.4 Comparaison de pointeurs

On peut comparer 2 pointeurs entre eux avec l’opérateur = ou <> à condition qu’ils ont le même sous
type. Et on peut comparer la valeur Nil à n’importe quel pointeur quelque soit son sous-type.
On peut aussi comparer les valeurs des variables pointées par 2 pointeurs.


Chapitre 4 Les listes
1- Introduction
Le principal problème des données stockées sous forme de tableaux est que celles-ci doivent être
ordonnées : le "suivant" doit toujours être stocké physiquement après. Un tableau correspond à une
gestion dans un cahier : un adhérent par page. Supposons qu’on veut stocker les adhérents par ordre
alphabétique. Si un nouvel adhérent se présente, il va falloir trouver où l'insérer, effacer toutes les pages
suivantes pour les réécrire une page plus loin, puis insérer le nouvel adhérent. Pour résumer, la faiblesse
d’un tableau provient de son aspect statique :
Une fois qu’il est déclaré, sa taille ne change plus.

Il n’est pas possible de placer une information à une position précise du tableau sans écraser
l’information qui s’y trouve, à moins de la déplacer elle-même.
Une meilleure solution permettant de contourner ces difficultés liées aux tableaux, que nous
venons d’identifier, consiste à introduire la structure de liste chaînée : les pages sont numérotées, sur
chaque page est indiquée la page de l'adhérent suivant, sur le revers de couverture on indique l'adresse du
premier. Ainsi, l'insertion d'un nouvel adhérent se fera avec le minimum d'opérations.
2- Définition
Les listes font parties des structures de données abstraites très utilisées dans les programmes. Une
structure de données abstraite est un type de donnée défini par l’utilisateur sous forme de deux
composantes une pour représenter les données et une pour représenter les opérations d’accès aux données
et ses caractéristiques.
Une liste stocke un ensemble de données et permet de parcourir cet ensemble du début à la fin dans
l'ordre. C’est une suite finie d'éléments, lorsque elle n’est pas vide, son premier élément est appelé tête et
la suite constituée des autres éléments est appelée queue.
Les listes servent pour représenter des structures de données dont la taille change souvent ou pour
stocker des données dans l'ordre en ayant la possibilité de les mettre à jour quand il y a des changements.
3- Opérations sur les listes

Il existe un certain nombre d'opérations classiques sur les listes.
 Le test si la liste est vide.
Cours 4 : Listes Page 33

 L’ajout d’un élément selon les différentes versions suivantes:
o au début de la liste
o à la fin de la liste
o à un rang donné
 La recherche d’un élément:
o résultat booléen
o résultat = rang de la première occurrence
o résultat = nombre d'occurrences
 La suppression d’un élément:
o caractérisé par sa valeur
o caractérisé par son rang
 Le calcul de la longueur d'une liste (nombre d'éléments)
4- Représentation
4.1 Représentation graphique
4.2 Représentation des données

La structure de donnée qui permet de représenter une liste chaînée dans le cas général est déclarée comme
suit :
Ainsi le type Liste est un pointeur vers le type Cellule qui est un enregistrement formé de deux champs :
 le 1er contient la valeur de l’élément donc le type peut être un type quelconque
 le 2ème contient un pointeur vers la cellule suivante c'est-à-dire il contient l’adresse de cette cellule.
La dernière cellule ne pointe vers rien donc elle doit contenir la valeur Nil.

Le type Liste contient un pointeur vers le type Cellule qui contient l’adresse du 1er élément de la liste.
5- Algorithmes de quelques opérations sur les listes

Pour simplifier on va travailler sur une liste dont les valeurs sont de type entier.
Donc la définition du type liste sera comme suit :
5.1 ListeVide
La 1ère fonction de base qu’on doit écrire pour pouvoir manipuler des données de type liste est la fonction
ListeVide () qui prend en entrée une liste et retourne vrai si elle est vide et faux sinon.
5.2 PosFin
La fonction PosFin () prend en entrée une liste et retourne un pointeur vers le dernier élément de la liste.

5.3 AjouterTete
La fonction AjouterTete () prend en entrée une valeur à ajouter en tête d’une liste donnée et retourne un
pointeur vers le début de la nouvelle liste.
Cette fonction doit créer une nouvelle variable dynamique pour contenir la nouvelle cellule, puis remplir
le champ valeur et le champ suivant de cette cellule ensuite mettre l’adresse de cette cellule dans le
pointeur vers la tête de liste et retourner cette valeur.

5.4 Ajouter_fin
La procédure Ajouter_fin() prend en entrée une valeur à ajouter à la fin d’une liste donnée.
Procedure Ajouter_fin(var liste1 : Liste, e : entier)

Var
liste2 : Liste
Debut
Si (liste1= Nil) Alors

liste1  AjouterTete(e, liste1)
Sinon
liste2  PosFin(liste1) /* parcours de la liste vers la fin */
liste2.suivant  AjouterTete(e, Nil) /*ajout de l’élèment e à la fin de la liste */

Finsi
Fin
5.5 Longueur d’une Liste
Cette fonction calcule le nombre des éléments de la liste. Elle prend comme argument à l’entrée une liste et
retourne en sortie un entier représentant la longueur de la liste.
Version itérative:
Fonction longueur(liste1 : Liste) : entier

Var
x : entier
listeAux : Liste
Début
x0
listeAux  liste1
Tantque (listeAux^.suivant <> Nil) Faire
xx+1
listeAux  listeAux^.suivant
Fintanque
Retourner (x)
Fin
Version récursive:
Fonction long(liste1 : Liste) : entier

Var
Début
Si liste1=Nil alors
Retourner (0)

Sinon
Retourner (1 + long(liste1^.suivant) )
Finsi
Fin
5.6 Chercher un élément dans la liste

Cette fonction permet de chercher si un élément appartient à une liste et retourne vrai dans ce cas sinon, la
fonction retourne faux. Ses paramètres d’entrée sont alors la liste et l’élément recherché, et son paramètre de
sortie est un booléen.
Version itérative :
Fonction appartient(x : entier, liste1 : Liste) : booleen
Var
liste2 : Liste
Début
liste2  liste1
Tantque (liste2 <> Nil et liste2^.valeur <>x)
liste2  liste2^.suivant
Fintantque
Si (liste2 <> Nil) alors
Retourner (vrai)
Sinon
Retourner (faux)
Finsi
Fin
Version récursive:
Fonction appart(x : entier, liste1: Liste) : booleen
Var
Début
Si (liste1 = Nil) alors
Retourner (faux)

Sinon
Si (x = liste1^.valeur) alors
Retourner (vrai)
Sinon
Retourner (appart(x, liste1^.suivant))
Finsi
Finsi
Fin


Chapitre5 Les piles et les files
1- Introduction
Le but de ce chapitre est de décrire des représentations des structures de données de base à savoir les piles
et les files.
2- Les piles
2.1 Présentation
Une pile est une suite de cellules allouées dynamiquement (liste chaînée) où l’insertion et la suppression
d’un élément se font toujours en tête de liste.
L’image intuitive d’une pile peut être donnée par une pile d’assiettes, ou une pile de dossiers à condition
de supposer qu’on prend un seul élément à la fois (celui du sommet). On peut résumer les contraintes
d’accès par le principe « dernier arrivé, premier sorti » qui se traduit en anglais par : Last In First Out
(figure 1).
La structuration d’un objet en pile s’impose lorsqu’on mémorise des informations qui devront être traitées
dans l’ordre inverse de leur arrivée. C’est le cas, par exemple, de la gestion des adresses de retour dans
l’exécution d’un programme récursif.
En supposant que les éléments de la pile sont des entiers, celle-ci se déclare de la façon suivante :
Cours 5 : Piles & Files Page 41

2.2 Manipulation d’une pile

D’un point de vue manipulation, les contraintes d’accès sont matérialisées par les procédures et les
fonctions suivantes :
 Procédure Initialiser (Var P : Pile) : crée une pile vide P.

 Fonction Pile_Vide (P : Pile) : Booléen : renvoie la valeur vrai si la pile est vide.
 Procédure Empiler (x : Entier , Var P : Pile) : ajoute l’élément x au sommet de la pile.
 Procédure Dépiler (Var x : Entier , Var P : Pile) : dépile le sommet de la pile et le met dans la
variable x.

3- Les Files
3.1 Présentation
Une file est une suite de cellules allouées dynamiquement (liste chaînée) dont les contraintes d’accès sont
définies comme suit :
- On ne peut ajouter un élément qu’en dernier rang de la suite.

- On ne peut supprimer que le premier élément.
L’image intuitive d’une file peut être donnée par la queue devant un guichet lorsqu’il n’y a pas de
resquilleurs. On peut résumer les contraintes d’accès par le principe « premier arrivé, premier sorti » qui
se traduit en anglais par : First In First Out (figure 2).

La structuration d’un objet en file s’impose en particulier lorsqu’une ressource doit être partagée par
plusieurs utilisateurs : il y a formation d’une file d’attente.
Un exemple est donné par le spooler d’impression qui est un programme qui reçoit, traite, planifie et
distribue les documents à imprimer dans un système multiprogrammé.
En supposant que les éléments de la file sont des entiers, celle-ci se déclare, alors, de la façon suivante :
3.2 Manipulation d’une file

D’un point de vue manipulation, les contraintes d’accès sont matérialisées par les procédures et les fonctions
suivantes :
 Procédure Initialiser (Var F : File) : crée une file vide F.

 Procédure Ajouter (x : entier, Var F : File) : ajoute l’élément x à la fin de la file.
 Procédure Extraire (Var x : entier, Var F : File) : extrait le sommet de la file et met sa valeur dans la
variable x.

Dans le cas où la file est vide, comme la queue, la tête de la file doit également pointer vers le nouvel
élément.



Chapitre 6 Les arbres et les graphes
Introduction
Les structures que nous avons considérées jusqu’à présent sont uniquement des structures linéaires, dans
le sens où :
1. chaque élément de la structure possède au plus un prédécesseur direct, et

2. chaque élément de la structure possède au plus un successeur direct.
En effet, dans un tableau de taille n, chaque case i (pour 1 < i < n) possède comme unique prédécesseur la
case i−1, et comme unique successeur la case i+1. La case 0 n’a pas de prédécesseur, mais la case 1 est
son unique successeur. La case n n’a elle pas de successeur, mais bien un prédécesseur : la case n−1.
Dans les listes, chaque élément possède un seul et unique champ next, qui référence un successeur
unique, ou qui contient une valeur conventionnelle pour indiquer qu’il n’y a pas de successeur. Par
ailleurs, la tête n’a pas de prédécesseur, et, pour tous les autres éléments e, il n’existe qu’un seul autre
élément e0 dont le champ next référence e. Enfin, les piles et files sont essentiellement des listes.
Nous allons considérer, dans ce chapitre, une généralisation de ces structures linéaires en levant la
restriction numéro 2 : chaque élément sera autorisé à avoir plusieurs successeurs tout en ayant au plus un
seul prédécesseur. On a dès lors affaire à une structure qui se ramifie, puisque, lors d’un parcours de cette
structure, on a, à chaque élément, plusieurs successeurs possibles pour « continuer le parcours ». C’est
pour cette raison que ce type de structures est appelé un arbre
1- Les Arbres
1.1 Définition
Un arbre est un ensemble de nœuds avec une relation de hiérarchie entre Père et Fils
Remarque :
- Un arbre est :
- soit un arbre vide
- soit un nœud racine et un ensemble de (sous)-arbres T1,…, Tn de sorte à ce que la racine de TI
est connecté par un lien direct à la racine.
- la racine est un nœud sans père
- la feuille est un nœud sans fils
- le nœud interne est un nœud admettant au moins un fils
Cours 6 : Arbres & Graphes Page 48
1. Exemple
1.2 Opérations sur les arbres
Il existe un certain nombre d'opérations classiques sur les arbres :

 Tester si l’arbre est vide ou non
 Créer un arbre ou une feuille
 Supprimer un nœud ou la totalité de l’arbre
 Accéder à une valeur qui se trouve dans la racine.
1.3 Implémentation
Un arbre peut être représenté par un ensemble de nœuds, chaque nœud contient une valeur et un tableau
de N cases qui contiennent des pointeurs pour les N fils du nœud. N représente le nombre maximal de fils
que peut avoir un nœud dans l’arbre.
Ainsi il se définit comme suit :

La figure ci-dessous représente un arbre avec N= 3, donc chaque nœud doit avoir au maximum 3 fils.
1.4 Les fonctions d’accès

Nous allons étudier un cas particulier des arbres : les arbres binaires. Un arbre binaire est un arbre où
tout nœud a zéro ou deux fils.
La représentation de la structure de données arbre binaire est constituée de 2 parties une pour représenter
un nœud qui contient une valeur, un pointeur vers le nœud gauche appelé aussi fils gauche et un pointeur
vers le nœud droit ou le fils droit ; et une autre partie qui constitue la représentation de l’arbre sous forme
d’un pointeur vers un nœud qui est la racine. On travaille sur les valeurs de type entier.
1.4.1 ArbreBinVide
Teste si un arbre binaire est vide ou non.
Fonction ArbreBinVide (A : Arbre_binaire) : Booleen

Debut

Si (A = Nil) Alors
Retourner (Vrai)
Sinon
Retourner (Faux)
FinSi
Fin
1.4.2 CreerFeuille
Cette fonction crée un nœud contenant une valeur et retourne son adresse en mémoire.
Fonction CreerFeuille (v : entier) : Arbre_binaire

Var
F : Arbre_binaire
Debut
Allouer (F)
F^.valeur  v
F^.fils_gauche  Nil
F^.fils_droit  Nil
Retourner (F)
Fin
1.4.3 CreerArbreBin
Cette fonction crée un arbre binaire à partir d’un sous arbre droit et un sous arbre gauche existants et
d’une valeur à mettre dans la racine enfin elle retourne l’adresse de la racine.
Fonction CreerArbreBin (v : entier, fg : Arbre_binaire, fd : Arbre_binaire) : Arbre_binaire

Var
R : Arbre_binaire
Debut
Allouer (R)
R^.valeur  v
R^.fils_gauche  fg
R^.fils_droit  fd
Retourner (R)
Fin

1.4.4 SupprimeArbreBin
Cette procédure permet de supprimer tous les nœuds d’un arbre binaire dont l’adresse de sa racine est
fournie en paramètre.
Procedure SupprimeArbreBin (A : Arbre_binaire)

Debut
Si (ArbreBinVide(A) = Faux) Alors
SupprimeArbreBin (A^.fils_gauche)
SupprimeArbreBin (A^.fils_droit)
Liberer(A)
FinSi
Fin
1.4.5 Accès à la racine

Cette fonction récupère la valeur contenue dans le nœud racine
Fonction Racine (A: Arbre_Binaire) : entier
Debut
Si (A<>Nil)
Retourner (A^.valeur)
Sinon
Ecrire (« Erreur »)
Fin Si
Fin
1.4.6 Niveau et hauteur d’un arbre :

- Le niveau d’un nœud v est le nombre de ses ancêtres
- si v est la racine alors son niveau est 0
- sinon le niveau de v est : 1+ niveau du père de v
- La hauteur d’un nœud v est définie par la définition suivante :
- si v est un nœud feuille alors sa hauteur est 0
- sinon la hauteur de v est : 1+ maximum des hauteurs de ses fils
- La hauteur d’un arbre est la hauteur de sa racine

- Nœud « b » :
- niveau=1
- hauteur=2
- hauteur de l’arbre=3
1.5 Parcours d’un arbre
1.5.1 Types de parcours

- Parcourir un arbre revient à visiter ses nœuds
- Visiter un nœud revient à effectuer un certain traitement sur ce nœud qui dépend de l’application
(affichage du contenu, modification d’un attribut, calcul d’une valeur, …)
- Il existe 2 types de parcours :
o Le parcours en profondeur qui explore l’arbre branche par branche et peut être préfixé, infixé
ou post fixé :
 Parcours préfixé : on parcourt la racine puis le sous arbre gauche enfin les sous arbres
droit.
 Parcours infixé: on parcourt le sous arbre gauche puis la racine enfin les sous arbres droit.
 Parcours postfixé: on parcourt le sous arbre gauche puis les sous arbres droit enfin la
racine.
o Le parcours en largeur qui explore l’arbre niveau par niveau en commençant par la racine.
1.5.2 Parcours Infixé

Soit un arbre binaire dont les valeurs sont des entiers on veut écrire une procédure récursive qui fait un
parcours infixé de cet arbre pour afficher les valeurs qui se trouvent dans tous les nœuds.
Procedure Infixe (A : Arbre_binaire)

Var
Debut
Si (ArbreBinVide(A) = Faux) Alors

Infixe (A^.fils_gauche)
Ecrire (A^.valeur)
Infixe (A^.fils_droit)
FinSi
Fin
1.5.3 Exemple
Si on prend l’arbre suivant :

Le parcours préfixé donne : (1,2,5,6,3,4,7)

Le parcours postfixé donne : (5,6,2,3,7,4,1)
Le parcours infixé donne : (5,2,6,1,3,7,4)
Le parcours en largeur donne : (1,2,3,4,5,6,7)
2- Les graphes
Remarquons que si nous relâchons les deux hypothèses de l’Introduction, à savoir qu’on autorise
également chaque élément à avoir plusieurs prédécesseurs, on obtient un graphe. Nous présentons dans le
paragraphe suivant la structure de données « Graphe » et les opérations de base concernant cette structure.
2.1 Définition
- Les graphes sont des structures de données qui permettent de représenter un grand nombre de données :
des réseaux, des plans, des trajets, etc.
- Un graphe orienté est un couple G=(S, A) où :
- S représente un ensemble de sommets,
- A représente un ensemble d’arcs.
Soit a  A, a= (u, v)
- u est appelé origine de a,
- v est appelé extrémité de a,
- u=prédécesseur (v)
- v=successeur (u)
- l’arc a est noté uv
2.2 Exemple
S= {1, 2, 3, 4,5}
A= {(1,2), (1,3), (2,4), (2,5), (3,1), (3,3), (4,5), (5,1)}

2.3 Implémentation :
Pour implémenter un graphe, nous allons utiliser le mode de représentation par matrice d’adjacence.
Dans un graphe, il faux pouvoir bénéficier des fonctionnalités suivantes :
- créer un graphe
- initialiser un graphe
- ajouter un arc dans un graphe
- supprimer un arc dans un graphe
- ajouter un sommet dans le graphe
- trouver le successeur d’un sommet du graphe
2.3.1 Structure de données

Pour implémenter la structure de données graphe selon la représentation matricielle, nous avons besoin
de :
- un tableau à deux dimensions pour définir le graphe
- un type de données sommet, dans ce cas un sommet est un entier (indice de ligne ou de colonne de la
matrice)
- un arc défini par deux sommets : une origine et une extrémité.
Type
Sommet=entier
Arc = Enreg
Origine : Sommet
Extrémité : Sommet
FinEnreg
Graphe =Enreg
T : Tableau [1..Max][1..Max] de Sommet
NS : entier
FinEnreg
Avec NS=Nombre de sommets dans les graphes.
Max : nombre maximal pour le nombre de sommets du graphe

2.3.2 Création du graphe

Pour créer un graphe, revient à initialiser le nombre de sommet.
Fonction CreerGraphe(n: entier): Graphe
Var G: Graphe
Debut
G.NS n
Allouer (G.T, n*n)
Retourner (G)
Fin
2.3.3 Initialisation du graphe

Cette fonction permet d’initialiser les cases de la matrice à 0, le graphe une fois crée est initialisé, ensuite
les arcs sont ajoutés au fur et à mesure des besoins de l’application.
Fonction InitialiserGraphe(G: Graphe): Graphe
Var i, j : entier
Debut
Pour i de 1 à G.NS faire
Pour j de 1 à G.NS faire
G.T[i,j]0
Fin Pour
Fin Pour
Retourner (G)
Fin
2.3.4 Ajout d’un arc

Permet d’attacher un arc préalablement crée au graphe
Fonction AjouterArc (G: Graphe, a :Arc): Graphe
Debut
Si (a.origine >G.NS ou a.extrémité>G.NS ou a.origine <1 ou a.extrémité<1) alors
Ecrire (« Arc non défini »)
Sinon
G.T [a.origine, a.extrémité] 1
Fin Si
Retourner (G)
Fin
2.3.5 Suppression d’un arc

Permet de supprimer un arc existant du graphe
Fonction SupprimerArc (G: Graphe, a: Arc): Graphe
Debut
Si (a.origine >G.NS ou a.extrémité>G.NS ou a.origine <1 ou a.extrémité<1) alors
Sinon
G.T [a.origine, a.extrémité]  0

Fin Si
Retourner (G)
Fin
2.3.6 Ajout d’un sommet

Cette fonction permet d’ajouter un sommet au graphe dans la limite de la taille prévue, et initialise les
arcs du nouveau sommet à 0.
Fonction AjouterSommet (G : Graphe, s : Sommet) :Graphe
Debut
Si (s>Max) alors
Sinon
G.NS=G.NS+1
Pour i de 1 à G.NS faire
G.T [s, i]  0
G.T [i, s]  0
Fin pour
Fin Si
Retourner (G)
Fin
2.3.7 Successeur d’un sommet

Recherche le premier successeur d’un sommet du graphe. Cette fonction retourne le premier successeur
du sommet dans le graphe, et la valeur -1 s’il n’existe pas de successeur
Fonction Successeur (G : Graphe, s : Sommet) : Sommet
Var
Trouve : booléen
succ: Sommet
Début
Si (s<1) ou (s>G.NS) alors
Ecrire (« Sommet inexistant »)
Sinon
Trouve faux
Succ 1
Tant que (succ<G.NS) et (trouve<>vrai) faire
Si (G.T[s,succ]=1) alors
Trouvevrai
Sinon
Succsucc+1
Fin Si
Fin Tant que
Si (trouve=vrai) alors
Retourner (succ)
Sinon
Retourner (-1)
Fin Si
Fin

2.3.8 Exemple
Nous allons créer le graphe suivant :
Algorithme Principal //1ère arc

A.origine  1
Type
A.extrémité  1
Sommet=entier G1 AjouterArc(G1,A) ;
Arc = Enreg
Origine : Sommet //2ème arc
Extrémité : Sommet A.origine  1
FinEnreg A.extrémité  2
Graphe =Enreg G1 AjouterArc(G1,A) ;
T : Tableau [1..Max][1..Max] de Sommet
NS : entier //3ème arc
FinEnreg A.origine  1
A.extrémité  3
Var
G1 AjouterArc(G1,A) ;
G1: Graphe
//4ème arc
A: Arc
A.origine  3
Début A.extrémité  2
G1 AjouterArc(G1,A) ;
G1CreerGraphe(3)
Fi
G1InitialisationGraphe(G1)


Chapitre 7 : Les algorithmes récursifs de recherche
1- Introduction
Un algorithme de recherche est un type d'algorithme qui cherche, parmi une liste de données, les
éléments satisfaisant certains critères.
En général, le critère de recherche porte sur la valeur d'une clé (ex : chercher un numéro de tel dans un
ensemble de personnes (une personne=nom + adresse + tel...), rechercher un mot dans un dictionnaire
(dictionnaire=mots+définitions+photo+...), ...). Cette clé peut aussi être simplement la valeur de l'objet
(recherche d'un entier dans une liste d'entier, ...).
Les algorithmes de recherche que nous allons présenter retournent un élément quelconque ayant une clé
de la valeur cherchée. Il est parfois plus utile de retourner la place de cet élément dans l'ensemble des
données (pour par exemple effectuer ensuite une suppression, ...).
2- Recherche dans une liste chainée

2.1 Recherche séquentielle
La recherche séquentielle est une méthode de recherche qui consiste à chercher un élément dans une liste
d'éléments de même type. On commence du premier élément de la liste jusqu'à ce qu'on trouve l'élément.
Si on ne le trouve pas, alors on aura parcouru toute la liste. Si on teste souvent une liste et si ces éléments
sont répartis de manière aléatoire, le nombre moyen d'éléments à comparer pour savoir si un élément est
dans la liste ou non est de : N/2 où N est le nombre d'éléments de la liste.
2.1.1 Recherche par valeur

La fonction recherche par valeur retourne un pointeur vers le premier élément trouvé dont la valeur est
passée en paramètre, ou le pointeur nil si aucun élément n'a été trouvé.
Fonction recherche_valeur (L: Liste, val:entier): Liste

Début
si (L=nil ) alors
Retourner (nil)
sinon
si (L^.valeur = val) alors
Retourner(L)
sinon
Retourner recherche_valeur (L^.suivant,val)
finsi
finsi
fin
Cours 7 : Algorithmes récursifs de recherche Page 60

2.1.2 Recherche par position

La fonction recherche par position retourne un pointeur vers l'élément ayant la position passée en
paramètre. Si la liste contient moins d’éléments que le paramètre position, le pointeur nil est retourné.
Fonction recherche_postion (L: Liste, pos:entier): Liste
Début
si (L=nil ou pos=1) alors
Retourner(L)
sinon
Retourner recherche_position (L^.suivant , pos-1)
finsi
fin
2.2 Recherche dichotomique

La recherche dichotomique consiste à décomposer une liste en deux sous-listes A et B puis à déterminer
si l'élément recherché se trouve en A ou en B. Puis on redécoupe en deux sous-listes C et D, la sous-liste
où se trouve l'élément puis on détermine si l'élément recherché se trouve en C ou en D. On répète
l'opération tant qu'on n'a pas trouvé l'élément ou que les sous-listes restantes ne soient composées plus
que d'un seul élément, puisqu'on n'a pas décomposé une liste d'un seul élément. Dans ce cas, on considère
que l'élément n'est pas dans la liste recherchée.
La méthode par dichotomie est une des méthodes de recherche la plus rapide, le problème essentiel de la
recherche dichotomique est la nécessité que les éléments de la liste soient triés (croissant ou décroissant).
Recherche dans une liste ordonnée

Dans ce paragraphe, on Suppose que la liste est triée par ordre croissant.
Principe :
On regarde l'élément au milieu de la liste :
 S’il est égal à la valeur cherchée, c'est fini
 S’il est inférieur à la valeur cherchée, il ne reste à traiter que la moitié droite de la liste
 S’il est supérieur à la valeur cherchée, il ne reste à traiter que la moitié gauche de la liste
On continue ainsi la recherche en diminuant à chaque fois de moitié le nombre d'éléments de la liste
restant à traiter.
Pour réaliser la recherche dichotomique dans une liste triée, la fonction Recherche_dicho est
implémentée, elle prend 4 paramètres : l’élément x à cherchée, L : la tête de la liste chaînée, le début et la
fin de la sous liste dans la quelle la recherche de x est éffectuée.

Dans l’algorithme principal, l’appel sera comme suit : Recherche_dicho(x, L, 1, longueur (L))
Avec longueur (L) est une fonction qui renvoi la longueur de la liste chaînée.
La fonction ieme (milieu, L) est une fonction qui retourne la valeur de la cellule ayant la position milieu
de la liste L.

La fonction longueur (L) est une fonction qui calcule la longueur d’une liste chaînée L.
3- Recherche dans un arbre binaire

La recherche dans un arbre binaire d'un nœud ayant une valeur particulière est un procédé récursif. On
commence par examiner la racine. Si sa valeur est égale à la valeur recherchée, l'algorithme se termine et
renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre droit, sur lequel on
effectue alors récursivement la recherche. De même si la valeur de la racine est strictement supérieure à
la valeur recherchée la recherche continue sur le sous-arbre gauche. Si on atteint une feuille dont la
valeur n'est pas celle recherchée, on sait alors que la valeur recherchée n'appartient à aucun nœud. On
peut la comparer avec la recherche par dichotomie qui procède à peu près de la même manière.
3.1 Parcours en profondeur
Le parcours en profondeur est un parcours récursif sur un arbre. Il existe trois ordres pour cette méthode
de parcours.
3.1.1 Parcours préfixé
Dans ce mode de parcours, on traite la racine, puis le sous-arbre gauche, puis le sous-arbre droit.

Ainsi, un parcours préfixé pour cet arbre va nous donner comme résultat :
 11- 8 -5 -10 -14 -13 -15
La procédure récursive de la recherche préfixée est :
Remarque :
Traiter(A) : est le traitement à exercer sur l’arbre de racine A, ajout, suppression, recherche, affichage, …
3.1.2 Parcours infixé
Dans ce mode de parcours, on traite le sous-arbre gauche, puis la racine, puis le sous-arbre droit.

Ainsi un parcours infixé pour cet arbre va nous donner comme résultat :
 5 – 8 – 10 – 11 – 13 – 14 – 15
La procédure récursive de la recherche infixée est :
3.1.3 Parcours postfixé

Dans ce mode de parcours, on traite le sous-arbre gauche, le sous-arbre droit, puis la racine.
Ainsi un parcours postfixé pour cet arbre va nous donner comme résultat :
 5 – 10 – 8 – 13 – 15 – 14 – 11
La procédure récursive de la recherche postfixée est :

3.2 Application
Recherche récursive du père d’une valeur dans un sous arbre de racine A :

3.3 Arbre binaire de recherche
Un arbre binaire de recherche (ABR) est un arbre binaire tel que la valeur stockée dans chaque sommet
est supérieure à celles stockées dans son sous-arbre gauche et inférieur à celles de son sous-arbre droit.
Exemple :
Algorithme de recherche dans un arbre binaire de recherche:


Chapitre 8 : Les algorithmes de tri
1- Introduction
On désigne par "tri" l'opération consistant à ordonner un ensemble d'éléments en fonction de clés sur
lesquelles est définie une relation d'ordre.
Les algorithmes de tri ont une grande importance pratique. Ils sont fondamentaux dans certains domaines,
comme l'informatique de gestion où l'on tri de manière quasi-systématique des données avant de les
utiliser.
2- Tri par sélection ordinaire

2.1 Principe
L’algorithme initialise un vecteur V formé de N entiers par les valeurs initiales du tableau à trier. Et il
utilise un autre vecteur VT (vecteur trié) formé aussi de N entiers, qui va servir pour le stockage des
valeurs du tableau V ordonnées dans l’ordre ascendant. Au départ le tableau VT n’est pas initialisé
ensuite, on rempli les N cases de la 1ère vers la dernière et dans chaque case on met la bonne valeur. En
appliquant les étapes suivantes :
 Initialisation : Chercher le plus grand élément dans le vecteur initial V, le stocker dans une variable
MAX.
 Itération : Pour i (l’indice de parcourt de VT) allant de 1 à N-1 faire les 3 étapes suivantes :
 Etape 1 : Chercher le plus petit élément dans le vecteur V.
 Etape 2 : Le mettre dans le vecteur VT dans la case d’indice i.
 Etape 3 : Le remplacer par le plus grand élément dans le vecteur V (pour qu'il ne sera plus le
minimum).
 Etape finale : mettre le MAX de V dans la Nième case de VT.
2.2 Algorithme de tri par sélection

Procedure lire_vecteur (var T : Tableau [1..N] de entier)
Var
Debut
Pour i de 1 a N faire
Lire (T[i])
FinPour
Fin
Fonction Max_vecteur (T : Tableau [1..N] de entier) : entier

Var max : entier
Debut
max  T[1]
Pour i de 2 à N FAIRE
Si max < T[i] Alors
max  T[i]
FinSi
FinPour
Retourner (max)
Cours 8 : Algorithmes de tri Page 69

Fin
ALGORITHME TRI_SELECTION
CONST N = 100
VAR
V, VT : Tableau [1..N] de entier
i, j, i_min, MIN, MAX : entier
DEBUT
Lire_vecteur (V)
MAX  Max_vecteur (V)
POUR i de 1 à N-1 FAIRE

{Recherche du MIN de V}
MIN  V [1]
i_min  1
Pour j de 2 à N faire
Si MIN > V[j] ALORS
MIN  V[j]
i_min  j
FinSi
FinPour
{Mettre le MIN dans VT[i]}
VT[i]  MIN
V [i_min]  MAX
FinPour
{Remplir la case N de VT par MAX}

VT [N]  MAX
{Affichage du résultat}
Pour i de 1 a N Faire
Ecrire (VT[i])
FinPour
FIN
3- Tri par insertion séquentielle

3.1 Principe
L’algorithme lit une suite de N entier et les insère dans un tableau V formé de N entier de telle sorte
qu’après chaque insertion d’une valeur le tableau reste toujours trié. Cet algorithme utilise un seul tableau
et non pas 2 comme l’algorithme de tri par sélection.
Pour chaque valeur lue on l’insère dans le tableau en suivant les étapes suivantes :
 On cherche la position p d’insertion qui est la position du 1er élément > la valeur lu.
 On décale d’une case tous les éléments du tableau à partir de l’indice p.
 On met la valeur lue dans la case N° p.

3.2 Algorithme de tri par insertion séquentielle
ALGORITHME TRI_insertionS
CONST N = 100
VAR
V : Tableau [1..N] de entier
e, i, j, k, p : entier
trouve : booleen
DEBUT
Pour i de 1 à N Faire
Lire(e)
{chercher la position d'insertion p}
j 1
trouve  faux
pi
Tantque (j < i) et (trouve = faux) Faire
Si (V[j] > e) Alors
pj
trouve  vrai
FinSi
jj+1
FinTantque
{decaler les cases entre p et i}
Pour k de i a p+1 Pas (-1) Faire
V[k]  V[K-1]
FinPour
{mettre la valeur lu dans la case p}
V[p]  e
FinPour
{affichage du résultat}
Ecrire (V[i])
FinPour
FIN
3.3 Exemple
Les grandes étapes d’évolution du tableau au fil de l'algorithme. En bleu, le tableau trié, en rouge, la
valeur de la mémoire qui contient la valeur à insérer.

4- Tri par insertion dichotomique

4.1 Principe
L’algorithme lit une suite de N entier et les insère dans un tableau V formé de N entier de telle sorte
qu’après chaque insertion d’une valeur le tableau reste toujours trié.
Pour chaque valeur lue on l’insère dans le tableau en suivant les étapes suivantes :
 On fait une recherche dichotomique de la position p d’insertion qui est la position du 1 er élément > la
valeur lu.
 On décale d’une case tous les éléments du tableau à partir de l’indice p.
 On met la valeur lue dans la case N° p.
4.2 Algorithme de tri par insertion dichotomique
ALGORITHME TRI_InsertionD
CONST N = 100
VAR
V : Tableau [1..N] de entier
bi, bs, e, i, j, k, p : entier
trouve : booleen
DEBUT
Pour i de 1 à N Faire
Lire(e)
{chercher la position d'insertion p}
j 1
bs  i
bi  i DIV 2
trouve  faux
pi
Tantque (j < i) et (trouve = faux) Faire

Si( e <= V[j] ) Alors
pj
trouve  vrai
Sinon
Si (e > V[bi]) Alors
j  bi + 1

bi  (bi + bs) DIV 2

Sinon
jj+1
bs  bi
bi  bs DIV 2
FinSi
FinSi
FinTantque
{decaler les cases entre p et i}
Pour k de i a p+1 Pas (-1) Faire
V[k]  V[K-1]
FinPour
{mettre la valeur lu dans la case p}
V[p]  e
FinPour
{affichage du résultat}
Ecrire (V[i])
FinPour
FIN
5- Algorithme de tri rapide

5.1 Présentation :
L'algorithme de tri rapide, "quick sort" en anglais, est un algorithme de type dichotomique. Son
principe consiste à séparer l'ensemble des éléments en deux parties. Pour effectuer la séparation, une
valeur pivot est choisie. Les valeurs sont réparties en deux ensembles suivant qu'elles sont plus
grandes ou plus petites que le pivot. Ensuite, les deux ensembles sont triés séparément, suivant la
même méthode. L'algorithme, est récursif, mais il n'est pas nécessaire de fusionner les deux
ensembles. Le résultat du tri est égal au tri de l'ensemble dont les valeurs sont inférieures au pivot
concaténé à l'ensemble des valeurs supérieures au pivot.
5.2 Choix du pivot :
Le choix du pivot est le problème central de cet algorithme. En effet, l'idéal serait de pouvoir répartir
les deux ensembles en deux parties de taille à peu prés égales. Cependant, la recherche du pivot qui
permettrait une partition parfaite de l'ensemble en deux parties égales aurait un coût trop important.
C'est pour cela que le pivot est choisit de façon aléatoire parmi les valeurs de l'ensemble. Dans la
pratique, le pivot est le premier ou le dernier élément de l'ensemble à fractionner. En moyenne, les
deux ensembles seront donc de taille sensiblement égale.
5.3 Exemple :
Les grandes étapes de l'évolution du tableau au fil de l'algorithme : En bleu, les valeurs déja
positionnées, en rose, les valeurs qui servent de pivot pour passer à la ligne suivante.

5.4 Algorithme
Fonction Partition (var T : tableau [1..N] de entier, deb, fin : entier) : entier
Var
i, j, v, p: entier
Debut
i deb-1
j fin
p  T[fin]
Repeter
Repeter
i  i+1
Jusqu'à ( T[i] ≥ p )
Repeter
j  j-1
Jusqu'à ( T[j] ≤ p )
Si ( i< j) Alors
v  T[i]
T[i]  T[j]
T[j]  v
FinSi
Jusqu'à ( i ≥ j )
T[fin]  T[i]
T[i]  p
Retourner (i)
Fin
Procedure Tri_Rapide (var T : tableau[1..N] de entier, deb, fin :entier)

Var
Pos : entier
Debut
Si (deb < fin) Alors
Pos  Partition (T,deb,fin)
Tri_Rapide (T,deb,pos-1)
Tri_Rapide (T,pos+1,fin)
FinSi
Fin

6- Tri par tas

6.1 Définition
Un tas est un arbre binaire complet dans lequel il existe un ordre entre un nœud et ses descendant.
Un arbre binaire complet est un arbre dont le ième niveau contient 2^i nœuds sauf éventuellement le
dernier niveau où les feuilles sont regroupés à gauche. Ainsi au niveau de la racine qui représente le
niveau 0 on a 2^0 c'est-à-dire 1 seul nœud, au niveau 1 on a 2^1 c'est-à-dire 2 nœuds, et ainsi de suite
jusqu’à l’avant dernier niveau, le seul niveau qui respecte pas cette règle et peut contenir moins de 2^i
éléments est le dernier niveau.
Un tas est un arbre binaire complet qui respecte la relation d’ordre suivante : pour chaque nœud on a
une valeur ≥ aux valeurs de chacun de ses fils.
Remarque :
Les éléments qui se trouvent au dernier niveau sont placés dans les feuilles les plus à gauches.
Exemple :
10
8 7
2 3 6
6.2 Utilisation d’un tas pour le tri

L'idée de base consiste à insérer les éléments du tableau à trier dans un tas. Il reste alors à ressortir les
éléments du plus grand au plus petit en vidant le tas progressivement et on obtient ainsi un tableau trié.
Les 2 opérations de base qu’on va faire sur un tas sont l’ajout d’un élément et la suppression du nœud
ayant la valeur maximale dans le tas.
Pour l’ajout dans un tas, on ajoute l'élément sur la première feuille libre de manière à ce que l'arbre
binaire reste toujours complet. Et on rétablit la propriété d’ordre en échangeant l'élément avec son père si
la valeur de ce dernier est inférieure, et en propageant ce type d'échange aussi loin qu'il le faut jusqu’à ce
qu’on atteint la racine.
Pour la suppression du maximum, on remplace l'élément racine qui contient le maximum par le
dernier élément (dernière feuille) de manière à ce que l'arbre binaire reste toujours complet. Et on rétablit
la propriété d’ordre en effectuant si nécessaire des échanges des pères avec le plus grand de leurs fils, en
partant de la racine de l'arbre vers les feuilles.
Ainsi l’algorithme de tri par tas est basé sur l’utilisation d’une procédure appelée Insert qui fait les
insertions successives dans le tas et d’une fonction appelé SuppMax qui fait les suppressions successives
des éléments des plus grands vers les plus petits.
Remarque :
On peut représenter un tas par un tableau T à une dimension à condition que les propriétés suivantes
restent vérifiées sur le tableau :
T [1] désigne la racine du tas.

T [i div 2] désigne le père de T[i].

T [2i] et T [2i + 1] sont les fils de T[i].

Si le tas a N nœuds avec N = 2i, alors T[i] n'a qu'un seul fils qui est T[p].
Si i > N div 2, alors T[i] est une feuille.
6.3 Algorithme de tri par tas

Procedure Insert (k : entier)
Var
V, j : entier
Debut
V  T [k]
j  k DIV 2
Tantque ( j > 0 et T [j] <= V) Faire

T [k]  T [j]
k  k DIV 2
j  k DIV 2
FinTantque
T [k]  V
Fin
Fonction SuppMax (M : entier) : entier

Var
j, max, v : entier
Debut
max  1
Pour j de 1 à M Faire
Si (T[j] > T[max]) Alors
max  j
FinSi
FinPour
v  T[max]
T[max]  T [M]
Retourner (v)
Fin

{----------------------------------------------------------------------------}
ALGORITHME TRI_TAS
CONST N = 100
VAR
S, T : tableau [1..N] de entier
N, i : entier
DEBUT
Lire_vecteur (S)
T[i]  S[i]
Insert (i)
FinPour
Pour i de N a 1 PAS (-1) Faire
T[i]  SuppMax (i)
FinPour
Affiche_vecteur(T)
FIN


Chapitre 9 : La complexité des algorithmes
1- Introduction
Un algorithme est une procédure finie et un enchaînement des étapes de résolution d’un problème. Un
algorithme doit être appliqué sur toutes les données possibles du problème et doit fournir une solution
correcte dans chaque cas. En informatique, il est possible de résoudre un problème donné par
implantation d’un algorithme conçu spécification pour la résolution. Cependant, pour un problème
donné, il peur être résolu souvent avec plusieurs algorithmes.
Le problème qui se pose alors : Comment choisir entre les algorithmes? Comment déterminer
l’efficacité d’un algorithme par rapport à un autre ? De ces questions est née la complexité des
algorithmes.
2- Définition
La mesure de la complexité d’un algorithme est une estimation de son temps d’exécution ainsi que de
l’espace mémoire utilisé. Ces 2 mesures sont appelées complexité spatiale et temporelle de
l’algorithme.
La complexité spatiale exprime la taille occupée par les données de l’algorithme dans la mémoire de
l’ordinateur.
La complexité temporelle exprime le temps que prendra l’exécution de l'algorithme.
La mesure de la complexité permet de décider si un algorithme est efficace ou non indépendamment

de la machine qui va l’exécuter et du langage d’implémentation, elle ne dépend que de l’algorithme
lui-même.
3- Calcul de la complexité
Le temps d’exécution d’un algorithme est fonction du nombre d’opérations élémentaires dans cet
algorithme. Par exemple, pour le parcourt d’un tableau et la recherche d’un élément donnée, la
comparaison entre l’élément courant du tableau et l’élément recherché sera prise en compte.
Cours9 : Complexité des algorithmes Page 79

La complexité d’un algorithme dépend de plusieurs facteurs, tel que la taille des données à traiter et le
type d’opérations à effectuer, par exemple une addition est plus rapide qu’une multiplication.
Il n’existe pas de méthode formelle pour calculer la complexité d’un algorithme mais il y a des règles
qui peuvent être appliquées.
On note T (Op) : le temps d’exécution d’une opération Op, voici les règles qui peuvent être appliquées
lors du calcul du temps d’exécution d’un algorithme :
- Si Op est une instruction élémentaire alors T (Op) est considéré comme constant et il est noté
O(1).
- Si Op est une instruction conditionnelle (si condition alors op1 sinon op2) alors T (Op) est
estimé à T (condition) + Max (T (op1) + T (op2)).
- Si Op est une boucle (Pour i de 1 à N faire Opération) alors T (Op) est estimé à Somme (T
(Opération)) qui représente la somme des temps des opérations de chaque itération.
4- Type de complexité
Les algorithmes usuels peuvent être classés en un certain nombre de grandes classes de complexité.
 Les algorithmes sous-linéaires, dont la complexité est en général en O(log n). C'est le cas de la
recherche d'un élément dans un ensemble ordonné fini de n éléments (recherche d’un élément
dans un tableau de taille n).
 Les algorithmes linéaires en complexité O(n) sont considérés comme rapides, comme
l'évaluation de la valeur d'une expression composée de n symboles ou les algorithmes de tri de
tableaux de n éléments.
 Plus lents sont les algorithmes de complexité située entre O(n2) et O(n3), c'est le cas de la
multiplication des matrices de taille n.
Puisque on calcule la complexité temporelle en faisant une approximation, on utilise donc les notations
suivantes:

O(1) : complexité constante
O(log(n)) : complexité logarithmique
O(n) : complexité linéaire
O(n2) : complexité quadratique
O(n3) : complexité cubique
p
O(n ) : complexité polynomiale
O(2n) : complexité exponentielle
5- Complexité de quelques algorithmes

5.1 Recherche du plus petit élément d’un tableau
Soit l'exemple suivant:
fonction plusPetit (x: Tableau[1..n] de entier)

var k,i: entier
Debut
k0
pour i de 1 à n faire
si(x[i] < x[k]) alors

ki
finsi
finpour
Retourner (k)
Fin
Dans cette fonction, on exécute (n-1) tests de comparaison. La complexité temporelle est donc de
l’ordre de (n-1) : elle est noté O(n).

5.2 Produit de deux matrices
Soit l'exemple suivant:
Algorithme Produit_Matrice
var
u,v, w : Tableau[1..n] de entier
i : entier
Debut
pour i de 1 à n faire
pour j de 1 à n faire
w[i,j]  u[i,j] * v[i,j]
finpour
finpour
fin
La complexité temporelle de cet algorithme est la somme des temps nécessaire pour faire les multiplications sur
une ligne de la matrice w à savoir n * le temps d’une multiplication qui est considéré comme constante donc
O(n). Ce calcul est répété pour chaque ligne donc la complexité précédente doit être multipliée par n.
Finalement on peut en déduire que l’algorithme est de complexité égale à O(n 2).

Cours Algorithmique Niveau 2 PDF

Transféré par

Droits d'auteur :

Formats disponibles

Cours Algorithmique Niveau 2 PDF

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours Algorithmique Niveau 2 PDF

Transféré par

Droits d'auteur :

Formats disponibles

Ministère de l’Enseignement Supérieur, de la Recherche Scientifique et de la Technologie

Direction Générale des Etudes Technologiques

Institut Supérieur des Etudes Technologiques de Beja

Département TECHNOLOGIES DE l’INFORMATIQUE

Support de cours adressé aux étudiants du réseau ISETs et aux autres

Réalisé par le groupe Unité d’Enseignement Programmation2:

Bn KHADIJA Maali LARIBI Fatma

El KAMEL Ali MENSI Ali (coordinateur

Equipe UE Programmation 2 Page 1

CHAPITRE 1 LA RECURSIVITE ........................................................................... 8

CHAPITRE 2 LES ENREGISTREMENTS.............................................................17

CHAPITRE 3 LES POINTEURS ...........................................................................23

CHAPITRE 4 LES LISTES ...................................................................................33

CHAPITRE5 LES PILES ET LES FILES .............................................................41

CHAPITRE 6 LES ARBRES ET LES GRAPHES .................................................48

CHAPITRE 7 LES ALGORITHMES RECURSIFS DE RECHERCHE ...................60

CHAPITRE 8 LES ALGORITHMES DE TRI .........................................................69

CHAPITRE 9 LA COMPLEXITE DES ALGORITHMES........................................79

Equipe UE Programmation 2 Page 2

Spécialité : Technologies de l’informatique

Répartition horaire des cours

N° Titre Semaine(s) Responsable(s)

1 La récursivité S1-S2 Karim Jendoubi

2 Les enregistrements S3 Karim Jendoubi et

3 Les pointeurs S4 Olfa Arfaoui

4 Les listes S5 Ali Mensi

5 Les piles et les files S6-S7 Yosra Landolsi

6 Les arbres et les graphes S8-S9 Fatma Laribi

Les algorithmes récursifs de

8 Les algorithmes de tri S12-S13 Maali Ben Khadija

Répartition horaire des cours

Supports et Références Bibliographiques

[1] Le Langage C, Christian Bac, 24 février 2004.

[2] Algorithmique et Bases de la Programmation, Hamrouni M. Kamel, Année : 2004-05.

[3] Algorithmique – Niveau 1, Belhassen GUETTAT, 1er Semestre 2003-2004.

[5] Introduction à l'informatique et programmation en langage C, Jean Fruitet, 1999.

[7] Brian W. Kernighan, Dennis M. Ritchie Programmieren in C, 2. Ausgabe, ANSI-C Carl

[8] Autoformation, Le Langage C, Joelle Maillefert.

[10] Claude Delannoy Exercices en Langage C Edition EYROLLES, 1992.

1- Rappel : Les procédures

 nomP est le nom de la procédure.

1.3 Schéma d’exécution

Fig : schéma d’exécution d’un programme

2- Les variables et les paramètres

3- Passage des paramètres

3.2 Passage des paramètres par variable

 définition non récursive (ou itérative):

5.2 Fonctions récursives

Ce qui se traduit par la fonction récursive suivante:

Il est clair que sans le test « Si (n = 1) » cette fonction ne s'arrêterait jamais.

5.2.3 Exécution d’une fonction récursive

5.2.4 Variables locales et paramètres des fonctions récursives

Il en est de même des paramètres des fonctions.

Chapitre 2 Les enregistrements

1- Les types de base

1.1 Types simples

1.2 Types complexes

Cours2 : Enregistrements Page 17

2- Définition d’un enregistrement