Université Tahri Mohamed de Béchar

Faculté des sciences exactes

Département des Mathématiques et Informatique
1ère année Master (Intelligence Artificielle - Réseaux et Systèmes Distribués)

Matière:

Algorithmique avancée
et complexité
Cours n° 03

Enseignant : Benyamina Ahmed

1
 Matière: Algorithmique avancé et complexité
(AAC)

Programme de la matière :
1- Introduction à la complexité algorithmique et notions préliminaires
2- Analyse de la complexité temporelle
3- Structures de données et complexité
1. Listes chainée,
2. Structures de données hiérarchiques
1. arbres,
2. graphes,
3. tas.
3. opérations courantes et complexité associée.
4- Techniques d'analyse de complexité
5- Complexité spatiale
6- Complexité et Preuve de Correction
7- Optimisation d'algorithmes

2
 3- Structures de données et complexité
1. Listes chainée
Une liste chaînée est une structure de données dynamique composée de nœuds.
Chaque nœud contient :
→ une donnée
→ un lien vers le suivant
Contrairement aux tableaux, les éléments ne sont pas contigus en mémoire.

3
 3- Structures de données et complexité
1. Listes chainée

Types principaux :
1. Simplement chaînée :
chaque nœud pointe vers le suivant.

2. Doublement chaînée :
chaque nœud pointe vers le suivant
et le précédent.

3. Circulaire :
le dernier nœud pointe vers le premier.

4
 3- Structures de données et complexité
1. Listes chainée

Application : représentation de piles, files, graphes:

les listes chaînées ne sont pas seulement une structure abstraite, elles servent
aussi de support d’implémentation pour d’autres structures de données
comme piles, files et graphes.
1. Piles (Stack)
Une pile est une structure LIFO (Last In, First Out).
Si on utilise une liste chaînée, on peut considérer :
 La tête (head) de la liste comme le sommet de la pile.
 Chaque insertion (push) = ajout en tête.
 Chaque suppression (pop) = retrait en tête.
Exemple (pile avec liste chaînée) :
Push(10) → [10]
Push(20) → [20]→[10]
Push(30) → [30]→[20]→[10]
Pop() → retire [30], reste [20]→[10]

5
 3- Structures de données et complexité
1. Listes chainée

Application : représentation de piles, files, graphes:

les listes chaînées ne sont pas seulement une structure abstraite, elles servent
aussi de support d’implémentation pour d’autres structures de données
comme piles et files.
2. Files (Queue)
Une file est une structure FIFO (First In, First Out).
Avec une liste chaînée, on peut utiliser :
 La tête (head) comme début de la file (élément à sortir).
 La queue (tail) comme fin de la file (élément à entrer).
Exemple (file avec liste chaînée) :
Enfiler(10) → [10]
Enfiler(20) → [10]→[20]
Enfiler(30) → [10]→[20]→[30]
Defiler() → retire [10], reste [20]→[30]

6
 3- Structures de données et complexité
2. vs structures de données hiérarchiques
Exemple 1:
- Organisation du système de fichiers d’un ordinateur est arborescente. Les
fichiers sont organisés de manière hiérarchique à partir d’une racine, à laquelle
peuvent être rattachés des répertoires (dossiers) et des fichiers, les répertoire
pouvant eux-mêmes de manière récursive contenir d’autres répertoire et/ou
fichiers.

7
 3- Structures de données et complexité
2. vs structures de données hiérarchiques

Exemple 2:
- Le DOM (Document Object Model) modèle objet de document du langage
HTML représente un document web de manière structurée sous forme d’un
arbre hiérarchique

8
 3- Structures de données et complexité
2. vs structures de données hiérarchiques

1. Structures linéaires : les éléments sont organisés de manière séquentielle,

enchaînés les uns aux autres. Chaque élément (sauf extrémités) possède un
prédécesseur et un successeur. Ce mode d’organisation facilite le parcours de
données dans un seul passage:
2. Structures hiérarchiques (non-linéaires) : les éléments ne sont pas disposés
en ligne mais dans une disposition multi-niveaux ou ramifiée, permettant des
relations multiples entre les éléments

9
 3- Structures de données et complexité
2. vs structures de données hiérarchiques

Structure non-linéaire /
Critère Structure linéaire
hiérarchique
Hiérarchique ou réseau,
1. Organisation des données Séquentielle (ordre strict)
relations multiples
Plusieurs niveaux, souvent
2. Niveaux Un seul niveau
arborescents
Plus sophistiquée, nécessite
3. Implémentation Simple, intuitive
des algorithmes spécifiques
Utilisation d’algorithmes
4. Parcours / Traversée Parcours direct (boucle unique)
spécialisés (DFS, BFS…)
Moins efficace, nécessite
5. Utilisation de la mémoire Plus efficace, flexibilité accrue
souvent un espace contigu
Array, Stack, Queue, Linked Arbres (Tree), Graphes
6. Exemples
List (Graph)
Intelligence artificielle,
Développement d’applications
7. Applications typiques traitement d’image, systèmes
simples, workflows séquentiels
complexes

10
 1. Structures
de données linéaires
vs structures de données hiérarchiques
2. Arbre
Un arbre est une structure de données hiérarchique non linéaire, composée de
nœuds reliés entre eux par des arêtes, selon une organisation arborescente. Elle est
fondée sur un principe parent-enfant, avec un unique chemin entre deux nœuds
donnés
Vocabulaire essentiel
1. Racine : nœud initial sans parent
2. Nœud interne : nœud disposant d’au moins un enfant
3. Feuille (ou nœud externe/terminal) : nœud sans enfants
4. Parent / enfant : relation directe ascendante / descendante entre deux
nœuds reliés
5. Frères (siblings) : nœuds partageant le même parent
6. Sous-arbre : région de l’arbre ayant pour racine un nœud quelconque avec
tous ses descendants
Propriétés structurelles
1. Chaque nœud, sauf la racine, a exactement un parent
2. Il n’existe aucun cycle : c’est une structure acyclique
3. L’arbre est souvent représenté graphiquement avec la racine en haut,
descendant en branches
11
 1. Structures de données linéaires
vs structures de données hiérarchiques
2. Arbre
Terminologie quantitative
1. Profondeur (depth) d’un nœud : nombre d’arêtes entre la racine et ce nœud.
•Le nœud 5 est donc de profondeur « 0 »,
•Les nœuds 1 et 3 de profondeur « 1 »
•Les nœuds 4, 2, 6 et 7 de profondeur « 2 ».
2. Hauteur (height) d’un arbre: Est la profondeur maximale de ses feuilles
• La hauteur de cet arbre est « 2 »
3. Arity (arité) : nombre maximum d’enfants autorisés par nœud (ex. un arbre
binaire a une arité de 2) et dans cet arbre: 3
4. Taille : nombre total de nœuds de l’arbre: 7 nœuds
5. Définition récursive
6. Degré d'un nœud:Est égal au nombre de ses fils
•Le nœud 5 est de degré « 2 ».
•Le nœud 1 de degré « 1 ».
•Le nœud 3 de degré « 3 ».
•Les feuilles (4,2,6,7) de degré « 0 ».
Définition récursive
1. Un arbre peut être défini de manière récursive :
2. Un arbre vide,
3. Ou un nœud racine accompagné d'une liste (ou ensemble) de sous-arbres
12
 1. Structures
de données linéaires
vs structures de données hiérarchiques
2. Arbre
Représentation d’un arbre :
La structure générale des nœuds d’un arbre est
illustré à la figure ci-après:

13
 1. Structuresde données linéaires
vs structures de données hiérarchiques

2. Arbre
Le passage d'un arbre n-aire à un arbre
binaire:

Prochaine séance
14
 Université Tahri Mohamed de Béchar
Faculté des sciences exactes
Département des Mathématiques et Informatique
1ère année Master (Intelligence Artificielle - Réseaux et Systèmes Distribués)

Matière:

Algorithmique avancée
et complexité
Cours n° 04

Enseignant : Benyamina Ahmed

1
 Matière: Algorithmique avancé et complexité
(AAC)

Programme de la matière :
1- Introduction à la complexité algorithmique et notions préliminaires
2- Analyse de la complexité temporelle
3- Structures de données et complexité
1. listes,
2. arbres,
3. graphes,
4. tas.
5. opérations courantes et complexité associée.
4- Techniques d'analyse de complexité
5- Complexité spatiale
6- Complexité et Preuve de Correction
7- Optimisation d'algorithmes

2
 3. Les arbres binaires
Introduction: Il existe de nombreux types d'arbres
dans le domaine des structures de données. Voici
quelques-uns des types d'arbres les plus courants :
1. Arbres binaires
2. Arbres de recherche binaire
3. Arbres généalogiques
4. Arbres d'expression

4. 1- Arbre binaire: Un arbre binaire est une

structure de données hiérarchique composée de
nœuds, où chaque nœud a au plus deux enfants,
généralement appelés "gauche" et "droite". Chaque
nœud d'un arbre binaire peut avoir un maximum de
deux sous-arbres, un à gauche et un à droite. La
structure d'un arbre binaire est telle que chaque nœud
a un seul parent, à l'exception du nœud racine qui n'a
pas de parent.
3
 3. Les arbres binaires

4.2- Arbre binaire de recherche: Un type particulier d'arbre binaire dans

lequel les nœuds sont organisés de manière à faciliter la recherche. Pour
chaque nœud, tous les nœuds du sous-arbre gauche sont inférieurs, et tous
les nœuds du sous-arbre droit sont supérieurs. Ces propriétés permettent une
recherche, une insertion et une suppression très efficaces. En fait, le temps de
recherche moyen pour un arbre de recherche binaire est directement
proportionnel à sa hauteur : O(h)

4
 3. Les arbres binaires

4.3. Arbres généalogiques : Les arbres généalogiques sont utilisés pour

représenter les relations familiales, avec les nœuds représentant des
individus et les liens entre eux indiquant des relations parent-enfant.

5
 3. Les arbres binaires

4.4. Arbres d'expression : Les arbres d'expression sont utilisés pour représenter des
expressions mathématiques ou arithmétiques.
L’arbre est hétérogène, le genre d’information est pas le même sur chaque nœud (opérateur,
opérande).
Les feuilles contiennent les opérandes,
Les nœuds internes contiennent les opérateurs.
Ils permettent l'évaluation et la simplification des expressions.

Exemple:
Voici l’expression suivante :
(2*3+5)*(10*10+9*9)

6
 3. Les arbres binaires

A- Parcours d’un arbre binaire :

Il existe trois principaux types de parcours :

1. Le parcours préfixe ou préordre: Preorder Traversal

2. Le parcours infixe ou en ordre: Inorder Traversal
3. Le parcours postfixe ou postordre : Postorder
Traversal).

7
 3. Les arbres binaires: Parcours

A-1- Parcours Préfixe (Preorder Traversal) :

Le parcours de préfixé est un algorithme permettant de visiter (traiter)
tous les nœuds d'un arbre binaire. L'algorithme visitera d'abord ce nœud
(la « racine » de son sous-arbre), puis il visitera de manière récursive
tous les nœuds de son sous-arbre de gauche, et enfin il visitera de
manière récursive tous les nœuds de son sous-arbre de droite.
Visite le nœud courant  R
Visite le sous-arbre gauche  G
Visite le sous-arbre droit  D

Utilisation:

La création d'une copie de l'arborescence,

8
 3. Les arbres binaires: Parcours
A-1- Parcours Préfixe (Preorder Traversal) : (RGD)
Algorithme : L’ approche de parcours présenté est récursive utilisant une pile
d'appels système pour garder une trace des nœuds à visiter ensuite. C'est une
méthode simple et directe, mais elle peut entraîner des erreurs de débordement de
pile si l'arborescence est très profonde.
def recursive_pre_order_traverse (node):
if node is None:
return
node. visit ()
recursive_pre_order_traverse (node . left)
recursive_pre_order_traverse (node. right)
Oú

class Node:
def _init__ (self, key) :
self.key = key
self.left = None
self. right = None
def visit (self):
print (self . key , end=" ")
9
 3. Les arbres binaires: Parcours

A-1- Parcours Préfixe (Preorder Traversal) : (RGD)

Complexité temporelle : O(n), où n est le nombre de nœuds dans l'arborescence.
En effet, chaque nœud de l'arborescence est visité exactement une fois pendant le
parcours.

10
 3. Les arbres binaires: Parcours

A-1- Parcours Préfixe (Preorder Traversal) : (RGD)

Exemple 1: Z=3x+1

Représentation schématique :

Représentation préfixée :=z+*3 X1

11
 3. Les arbres binaires: Parcours

A- Parcours d’un arbre binaire :

Il existe trois principaux types de parcours :

1. Le parcours préfixe ou préordre: Preorder Traversal

2. Le parcours infixe ou en ordre: Inorder Traversal
3. Le parcours postfixe ou postordre : Postorder
Traversal).

12
 3. Les arbres binaires: Parcours

A-2- Parcours Infixe (Inorder Traversal):

Visite le sous-arbre gauche  G
Visite le nœud courant  R
Visite le sous-arbre droit  D

Utilisation:

1. Affichage trié :
produit une séquence triée des éléments.
2. Validation de l'expression arithmétique :
récupérer l'expression dans l'ordre correct.

13
 3. Les arbres binaires: Parcours

A-2-Parcours Infixe (Inorder Traversal): (GRD)

Algorithme :
L’ approche de parcours infixe présenté est récursive.

def recursive_in_order_traverse (node):

if node is None:
return
recursive_in_order_traverse (node. left)
node.visit()
recursive_in_order_traverse (node . Right)

14
 3. Les arbres binaires: Parcours

A-2-Parcours Infixe (Inorder Traversal):(GRD)

Complexité temporelle : O(n), où n est le nombre de nœuds dans l'arborescence.

15
 3. Les arbres binaires: Parcours

A-2-Parcours Infixe (Inorder Traversal): (GRD)

Exemple: Z=3x+1
Représentation schématique :

Représentation infixée : Z=3*X+1

16
 3. Les arbres binaires: Parcours

A- Parcours d’un arbre binaire :

Il existe trois principaux types de parcours :

1. Le parcours préfixe ou préordre: Preorder Traversal

2. Le parcours infixe ou en ordre: Inorder Traversal
3. Le parcours postfixe ou postordre : Postorder
Traversal).

17
 3. Les arbres binaires: Parcours
A-3- Parcours Postfixe (Postorder Traversal):
Visitez le sous-arbre gauche  G
Visitez le sous-arbre droit  D
Traitez le nœud courant  R

Utilisation:

Utilisé pour l’évaluation d’une expression arithmétique

Illustrons cela avec un exemple d'expression postfixe : 23*5+.
1.Parcours de gauche à droite :
•2 (opérande) -> empile 2
•3 (opérande) -> empile 3
•(opérateur) -> dépile 3 et 2, calcule 3 * 2, empile 6
•5 (opérande) -> empile 5
•(opérateur) -> dépile 5 et 6, calcule 5 + 6, empile 11
18
 3. Les arbres binaires: Parcours

A-3- Parcours Postfixe (Postorder Traversal): (GDR)

Algorithme :
L’ approche de parcours infixe présenté est récursive.

def recursive_post_order_traverse (root) :

if root is not None:
recursive_post_order_traverse (root. left)
recursive_post_order_traverse (root.right)
root.visit ()

19
 3. Les arbres binaires: Parcours

A-3- Parcours Postfixe (Postorder Traversal): (GDR)

Complexité temporelle : O(n), où n est le nombre de nœuds dans l'arborescence.

20
 3. Les arbres binaires: Parcours

A-3- Parcours Postfixe (Postorder Traversal): (GDR)

Exemple :

1 - (y)(+)=
2 - y(/)(z)+=
3 - y(+)(6)/z+=
4 - y(x)(y)+6/+=

Représentation post fixée : yxy+6/z+=

Question: Evaluer l’expression arithmétique de cette notation postfixe?

21
 Université Tahri Mohamed de Béchar
Faculté des sciences exactes
Département des Mathématiques et Informatique
1ère année Master (Intelligence Artificielle - Réseaux et Systèmes Distribués)

Matière:

Algorithmique avancée
et complexité
Cours n° 06

Enseignant : Benyamina Ahmed

1
 Matière: Algorithmique avancé et complexité
(AAC)

Programme de la matière :
1- Introduction à la complexité algorithmique et notions préliminaires
2- Analyse de la complexité temporelle
3- Structures de données et complexité
1. listes,
2. arbres,
3. graphes,
4. tas.
5. opérations courantes et complexité associée.
4- Techniques d'analyse de complexité
5- Complexité spatiale
6- Complexité et Preuve de Correction
7- Optimisation d'algorithmes

2
 Les graphes
1.Définitions
Les graphes: Un graphe est une structure de données qui permet de
représenter des objets et des relations entre eux. Un graphe est composé
de sommets (ou nœuds) et d’arêtes (ou arcs) qui relient les sommets,
c'est-à-dire, Le graphe G = (V, E), où V représente l'ensemble des sommets
et E représente l'ensemble des arêtes.

Exemples: On peut utiliser un graphe

pour modéliser:
1. Un réseau social: pour modéliser
les relations sociales sur les
plateformes numériques, (+ détail)
2. Un réseau routier: en représentant
les connexions entre intersections
3. Un circuit électrique: en analysant
la circulation du courant entre
composants;
3
 Les graphes
1.Définitions : types de graphes
-Il existe deux types de graphes : les graphes non orientés et
les graphes orientés.

1. Graphe non orienté:

Les arêtes n’ont pas de sens,
c’est-à-dire qu’on peut parcourir
une arête dans les deux sens.

Le graphique représenté à la figure

a six sommets et sept arêtes non orientées :
V = {a, b, c, d, e, f },
E = {(a, c), (a, d), (b, c), (b, f), (c, e), ( d, e), (e, f)}
Cardinalité : V = N = 6 ; E =M =7

4
 Les graphes
1.Définitions : types de graphes
-Il existe deux types de graphes : les graphes non orientés et
les graphes orientés.

2. Graphe orienté:
Les arêtes ont un sens, c’est-à-dire
qu’on ne peut parcourir une arête
que dans une seule direction.
On représente les arêtes orientées
par des flèches.
Le digraphe représenté à la figure comporte six sommets et huit
arêtes dirigées :
V = {a, b, c, d, e, f },
E = {(a, c), (b, c), (b, f), (c, e), (d, a), ( d, e), (e, c), (e, f)}
Cardinalité : V =N =6 ; E = M =8
5
 Les graphes
1.Définitions

1. Ordre du graphe: C’est le nombre de sommets du graphe.

Exemple: L’ordre du graphe 1 est 4,
Celui du graphe 2 est 3.
2. Degré : le degré d'un sommet est défini comme le nombre
d'arêtes incidentes à ce sommet.
Exemple : Le degré du sommet A est 1, le degré du sommet
B est 3, C et D sont de degré 2 (graphe 2 ou 3). Le degré du
sommet D du graphe 4 est 0
Objectif: Le calcul du degré est pour identifier les sommets
isolés (degré zéro), les sommets terminaux (degré un), les
séquences de degrés, et d'autres caractéristiques structurales
des graphes.
3. Connexe: Un graphe est dit connexe s’il n’y a pas de point
isolé.
Exemple: Le graphe 4 n’est pas connexe car le sommet D est
isolé
6
 Les graphes
1.Définitions

1. Graphe symétrique: Si toutes ces arêtes orientés peuvent se

parcourir dans les 2 sens.
Exemple: - Le graphe 1 est symétrique,
- Celui du graphe 2 ne l’est pas car l’arc AB
existe mais pas l’arc BA
- un graphe 3 non-orienté est symétrique
car les arêtes peuvent se parcourir dans les 2 sens.
2. Sommets adjacents: deux sommets sont dits adjacents s’il
existe une arête ou un arc les reliant : peu importe qu’il soit orienté
ou non.
Exemple: B et A sont adjacents, mais B et C ne le sont pas
3. Graphe valué: Un graphe valué est un ensemble de connexions
entre des sommets, où chaque connexion a un nombre associé,
représentant une mesure telle que la distance, le coût, ou une autre
valeur pertinente.
4. Boucle: Est un arc reliant un nœud à lui même. Graphe 5.
7
 Les graphes
1.Définitions
1. Graphe complet: Un graphe est complet si tous les sommets
sont adjacents, c’est-à-dire que tout les sommets sont reliés deux
à deux entre eux.
Exemple: - Le graphe 1 est complet,
- Celui du graphe 2 ne l’est pas car l’arc AB car
il n’y a aucune arête entre B et C :
2. Chemin: suite d’arcs (orienté) ou de connexions (non orienté)
consécutifs qui relient deux nœuds.
Exemple: Chemin de A et D : ({A, B}, {B,D}) ou ({A, D})
Un chemin est dit simple s’il ne rencontre pas deux fois le
même sommet.
3. Circuit: est un chemin fermé. Le nœud initial c’est le nœud
final.
Exemple: ({A, B}, {B,D}, {D,A})
4. Longueur d’un chemin: est le nombre d’arcs constituant un
chemin.
Exemple : Le chemin {A, B}, {B,D} est de longueur 2
Le chemin {A, D} est de longueur 1 8
 Les graphes
1.Définitions

Les graphes:
1. Un réseau social: Est une plateforme numérique en ligne ou un
service pour modéliser les relations sociales entre les individus.

De tels graphes
permettent ainsi aux sites
de réseaux sociaux de
vous proposer de
nouveaux contacts en
fonction de vos envies et
de vos connaissances.

D’après le diagramme
précédent, quelle visite
pourrait-on conseiller à
Bob ?
9
 Les graphes
1.Définitions
Les graphes: Après avoir vu les notions des graphes revenons à les voir
dans l’exemple de réseau social

Conclusion: Ces concepts clés dans les réseaux sociaux fournissent une
perspective structurée pour comprendre les relations, les influences et les
dynamiques au sein de ces espaces interconnectés.
10
 Les graphes
2.Représentation des graphes

➢Représentation d'un graphe : Il existe plusieurs types

de représentations des graphes.
Parmi ces représentations on a les deux types suivants:
1. Matrice d’adjacence,
2. Matrice d’incidence.
3. Représentation chaînée

11
 Les graphes
2.Représentation des graphes

➢Représentation d'un graphe :

1. Matrice d’adjacence:
La matrice d’adjacence, est une matrice, qui fait correspondre les sommets
origines des arcs (placés en ligne) aux sommets destination (placés en
colonnes).
L’existence d’un arc (xi,xj) se traduit par la présence d’un 1 à l’intersection
de la ligne xi et de la colonne xj; l’absence d’arc par la présence d’un 0.
Exemple : Le graphe suivant est représenté par la matrice d’adjacence :
Sommets
v1 v2 v3 v4
v1 0 1 0 0
v2 0 0 0 1
v3 1 0 0 0
v4 1 0 1 0
L’inconvénient majeur est la consommation de mémoire quelque soit
le graphe (pour V nœuds on a V2 places mémoires) 12
 Les graphes
2.Représentation des graphes
➢Représentation d'un graphe :
2. Matrice d’incidence:
La matrice d'incidence est une matrice qui fait correspondre les sommets
(placés en ligne) aux arêtes (placées en colonnes). Chaque ligne représente
un sommet et chaque colonne représente une arête. Les éléments de la
matrice indiquent la participation des sommets aux arêtes.
Une entrée de cette matrice:  1 si l' arc commence en i
(sommet,arc) = (i,uj) vaut 0 ou 1 : = − 1 si l' arc se termine en i
0 sinon

Exemple : Le graphe suivant est représenté par la matrice d’incidence :
Arcs
Sommets u1 u2 u3 u4 u5
1 1 -1 -1 0 0
2 -1 0 0 1 0
3 0 1 0 0 -1
4 0 0 1 -1 1
La consommation de mémoire pour V nœuds et M arcs est: V.M places 13
 Les graphes
2.Représentation des graphes
➢Représentation d'un graphe :
3. Représentation chaînée : Les nœuds et les arcs seront codés
sous forme d'enregistrement, avec gestion dynamique de la mémoire.

3.1. Représentation d’un nœud :

Les champs "Nombre d'arcs sortant"

et "Nombre d'arcs entrant" sont utilisés
lors de la recherche de tous les arcs
associés à un nœud.

Exemple: Un réseau de transport aérien

dans un graphe, les nœuds sont les aéroports desservis.

14
 Les graphes
2.Représentation des graphes
➢Représentation d'un graphe :
3. Représentation chaînée : Les nœuds et les arcs seront codés
sous forme d'enregistrement, avec gestion dynamique de la mémoire.

3.2. Représentation d’un arc:

Le champ "Info" est utilisé dans le cas valué.

Exemple: Un réseau de transport aérien:

Dans un graphe, les arcs sont les vols entre ceux-ci.
On peut coder en champs "Info", les distances entre aéroports

15
 Les graphes
2.Représentation des graphes
➢Représentation d'un graphe :
3. Représentation chaînée :
Exemple:

Ce graphe est orienté contenant

des arcs valués.
Les nœuds sont chaînés les uns
des autres.
Par suite on a une liste chaînée
de nœuds.
La notion de premier arc sortant
et de premier arc entrant est arbitraire
16
 Les graphes
3.Parcours des graphes
➢Parcours des graphes : Le parcours d’un graphe consistant à visiter
chaque sommet une et une seule fois. Si le graphe n’est pas connexe,
l’algorithme ne pourra parcourir que la composante connexe du sommet de
départ.

On se limite seulement à voir le parcours dans un graphe représenté par une

matrice d’adjacence.
Les types de parcours dans un graphe:

1- Parcours en profondeur (Depth-first Search): DFS

2- Parcours en largeur (Breadth-first Search): BFS

17
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
1- Parcours en largeur (Breadth-first Search : BFS)

Le (BFS) est un algorithme de parcours de graphe.

L'algorithme BFS utilise une file d'attente (FIFO)
pour empiler les nœuds visités.
Il commence au sommet sélectionné et visite
d'abord tous ses voisins, puis tous leurs voisins,
et ainsi de suite, jusqu'à ce que tous les sommets
du graphe aient été visités.
Remarques: à appliquer durant le parcours.
1. Si le nœud actuel n'a aucun nœud adjacent non visité, l'algorithme
supprime le nœud suivant de la file d'attente et en fait le nœud actuel.
2. Si la file d'attente est vide, le parcours est terminé. Tous les nœuds du
graphe sont visités.

18
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
1- Parcours en largeur (Breadth-first Search : BFS)
1. Commencez par n'importe
quel nœud, marquez-le
comme visité, et ajoutez-le à
la file d'attente.
2. Tant que la file d'attente n'est
pas vide :
a) Retirez le nœud en tête de la
file d'attente (défilement ou
dépilement).
b) Explorez tous les nœuds
adjacents non visités du nœud
actuel.
c) Marquez chaque nœud
adjacent comme visité et
ajoutez-le à la file d'attente.
3. Répétez les étapes 2a à 2c
jusqu'à ce que la file d'attente
soit vide.
19
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
1- Parcours en largeur (Breadth-first Search : BFS)
Exemple: Soit le graphe suivant
Ainsi sa matrice d’adjacence
Question; Trouver la séquence de parcours
Avec le parcours BFS

Etape Sommets adjacents dans la file Sommets visités

s

20
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
1- Parcours en largeur (Breadth-first Search : BFS)
Exemple: Soit le graphe suivant
Ainsi sa matrice d’adjacence

Etape Sommets adjacents dans la file Sommets visités

s
1 v1 v1
2 v2, v3, v5 (dépilement de v5) v1, v2, v3, v5
3 v2, v3 (v5 n’a pas la
deséquence de parcours
sommets non v1, v2, est
v3, :v5v1, v2, v3, v5, v4
visité)
dépilement de v3)
4 v2, v4 (dépilement de v4) v1, v2, v3, v5, v4
21
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
2- Parcours en profondeur (Depth-first Search):DFS
Depth First Search (DFS) est un algorithme de
parcours de graphe qui part d'un sommet
sélectionné et visite tous les sommets du graphe
en profondeur.
L'algorithme de parcours en profondeur (DFS)
utilise une pile (stack en anglais) pour maintenir
l'ordre des nœuds à explorer.
La pile suit le principe Last In, First Out (LIFO), ce qui signifie que le
dernier nœud ajouté à la pile est le premier à en être retiré.
L'algorithme visite un sommet puis visite tous les voisins du sommet de
manière récursive, jusqu'à ce qu'il atteigne la fin d'un chemin ou une
impasse.
Si l’algorithme atteint une impasse, il revient au dernier sommet visité
et continue le parcours à partir de là.
22
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
2- Parcours en profondeur (Depth-first Search):DFS
1. Commencer par visiter un sommet
2. Si le sommet actuel a un sommet
a) Marquer le sommet comme visité.
adjacent non visité :
b) Empiler le sommet sur une pile.
a) Empiler le sommet sur la pile.
b) Marquer le sommet comme visité.
Sinon :
a) Dépiler le sommet de la pile.
b) Rechercher un sommet adjacent
non visité à partir du sommet en
haut de la pile.
c) Si un tel sommet est trouvé, le
marquer comme visité et l'empiler.

3. Répéter l'étape 2 jusqu'à ce que la pile soit vide.

4. La pile est vide, ce qui signifie que tous les sommets ont été visités.
5. La recherche du sommet adjacent commence depuis le début de la liste de tous les sommets
du graphe. 23
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
1- Parcours en largeur (Depth-first Search : DFS)
Exemple: Soit le graphe suivant Som v1 v2 v3 v4 v5 v6
m
Ainsi sa matrice d’adjacence
v1 0 1 1 0 0 0
Question; Trouver la séquence de parcours
v2 1 0 1 1 1 0
Avec le parcours DFS v3 1 1 0 1 1 0
v4 0 1 1 0 1 1
v5 0 1 1 1 0 1

v6 0 0 0 1 1 0

24
 Les graphes
3.Parcours des graphes
➢Parcours des graphes :
1- Parcours en largeur (Depth-first Search : DFS)
Exemple: Soit le graphe suivant Som v1 v2 v3 v4 v5 v6
m
Ainsi sa matrice d’adjacence
v1 0 1 1 0 0 0
v2 1 0 1 1 1 0
v3 1 1 0 1 1 0
v4 0 1 1 0 1 1
v5 0 1 1 1 0 1
la séquence de parcours
v6
est : v1, v2, v3, v4, v5,
1
v6
0 0 0 1 0

25
 Les graphes
3.Parcours des graphes : complexités
➢Parcours des graphes :Complexité Dans le pire des cas
Le graphe possède:
V : nbre de sommets
E : nbre d’ arêtes
Complexité en temps
Parcours Matrice Matrice
Incidence d’adjacence
Parcours en profondeur : O(V . E) O(V2)
Depth-first Search : DFS
Parcours en largeur : O(V . E) O(V2)
Breadth-first Search : BFS
chaque sommet du graphe doit être visité une fois
chaque arête du graphe doit être examinée une fois

26
 Université Tahri Mohamed de Béchar
Faculté des sciences exactes
Département des Mathématiques et Informatique
1ère année Master (Intelligence Artificielle - Réseaux et Systèmes Distribués)

Matière:

Algorithmique avancée
et complexité
Cours n° 01
Enseignant : Benyamina Ahmed
1
 Matière: Algorithmique avancé et complexité
(AAC)

Programme de la matière :
1- Introduction à la complexité algorithmique et notions préliminaires
2- Analyse de la complexité temporelle
3- Structures de données et complexité
4- Techniques d'analyse de complexité
5- Complexité spatiale
6- Complexité et Preuve de Correction
7- Optimisation d'algorithmes

2
 Références bibliographiques

----------------- Applications (Document ) -------------------

-----

3
 Matière: Algorithmique avancé et complexité
(AAC)

Programme de la matière :
1- Introduction à la complexité algorithmique et notions
préliminaires
• Définition d'algorithme et d’algorithmique.
• Notion de problème algorithmique et sa résolution.
• Pourquoi analyser la complexité ? Comparaison d'algorithmes pour un même problème.
• Notions de base et types de complexité : temporelle et spatiale.
2- Analyse de la complexité temporelle
3- Structures de données et complexité
4- Techniques d'analyse de complexité
5- Complexité spatiale
6- Complexité et Preuve de Correction
7- Optimisation d'algorithmes

4
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Définition d'algorithme et d’algorithmique

Un algorithme est une suite de règles précises qui permettent de résoudre un

problème en un temps fini.
Exemples de problèmes :
Pb1: Trier une liste de nombres Pb2: Recherche d’un élément
1. Tri à bulles (Bubble sort) → compare 1. Recherche linéaire : on regarde un
deux à deux et échange. par un, du début à la fin.
2. Tri rapide (Quick sort) → choisit un 2. Recherche dichotomique
pivot et divise en sous-listes. (binaire) : si la liste est triée, on
3. Tri fusion (Merge sort) → découpe la divise en deux à chaque étape.
liste puis fusionne en ordre.
Toutes ces étapes sont différentes, mais donnent le même résultat.
Efficacité :
Un éfficace algorithme doit :
 Etre rapide (gagner du temps),
 Utiliser peu de mémoire et peu d’opérations.

5
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Définition d'algorithme et d’algorithmique

Qu’est-ce que l’algorithmique ?

 L’algorithmique est la science qui étudie et conçoit les algorithmes.
Son objectif : Trouver une meilleure solution : rapide, peu coûteuse en mémoire
et simple à appliquer.
Points clés :
1. Un algorithme doit toujours être correct (donner le bon résultat).
2. Entre plusieurs solutions (Algorithmes), certaines sont plus efficaces que
d’autres.
3. Le rôle de l’algorithmique est de comparer, choisir ou inventer
l’algorithme le plus adapté.
Exemple :
Chercher un mot dans un dictionnaire :
1. Lire page par page → lent.
2. Utiliser une recherche dichotomique → beaucoup plus rapide.

6
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Notion de problème algorithmique et sa résolution
1. Qu’est-ce qu’un problème algorithmique ?

Un problème algorithmique est une question bien définie, caractérisée par trois
éléments :

1. Entrées : les données fournies.

2. Sorties : le résultat attendu.
3. Conditions : la relation entre les entrées et la sortie.

Exemple de Problème : “Trier une liste de nombres”.

1. Entrée : [7, 2, 5, 1].

2. Sortie attendue : [1, 2, 5, 7].
3. Plusieurs algorithmes (tri bulle, tri rapide, tri fusion) permettent de
résoudre ce problème.
.

7
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Notion de problème algorithmique et sa résolution
2. Résolution d’un problème algorithmique:

Résoudre un problème ne signifie pas seulement écrire “un” algorithme, mais suivre
une démarche précise :

1. Formuler clairement le problème (définir entrées et sorties).

2. Choisir une stratégie de résolution (appelée paradigme).
3. Concevoir un algorithme basé sur cette stratégie.
4. Analyser son efficacité en termes de temps d’exécution et d’utilisation
mémoire.
5. Comparer cet algorithme à d’autres possibles pour retenir le plus adapté.

Exemple : pour trier une liste, le tri à bulles est correct mais coûteux (O(n²)),
tandis que le tri rapide est plus efficace (O(n log n)).

8
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Notion de problème algorithmique et sa résolution
3. Paradigmes de conception:
En algorithmique avancée, on classe les algorithmes selon des paradigmes, c’est-à-
dire des philosophies de résolution. Chaque paradigme regroupe une famille de
méthodes adaptées à certains types de problèmes.

1. Diviser pour régner : découper le problème en sous-problèmes plus petits,

résoudre séparément puis combiner.
 Exemple : tri rapide, tri fusion.
2. Programmation dynamique : réutiliser des résultats intermédiaires pour éviter
de recalculer plusieurs fois les mêmes choses.
 Exemple : suite de Fibonacci optimisée, problème du sac à dos.
3. Glouton (Greedy) : faire à chaque étape un choix local optimal en espérant une
solution globale satisfaisante.
 Exemple : rendu de monnaie avec les plus grosses pièces.

9
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Pourquoi analyser la complexité ? Comparaison d'algorithmes pour un même problème

1. Qu’est-ce que la complexité ?

La complexité algorithmique mesure les ressources qu’un algorithme

utilise en fonction de la taille de l’entrée (n).

Ces ressources peuvent être de deux types :

1. Complexité en temps : nombre d’opérations nécessaires selon la

taille de l’entrée.
2. Complexité en espace : quantité de mémoire utilisée.

 L’analyse d’un algorithme dépend de la taille de l’entrée, pas de la

machine. Cela permet de comparer les algorithmes de façon indépendante
du matériel.
.

10
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Pourquoi analyser la complexité ? Comparaison d'algorithmes pour un même problème

2. Pourquoi l’analyser ?

1. Parce qu’un même problème peut avoir plusieurs algorithmes de

résolution.
2. Certains sont corrects mais lents, d’autres optimisés et rapides.
3. L’analyse de complexité permet de prédire le comportement de
l’algorithme quand la taille des données augmente.

Exemple :

Pour trier 10 éléments, peu importe la méthode, tout paraît rapide.

Mais pour trier 1 million d’éléments, la différence devient énorme :
Tri bulle (O(n²)) → ≈ 10¹² opérations.
Tri fusion (O(n log n)) → ≈ 20 millions d’opérations.

11
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Pourquoi analyser la complexité ? Comparaison d'algorithmes pour un même problème

3. Comparaison d’algorithmes pour un même problème

Prenons un problème concret : chercher un élément dans une liste.

1. Recherche séquentielle (linéaire) :

On parcourt la liste élément par élément.
Complexité : O(n) (proportionnelle à la taille de la liste).

2. Recherche dichotomique (binaire) :

La liste doit être triée.
À chaque étape, on coupe la liste en deux.
Complexité : O(log n) (beaucoup plus rapide).

 Si n = 1 000 000 :
Recherche linéaire → jusqu’à 1 000 000 comparaisons.
Recherche binaire → environ 20 comparaisons seulement.

12
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Notions de base et types de complexité : temporelle et spatiale
2. Complexité temporelle

Définition : la complexité temporelle mesure le nombre d’opérations

élémentaires qu’un algorithme exécute.

On s’intéresse à la vitesse de l’algorithme.

Elle dépend de :
1. la taille de l’entrée (n),
2. la structure de l’algorithme (boucles, récursions, etc.).

Exemple :

1. Recherche séquentielle dans une liste de n éléments → O(n)

comparaisons au maximum.
2. Recherche dichotomique → O(log n) comparaisons seulement.

13
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Notions de base et types de complexité : temporelle et spatiale

3. Complexité spatiale

Définition : la complexité spatiale mesure la quantité de mémoire

supplémentaire qu’un algorithme nécessite, en plus des données d’entrée.

Elle inclut :
1. les variables utilisées,
2. les structures de données temporaires,
3. la mémoire des appels récursifs.

Exemple :

1. Tri par insertion → nécessite peu de mémoire supplémentaire (O(1)).

2. Tri fusion → nécessite de créer des sous-listes temporaires (O(n)).

14
 1- Introduction à la complexité algorithmique et notions
préliminaires
- Notions de base et types de complexité : temporelle et spatiale

4. Différence et importance des deux:

1. Complexité temporelle → indique si l’algorithme sera rapide.

2. Complexité spatiale → indique s’il peut tourner sur une machine avec
mémoire limitée.

Exemple concret :

Sur un smartphone, un algorithme trop gourmand en mémoire peut être

inutilisable même s’il est rapide.
Sur un supercalculateur, on privilégie souvent la rapidité au détriment de la
mémoire.

15
 Université Tahri Mohamed de Béchar
Faculté des sciences exactes
Département des Mathématiques et Informatique
1ère année Master (Intelligence Artificielle - Réseaux et Systèmes Distribués)

Matière:

Algorithmique avancée
et complexité
Cours n° 05

Enseignant : Benyamina Ahmed

1
 Matière: Algorithmique avancé et complexité
(AAC)

Programme de la matière :
1- Introduction à la complexité algorithmique et notions préliminaires
2- Analyse de la complexité temporelle

3- Structures de données et complexité

1. listes,
2. arbres,
3. graphes,
4. opérations courantes et complexité associée.

4- Techniques d'analyse de complexité

5- Complexité spatiale
6- Complexité et Preuve de Correction
7- Optimisation d'algorithmes

2
 5. Arbre binaire de recherche
1. Définition

Un arbre binaire de recherche (ABR ou BST) est un arbre binaire

(chaque nœud a au plus deux enfants) qui respecte la propriété
d’ordre :
Pour chaque nœud N :
1. Tous les éléments du sous-arbre gauche ≤ valeur de N.
2. Tous les éléments du sous-arbre droit ≥ valeur de N.
Cette propriété doit être vraie récursivement pour tous les nœuds.
75

30 80

12 60 90

3
3
 5. Arbre binaire de recherche
3. Représentation mémoire
Comme tout arbre binaire, un BST peut être représenté : 75

30 80
En mémoire par pointeurs :
12 60 90
3

# Définition d'un nœud pour un arbre # Exemple d'utilisation :

binaire (exemple BST) root = Noeud (75)
class Noeud: root.left = Node(30)
def __init__(self, key): root.right = Node(80)
self.key = key # valeur du root.left.left = Node(12)
nœud root.left.left.left = Node(3)
self.left = None # pointeur vers root.left.right = Node(60)
le fils gauche root.right.left = None
self.right = None # pointeur vers root.right.right = Node(80)
le fils droit root.right.right = Node(90)

4
 5. Arbre binaire de recherche
3. Représentation mémoire 75

Comme tout arbre binaire, un BST peut être représenté : 30 80

12 60 90
3

# Vérification : parcours infixe => tri croissant (avec doublons)

def inorder(p):
if not p: return
inorder(p.left)
print(p.data, end=" ")
inorder(p.right)
inorder(root) # attendu : 3 12 30 60 75 80 90

5
 5. Arbre binaire de recherche
2. Opérations sur les arbres binaires de recherche

Un arbre binaire de recherche (ABR) permet de localiser

efficacement un élément en suivant une branche précise selon sa
valeur (plus petite ou plus grande que la racine).
Grâce à cette structure hiérarchique, on peut retrouver rapidement un
élément et aussi trier ou ordonner une liste d’éléments de manière
structurée.
Pour exploiter un arbre binaire de recherche, il faut résoudre trois
points essentiels :

1. Gérer la multiplicité des éléments

2. Insérer un nouvel
3. Retrouver l’ordre des éléments

6
 5. Arbre binaire de recherche
2. Opérations sur les arbres binaires de recherche
1. Gérer la multiplicité des éléments
Signification :
Dans un arbre binaire de recherche, chaque nœud représente une valeur
unique. Cependant, il arrive qu’une même valeur apparaisse plusieurs fois
dans les données (par exemple plusieurs fois le nombre 15).
Pour éviter de créer plusieurs nœuds identiques, on ajoute à chaque nœud un
champ supplémentaire appelé compteur ou fréquence.
Rôle de ce champ :
Il indique combien de fois cette valeur a été insérée.
Cela simplifie la structure de l’arbre et évite la duplication de branches
inutiles.
Exemple :
Si l’on insère la valeur 10 trois fois, le nœud correspondant à 10 aura :
valeur = 10
fréquence = 3
Ainsi, on sait qu’il y a trois occurrences de la valeur 10 dans l’arbre sans
multiplier les nœuds. 7
 5. Arbre binaire de recherche
2. Opérations sur les arbres binaires de recherche
2. Insérer un nouvel élément
Signification :
L’insertion dans un arbre binaire de recherche suit une règle d’ordre :
Si la nouvelle valeur est inférieure à celle du nœud courant, on descend dans le sous-
arbre gauche.
Si elle est supérieure, on descend dans le sous-arbre droit.
On répète cette comparaison récursivement jusqu’à trouver un pointeur nul.
C’est à cet endroit précis que l’on crée le nouveau nœud.
Exemple :
Si l’arbre contient :
et qu’on veut insérer 6 :
➡ on compare 6 avec 8 → plus petit → on va à gauche.
➡ on compare 6 avec 3 → plus grand → on va à droite.
➡ le pointeur droit de 3 est NULL → on insère 6 à cet emplacement.
Résultat :

8
 5. Arbre binaire de recherche
2. Opérations sur les arbres binaires de recherche
3. Retrouver l’ordre des éléments
Signification :
Un parcours infixe permet d’extraire les valeurs de l’arbre dans l’ordre croissant.
Le principe consiste à visiter les nœuds dans cet ordre :
Le sous-arbre gauche,
Le nœud courant,
Le sous-arbre droit.
Pourquoi cela fonctionne ?
Parce qu’un arbre binaire de recherche est structuré de manière à ce que :
Toutes les valeurs du gauche soient inférieures à la racine,
Toutes celles du droit soient supérieures.
Le parcours infixe respecte donc naturellement l’ordre croissant.
Exemple :

Parcours infixe → 1, 2, 3, 5, 8, 9
→ Les valeurs apparaissent triées automatiquement.

9
 5. Arbre binaire de recherche
2. Algorithme de recherche d’un élément :
La recherche d’un élément dans un arbre binaire de recherche est très facile si on
profite du caractère récursif d’un arbre binaire.
Programme de recherche dans un arbre binaire de recherche en Python
# Définition d'un nœud d'arbre binaire
class Noeud:
def __init__(self, data):
self.data = data
self.gauche = None
self.droit = None
# Fonction de recherche récursive
def Chercher(P, X):
if P is None: # Cas de base : l'arbre (ou la sous-branche) est vide
return 0
else:
if P.data == X: # Si l'élément courant correspond à X
return 1
elif X < P.data: # Si X est plus petit → aller à gauche
return Chercher(P.gauche, X)
else: # Sinon → aller à droite
return Chercher(P.droit, X)
10
 5. Arbre binaire de recherche
2. Algorithme d’insertion d’un élément :

L’élément à ajouter est inséré là où on l’aurait trouvé s’il avait été présent dans
l’arbre. L’algorithme d’insertion recherche donc l’élément dans l’arbre et, quand il
aboutit à la conclusion que l’élément n’appartient pas à l’arbre (il aboutit à la terre), il
insère l’élément comme fils du dernier noeud visité.

Programme d’insertion d’un élément dans un arbre binaire de recherche

# Définition d'un nœud de l'arbre binaire
class Noeud:
def __init__(self, data):
self.data = data
self.freq = 1 # compteur d'occurrences
self.gauche = None
self.droit = None

11
 5. Arbre binaire de recherche
2. Algorithme d’insertion d’un élément :
Programme d’insertion d’un élément dans un arbre binaire de recherche
# Fonction d'insertion récursive
def Inserer(P, X):
# Si l'arbre est vide, on crée un nouveau nœud pour X
if P is None:
return Noeud(X)

# Si l'élément existe déjà, on incrémente la fréquence

if X == P.data:
P.freq += 1

# Si X est plus petit → insérer dans le sous-arbre gauche

elif X < P.data:
P.gauche = Inserer(P.gauche, X)

# Si X est plus grand → insérer dans le sous-arbre droit

else:
P.droit = Inserer(P.droit, X)

return P

12
 5. Arbre binaire de recherche
2. Algorithme de suppression d’un élément :

La suppression d’un élément est plus compliquée que l’insertion, car si cet élément
est un père à qui confier ses fils ?
Il existe trois cas possibles :

1er cas : l’élément à supprimer n’a pas de fils

2ème cas : l’élément a un fils unique
3ème cas : l’élément à supprimer a deux fils

13
 5. Arbre binaire de recherche
2. Algorithme de suppression d’un élément :

1er cas : l’élément à supprimer n’a pas de fils  il est terminal et il suffit de le
supprimer
Exemple : Suppression du nœud 13

14
 5. Arbre binaire de recherche
2. Algorithme de suppression d’un élément :

2ème cas : l’élément a un fils unique  on supprime le nœud et on relie son fils à son
père
Exemple : Suppression du nœud 16

15
 5. Arbre binaire de recherche
2. Algorithme de suppression d’un élément :

3ème cas : l’élément à supprimer a deux fils  on le remplace par son successeur qui
est toujours le minimum de ses descendants droits.
Exemple : Suppression du nœud 5

16
 5. Arbre binaire de recherche
4. Complexités des opérations dans l’arbre binaire de recherche
Complexités
1. Complexité générale : O(h)
→ La complexité d’une opération dans un arbre binaire de recherche dépend
de la hauteur de l’arbre (h), car il faut au maximum parcourir un chemin
allant de la racine jusqu’à une feuille.  Figure 1 : O(h) = O(2)
2. Arbre équilibré : O(log n)
→ Lorsque l’arbre est équilibré, sa hauteur est proportionnelle au logarithme
du nombre de nœuds, ce qui permet d’effectuer les opérations de recherche,
d’insertion ou de suppression très efficacement.  figure 2 : O(log2​(n)) =
O(log2​(10)) ≈ O(3,3)
3. Arbre dégénéré : O(n)
→ Si l’arbre est déséquilibré (chaîne linéaire), sa hauteur devient égale au
nombre total de nœuds, rendant les opérations aussi coûteuses qu’un
parcours de liste.  Figure 3 : O(n) = O(7)

1 2 3

17
 Université Tahri Mohamed de Béchar
Faculté des sciences exactes
Département des Mathématiques et Informatique
1ère année Master (Intelligence Artificielle - Réseaux et Systèmes Distribués)

Matière:

Algorithmique avancée
et complexité
Cours n° 02

Enseignant : Benyamina Ahmed

1
 Matière: Algorithmique avancé et complexité
(AAC)

Programme de la matière :
1- Introduction à la complexité algorithmique et notions préliminaires
2- Analyse de la complexité temporelle
1. Notation de Landau (grand O )
2. Classification des algorithmes
3. Règles de calcul sur les O(n) :
4. Temps d’éxecution
3- Structures de données et complexité
4- Techniques d'analyse de complexité
5- Complexité spatiale
6- Complexité et Preuve de Correction
7- Optimisation d'algorithmes

2
 II. Notion de complexité algorithmique
1- Notation de Landau grand O(n) :

Hypothèse : La complexité dépend des données du problème

Notation de Landau : f est en O(g(n)) ou f  O(g(n)) signifie :
 n>n00, telle que c>0 / f(n)≤ c.g(n)

3
 II. Notion de complexité algorithmique
1- Notation de Landau O(n) :
Règle Preuve
Si f(n)  O(kg(n)), alors f(n) Si f(n)  O(kg(n)), alors k'>0 tels que :
 O(g(n)) f(n)≤ kk'g(n)=Kg(n) n positif
Alors f(n)  O(g(n))
5n2+3n+4  O(n2) On a: n>1 , 5n2+3n+4< 5n2+3n2+4n2 =12n2
Donc si on pose k=12 et n0=1
On obtient : n>n0, 5n2+3n+4<kn2
Ce qui prouve que 5n2+3n+4  O(n2)
2n+2 is O(2n). 2n+2 = 2n ·22 = 4·2n ; par conséquent, nous pouvons prendre c =
4 et n0 = 1 dans ce cas.
si f(n) = O(g(n)) et g(n) = Ce que nous devons montrer ici, c'est que f(n) ≤ c3 · h(n) pour n
O(h(n)), alors f(n) = > n3 étant donné que f(n) ≤ c1 · g(n) et g(n) ≤ c2 · h(n), pour n
O(h(n)). > n1 et n > n2, respectivement. En mettant en cascade ces
inégalités, on obtient ça f(n) ≤ c1 · g(n) ≤ c1c2 · h(n) pour n >
n3 = max(n1, n2).

4
 II. Notion de complexité algorithmique
2- Classification des algorithmes
Cas d’utilisation courant Cas d’utilisation
courant
• Accéder au premier élément d’un ensemble de données G(n)=1  C est O(1)

• Couper un ensemble de données en deux parties G(n)=log(n)  C est

O(log(n))
• Algorithme traitant directement sur chacune des n donnés G(n)=n  C est O(n)
• Parcourir un ensemble de données
• Couper répétitivement un ensemble de données en deux, et G(n)=n.log(n)  C est
parcourir chacune de ces parties O(n.log(n))
• Algorithme traitant généralement des couples de données (dans G(n)=n2  C est O(n2)
deux boucles imbriquées)
• Complexité cubique. Idem quadratique mais avec ici par G(n)=n3  C est O(n3)
exemple trois boucles imbriquées
• Complexité exponentielle. Générer tous les sous-ensembles G(n)=2n  C est O(2n)
possibles d’un ensemble de données
• Générer toutes les permutations possibles d’un ensemble de G(n)=n !  C est
données O(n !)
5
 II. Notion de complexité algorithmique
3- Règles de calcul sur les O(n)
Règle O(g(n))

1- O(4n + 3) O(n)

2- O(log n) + O(log n) O(log n)

3- O(n2) + O(n) = O(n2)

4- O(m).O(n)= 0(m.n)

5- O(n3).O(n2.log n) = O(n5n2.log n)

6- O(n2/2) = O(n2) =

7- f(n)O(g(n)) implique () g(n)  O(f(n))

8- f(n)=O(g(n)) implique log(f(n))=O(log(g(n)))

où log(g(n))1 n >>0
9- f(n)=O(g(n)) implique 2f(n)=O(2g(n))

6
 II. Notion de complexité algorithmique
3- Règles de calcul sur les O(n)
Règle O(g(n))

10- Si f(n) = O(g(n)) et g(n) = O(h(n)), alors f(n) = O(h(n))

11- Si f(n)  O(kg(n)) Alors f(n)  O(g(n)) c'est faux car n2 O(n3) mais n3O(n2)

12- Si f1(n)=O(g1(n)) et f2(n) = O(g2(n)) alors (f1 + f2)(n) = O(max(g1(n), g2(n)))

13- Si f1(n)=O(g1(n)) et f2(n) = O(g2(n)) alors f1(n)f2(n) = O(g1(n) g2(n))

14- Si f1(n)=O(g1(n)) et f2(n) = O(g2(n)) alors f1(n)f2(n) = O(g1(n) g2(n))

15- la complexité d’un ensemble d’instructions la somme de leurs complexités

16- Instruction if: maximum entre le then et le else

7
II. Notion de complexité algorithmique
3- Règles de calcul sur les O(n)

Règle n°
17

Les opérations élémentaires telle

que l’affectation, test, accès à un
tableau, opérations logiques et
arithmétiques, lecture ou écriture
d’une variable simple ... etc, sont :
en O(1)

8
 II. Notion de complexité algorithmique
3- Règles de calcul sur les O(n)

Règle n° 18
Instructions de répétition
1. la complexité de la boucle for est calculée par la :
- complexité du corps de cette boucle
- multipliée par le nombre de fois qu’elle est répétée.
2. En règle générale, pour déterminer la complexité
d’une boucle while, il faudra avant tout déterminer :
- le nombre de fois que cette boucle est répétée,
- ensuite le multiplier par la complexité du corps de
cette boucle.

9
 Cours n°03
II. Notion de complexité algorithmique
3- Règles de calcul sur les O(n)

Règle n° 19

Procédure et fonction:

Leur complexité est déterminée par celui de leur

corps. L’appel à une fonction est supposé prendre
un temps constant en O(1)

10
II. Notion de complexité algorithmique
4- Temps d’exécution
Temps d'exécution :

106 opérations élémentaires par seconde

11
II. Notion de complexité algorithmique
4- Temps d’exécution

Exemple de temps d'exécution

12
 II. Notion de complexité algorithmique
Conclusion

d'après ces schémas, il est clair que certains algorithmes

sont utilisables pour résoudre des problèmes sur
ordinateurs, et que d'autres ne sont pas, ou peu utilisable.
Les algorithmes utilisables pour des données de petite
tailles sont ceux qui s'exécutent en temps : Constant,
logarithmique, linéaire ou en n.log n.
Les algorithmes polynomiales en O(nn) n>0 ne sont pas
vraiment utilisable pour n>3.
Les algorithmes exponentielles en O(2n) sont à peu près
peu utilisable sauf pour des problèmes de petites taille.

13
Structures de données
et complexité

PROCHAIN COURS

14
Université Tahri Mohamed de Béchar
Faculté des sciences exactes
Département des Mathématiques et Informatique
Deuxième Année Ingénieur Informatique
Matière : Algorithmiques et structures de données 3

Correction Test n° 01
Répondez aux questions suivantes par cocher la case du choix correcte
1. Question 1: Quelle est la profondeur du nœud racine (root node) ?
 A. 0 ✅
 B. 1
 C. 2
 D. 3

2. Question 2: Pour obtenir une expression préfixée, quel type de parcours d’arbre faut-il utiliser ?
 A. Parcours en largeur (Level-order)
 B. Parcours préfixé (Pre-order) ✅
 C. Parcours postfixé (Post-order)
 D. Parcours infixe (In-order)

3. Question 3: Quel est le nombre maximal d’enfants qu’un nœud d’un arbre binaire peut avoir ?
 A. 0
 B. 1
 C. 2 ✅
 D. 3

4. Question 4: Lequel des algorithmes de parcours suivants n’est pas utilisé pour parcourir un arbre
?
 A. Parcours postfixé
 B. Parcours préfixé
 C. Parcours infixe
 D. Parcours aléatoire (Randomized) ✅

5. Question 5: Combien d’enfants un nœud peut-il avoir dans un arbre binaire ?

 A. 2
 B. 0 ou 1
 C. 0 ou 1 ou 2 ✅
 D. Un nombre quelconque d’enfants

6. Question 6: Laquelle des affirmations suivantes est fausse à propos d’un arbre binaire de
recherche (Binary Search Tree) ?
 A. L’enfant gauche est toujours inférieur à son parent
 B. L’enfant droit est toujours supérieur à son parent
 C. Les sous-arbres gauche et droit doivent aussi être des arbres binaires de recherche
 D. La séquence Inorder donne un ordre décroissant d’éléments ✅
7. Question 7: Dans la liste [10, 5, 20, 15, 30], combien de comparaisons sont nécessaires pour
déterminer que 25 n’est pas présent en utilisant la recherche linéaire ?
 A. 6
 B. 2
 C. 4
 D. 5 ✅

8. Question 8: Que fait la fonction Python suivante ?

def func(root):
if root is None:
return
func(root.left)
func(root.right)
print(root.data)
 A. Parcours préfixé (Preorder)
 B. Parcours infixe (Inorder)
 C. Parcours postfixé (Postorder) ✅
 D. Parcours en largeur (Level order)

9. Question 9: Quelle structure de données a une taille fixe ?

 A. Tableaux (Arrays) ✅
 B. Listes chaînées (Linked lists)
 C. Arbres (Trees)
 D. Graphes (Graphs)

10. Question 10: Laquelle des structures de données suivantes est non linéaire ?
 A. Piles (Stacks)
 B. Listes (Lists)
 C. Chaînes (Strings)
 D. Arbres (Trees) ✅

11. Question 11: Dans une pile (stack), si TOP = MAX – 1, alors la pile est :
 A. Vide
 B. Pleine (Full) ✅
 C. Contient quelques données
 D. Aucune des réponses ci-dessus

12. Question 12: Dans une pile (stack), l’insertion s’effectue à :

 A. Sommet (Top) ✅
 B. Avant (Front)
 C. Arrière (Rear)
 D. Milieu (Mid)

13. Question 13: Une pile (stack) est aussi appelée :

 A. Dernier entré, premier sorti (LIFO) ✅
 B. Premier entré, dernier sorti
 C. Dernier entré, dernier sorti
 D. Premier entré, premier sorti
14. Question 14: Dans une file (queue), la position à partir de laquelle un élément est supprimé
s’appelle :
 A. Sommet (Top)
 B. Avant (Front) ✅
 C. Arrière (Rear)
 D. Milieu (Mid)

15. Question 15: Quelle est la complexité dans le pire des cas de l’algorithme Quick Sort ?
 A. O(N)
 B. O(N²) ✅
 C. O(log N)
 D. O(N log N)

16. Question 16: Une machine met 200 secondes pour trier 1000 éléments avec Quick Sort.
Combien de temps approximatif faut-il pour trier 200 éléments ?
 A. 31,11 secondes ✅
 B. 45,54 secondes
 C. 20 secondes
 D. 60,2 secondes

17. Question 17: Quel algorithme de tri est le mieux adapté pour trier un tableau d’un million
d’éléments ?
 A. Insertion sort
 B. Quick sort ✅
 C. Merge sort
 D. Bubble sort

18. Question 18: Quelle est la complexité moyenne de l’algorithme Merge Sort ?
 A. O(n log n) ✅
 B. O(n²)
 C. O(n² log n)
 D. O(n log n²)

19. Question 19: Quelle est la complexité spatiale auxiliaire (mémoire utilisée en plus) de Merge
Sort ?
 A. O(1)
 B. O(log n)
 C. O(n log n)
 D. O(n) ✅

20. Question 20: Combien de passes contient l’algorithme Insertion Sort ?

 A. N + 1
 B. N
 C. N − 1 ✅
 D. N²
21. Question 21: Quel est le temps d’exécution moyen d’un algorithme Insertion Sort ?
 A. O(N log N)
 B. O(N²) ✅
 C. O(log N)
 D. O(N)

22. Question 22: Quelle est la complexité temporelle de la recherche binaire itérative ?
 A. O(n log n)
 B. O(n²)
 C. O(log n) ✅
 D. O(n)

23. Question 23: Quelle est la formule utilisée pour calculer la position dans la recherche par
interpolation ?
 A. ((x − A[low]) × (high − low)) / (A[high] − A[low])
 B. x + ((x − A[low]) × (high − low)) / (A[high] − A[low])
 C. low + ((x − A[low]) × (high − low)) / (A[high] − A[low]) ✅
 D. high + ((x − A[low]) × (high − low)) / (A[high] − A[low])
Évaluation d’une Expression Postfixée
Ce document explique comment évaluer une expression arithmétique en notation
postfixée (ou polonaise inversée) à partir d’un arbre binaire d’expression.

1. Expression donnée
Représentation postfixée : yxy+6/z+=

Expression infixée équivalente : y = ((x + y) / 6) + z

2. Principe d’évaluation postfixée

L’évaluation d’une expression postfixée utilise une pile (stack) selon les règles suivantes
:

1. Lire la chaîne de gauche à droite.

2. Empiler les opérandes (variables ou nombres).
3. Lorsqu’un opérateur est rencontré, dépiler les deux derniers éléments, appliquer
l’opération et empiler le résultat.
4. À la fin, le résultat restant dans la pile correspond à la valeur finale.

3. Étapes d’évaluation
Étape Élément lu Action Contenu de la Explication
pile

1 y Empiler [y] Variable y

2 x Empiler [y, x] Variable x

3 y Empiler [y, x, y] Variable y

4 + Dépiler y et x, [y, (x + y)] Résultat de

calculer (x + y) l’addition

5 6 Empiler [y, (x + y), 6] Constante 6

6 / Dépiler 6 et (x [y, ((x + y)/6)] Division

+ y), calculer effectuée
(x + y)/6

7 z Empiler [y, ((x + y)/6), Variable z

z]

8 + Dépiler z et ((x [y, (((x + y)/6) Addition

+ y)/6), + z)] effectuée
calculer ((x +
 y)/6) + z

9 = Dépiler (((x + [résultat final] Affectation

y)/6) + z) et y, terminée
faire y = (((x +
y)/6) + z)

4. Résultat final
Résultat arithmétique final : y = ((x + y) / 6) + z

Cette expression correspond à la forme infixée classique de l’expression donnée en

notation postfixée.