0% ont trouvé ce document utile (0 vote)

5 vues273 pages

Introduction aux algorithmes et récursivité

Ce document est un cours sur l'algorithmique, introduisant la notion d'algorithme, sa correctitude et les algorithmes récursifs. Il explique les concepts de base tels que la définition d'un algorithme, la différence entre algorithme et implémentation, ainsi que l'importance des invariants de boucle pour prouver la correctitude des algorithmes. Le cours aborde également des exemples pratiques d'algorithmes, comme le calcul de la somme d'une série géométrique et la recherche du maximum dans une liste.

Transféré par

nina.henzelin

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

5 vues273 pages

Introduction aux algorithmes et récursivité

Transféré par

nina.henzelin

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

ICS - Algorithmique

Cours 7 : Introduction, correctitude,

algorithmes récursifs

12.11.2025

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 1 / 45

7.1 Introduction

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 2 / 45

Qu’est-ce qu’un algorithme ?

↭ Un algorithme est une procédure pour résoudre un

problème.
↭ Il prend en entrée (input) une instance de ce problème
↭ et produit la sortie (output) correspondant à cette instance.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 3 / 45

Qu’est-ce qu’un algorithme ?

Par exemple, on peut écrire un algorithme qui calcule le

minimum d’une liste de nombres.
↭ Entrée : une liste de nombre réels
↭ Sortie : le minimum des nombres de la liste
↭ Algorithme (en français) :
↭ mettre le_min = le premier élément de la liste ;
↭ passer sur chaque élément de la liste. S’il est plus petit que
le_min, mettre le_min = cet élément ;
↭ retourner le_min.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 4 / 45

Qu’est-ce qu’un algorithme ?
↭ Une instance de ce problème : la liste [10, -3, 7, 2, 6, 7]

↭ Une autre instance : la liste [8, 33, 5, -20, 0]

↭ Ne sont pas des instances valides de ce problème :

↭ [[0, 1], [1, 2]]
↭ [’a’, ’b’, ’c’] (même s’il existe un ordre sur les chaîne de
caractères !)

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 5 / 45

Problème vs. algorithme

↭ A un problème peuvent correspondre plusieurs

algorithmes qui le résolvent
↭ Comment caractériser “le meilleur” ?
↭ Pour certains problèmes on ne sait pas s’il existe un
algorithme qui les résoud ; ! pour certains problèmes on
sait qu’il n’en existe aucun. "
↭ Pour certains problèmes, on ne connaît encore aucun
algorithme e!cace qui les résoud.
↭ Que veut dire “e!cace” ?

1. [Link]
2. [Link]
Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 6 / 45
Algorithme vs. implémentation

↭ Un algorithme est une procédure générale pour résoudre

un problème.
↭ Un programme est une implémentation spécifique d’un
algorithme dans un langage de programmation donné, par
exemple Python, et sur un système donné.
↭ A un même algorithme correspondent donc plusieurs
implémentations. #
↭ Les algorithmes vus dans ce cours seront donnés sous
forme de programmes Python.

3. Voir [Link] pour des implémentations de divers

algorithmes en plus de 800 langages de programmation.
Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 7 / 45
Problème, algorithmes, implémentation

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 8 / 45

Structure de ces 6 cours

↭ Formalisation de la notion d’algorithme, correctitude d’un

algorithme
↭ Algorithmes récursifs
↭ Complexité algorithmique (analyse mathématique du
temps de parcours des algorithmes)
↭ Algorithmes de recherche
↭ Algorithmes de tri
↭ Algorithmes de graphes

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 9 / 45

7.2 Correctitude
d’algorithmes

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 10 / 45

Evaluer un algorithme

↭ Correctitude => fout

avant

↭ E!cacité

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 11 / 45

Invariant de boucle

Comment prouver qu’un algorithme calcule bien ce qu’il est

censé calculer ?
↭ Pour un algorithme sans boucles, c’est assez simple.
↭ Pour un algorithme contenant des boucles while ou for,
c’est plus compliqué !
↭ On formule et on prouve un invariant de boucle : une
propriété qui est valide pour toutes les itérations de la
boucle et dont la validité à la sortie de la boucle prouve
qu’elle calcule bien la bonne valeur.
>
preuva parrecurence

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 12 / 45

Invariant de boucle

L’utilisation d’un invariant de boucle pour prouver la

correctitude d’un programme se fait en trois étapes :
↭ Initialisation : Prouver que l’invariant de boucle est vrai
avant la première itération de la boucle
↭ Maintenance : Prouver que si l’invariant de boucle est vrai
pour une itération de la boucle, alors il est vrai pour la
prochaine itération de la boucle
(Avec ces deux étapes, on a prouvé que l’invariant reste vrai
à toutes les itérations de la boucle.)
↭ Terminaison : Si l’invariant de boucle est vrai à la sortie de
la boucle, on en déduit (directement ou indirectement) la
correctitude du programme.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 13 / 45

Une boucle pour calculer une série géométrique

Problème : pour un réel a et un entier n → 0 en entrée, écrire un

algorithme (sous forme de fonction Python) qui retourne
n→1
!
ak = 1 + a + a2 + · · · + an→1 .
k =0

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 14 / 45

Une boucle pour calculer une série géométrique

Problème : pour un réel a et un entier n → 0 en entrée, écrire un

algorithme (sous forme de fonction Python) qui retourne
n→1
!
ak = 1 + a + a2 + · · · + an→1 .
k =0

Voici une solution :

def serie_geom (a, n):

s = 0
for i in range(n):
s = s * a + 1

return s

Prouvons que cet algorithme calcule bien la somme demandée !

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 14 / 45

Série géométrique : invariant de boucle

def serie_geom (a, n):

s = 0
for i in range(n):
s = s * a + 1

return s

Invariant de boucle :
Au début de la i ème itération de la boucle for, s contient la
valeur
i →1
!
ak = 1 + a + · · · + ai →1 .
k =0

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 15 / 45

Série géométrique : invariant de boucle - preuve
(initialisation)

def serie_geom (a, n):

Invariant de boucle :
s = 0 Au début de la i ème itération de la boucle
for i in range(n): for, s contient la valeur
s = s * a + 1 i →1
!
ak = 1 + a + · · · + ai → 1 .
return s k =0

↭ Initialisation : Avant le début de la boucle for, s = 0, ce

qui correspond bien à la somme vide. $

!j
4. Une somme de la forme i k avec j < i est dite vide et vaut 0.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 16 / 45

Série géométrique : invariant de boucle - preuve
(maintenance)

def serie_geom (a, n):

Invariant de boucle :
s = 0 Au début de la i ème itération de la boucle
for i in range(n): for, s contient la valeur
s = s * a + 1 i →1
!
ak = 1 + a + · · · + ai → 1 .
return s k =0

↭ Maintenance : On suppose qu’au début de la i ème

"
itération, on a s = ik→=10 ak . Or la i ème itération consiste à
exécuter l’instruction s = s * a + 1. La valeur de s
devient donc
i
!
(1 + a + · · · + ai →1 )a + 1 = (a + a2 + · · · + ai ) + 1 = ak
k =0

à la fin de la i ème itération (et au début de la i + 1ème).

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 17 / 45
Série géométrique : invariant de boucle - terminaison

def serie_geom (a, n):

Invariant de boucle :
s = 0 Au début de la i ème itération de la boucle
for i in range(n): for, s contient la valeur
s = s * a + 1 i →1
!
ak = 1 + a + · · · + ai → 1 .
return s k =0

↭ Terminaison : A la sortie de la boucle (càd au début de la

"
“n”ème itération, qui n’aura pas lieu), on a s = n1→1 k , ce
qui est exactement ce que la boucle prétend calculer.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 18 / 45

Une boucle pour calculer un maximum

def max_liste (L):

’’’
Entree : liste L de nombres de taille >= 1
Sortie : maximum de L
’’’
max_L = L[0]

for i in range (1, len(L)):

if L[i] > max_L:
max_L = L[i]

return max_L

Cet algorithme retourne le maximum de la liste L.

l'invariant
comprendre ce
que fait l'algo pour
trouver

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 19 / 45

Maximum : invariant de boucle

def max_liste (L):

’’’
Entree : liste L de nombres de taille >= 1
Sortie : maximum de L
’’’
max_L = L[0]

for i in range (1, len(L)):

if L[i] > max_L:
max_L = L[i]

return max_L

Invariant de boucle : Au début de la i ème itération de la boucle

for, max_L a la valeur du maximum de L[0:i].

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 20 / 45

Maximum : invariant de boucle - preuve (initialisation)

Invariant de boucle :
Au début de la i ème itération de la
boucle for, max_L a la valeur du
maximum de L[0:i].

↭ Initialisation : Avant le début de la boucle for, donc au

début de l’itération i = 1, max_L est égal à L[0] qui est
bien le maximum (et l’unique élément) de L[0:1].

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 21 / 45

Maximum : invariant de boucle - preuve (maintenance)

Invariant de boucle :
Au début de la i ème itération de la
boucle, max_L a la valeur du
maximum de L[0:i].

↭ Maintenance : On suppose qu’au début de la i ème

itération, max_L est égal au maximum de L[0:i]. Durant la
i ème itération, on a"ecte à max_L la valeur
max(max_L, L[i]) = max(L[0:i+1])
et donc au début de la prochaine itération, max_L est bien
égal au maximum de L[0:i+1].

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 22 / 45

Maximum : invariant de boucle - terminaison

Invariant de boucle :
Au début de la i ème itération de la
boucle, max_L a la valeur du
maximum de L[0:i].

↭ Terminaison : A la sortie de la boucle (c’est-à-dire au début

de la len(L)-ième itération, qui n’aura pas lieu), max_L est
égal au maximum de L[0:len(L)], donc au maximum de
la liste entière.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 23 / 45

Condition de terminaison

↭ Si l’algorithme contient une boucle while, il faut prouver

que l’algorithme termine.
↭ Pour cela, on définit en général une expression (un variant
de boucle)
↭ qui croît ou décroît strictement en fonction du nombre
d’itérations
↭ telle que la boucle termine lorsque l’expression atteint une
certaine valeur.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 24 / 45

Algorithme d’Euclide

↭ Etant donné deux entiers a et b strictement positifs, on veut

calculer leur plus grand commun diviseur (pgcd).
↭ pgcd(3060, 924) = pgcd(22 ·32 ·5·17 , 22 ·3·7·11) = 22 ·3 = 12.
↭ Trouver la factorisation en nombres premiers d’un très
grand nombre est un problème qu’on conjecture (et qu’on
espère) très di!cile.
↭ L’algorithme d’Euclide, beaucoup plus simple, se base sur
une propriété importante :

pgcd(a, b) = pgcd(b, a mod b). (↑)

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 25 / 45

pgcd(a, b) = pgcd(b, a mod b)
Preuve :
↭ On écrit la division entière de a par b comme

a = bq + r , 0 ↓ r < b,
a = bq + (a mod b).

↭ Cette équation montre immédiatement qu’un diviseur de b et

r divise aussi a (et b).
↭ En réorganisant cette équation en

r = a ↔ bq

on voit aussi qu’un diviseur de a et b divise également r (et b).

↭ Par conséquent, a et b ont exactement les mêmes diviseurs
communs que b et r . Par conséquent, leur pgcd est bien sûr le
même. ↫
Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 26 / 45
Algorithme d’Euclide - Exemples
30

r
pgcd(3060, 924) = pgcd(924, 288)
38 @
= pgcd(288, 60) %
Ay
= pgcd(60, 48) 10
¢
U

= pgcd(48, 12)Pas reste

ce
u Z
-
= pgcd(12, 0) = 12. τ

pgcd(2437, 181) = pgcd(181, 84)

= pgcd(84, 13)
= pgcd(13, 6)
= pgcd(6, 1)
= pgcd(1, 0) = 1.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 27 / 45

Algorithme d’Euclide - terminaison

On peut utiliser ce fait pour créer un algorithme.

def pgcd(a, b):
’’’
Entree : a, b entiers strictement positifs
Sortie : plus grand diviseur commun de a et b
’’’
i, k = a, b

while k > 0:
i, k = k, i % k

return i

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 28 / 45

Algorithme d’Euclide - terminaison

On peut utiliser ce fait pour créer un algorithme.

def pgcd(a, b):
’’’
Entree : a, b entiers strictement positifs
Sortie : plus grand diviseur commun de a et b
’’’
i, k = a, b

while k > 0:
i, k = k, i % k

return i

↭ Pourquoi cet algorithme termine-t-il ?

↭ k décroît d’au moins 1 à chaque itération de la boucle while
(i mod k < k et ce sont des entiers).
↭ La boucle se termine lorsque k (initialement > 0) atteint
une valeur ↓ 0.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 28 / 45

Algorithme d’Euclide - correctitude

def pgcd(a, b):

i, k = a, b
while k > 0:
Pourquoi cet algorithme rend-il
i, k = k, i % k une valeur correcte ?
return i

↭ Au moment où l’algorithme retourne la valeur i ,

↭ k vaut 0 (k étant le reste d’une division entière, il n’est
jamais négatif)
↭ La valeur rendue i = pgcd(i , 0) = pgcd(i , k ).
↭ Or l’égalité pgcd(a, b) = pgcd(b, a mod b) (avec la
terminaison de la boucle while) implique l’invariant de
boucle :
A chaque itération de la boucle, pgcd(i , k ) = pgcd(a, b).
↭ Pour a, b entiers strictement positifs en entrée, l’algorithme
retourne donc bien pgcd(a, b).

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 29 / 45

7.3 Algorithmes récursifs

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 30 / 45

Algorithmes récursifs

↭ Un algorithme récursif résout une instance d’un problème

en résolvant une ou plusieurs instances du même problème
de taille plus petite et combinant les solutions obtenues
pour obtenir la solution à l’instance initiale du problème.
↭ On parle du paradigme “diviser-pour-régner”.
↭ La correctitude de l’algorithme pour une instance d’une
certaine taille découlera en général de la correctitude pour
les instances plus petites.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 31 / 45

Algorithmes récursifs

↭ Un algorithme récursif résout une instance d’un problème

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 31 / 45

Algorithmes récursifs

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 32 / 45

Factorielle

↭ Pour n ↗ N, la factorielle de n est définie comme

n! = n · (n ↔ 1) · · · 2 · 1

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 33 / 45

Factorielle

↭ Pour n ↗ N, la factorielle de n est définie comme

#
n · (n ↔ 1)! , n → 1
n! = n · (n ↔ 1) · · · 2 · 1 =
1 ,n = 0

↭ On peut calculer la valeur de n! à partir de celle de (n ↔ 1)!,

c’est-à-dire ramener la résolution du problème pour une
instance de taille n à la résolution du problème pour une
instance de taille n ↔ 1.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 33 / 45

Factorielle
Cela suggère l’algorithme suivant :

↭ Pour le cas de base, la valeur de la fonction est définie

directement, sans appels récursifs. - casonon connait
↭ On peut définir un ou plusieurs cas de base. La réponse

↭ On peut e"ectuer un ou plusieurs appels récursifs.

↭ fact calcule la factorielle de n avec n appels récursifs.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 34 / 45

Appels de fonctions - visualisation

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 35 / 45

Factorielle - appels récursifs

Vous pouvez suivre les appels récursifs de la fonction

factorielle :
↭ sur Python Tutor
↭ sur Recursion Visualizer

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 36 / 45

Factorielle - appels récursifs

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 37 / 45

Suite de Fibonacci

↭ Pour n ↗ N, le nème nombre de Fibonacci est défini comme


fn→1 + fn→2 , n → 2

fn = 1 ,n = 1


0 ,n = 0

↭ On peut ramener la résolution du problème pour une

instance de valeur n à la résolution du problème pour deux
instances de valeur n ↔ 1 et n ↔ 2.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 38 / 45

Suite de Fibonacci

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 39 / 45

Fibonacci - appels récursifs

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 40 / 45

Fibonacci - appels récursifs

On peut prouver que pour l’entrée n le nombre d’appels récursifs de

fib et son temps de parcours sont exponentiels en n.

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 41 / 45

Somme récursive

On a déjà vu un algorithme itératif (contenant une boucle) qui

prend en entrée un entier n strictement positif et calcule la
somme des nombres de 1 à n.

def somme (n):

s = 0
for i in range (1, n+1):
s += i
return s

Peut-on écrire un algorithme récursif (sans boucle) somme_rec

qui calcule la même somme ?

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 42 / 45

Somme récursive

↭ Pour n entier strictement positif,

n
#
! 1 ,n = 1
i = "n→1
1 1 i+n ,n > 1

↭ somme_rec(n) doit donc retourner 1 si n = 1 (cas de base),

et somme_rec(n-1) + n sinon (appel récursif).

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 43 / 45

Somme récursive

def somme_rec (n):

’’’
Entree : n entier strictement positif
Sortie : somme des nombres entiers de 1 a n inclus
’’’
if n == 1:
return 1
return somme_rec (n-1) + n

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 44 / 45

Algorithmes récursifs vs algorithmes itératifs

↭ On peut toujours remplacer un algorithme récursif par un

algorithme itératif qui fait le même travail. Alors pourquoi
écrire des algorithmes récursifs ?
↭ Certains problèmes ont naturellement une structure
récursive (ex. calcul de la factorielle) et il est donc plus
facile d’y réfléchir récursivement.
↭ Mais les algorithmes récursifs sont souvent moins
e!caces...

Leonard Hardiman, Ghid Maatouk ICS - Cours 7 12.11.2025 45 / 45

ICS - Algorithmique

Cours 8 : Complexité algorithmique

19.11.2025

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 1 / 41

Critères d’évaluation d’un algorithme

soude
de

↭ Correctitude ss quven etheeJuste

' assure
dog invariant
ay

↭ Performance
↭ Temps de parcours
↭ Espace requis en mémoire
↭ Nombre d’appels à la mémoire de disque
↭ ...

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 2 / 41

Critères d’évaluation d’un algorithme

↭ Correctitude
↭ Performance
↭ Temps de parcours
↭ Espace requis en mémoire
↭ Nombre d’appels à la mémoire de disque
↭ ...
On s’intéresse au temps de parcours d’un algorithme en
fonction de la taille n de l’entrée.
↭ Si l’entrée est une liste de n éléments, on dira que l’entrée
est de taille n.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 2 / 41

Exemple : rechercher le maximum d’une liste

On sait que l’algorithme suivant calcule correctement le

maximum d’une liste de nombres.
def max_liste (L):

n = len(L)
max_L = L[0]

for i in range (1, n):

if L[i] > max_L:
max_L = L[i]

return max_L

Que peut-on dire sur son temps de parcours ?

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 3 / 41

Mesurer le temps de parcours

changer d'un essaie à lantra

~
↭ La fonction time() du module time de Python retourne le
temps au moment de l’appel en secondes, calculé depuis
une date de référence qui dépend du système (souvent le
1er janvier 1970).
↭ On l’utilisera pour mesurer le temps pris par un appel à la
fonction max_liste.
donnedesbr aléatoire
↭ La fonction randrange(start, stop, step) du module
random retourne un nombre aléatoire entre start et stop
(on utilisera randrange(N) pour un grand entier N).
↭ On l’utilisera pour générer une liste L de grande taille qu’on
passera en argument à max_liste.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 4 / 41

Mesurer empiriquement le temps de parcours : code
from time import time
from random import randrange

def max_liste (L):

n = len(L)
max_L = L[0]
for i in range (1, n):
if L[i] > max_L:
max_L = L[i]
return max_L

L = []
n = 1000
for i in range(n):
L. append ( randrange (10))

t0 = time () Avant l'appel

>
-

m = max_liste (L)
t1 = time () A pres
>
-

print("n:", n, "; duree :", t1 - t0)

Exercice : testez le temps de parcours de l’algorithme

max_liste en changeant la taille de la liste L.
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 5 / 41
Mesurer empiriquement le temps de parcours :
quelques points de données

n durée

103 0.0002779961
104 0.0010309219
105 0.0041978359
106 0.0258612632
107 0.2596998214
108 2.64670395851

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 6 / 41

Mesurer empiriquement le temps de parcours : plein
de points de données

from time import time

from random import randrange
from fonctions_ics import ics_plot , max_liste

N = list( range (10000 ,100000 , 2000) )

R = []

for n in N:
L = []
for i in range(n):
L. append ( randrange (10))

t0 = time ()
m = max_liste (L)
t1 = time ()
R. append (t1 - t0)

ics_plot (N,R)

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 7 / 41

Mesurer empiriquement le temps de parcours : plein
de points de données

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 8 / 41

Vers une analyse théorique du temps de parcours

↭ Le calcul du temps de parcours empirique avec le module

time est problématique : le temps de parcours varie d’un
langage de programmation à l’autre, d’une machine à
l’autre, d’un moment à l’autre sur la même machine...
↭ Pour évaluer la performance d’un algorithme
indépendamment des détails d’implémentation, on va
modéliser le fonctionnement d’un ordinateur.

Teine
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 9 / 41
Vers une analyse théorique du temps de parcours
On s’intéresse au temps de parcours d’un algorithme en
fonction de la taille n de l’entrée.
↭ Si l’entrée est une liste de n éléments qui ne grandissent
pas avec n, on dira que l’entrée est de taille n.
n constant ↭ On suppose en général que les opérations suivantes
prennent un temps constant si elles s’appliquent à des
objets/valeurs qui ne grandissent pas avec n :
↭ Opérations arithmétiques : addition, soustraction,
multiplication, division, reste entier,...
Em
ou ↭ Manipulation de données : créer une variable, a!ecter une
"ser
valeur à une variable, lire et comparer les valeurs de deux
er
·

Cong
variable,...
ey ↭ Opérations de contrôle : instructions if,...
↭ Appel d’une fonction
↭ Accéder à un élément d’une liste L[i] étant donné l’index i
↭ Invoquer la fonction len et les méthodes append et pop
(sans arguments !) sur une liste.
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 11 / 41
Exprimer le temps de parcours de max_liste

temps constant

cste

Este

obouale

aste

c sife

L’appel à la fonction max_liste dure (en secondes)

T (n) = c0 + c1 + c2 + c3 + (c4 + c5 + c6 )(n → 1) = c + c → n :

max_liste a un temps de parcours linéaire en n.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 12 / 41
Problème de la somme maximale

↭ Etant donné une liste de n nombres (n ↑ 2), donner un

algorithme qui calcule la plus grande somme de deux
éléments de la liste (d’indices distincts).
Par exemple,
↭ Entrée : L = [945, 815, 1132, 731, 981, 673]
↭ Sortie : 1132 + 981 = 2113
↭ Nous allons donner deux algorithmes pour ce problème,
puis comparer leurs temps de parcours.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 13 / 41

Un algorithme pour la somme maximale

def max_somme (L):

’’’
Entree : liste L de nombres de taille n >= 2
Sortie : Somme maximale de deux elements de L
’’’
n = len(L)
max_s = L[0] + L[1]

for i in range(n):
for j in range (i+1, n):
if L[i] + L[j] > max_s:
max_s = L[i] + L[j]

return max_s

On appelle ce type d’algorithme qui essaie toutes les

combinaisons possibles un algorithme de force brute.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 14 / 41

Correctitude (idée de preuve)

for i in range(n):
for j in range(i+1, n):
if L[i] + L[j] > max_s:
max_s = L[i] + L[j]

On peut réfléchir de deux manières.

↭ Les boucles imbriquées itèrent sur toutes les paires
possibles (i,j) pour i et j distincts. Au début de la
"(i,j)ème" exécution du corps de la boucle intérieure,
max_s contient la valeur de la somme maximale pour
toutes les paires vues jusque-là.
↭ On peut aussi formuler et prouver un invariant de boucle
pour la boucle extérieure, qui dépendra d’un invariant de
boucle de la boucle intérieure (qui sera fonction du numéro
d’itération i).

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 15 / 41

Temps de parcours
for i in range(n):> augmenta achagus boucle
- i

for j in range(i+1, n): temps da parcour an pire des as

if L[i] + L[j] > max_s:

max_s = L[i] + L[j]

↭ La boucle extérieure est exécutée n fois (i = 0, . . ., n-1).

↭ A la ième itération de la boucle extérieure, la boucle
intérieure est exécutée n → i → 1 fois :
↭ i = 0 : j parcourt range(1, n) : n → 1 itérations
↭ i = 1 : j parcourt range(2, n) : n → 2 itérations
↭ ···
↭ i = n-1 : j parcourt range(n, n) : 0 itérations
↭ Temps de parcours des boucles imbriquées :
temps constant

n(n → 1)
c · [(n → 1) + (n → 2) + · · · + 1 + 0] = c · .
2
↭ Temps de parcours total de l’algorithme :
Ts (n) = c2 n2 + c1 n + c0 .
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 16 / 41
Temps de parcours empirique de max_somme
Car 12

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 17 / 41

Un autre algorithme pour la somme maximale

Etant donné une liste de n nombres (n ↑ 2), donner un

algorithme qui calcule la plus grande somme de deux éléments
de la liste.

def max_somme_lineaire (L):

’’’
Entree : liste L de nombres de taille n >= 2
Sortie : Somme maximale de deux elements de L
’’’
n = len(L)
max1 = max_liste (L)
L. remove (max1) enleve et désale les autre éleme
>
-
-
linéa
>

max2 = max_liste (L)

return max1 + max2
reMor

c3 n + c4 (si on admet 1 que

Temps de parcours : Tω (n) = ^
[Link]() a temps de parcours linéaire en n).

1. Sinon, modifiez max_liste pour qu’elle rende les deux plus grands éléments de la
liste d’un coup, et vérifiez que son temps de parcours est toujours linéaire en n.
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 18 / 41
Temps de parcours de max_somme_lineaire

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 19 / 41

Comparaison empirique des temps de parcours

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 20 / 41

Comparaison asymptotique des temps de parcours :
notation O(·)

↭ Pour une liste de taille n en entrée, on a l’impression que

max_somme_linéaire (Tω (n) = c3 n + c4 ) est plus
performant que max_somme (Ts (n) = c2 n2 + c1 n + c0 ).
Peut-on préciser cette intuition, indépendamment de la
valeur des constantes ?

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 21 / 41

Comparaison asymptotique des temps de parcours :
notation O(·)

↭ Pour une liste de taille n en entrée, on a l’impression que

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 21 / 41

Comparaison asymptotique des temps de parcours :
notation O(·)

↭ Pour une liste de taille n en entrée, on a l’impression que

max_somme_linéaire (Tω (n) = c3 n + c4 ) est plus
performant que max_somme (Ts (n) = c2 n2 + c1 n + c0 ).
Peut-on préciser cette intuition, indépendamment de la
valeur des constantes ?
↭ De plus, on s’intéresse au comportement asymptotique
d’un algorithme, i.e., au temps de parcours en fonction de
la taille de l’entrée n lorsque n tend vers l’infini.
↭ On étudie alors la performance temporelle asymptotique
(la complexité) des algorithmes à l’aide de la notation O(·) :
c’est un outil mathématique qui permet de borner la
vitesse asymptotique de croissance d’une fonction.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 21 / 41

Notation O(·)

Définition (Grand O) Notation delandam

Soit n ↓ N, et g une fonctions positives de n. O(g) est l’ensemble des

fonctions positives f (n) pour lesquelles il existe des réels C > 0,
N > 0 tels que A partir f(x)
de N plus petit
reste
Lign fest O(g)
que

↔n > N f (n) ↗ C · g(n). I dominé

parg

aste
=>
temps vers l'infini mais

le des deux
quel temps
↓a
plus sits

9 ins croit plus

vite
que
fon)

(Abus de) notation : pour f ↓ O(g), on dira que “f est O(g)” ou

“f = O(g)”.
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 22 / 41
Exemples

f = O(g) ↘≃ ⇐C, N > 0 t.q. ↔n > N f (n) ↗ C · g(n).

↭ 1000n = O(n2 ) :

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 23 / 41

Exemples
f = O(g) ↘≃ ⇐C, N > 0 t.q. ↔n > N f (n) ↗ C · g(n).

sommes de puissances rationnelles de n dont les plus
hautes sont respectivement np et nq ,

f (n) = O(g(n))
⇒
↭ n + n = O(n)
⇒
↭ n n + 1000n = O(n1.6 )
↭ ···
↭ Si p < q, alors f = O(g) mais g ⇑= O(f ).

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 32 / 41

Notation !(·)
Définition (Grand Omega) >
-
>"inverse" of O

Soit n ↓ N, et g une fonction positive de n. !(g) est l’ensemble des

fonctions positives f (n) pour lesquelles il existe des réels C > 0, N > 0
tels que
↔n ↑ N f (n) ↑ C · g(n).

)
&
= reste plus grand que cam)

fest Rg

& (n) groit moins vite

que fin)

↭ (Abus de) notation : On dira “f = !(g)” pour “f ↓ !(g)”.

↭ On peut montrer que
g = O(f ) ↘≃ f = !(g).
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 33 / 41
Notation ”(·)
Définition (Grand Theta) embrique entre 81f) et M 19)

Soit n ↓ N et g une fonction positive de n. ”(g) est l’ensemble des

fonctions positives f pour lesquelles il existe des réels C1 , C2 > 0 et
N > 0 tels que
↔n > N C1 · g(n) ↗ f (n) ↗ C2 · g(n).

croit de la même
facot

↭ (Abus de) notation : On dira “f = ”(g)” pour “f ↓ ”(g)”.

↭ On peut montrer que
f = ”(g) ↘≃ f = O(g) et f = !(g).
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 34 / 41
Exemples
↭ Pour tous polynômes f et g de même degré,

f (n) = ”(g(n))

↭ Pour toutes sommes f et g de puissances rationnelles avec

le même terme dominant,

f (n) = ”(g(n))

↭ 10n2 + 7n + 30 = ”(n2 )
↭ 1000n 2
”(n2 )
⇒ + 42 = ⇒
↭ 100n n = ”(n n + n)
↭ ···
↭ La notation ”(·) cache les constantes et les termes d’ordre
inférieur, et donne le comportement asymptotique d’une
fonction de n (lorsque n tend vers l’infini).
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 35 / 41
Exemples

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 36 / 41

Temps de parcours d’algorithmes en notation
asymptotique

↭ On aimerait exprimer le temps de parcours d’un

algorithme comme une fonction T (n) de la taille n de
l’entrée, puis étudier asymptotiquement la vitesse de
croissance de T (n).
↭ Problème : pour la taille n de l’entrée fixée, le temps de
parcours d’un algorithme peut également dépendre de
l’instance du problème qui lui est fournie en entrée !
↭ Par exemple, problème de la recherche d’une valeur x dans
une liste : l’algorithme intuitif (parcourir la liste) tourne en
temps constant ”(1) si x est le premier élément de la liste, et
en temps ”(n) si c’est le dernier !
↭ Par contre, pour les algorithmes vus aujourd’hui, l’ordre de
croissance du temps de parcours est indépendant de
l’instance du problème fournie en entrée.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 37 / 41

Temps de parcours d’algorithmes en notation
asymptotique

↭ On aimerait exprimer le temps de parcours d’un

algorithme comme une fonction T (n) de la taille n de
l’entrée, puis étudier asymptotiquement la vitesse de
croissance de T (n).
↭ Problème : pour la taille n de l’entrée fixée, le temps de
parcours d’un algorithme peut également dépendre de
l’instance du problème qui lui est fournie en entrée !
↭ En général, pour un algorithme donné, on définit T (n)
comme le temps de parcours de cet algorithme sur une
instance de taille n au pire des cas.
↭ Borner le temps de parcours d’un algorithme au pire des
cas o!re une garantie sur le temps de parcours.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 38 / 41

Temps de parcours d’algorithmes en notation
asymptotique

Soit T (n) le temps de parcours d’un algorithme pour une entrée

de taille n au pire des cas.
↭ Si on donne une fonction f1 (n) telle que T (n) = O(f1 (n)), f1
est une borne supérieure sur le temps de parcours de
l’algorithme.
↭ Si on donne une fonction f2 (n) telle que T (n) = !(f2 (n)), f2
est une borne inférieure sur le temps de parcours de
l’algorithme.
↭ Si on donne une fonction f (n) telle que T (n) = ”(f (n)), f est
à la fois une borne supérieure et une borne inférieure sur le
temps de parcours de l’algorithme : elle décrit le
comportement asymptotique du temps de parcours.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 39 / 41

Comportement asymptotique de max_liste

↭ Pour une entrée de taille n, max_liste a temps de parcours

(au pire des cas) T (n) = c + c → n donc max_liste a un temps
de parcours qui est ”(n) (linéaire en la taille de l’entrée).
↭ Peut-on mieux faire (asymptotiquement) ?
↭ Non ! Tout algorithme qui recherche le maximum d’une
liste de nombres doit au moins parcourir toute la liste, et
donc une borne inférieure triviale sur le temps de parcours
d’un tel algorithme est T (n) = !(n).
↭ Un algorithme de recherche du maximum avec temps de
parcours ”(n) est donc asymptotiquement optimal.

Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 40 / 41

Comportement asymptotique des algorithmes de
recherche de somme maximale
↭ Pour une entrée de taille n :
↭ max_somme a temps de parcours (au pire des cas)
Ts (n) = c2 n2 + c1 n + c0 : c’est un temps de parcours
quadratique en n (”(n2 )).
↭ max_somme_lineaire a temps de parcours (au pire des cas)
Tω (n) = c3 n + c4 : c’est un temps de parcours linéaire en n
(”(n)). croit
>
- commeh) misux que (n2)
troujours choisir linéaire
↭ max_somme_lineaire est donc un meilleur algorithme
>
- en n >

(asymptotiquement) que max_somme pour la résolution du

problème de la somme maximale de deux éléments d’une
liste : le temps de parcours de max_somme_lineaire est
dominé asymptotiquement par le temps de parcours de
max_somme : Tω (n) = O(Ts (n)), mais Ts (n) ⇑= O(Tω (n)) !
↭ Peut-on mieux faire ?... Non ! borne inférieure triviale : il
faut au moins lire toute l’entrée.
Leonard Hardiman, Ghid Maatouk ICS - Cours 8 19.11.2025 41 / 41
Informatique et Calcul Scientifique

Cours 9 : Recherche dans une liste,

introduction au logarithme

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 1 / 37

Aujourd’hui on verra

↭ Rappel notations O(·), !(·) et ”(·) et étude de la croissance

asymptotique du temps de parcours d’un algorithme
↭ Recherche d’un élément dans une liste quelconque
↭ Recherche d’un élément dans une liste triée
↭ Logarithme de base 2.

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 2 / 37

Rappel — la semaine dernière

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 3 / 37

Rappel — Préliminaires

↭ On s’intéresse à l’étude de la complexité de certains

algorithmes : la croissance asymptotique de leur temps
d’exécution en fonction de la taille des données d’entrée.
↭ Nous modélisons ce temps d’exécution (au pire des cas)
par une fonction T (n), où n désigne la taille de l’entrée,
mais nous ne pouvons définir cette fonction que modulo la
multiplication par un facteur constant.
↭ T (n) est une fonction de N vers R. Toute fonction abordée
dans ce cours doit être considérée comme étant de cette
forme.

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 4 / 37

Rappel — Les définitions théoriques
↭ O(g) = {f | →C, N > 0 t.q. ↑n > N , f (n) ↓ C · g(n)},
L’ensemble des fonctions dont la croissance asymptotique est dominée par
celle de g.

↭ !(g) = {f | →C, N > 0 t.q. ↑n > N , f (n) ↔ C · g(n)},

L’ensemble des fonctions dont la croissance asymptotique domine celle
de g.

↭ ”(g) = O(g) ↗ !(g),

L’ensemble des fonctions dont la croissance asymptotique est équivalente
à celle de g.

f (n) = O(g(n)) f (n) = !(g(n)) f (n) = ”(g(n))

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 5 / 37

La hiérarchie de la complexité
↭ Si f et g sont telles que f = ”(g), elles peuvent être
considérée comme équivalentes en ce qui nous concerne.
↭ En considérons les fonctions modulo cette équivalence,
nous obtenons la hiérarchie suivante :

! " ...
!(n) ” n1.5 O(n2 )

Supposons que T (n) modélise le temps d’exécution d’un algorithme.

↭ Notre objectif est de comprendre la position de T (n) dans
cette hiérarchie.
↭ Connaître une fonction g telle que T = O(g) donne une borne
supérieure à sa position,
↭ Connaître une fonction g telle que T = !(g) donne une borne
inférieure à sa position,
↭ Connaître une fonction g telle que T = ”(g) donne sa position
exacte.
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 6 / 37
Pour un algorithme donner, comment trouver T (n) ?
↭ En regardant le code ! Et en se rappelant qu’il faut
considérer le pire cas d’une donnée d’entrée de taille n.
↭ La plupart des instructions usuelles prennent un temps de
parcours constant (c’est notre modèle de computation).
↭ T (n) dépend alors souvent du nombre d’exécution d’une
instruction (ce qui est principalement lié aux boucles).
for i in range(n):
#TEMPS CONSTANT temps ”(n)

for i in range(n): !1 " ! "

for j in range(i+1, n): temps ” 2
n2 = ” n2
#TEMPS CONSTANT

for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n): temps ”(n3 )
#TEMPS CONSTANT

LEONARD
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 7 / 37
Algorithmes de recherche

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 8 / 37

Recherche dans une liste

↭ Etant donnés une liste L de nombres et un nombre x ,

trouver x dans L .
↭ Retourner un indice i tel que L[i] = x si x apparaît
dans L , sinon retourner None . >
- Jama:, fronver
X

↭ Sans utiliser l’instruction if x in L , dont le temps de

parcours n’est pas constant !
def recherche (L, x):
’’’
Entree : nombre x, liste L de nombres
Sortie : i t.q. L[i]=x si un tel i existe
None sinon
’’’
n = len(L)

for i in range(n):
if L[i] == x:
return i

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 9 / 37

Correctitude

def recherche (L, x):

n = len(L)
for i in range(n):
if L[i] == x:
return i

↭ Si l’algorithme retourne i , ce i satisfait L[i] = x .

↭ Si l’algorithme retourne None , x n’apparaît pas dans la
liste :
↭ Invariant de boucle : au début de la i ème itération de la
boucle for , on sait que x n’est pas dans L[0:i] .
⇐ À prouver chez vous !
Prendre latemps de parcours dans le pira des cas

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 10 / 37

Recherche dans une liste - temps de parcours

def recherche (L, x):

n = len(L)
for i in range(n):
if L[i] == x:
return i

↭ Si x est en tête de liste, ”(1) (temps constant)

↭ Si x est en fin de liste ou n’apparaît pas dans la liste, ”(n)
↭ Comme le temps de parcours est défini dans le pire des
cas, le temps de parcours de cet algorithme est ”(n).

”(1) ”(n) ”(n2 ) ”(n3 )

...

T ( n)

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 11 / 37

Recherche dans une liste triée

↭ Et si la liste était triée ?

↭ Exemple : recherche de l’élément 17 dans la liste
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51

. Un autre exemple
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 12 / 37
Recherche dans une liste triée

↭ Et si la liste était triée ?

Trouvé à l’index 14 de la liste !

. Un autre exemple
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 12 / 37
Recherche dans une liste triée

↭ Exemple : recherche de l’élément 31 dans la liste

-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51
-7, -3, -3, -1, 0, 0, 1, 2, 5, 6, 8, 9, 9, 13, 17, 18, 24, 26, 27, 32, 38, 47, 51

Pas trouvé !

tcmps de parcours
LLed U
. Crrile = T

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 13 / 37

Recherche binaire (recherche par dichotomie)

def recherche_binaire (L, x):

’’’
Entree : nombre x, liste L de nombres triee
Sortie : i t.q. L[i]=x s’il existe , None sinon
’’’
n = len(L)
bas = 0
haut = n - 1

while haut >= bas:

↭ Soit n un entier strictement positif. On suppose d’abord que

n est une puissance de 2, i.e., il existe k in N tel que n = 2k .
log en base
z de n

↭ Remarquons que cet exposant k est justement le nombre de

fois qu’il faut diviser n par 2 pour arriver à 1, autrement
dit, log n.
↭ Donc par définition, n = 2log n et log n = log(2k ) = k .

n log n
1 0
2 1
4 2
8 3
16 4

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 21 / 37

Propriétés de la fonction log
↭ La fonction log(x ) est en fait définie sur R→+ =]0, ⇒[.

log(x )
4

↘2

0 10 20 30 40 50
n
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 22 / 37
Propriétés de la fonction log

↭ log(x ) est strictement croissante : pour tous x1 , x2 ⇑]0, ⇒[,

x1 < x2 ⇓ log(x1 ) < log(x2 ).

↭ Pour tous x , x1 , x2 ⇑]0, ⇒[, pour toute puissance p

rationnelle :

log(x1 · x2 ) = log(x1 ) + log(x2 ),

log(x1 /x2 ) = log(x1 ) ↘ log(x2 ),
log(x p ) = p log(x ).

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 23 / 37

Propriétés de la fonction log
↭ On s’intéressera aux valeurs de log n uniquement pour n
entier, et en particulier pour n tendant vers l’infini.
↭ Pour n puissance de 2, log n a un sens combinatoire.
↭ Pour n entier positif qui n’est pas une puissance de 2, soit k
la plus grande puissance de 2 telle que 2k < n. On a donc
2k < n < 2k +1 .
↭ Puisque log est croissante, on a
log(2k ) < log n < log(2k +1 )

et donc k < log n < k + 1.

↭ Par exemple,

10 < log 2000 < 11, (puisque 1024 < 2000 < 2048).

↭ Pour n un entier positif quelconque, avec au plus log(n) + 1

divisions par 2, on est sûrs d’arriver à un nombre ↓ 1.
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 24 / 37
Comportement de la fonction log à l’infini
b p + Lentementque n

^
↭ lim log n = +⇒
n↑↓
Pour des puissances rationnelles p < q,
! " ! "
(log n)p = O (log n)q et (log n)q ⇔= O (log n)p .

↭ Par exemple,
! " ! "
log n = O (log n)2 et (log n)2 ⇔= O log n .
! " ! " ! "
”(1) ”(log n) ” (log n)2 ” (log n)3 ” (log n)4
! 5 "
” (log n) 2
6(log n)2 + 4 log n

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 25 / 37

Comportement de la fonction log à l’infini

↭ lim log n = +⇒
n↑↓
↭ Mais quand n tend vers l’infini, log n croît vers l’infini
beaucoup plus lentement que n :

log n
lim = 0.
n↑↓ n
↭ En particulier, log n = O(n), et n ⇔= O(log n). 1
! " ≃
”(1) ”(log n) ! (log n)2 !!(log n)3 " !!(log n)4 " ...
”( n)

Après combien de temps atteindrons-nous ”(n) ?

Jamais !

1. Preuve dans la série.

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 26 / 37
Comportement de la fonction log à l’infini
↭ Pour toute puissance p, et pour toute puissance strictement
positive q,
(log n)p
lim = 0.
n↑↓ nq
! "
↭ En particulier (log n)p = O(nq ) et nq ⇔= O (log n)p .
Par exemple,
↭ (log n)2 = O(n)
↭ (log n)10 = O(n)
≃
↭ (log n)10 = O( n)

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 27 / 37

Comportement de la fonction log à l’infini
↭ Pour toute puissance p, et pour toute puissance strictement
positive q,
(log n)p
lim = 0.
n↑↓ nq
! "
↭ En particulier (log n)p = O(nq ) et nq ⇔= O (log n)p .
Par exemple,
↭ (log n)2 = O(n)
↭ (log n)10 = O(n)
≃
↭ (log n)10 = O( n)
↭ log n et ses puissances ont une croissance logarithmique,
qui est dominée par la croissance polynomiale des
puissances de n.
logarithmique polynomiale

”(nq )
! "
”(1) ”(log n) ! (log n)2 !!(log n)3 " .!.!.(log n)4 " ...

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 27 / 37

De retour à la recherche binaire...

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 28 / 37

Recherche binaire - temps de parcours

↭ Temps de parcours au pire des cas : lorsque l’élément n’est

pas trouvé ou est trouvé lorsqu’on est arrivé à une liste de
taille 1.
↭ Dans ce cas, la boucle while termine après ”(log n)
itérations.
↭ L’algorithme de recherche binaire a donc temps de
parcours ”(log n) dans le pire des cas.
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 29 / 37
Recherche binaire - nombre d’itérations

La boucle while termine

après ”(log n) itérations.

↭ Idée de preuve :
↭ Si la tranche de liste considérée ( L[bas:haut + 1] ) à une
itération donnée est de taille ω, alors la tranche de liste
considérée à la prochaine itération est de taille ↓ ω/2.
↭ Une fois que cette liste est de taille 0 ou 1 (ce qui prend, au
plus, log(n) + 1 itérations), on sort de la boucle dans au plus
une itération.

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 30 / 37

Liste non triée

↭ Etant donné une liste non triée, comment la trier pour

pouvoir la donner en entrée à recherche_binaire ?
↭ Quel est le coût de trier une liste ? A partir de combien
d’appels à recherche_binaire sur une liste est-ce que cela
vaut la peine de trier la liste auparavant ?
↭ Questions à méditer jusqu’à la semaine prochaine...

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 31 / 37

Croissance exponentielle

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 32 / 37

La fonction an
↭ Pour a > 1, on définit la fonction exponentielle de base a :

an = a
# · a$%· · · a&
n fois

↭ Pour toute puissance rationnelle p,

np
lim = 0.
n↑↓ an

↭ En particulier, np = O(an ) (et an ⇔= O(np )). Par exemple,

↭ n = O(2n )
↭ n100 = O(2n )
↭ ...
↭ Pour tout polynôme f (n), la croissance polynomiale de f
est dominée par la croissance exponentielle de an .
≃
↭ n2 + n n + 1 = O(2n )
↭ n10 + n8 + 3n4 = O(2n )
↭ ...
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 33 / 37
Croissance exponentielle

·1018

1 n10
2n
0. 8

0. 6

0. 4

0. 2

0
0 10 20 30 40 50 60
n

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 34 / 37

La hiérarchie de la complexité II
Comme précédemment, nous pouvons considérer les
puissances de 2n . Ici, cela a pour e!et de multiplier n par une
constante dans l’exposant, ce qui crée une nouvelle classe de
complexité.

( 2n ) k = 2k · n .

Les classes de complexité vues jusqu’à présent peuvent donc

être résumées dans la hiérarchie suivante :

”(1)!(log n) !(log n2 ) . . .”(n) !(n )

2
!(n3 ) ... ”(2n ) !(22n ) !(23n ) ...

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 35 / 37

( 2n ) k = 2k · n .

Les classes de complexité vues jusqu’à présent peuvent donc

être résumées dans la hiérarchie suivante :

logarithmique polynomiale exponentielle

”(1)!(log n) !(log n2 ) . . .”(n) !(n )

2
!(n3 ) ... ”(2n ) !(22n ) !(23n ) ...

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 35 / 37

( 2n ) k = 2k · n .

Les classes de complexité vues jusqu’à présent peuvent donc

être résumées dans la hiérarchie suivante :

logarithmique polynomiale exponentielle

”(1)!(log n) !(log n2 ) . . .”(n) !(n )

2
!(n3 ) ... ”(2n ) !(22n ) !(23n ) ...

1 12·2n
3
22n + 3
↘ 145 n3 + 18 log n2

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 35 / 37

( 2n ) k = 2k · n .

Les classes de complexité vues jusqu’à présent peuvent donc

être résumées dans la hiérarchie suivante :

logarithmique polynomiale exponentielle

”(1)!(log n) !(log n2 ) . . .”(n) !(n )

2
!(n3 ) ... ”(2n ) !(22n ) !(23n ) ...

O(2n )

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 35 / 37

Algorithmes exponentiels
Certains algorithmes ont un temps de parcours T (n)
exponentiel en la taille n de l’entrée : T (n) = ”(an ) (ou
T (n) = !(an ) et T (n) = O(bn ) pour des constantes a, b).
↭ Exemple : on peut prouver que l’algorithme récursif fib
vu au Cours 7 pour calculer le neme nombre de Fibonacci a
un temps de parcours exponentiel en n. On observe
empiriquement la croissance de ce temps de parcours :

Leonard Hardiman, Ghid Maatouk ICS - Cours 9 36 / 37

Algorithmes exponentiels - somme de sous-ensembles

↭ Un autre exemple : le problème de la somme de

sous-ensembles 2 : étant donné une liste L de n nombres et
une valeur cible V , existe-t-il un sous-ensemble des indices
de L tel que la somme des éléments correspondants de L
vaut V ?
↭ Input : L = [11, 2, 9, -5, 2, 7, -2, -3] et V = 1
↭ Output : oui car 2 + 2 ↘ 3 = 1.
↭ L’algorithme naïf parcourt tous les sous-ensembles
d’indices de L et vérifie la somme des éléments.
↭ Il y a 2n tels sous-ensembles ! Le temps de parcours de cet
algorithme a une borne inférieure de !(2n ).

2. [Link]
Leonard Hardiman, Ghid Maatouk ICS - Cours 9 37 / 37
Informatique et Calcul Scientifique

Cours 10 : Algorithmes de tri

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 1 / 30

La fois passée, on a vu..

↭ Un algorithme linéaire de recherche dans une liste

↭ La fonction logarithme et son utilisation en informatique
↭ Un algorithme logarithmique de recherche binaire dans une
liste triée

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 2 / 30

Aujourd’hui, on verra..

Plusieurs algorithmes de tri et leurs temps de parcours

↭ Le tri par sélection
↭ Le tri par insertion
↭ Le tri par fusion.

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 3 / 30

Algorithmes de tri

↭ Problème : étant donnée une liste (de nombres, de

strings...) de taille n, trier les éléments de cette liste dans
l’ordre croissant.
↭ L = [0, -3, 2, 4, 2] → L = [-3, 0, 2, 2, 4]
↭ Ce problème peut être résolu par une multitude
d’algorithmes...
↭ On présente plusieurs algorithmes qui, étant donnée une
liste L , la modifient pour en trier les éléments (comme le
fait la méthode sort() de la classe list en Python).

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 4 / 30

Algorithmes de tri

↭ Pourquoi trier ?
↭ Par exemple, trier une liste sur laquelle on va souvent
appeler l’opération recherche.
↭ Dictionnaires (les vrais) ordonnés par ordre alphabétique
des mots, annuaires ordonnés par ordre alphabétique des
noms, listes d’étudiants au SAC ordonnés (par Sciper ?)...

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 5 / 30

Tri par sélection

↭ Idée : dans une liste triée, le premier élément est le plus

petit, le deuxième est le deuxième plus petit, etc.
↭ Pour trier la liste, on va rechercher le plus petit élément et
le mettre à la bonne place (en première position) ; puis
rechercher le deuxième plus petit élément (le plus petit
parmi ceux qui restent) et le mettre à la bonne place en
deuxième position, etc.
↭ On fait donc grandir une sous-liste triée, en insérant à
chaque fois le minimum des éléments restants à la fin de
cette sous-liste.

. Exemple interactif : [Link]

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 6 / 30
Tri par sélection

def tri_par_selection (L):

’’’
Entree : liste L de nombres
Trie L
’’’
n = len(L)
for i in range(n):
m = L[i]
m_index = i
for j in range (i+1,n):
if L[j] < m:
m = L[j]
m_index = j
L[i], L[ m_index ] = L[ m_index ], L[i]

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 7 / 30

Tri par sélection : correctitude

2n tets quand on jarit

〜
Invariant de boucle
(boucle extérieure) :
Au début de l’itération
i , la sous-liste L[0:i]
consiste des i plus petits
éléments de la liste L
donnée en entrée, triés.

Initialisation : au début de l’itération 0 , L[0:0] est vide et

consiste donc bien des 0 plus petits éléments de L .

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 8 / 30

Tri par sélection : correctitude

Invariant de boucle (boucle

extérieure) :
Au début de l’itération i , la
sous-liste L[0:i] consiste des i
plus petits éléments de la liste L
donnée en entrée, triés.

Maintenance : l’itération i consiste à mettre le i ème plus petit

élément à la i ème position dans la liste.
↭ Pour le prouver, il faut prouver que la boucle for intérieure
sélectionne bien le minimum de L[i:n]
↭ Et donc il faut formuler et prouver un invariant de boucle
pour la boucle for dans la i ème itération de la boucle
extérieure :
Au début de l’itération j de la boucle, m contient le
minimum de L[i:j] et m_index l’index de ce minimum.
Leonard Hardiman, Ghid Maatouk ICS - Cours 10 9 / 30
Tri par sélection : correctitude

Invariant de boucle
(boucle extérieure) :
Au début de l’itération
i , la sous-liste L[0:i]
consiste des i plus petits
éléments de la liste L
donnée en entrée, triés.

Terminaison : à la sortie de la boucle, donc au début de

l’itération n (qui n’aura pas lieu), L[0:n] consiste des n
éléments de la liste L , triés. Donc la liste entière est triée.

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 10 / 30

Tri par sélection : temps de parcours

↭ Ces deux boucles for imbriquées impliquent un temps de

parcours qui est !(n2 ).
↭ Y a-t-il une distinction entre le pire des cas et d’autres cas ?

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 11 / 30

Tri par insertion

↭ Idée : trier une liste comme on trie une main à un jeu de

cartes.
↭ On fait grandir une sous-liste triée, en insérant un élément
à la fois à la bonne place dans cette sous-liste.
n

. Exemple interactif : [Link]

algorithms/sorting/insertion-sort/visualize/
Leonard Hardiman, Ghid Maatouk ICS - Cours 10 12 / 30
Tri par insertion

def tri_par_insertion (L):

’’’
Entree : liste L de nombres
Trie L
’’’
n = len(L)
for i in range(n):
j = i
while j > 0 and L[j] < L[j-1]:
L[j], L[j-1] = L[j-1], L[j]
j -= 1

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 13 / 30

Tri par insertion : correctitude

def tri_par_insertion (L):

n = len(L)
for i in range(n):
j = i
while j > 0 and L[j] < L[j-1]:
L[j], L[j-1] = L[j-1], L[j]
j -= 1

Invariant de boucle (boucle extérieure) :

Au début de l’itération i , la sous-liste L[0:i] consiste des
mêmes i éléments initialement dans L[0:i] , mais triés.

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 14 / 30

Tri par insertion : temps de parcours

1 def tri_par_insertion (L):

2 n = len(L)
3 for i in range (n):
4 j = i
5 while j > 0 and L[j] < L[j-1]:
6 L[j], L[j-1] = L[j-1], L[j]
7 j -= 1

↭ Le temps de parcours au pire des cas est lorsque à

l’itération i de la boucle for , la boucle while itère i fois,
↭ c’est-à-dire lorsque la liste est triée dans l’ordre décroissant.
↭ Dans ce cas, les instructions aux lignes 6 et 7 s’exécutent au
total
n( n ↑ 1)
1 + 2 + · · · + (n ↑ 1) = fois.
2
↭ Le temps de parcours au pire des cas est !(n2 ).

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 15 / 30

Un algorithme de tri récursif

↭ Peut-on faire mieux que !(n2 ) ?

=↓ Oui, en utilisant un algorithme récursif : le tri par

fusion.

↭ Paradigme "diviser pour régner" : Pour une instance de

taille n du problème du tri, càd une liste de taille n,
tri_par_fusion :
↭ Divise la liste en deux sous-listes de taille
(approximativement) n/2
↭ Trie récursivement chaque sous-liste
↭ Fusionne les sous-listes triées pour obtenir une version
triée de la liste initiale.
↭ Le tri des sous-listes se fait récursivement et les appels
récursifs s’arrêtent pour les listes de taille 1 (cas de base).

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 16 / 30

Tri par fusion - idée
On suppose qu’on a accès à un algorithme de fusion, qui, étant
donnée une liste L dont les deux moitiés sont triées, trie tous
les éléments de L .

3, 5, 6, 1, 4, 7, 2

3, 5, 6, 1 4, 7, 2

3, 5 6, 1 4, 7 2

3 5 6 1 4 7

3, 5 1, 6 4, 7

1, 3, 5, 6 2, 4, 7

1, 2, 3, 4, 5, 6, 7

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 17 / 30

Tri par fusion

L’algorithme de tri par fusion est donc implémenté de manière

récursive pour une instance L :

def tri_par_fusion (L, bas , haut):

’’’
Entree : liste L, indices bas et haut
Trie la tranche L[bas:haut +1] entre bas et haut
’’’
if haut - bas > 0:
milieu = (bas + haut) // 2
tri_par_fusion (L, bas , milieu )
tri_par_fusion (L, milieu +1, haut)
fusion (L, bas , milieu , haut)

Remarque. Ici, le cas de base c’est de ne rien faire !

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 18 / 30

Fusion de deux sous-listes

def fusion (L, bas , milieu , haut):

’’’Entree : liste L t.q. L[bas: milieu +1] et
L[ milieu +1: haut +1] sont triees
Trie L[bas:haut +1] ’’’
L1 = L[bas: milieu +1]
L2 = L[ milieu +1: haut+1]
L1. append (float (’inf ’))
L2. append (float (’inf ’))
L1_index = 0
L2_index = 0
for i in range(bas , haut+1):
if L1[ L1_index ] <= L2[ L2_index ]:
L[i] = L1[ L1_index ]
L1_index += 1
else:
L[i] = L2[ L2_index ]
L2_index += 1

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 19 / 30

Tri par fusion : exemple

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 20 / 30

Tri par fusion : exemple

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 21 / 30

Correctitude (idée)

↭ La correctitude de tri_par_fusion(L, bas, haut)

découle, par un argument inductif, de la correctitude de
fusion et de la correctitude de tri_par_fusion sur des
instances plus petites (cas de base : une liste de taille 1 est
déjà triée).
↭ La correctitude de fusion est impliquée par l’invariant de
boucle suivant pour la boucle for :
Au début de l’itération i de la boucle, L[bas:i] contient
les (i - bas) plus petits éléments parmi ceux de L1 et
L2 , triés ; et L1[L1_index] et L2[L2_index] sont les plus
petits éléments de leurs listes respectives qui n’ont pas
encore été copiés dans L .

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 22 / 30

Fusion : temps de parcours
Soit F (n) le temps de de parcours de fusion (au pire de cas), où
n est la taille de L[bas:haut+1] , càd n = haut ↑ bas + 1.

On voit ici que F = !(n). Pour simplifier notre analyse

ultérieure on suppose qu’il y a un c ↔ R+ tel que
F (n) = cn.
Leonard Hardiman, Ghid Maatouk ICS - Cours 10 23 / 30
Tri par fusion : temps de parcours

↭ Soit T (n) le temps de parcours, au pire des cas, de

tri_par_fusion pour une entrée de taille n = haut - bas+1.
↭ On suppose que n = 2k où k > 0.

def tri_par_fusion (L, bas , haut):

if haut - bas > 0:
milieu = (bas + haut) // 2
tri_par_fusion (L, bas , milieu )
tri_par_fusion (L, milieu +1, haut)
fusion (L, bas , milieu , haut)

↭ On a alors

T (n) = 2T (n/2) + F (n),

= 2T (n/2) + cn .

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 24 / 30

Arbre de récurrence

T (n) = 2T (n/2) + cn

cn cn

c n2 c n2 cn

c n4 c n4 c n4 c n4 cn
log n + 1
niveaux
. .. .. ..
.. . . .

2c 2c 2c 2c cn
············
T (1) T (1) T (1) T (1) T ( 1) T ( 1) T ( 1) T ( 1) T (1)n

largeur (finale) : 2log n = n

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 25 / 30

Tri par fusion - temps de parcours

↭ La somme des temps de parcours à tous les sommets de

l’arbre est
cn log n + T (1)n
↭ On en déduit le temps de parcours de tri_par_fusion :

T (n) = !(n log n).

!(n) O(n log n) !(n1.1 ) !(n1.2 ) !(n1.5 ) !(n2 )
...

↭ Notre approche ici n’était pas rigoureuse à 100 %.

Formellement, nous avons e!ectivement formulé une
hypothèse, qui pourrait ensuite être prouvée par induction.

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 26 / 30

Master Theorem
↭ Il existe aussi un théorème (the master theorem) qu’on
peut appliquer pour trouver l’ordre de croissance d’une
fonction T (n) qui satisfait une récurrence de la forme

T (n) = aT (n/b) + f (n),

pour des constantes a ↗ 1 et b > 1 (et avec un ou des cas de

base appropriés).
↭ Cette récurrence modélise le temps de parcours pour un
algorithme où on divise un problème de taille n en a
sous-problèmes de taille (approximativement) n/b chacun.
f (n) représente le coût de créer/recombiner les
sous-instances.
↭ Il existe aussi des théorèmes pour résoudre des
récurrences plus compliquées, par exemples lorsque les
tailles des sous-problèmes sont inégales.
Leonard Hardiman, Ghid Maatouk ICS - Cours 10 27 / 30
Comparaison des algorithmes de tri

↭ Pour une entrée de taille n, tri_par_selection et

tri_par_insertion ont temps de parcours !(n2 ) alors que
tri_par_fusion a temps de parcours !(n log2 (n)).
↭ Par contre, tri_par_selection et tri_par_insertion
trient sur place, alors que tri_par_fusion a besoin de
!(n) espace de travail en mémoire.
↭ La constante qui se cache dans la notation !(·) pour
tri_par_fusion est assez grande. En pratique, pour de
petites valeurs de n, tri_par_insertion est l’algorithme à
préférer.
↭ L’algorithme implémenté par la méthode sort et la
fonction native sorted en Python est timsort : c’est un
algorithme hybride basé sur le tri par fusion et le tri par
insertion.

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 28 / 30

Comparaison des algorithmes de tri

↭ Un autre algorithme de tri répandu est le tri rapide ou tri

pivot (quicksort).
↭ Le tri rapide choisit un élément de la liste comme pivot, et
en comparant chaque autre élément de la liste au pivot,
crée deux sous-listes : la liste des éléments plus petits que
le pivot et la liste des éléments plus grand que le pivot.
Puis il trie récursivement ces deux sous-listes.
↭ Le tri rapide trie sur place.
↭ Si le pivot est choisi aléatoirement à chaque étape, le temps
de parcours de tri rapide est !(n2 ) au pire des cas mais
!(n log n) en moyenne (avec une plus petite constante que
celle du tri par fusion).

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 29 / 30

Comparaison des algorithmes de tri

↭ Tous les algorithmes que nous avons vus sont basés sur la
comparaison de paires d’éléments.
↭ On peut prouver que tout algorithme basé sur la
comparaison de paires d’éléments a un temps de parcours
qui est ”(n log n).
↭ Le tri par fusion est donc asymptotiquement optimal parmi
les algorithmes qui comparent des paires d’éléments.
↭ Si on a plus d’information sur les données de la liste, par
exemple si on sait que tous les éléments sont entre 0 et une
constante K , on peut trier en !(n) (sans e!ectuer de
comparaisons d’éléments).

Leonard Hardiman, Ghid Maatouk ICS - Cours 10 30 / 30

Informatique et Calcul Scientifique

Cours 11 : Algorithmes de graphes

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 1 / 55

Les sept ponts de Königsberg

↭ Existe-t-il un chemin à travers la ville qui emprunte chaque

pont exactement une fois ?
↭ En 1736, Euler prouva qu’il n’existe pas de tel chemin. Ce
résultat est considéré comme le début de la théorie des
graphes.

. [Link]
Leonard Hardiman, Ghid Maatouk ICS - Cours 11 2 / 55
Graphes

↭ Un graphe est une structure mathématique appropriée

pour représenter des relations entre des objets.
↭ Un graphe consiste en un ensemble de sommets ou nœuds
reliés par des arêtes.

A
C

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 3 / 55

Les sept ponts de Königsberg - modélisation

↭ On peut représenter chaque masse de terre par un sommet,

et relier deux sommets par une arête lorsque les deux
masses de terre correspondantes sont reliées par un pont.
↭ Dans le graphe ainsi obtenu, la question devient : existe-t-il
un chemin dans le graphe qui emprunte chaque arête
exactement une fois ?

. Image source : Wikipedia

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 4 / 55
Les sept ponts de Königsberg - modélisation

↭ La modélisation consiste à représenter mathématiquement

un problème de manière à pouvoir le résoudre avec des
outils et des méthodes mathématiques, en faisant
abstraction des détails qui ne contribuent pas à la
résolution du problème.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 5 / 55

Graphe - définition

↭ Un graphe G = (V , E ) est défini par son ensemble V de

sommets (vertices en anglais) et son ensemble E d’arêtes
(edges en anglais).
↭ Une arête (u, v ) représente une paire de sommets,
ordonnés ou non.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 6 / 55

Graphe dirigé
↭ Si les arêtes d’un graphe G sont des paires ordonnées de
sommets, le graphe est dit dirigé.
↭ Le graphe ci-dessous contient l’arête (A, B) mais pas l’arête
(B, A).
↭ On dira que B est voisin de A ou adjacent à A (mais A n’est
pas voisin de B)
↭ Les graphes dirigés sont appropriés pour représenter des
situations de flux ou de déplacement entre une source et
une destination.

A
C

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 7 / 55

Graphe non dirigé

↭ Si les arêtes d’un graphe G sont des paires non ordonnées

de sommets, le graphe est dit non dirigé.
↭ Dans le graphe ci-dessous, (A, B) et (B, A) dénotent la
même arête.
↭ A et B sont voisins l’un de l’autre ou adjacents l’un à l’autre.
↭ Les graphes non dirigés sont appropriés pour représenter
des relations symétriques entre des objets.

A
C

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 8 / 55

Graphe pondéré

↭ Un graphe (dirigé ou non) est dit pondéré si un poids est

associé à chaque arête du graphe.
↭ Les poids peuvent être des nombres entiers ou réels,
positifs, négatifs ou nuls selon les applications.
↭ Les graphes pondérés sont appropriés par exemple pour
représenter le coût d’emprunter un certain chemin ou de
prendre une certaine décision.

B → 8. 5
→1
D
2

A →1.2
C

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 9 / 55

Graphe simple vs multigraphe

↭ Le graphe obtenu dans la modélisation du problème des

ponts de Königsberg est en fait un multigraphe. Un
multigraphe (dirigé ou non)
↭ permet à plusieurs arêtes de relier la même paire de
sommets (u, v ) (dans le même ordre pour un multigraphe
dirigé)
↭ permet à une arête d’avoir la forme (u, u), c’est-à-dire de
relier un sommet à lui-même.
↭ Un graphe simple ne permet ni les arêtes “parallèles”, ni
les arêtes qui relient un sommet à lui-même.
↭ Sauf si spécifié autrement, on considèrera toujours des
graphes simples.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 10 / 55

Graphe simple vs multigraphe

A A
C C

B B

D D
F F

E E
Deux graphes simples Deux multigraphes

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 11 / 55

Exemple - réseaux routiers

↭ On peut représenter un réseau routier par un graphe dirigé

et pondéré :
↭ Chaque intersection de routes est un sommet
↭ Chaque segment de route entre deux intersections est une
arête dirigée selon le sens de la circulation
↭ Le poids d’une arête peut être la longueur du segment de
route correspondant, ou une estimation du temps
nécessaire pour parcourir ce segment de route
↭ On s’intéresse entre autres à des algorithmes qui calculent
le plus court chemin entre deux points (problème
d’optimisation).

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 12 / 55

Exemple - réseaux routiers

. Graphes obtenus à partir de Open Street Map

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 13 / 55
Exemple - réseaux sociaux

↭ On peut représenter les relations sur un réseau social

comme Facebook par un graphe non dirigé :
↭ Chaque personne est un sommet
↭ Il existe une arête entre deux sommets si ces deux
personnes sont amies
↭ Le graphe est non dirigé puisque la relation d’amitié est
symétrique.
↭ On s’intéresse entre autres à des questions du type “quels
sont les amis d’amis de la personne A ?” ou bien “quelle est
la distance entre les personnes A et B ?”
↭ Un réseau social où la relation de “suivi” est non
symétrique, comme Twitter, Instagram ou Tiktok, sera
modélisé par un graphe dirigé.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 14 / 55

Exemple - réseaux de flux
Qu’est-ce que ces situations ont en commun ?
↭ Une station d’épuration produit de l’eau qui est
transportée dans un réseau de tuyaux de diverses
grosseurs jusqu’à nos robinets.
↭ Un champ d’éoliennes fournit de l’électricité qui est
transportée dans un réseau électrique jusqu’aux
utilisateurs.
↭ Dans le cadre d’un service de vidéo sur demande, des
vidéos hébergées sur des serveurs sont streamées par des
utilisateurs via Internet.
↭ ...
Elles peuvent toutes être modélisées par des réseaux de flux :
des graphes dirigés, pondérés, où les sommets sont les “relais”,
les arêtes sont les “conduits” (qui ont chacun une certaine
capacité), et un flux de matériel/d’information/.. chemine
entre un sommet source et un sommet destination.
Leonard Hardiman, Ghid Maatouk ICS - Cours 11 15 / 55
Représentation d’un graphe en mémoire

↭ Comment stocker les données relatives à un graphe en

mémoire pour implémenter des algorithmes de graphe ?
↭ Le graphe est complètement décrit par l’ensemble de ses
sommets et l’ensemble de ses arêtes. Comment représenter
e!cacement ces ensembles de manière à pouvoir
↭ Accéder e!cacement à un sommet donné/à une arête
donnée
↭ Parcourir e!cacement les voisins d’un sommet
↭ ...
↭ Que veut dire e!cacement ?
↭ Espace en mémoire
↭ Temps de parcours des opérations
↭ Quelles sont les opérations qu’on veut pouvoir faire
e!cacement ?
↭ Cela dépendra de l’application...

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 16 / 55

Représentation d’un graphe en mémoire

↭ Les deux manières les plus communes pour représenter un

graphe en mémoire sont
↭ Avec une matrice d’adjacence
↭ Avec des listes d’adjacence.
↭ Dans ce qui suit, on va toujours considérer un graphe G
avec n sommets 0, 1, . . . , n → 1, et m arêtes.
↭ Si G est dirigé, m peut prendre n’importe quelle valeur
entre 0 (si G ne contient aucune arête) et n(n → 1) (si chaque
paire de sommets est reliée par une arête.)
↭ Si G est non dirigé, m peut prendre n’importe quelle valeur
entre 0 et n(n → 1)/2.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 17 / 55

Matrice d’adjacence
↭ Pour représenter G avec une matrice d’adjacence, on stocke
une matrice dont les lignes et les colonnes sont indexées
par les sommets de G. Elle contient à la ligne u et colonne
v:
↭ 1 si l’arête (u, v ) existe dans le graphe (si v est adjacent à u
ou voisin de u)
↭ 0 sinon.
↭ En Python, on peut représenter une telle matrice avec une
liste de taille n dont chaque élément est une liste de taille n.
↭ Pour le graphe ci-dessous :
[[0,1,0,0],[0,0,1,1],[0,0,0,1],[0,0,1,0]]

0 1 2 3
1 0 0 1 0 0
3 1 0 0 1 1
0 2 0 0 0 1
2 3 0 0 1 0

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 18 / 55

Matrice d’adjacence

↭ Si G est non dirigé, la matrice d’adjacence sera symétrique.

↭ Si G est pondéré, il su!t de remplacer chaque 1 dans la
matrice par le poids de l’arête correspondante.

0 1 2 3
1 →1 0 0 2 0 0
2
3 1 2 0 3.5 -1
3.5
0
2 0 3.5 0 0.5
0.5
2 3 0 -1 0.5 0

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 19 / 55

Liste d’adjacence

↭ Pour représenter G avec des listes d’adjacences, on stocke,

pour chaque sommet de G, une liste de ses voisins.
↭ Quelle serait une bonne structure de données en Python
pour stocker cette information ?

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 20 / 55

Liste d’adjacence
↭ En Python, on peut stocker ces données dans un
dictionnaire dont les clés sont les sommets et les valeurs les
listes des voisins des sommets.
↭ Pour le graphe de gauche : {0:[1], 1:[2,3], 2:[3],
3:[2]}
↭ Pour le graphe de droite : {0:[1], 1:[0,2,3], 2:[1,3],
3:[1,2]}
↭ Pour un graphe pondéré, on peut stocker, dans la liste des
voisins d’un sommet, des tuples représentant les paires
(sommet, poids).
1 1

3 3

0 0
2 2

↭ On pourrait aussi utiliser une liste où l’élément i est la liste

des voisins du sommet i, mais un dictionnaire nous permet
d’avoir des sommets nommés autrement que 0, 1, . . . , n → 1.
Leonard Hardiman, Ghid Maatouk ICS - Cours 11 21 / 55
Représentation de graphes

↭ Quelle est la meilleure manière de représenter des graphes

en mémoire ?
↭ Quel est l’espace requis en mémoire pour chacune de ces
représentations ?
↭ Quel est le temps requis pour e"ectuer diverses opérations
pour chacune de ces représentations ?
↭ Quelles sont les opérations qu’on désire e"ectuer ?

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 22 / 55

Structures de données

↭ Une partie fondamentale de l’algorithmique est l’étude des

structures de données : la manière d’organiser les données
et de les stocker en mémoire afin de permettre à certaines
opérations de manipulation des données de se dérouler de
manière e!cace.
↭ Quelles opérations ?
↭ L’insertion/la suppression
↭ La lecture/l’écriture
↭ La recherche
↭ L’extraction du min/du max
↭ ...
↭ En général, c’est le contexte de chaque algorithme qui
déterminera quelles opérations doivent être optimisées et
donc quelle structure de données doit être utilisée.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 23 / 55

Listes Python

↭ En CPython, une liste est stockée en mémoire comme un

bloc contigu de références aux éléments de la liste.
↭ Une référence est l’adresse en mémoire de l’élément auquel
elle se réfère.
↭ Chaque référence occupe un bloc de taille constante en
mémoire.
1
len(L)

L =[1, 12, "abcde", 5, 2] ...

"abcde"
12

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 24 / 55

Listes Python - accéder à un élément d’index connu

↭ Pour accéder à un élément L[i], il faut

↭ calculer l’adresse de la référence à l’objet correspondant
↭ accéder à l’élément en mémoire.
↭ Ces deux opérations se font en temps constant. On peut
donc accéder à un élément L[i] (pour le lire ou le
modifier) en temps !(1).

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 25 / 55

Listes Python - ajouter / e"acer un élément en fin de
liste

↭ Pour e"ectuer une opération [Link](), il faut

↭ modifier la longueur de la liste
↭ insérer une référence à un nouvel objet en fin de liste.
↭ On peut donc considérer que ces deux opérations se font
en temps constant !, et donc qu’on peut e"ectuer une
opération [Link]() en temps !(1).
↭ De même, on peut e"ectuer une opération [Link]() en
temps constant.
1. En fait, elles se font en temps moyen constant.
Leonard Hardiman, Ghid Maatouk ICS - Cours 11 26 / 55
Listes Python - insérer / e"acer un élément arbitraire

↭ Pour insérer un élément à l’index i avec [Link](i, x),

il faut décaler vers la “droite” tous les éléments à partir de
l’indice i.
↭ De même, pour enlever un élément (ou une tranche
d’éléments) avec [Link](x), [Link](i) ou del, il faut
décaler vers la “gauche” tous les éléments suivants.
↭ Ceci est nécessaire afin de maintenir la propriété de l’accès
en temps constant.
↭ Pour une liste de taille n, les opérations
d’insertion/d’e"açage à un index arbitraire d’une liste
prennent donc temps !(n) au pire des cas.
Leonard Hardiman, Ghid Maatouk ICS - Cours 11 27 / 55
Listes Python - temps de parcours

Soit L une liste de taille n.

Opération Temps de parcours moyen

lecture/écriture L[i] !(1)
[Link](x) !(1)
[Link]() !(1)
[Link](i,x) !(n)
[Link](i) !(n)
[Link](x) !(n)
del L[i:j:k] !(n)

. [Link]
Leonard Hardiman, Ghid Maatouk ICS - Cours 11 28 / 55
Dictionnaires Python

↭ Les dictionnaires en Python sont implémentés comme des

tables de hachage :
↭ Les clés sont transformées avec une fonction de hachage,
et ce qui est stocké est l’image des clés par cette fonction.
↭ Une (bonne) fonction de hachage est conçue de telle sorte
que la lecture, l’insertion et la suppression d’un élément se
font en temps moyen constant.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 29 / 55

Dictionnaires Python - temps de parcours

Soit D un dictionnaire de taille n (contenant n paires clé-valeur).

Opération Temps de parcours moyen

lecture
!(1)
D[key], [Link](key)
insertion/écriture
!(1)
D[key] = val
suppression
!(1)
[Link](key), del D[key]

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 30 / 55

Matrice vs listes d’adjacence - Espace

↭ La matrice d’adjacence prend un espace !(n2 ) en mémoire

indépendamment du nombre d’arêtes dans le graphe.
↭ Les listes d’adjacence prennent un espace !(n + m) en
mémoire :
↭ Le dictionnaire contient n éléments indépendamment du
nombre d’arêtes.
↭ Soit (u, v ) une arête de G. Si G est dirigé, v apparaît dans la
liste de u ; s’il est non dirigé, v apparaît dans la liste de u et u
dans la liste de v . Chaque arête contribue donc 1 (si G
dirigé) ou 2 (G non dirigé) à la taille totale des listes.
↭ La taille totale de toutes les listes est donc m (G dirigé) ou
2m (G non dirigé).

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 31 / 55

Matrice vs listes d’adjacence - Espace

↭ La matrice d’adjacence prend un espace !(n2 ) en mémoire

indépendamment du nombre d’arêtes dans le graphe.
↭ Les listes d’adjacence prennent un espace !(n + m) en
mémoire. Par exemple,
↭ Si m = O(n), alors une représentation par listes d’ajacence
prend un espace !(n)
↭ Si m = !(n log2 (n)), alors cette représentation prend un
espace !(n log2 (n))
↭ Si m = !(n2 ), alors cette représentation prend un espace
!(n2 ) en mémoire
↭ Sauf si le graphe a "beaucoup" d’arêtes (m = !(n2 )), la
matrice d’adjacence occupe beaucoup plus de place en
mémoire que les listes d’adjacence.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 32 / 55

Matrice vs listes d’adjacence - Temps de parcours

↭ Selon les opérations qu’on veut e"ectuer, il vaudra mieux

adopter une représentation par matrice d’adjacence ou par
listes d’adjacence.
↭ Déterminer s’il existe une arête entre deux sommets :
↭ se fait en temps constant dans une représentation par
matrice (il su!t de lire G[u][v])
↭ se fait en temps !(n) au pire des cas dans une
représentation par liste (il faut parcourir toute la liste des
voisins de u)

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 33 / 55

Matrice vs listes d’adjacence - Temps de parcours

↭ Selon les opérations qu’on veut e"ectuer, il vaudra mieux

adopter une représentation par matrice d’adjacence ou par
listes d’adjacence.
↭ Parcourir les voisins d’un sommet u :
↭ se fait en temps !(n) dans une représentation par matrice
(il faut parcourir toute la ligne G[u])
↭ se fait en temps proportionnel au nombre de voisins de u
dans une représentation par liste (!(n) au pire des cas, mais
souvent moins...)

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 34 / 55

Chemins, distance

Soit un graphe G et deux sommets u et v .

↭ Un chemin de longueur ω entre u et v est une suite de
sommets
u0 , u1 , . . . , uω , ω ↑ 1
tous distincts, avec u0 = u et uω = v , tels que ui et ui +1 sont
liés par une arête pour tout 0 ↓ i ↓ ω → 1.
↭ Un plus court chemin entre u et v est un chemin entre u et
v de longueur minimale.
↭ La distance entre u et v est la longueur d’un plus court
chemin entre u et v .
↭ S’il existe un chemin entre u et v , on dit que v est
atteignable depuis u.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 35 / 55

Exemple - graphe non dirigé

Il existe plusieurs chemins 0

entre 0 et 4 :
↭ 0, 1, 4 3
↭ 0, 2, 4
1
↭ 0, 1, 2, 4
2
↭ 0, 2, 1, 4 5
↭ 0, 3, 5, 4
4
↭ Les chemins les plus courts sont 0, 1, 4 et 0, 2, 4.
↭ Les chemins inverses (par ex 4, 1, 0) sont des chemins entre
4 et 0.
↭ Les sommets 0 et 4 sont à distance 2 l’un de l’autre.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 36 / 55

Exemple - graphe dirigé

1
2
5

↭ Le seul chemin entre 0 et 4 est 0, 2, 4. Le sommet 4 est à

distance 2 du sommet 0.
↭ Le seul chemin entre 4 et 0 est 4, 5, 3, 0. Le sommet 0 est à
distance 3 du sommet 4.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 37 / 55

Parcourir des graphes

↭ Etant donné un graphe G et un sommet s de G (la

“source”), un algorithme de parcours permet d’explorer
(ou de visiter), à partir de s, tous les sommets de G qui sont
atteignables depuis s.
↭ Un grand nombre d’algorithmes de graphes sont basés sur
des algorithmes de parcours.
↭ Pour l’instant, on va simplement a!cher les sommets du
graphe dans l’ordre dans lequel ils sont parcourus.
↭ Les algorithmes de parcours de graphe tombent en général
dans deux catégories : le parcours en largeur et le parcours
en profondeur.

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 38 / 55

Parcours en largeur (BFS)
↭ Le parcours de G en largeur (Breadth-First Search) à partir
d’un sommet source s explore les sommets de G en
commençant par s, puis par les sommets à distance 1 de s,
puis les sommets à distance 2,...

partir d’un sommet source s explore les sommets de G en
allant le plus loin possible avant de revenir en arrière.

3 7

1
2
5 8

4
6

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 53 / 55

Parcours de graphe - BFS
↭ L’algorithme BFS prend en entrée une représentation par
listes d’adjacence d’un graphe G, et un sommet s de G.
↭ Il a!che les sommets de G atteignables depuis s, en
garantissant que l’ordre d’a!chage correspond à un
parcours en largeur du G : si la distance entre s et u est plus
petite que la distance entre s et v , u apparaîtra avant v dans
le parcours.
↭ L’algorithme maintient un ensemble de sommets à
parcourir et choisit de cet ensemble un prochain sommet à
parcourir à chaque étape.
↭ Le choix de la structure de données qui contient cet
ensemble de sommets est crucial au bon fonctionnement et
à l’e!cacité de l’algorithme.
↭ On présente aujourd’hui une version de BFS qui
fonctionne correctement mais qui n’a pas un temps de
parcours optimal.
Leonard Hardiman, Ghid Maatouk ICS - Cours 11 54 / 55
BFS

def BFS(G,s):
’’’
Entree : graphe G en dict de listes d’adj , s sommet
Parcourt G en largeur , affiche les sommets parcourus
’’’
n = len(G)
a_parcourir = [s]
vu = [0 for i in range (n)]
vu[s] = 1

while a_parcourir :
sommet = a_parcourir .pop (0)
for u in G[ sommet ]:
if not vu[u]:
a_parcourir . append (u)
vu[u] = 1
print( sommet )

Leonard Hardiman, Ghid Maatouk ICS - Cours 11 55 / 55

Informatique et Calcul Scientifique

Cours 12 : Algorithmes de graphes II

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 1 / 38

Rappel

↭ Graphes : définition
↭ graphes dirigés, graphes non dirigés
↭ graphes pondérés
↭ Représentations de graphes par matrice d’adjacence et listes
d’adjacence
↭ Chemin, plus court chemin, distance
↭ Parcours de graphes : en largeur (BFS) et en profondeur
(DFS).

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 2 / 38

BFS - Propriétés

↭ Pour un graphe G et un sommet s de G , BFS(G,s) parcourt

exactement une fois chaque sommet de G atteignable depuis
s.
↭ De plus, l’ordre de parcours produit par BFS(G,s) sastisfait la
propriété suivante : pour tout d → N→ , tous les sommets à
distance d de s sont parcourus avant n’importe quel sommet
à distance d + 1 de s.

DFS

↭ Le parcours en profondeur est naturellement récursif : pour

aller le plus loin possible dans une “branche” depuis un certain
sommet avant d’aller dans une autre branche, il faut choisir
un voisin de ce sommet et aller de nouveau le plus loin
possible depuis ce sommet.
↭ L’algorithme peut être transformé en algorithme itératif en
simulant le parcours récursif à l’aide d’une pile (qu’on verra
un peu plus loin).

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 7 / 38

DFS

def DFS_rec (G , s , parcouru ) :

print ( s )
parcouru [ s] = True
for u in G [s ]:
if not parcouru [ u ]:
DFS_rec (G , u , parcouru )

def DFS (G , s ) :
parcouru = {u : False for u in G}
DFS_rec (G , s , parcouru )

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 8 / 38

Structures de données pour BFS et DFS

↭ BFS maintient un ensemble ( a parcourir ) de sommets à

parcourir et choisit de cet ensemble un prochain sommet à
parcourir à chaque étape.
↭ De même, la version itérative de DFS maintient un ensemble
( a parcourir ) de sommets à parcourir, et la version récursive
maintient implicitement un tel ensemble 1 .
↭ Une di!érence entre BFS et DFS est le choix du prochain
sommet à parcourir : DFS choisit le dernier sommet qui a été
ajouté à l’ensemble de sommets à parcourir, et BFS choisit le
plus “ancien”.
↭ Pour que ces algorithmes fonctionnent le plus e”cacement
possible, il faut choisir la bonne structure de données pour
représenter l’ensemble de sommets à parcourir.

1. via la pile d’appels récursifs (recursion stack)

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 9 / 38
Pile (stack)
↭ Une pile (stack) est une structure de données qui permet
d’e!ectuer e”cacement (en temps constant) les opérations
suivantes :
↭ L’ajout d’un élément au “haut” de la pile (push)
↭ L’accès à et la suppression de l’élément qui est actuellement au
“haut” de la pile (pop)
↭ Penser à une pile de plateaux à la cafétéria...
↭ Une pile est une structure de données LIFO (Last In, First
Out).

2. Et la version récursive maintient une pile d’appels récursifs

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 10 / 38
Pile (stack)
↭ Une pile (stack) est une structure de données qui permet
d’e!ectuer e”cacement (en temps constant) les opérations
suivantes :
↭ L’ajout d’un élément au “haut” de la pile (push)
↭ L’accès à et la suppression de l’élément qui est actuellement au
“haut” de la pile (pop)
↭ Penser à une pile de plateaux à la cafétéria...
↭ Une pile est une structure de données LIFO (Last In, First
Out).
↭ La version itérative de DFS maintient l’ensemble des
prochains sommets à explorer dans une pile 2 .

2. Et la version récursive maintient une pile d’appels récursifs

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 10 / 38
File (queue)

↭ Une file ou file d’attente (queue) est une structure de

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 11 / 38

File (queue)

↭ Une file ou file d’attente (queue) est une structure de

données qui permet d’e!ectuer e”cacement (en temps
constant) les opérations suivantes :
↭ L’ajout d’un élément à la “fin” de la file (enqueue)
↭ L’accès à et la suppression de l’élément qui est actuellement en
“tête” de file (dequeue)
↭ Toujours à la cafétéria, penser aux gens qui font la queue.
↭ Une file est une structure de données FIFO (First In, First
Out).
↭ BFS maintient l’ensemble des prochains sommets à explorer
dans une file, ce qui garantit que pour d → N→ , tous les
sommets à distance d de s sont parcourus avant n’importe
quel sommet à distance d + 1 de s.

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 11 / 38

Piles et files en Python

↭ En Python une pile est simplement implémentée par une

liste :
↭ On ajoute un élément au haut de la pile (i.e., en fin de liste)
avec [Link]()
↭ On accède à l’élément au haut de la pile et on le supprime
avec [Link]()
↭ Ces deux opérations se font en temps constant.
↭ Par contre, on ne peut pas implémenter de manière e”cace
une file avec une liste car la suppression d’un élément en tête
de file (i.e., en début de liste) prend temps #(n) pour une file
de longueur n...
↭ Pour implémenter une file en Python, on utilisera le type
deque du module collections .

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 12 / 38

[Link]
↭ La classe deque (double-ended queue) du module collections
est une structure de données qui permet d’e!ectuer les opérations
suivantes en temps (moyen) constant :
↭ L’ajout d’un élément à droite avec la méthode append()
↭ L’accès à et la suppression d’un élément à gauche la méthode
popleft()
mais aussi
↭ L’ajout d’un élément à gauche avec la méthode
appendleft()
↭ L’accès à et la suppression d’un élément à droite avec la
méthode pop() .
↭ Par contre, l’insertion, la suppression, et même l’accès à un élément
en milieu prend temps #(n).
Remarque. Si on utilise deque avec append() et popleft() il se
comporte comme une file. Mais si on l’utilise avec append() et
pop() , il se comporte comme pile.

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 13 / 38

[Link]

from collections import deque

d = deque ( [ 1] )
print ( type ( d ) ) # < class ’ collections . deque ’>

d . append (2)
d . append (3)
print ( d ) # deque ([1 , 2 , 3])

d . appendleft (4)
d . appendleft (5)
print ( d ) # deque ([5 , 4 , 1 , 2 , 3])

print ( d . pop () ) # 3
print ( d . popleft () ) # 5
print ( d ) # deque ([4 , 1 , 2])

d = deque ()
print ( d ) # deque ([])
print ( d . pop () ) # IndexError : pop from an empty deque

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 14 / 38

[Link] - Temps de parcours

Opération Temps de parcours moyen

from collections import deque

def BFS_chemins (G , s ) :

a_parcourir = deque ( [s ])
vu = {u : False for u in G}
vu [ s ] = True
chemin = { u :[ ] for u in G}
chemin [ s ] = [ s]

while a_parcourir :
sommet = a_parcourir . popleft ()
for u in G [ sommet ]:
if not vu [ u] :
a_parcourir . append ( u )
vu [ u] = True
chemin [ u ] = chemin [ sommet ] + [u ]

return chemin

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 21 / 38

Plus court chemin - graphes pondérés

↭ Pour un graphe G pondéré, la longueur d’un chemin

u0 , u1 , . . . , uω (ω ↑ 1) est la somme des poids des arêtes
(ui , ui+1 ).
↭ Pour u et v des sommets de G , un plus court chemin entre
u et v est un chemin entre u et v de longueur minimale.
↭ La distance entre u et v est la longueur d’un plus court
chemin entre u et v .

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 22 / 38

Exemple

0
6.5 8
↓3
1 2

3 1
3

↭ Il existe plusieurs chemins entre 0 et 3 :

↭ 0, 1, 3 de longueur 9.5
↭ 0, 2, 3 de longueur 9
↭ 0, 2, 1, 3 de longueur 8.
↭ Le plus court chemin entre 0 et 3 est 0, 2, 1, 3.
↭ La distance entre 0 et 3 est 8.
Leonard Hardiman, Ghid Maatouk ICS - Cours 12 23 / 38
Plus court chemin - graphes pondérés

1 4 1

1 3 5
1
1 2

0 1
100

↭ Dans un graphe non pondéré, un plus court chemin entre deux

sommets u et v est un chemin avec le plus petit nombre
possible d’arêtes, et on peut parcourir le graphe en largeur
pour trouver un plus court chemin entre u et v .
↭ Dans un graphe pondéré, un parcours en largeur trouvera un
chemin entre u et v avec le plus petit nombre possible
d’arêtes mais pas nécessairement un plus court chemin !

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 24 / 38

Plus court chemin - graphes pondérés
Soit G un graphe dirigé et pondéré à n sommets et m arêtes, et s
un sommet de G .
↭ Si tous les poids des arêtes sont positifs, l’algorithme de
Dijkstra 3 trouve le plus court chemin entre s et u pour tout
u en temps O((n + m) log2 (n)).
↭ L’algorithme de Bellman-Ford 4 permet les poids négatifs et
calcule un plus court chemin de s à u pour tout u en temps
O(nm).
↭ L’algorithme de Floyd-Warshall 5 prend en entrée la matrice
d’adjacence de G , permet les poids négatifs 6 et calcule un
plus court chemin de u à v pour toutes les paires de
sommets u et v en temps #(n3 ).
3. [Link] de Dijkstra
4. [Link] de Bellman-Ford
5. [Link] de Floyd-Warshall
6. mais pas les cycles de poids négatif
Leonard Hardiman, Ghid Maatouk ICS - Cours 12 25 / 38
Cycles, graphes acycliques
↭ Dans un graphe, un cycle est un chemin d’un sommet u à
lui-même, c’est-à-dire une suite de sommets

u0 , u1 , . . . , uω , ω↑1

tels que u0 = uω = u, les ui pour 0 < i < ω sont tous distincts,

et ui et ui+1 sont liés par une arête pour tout 0 ↔ i ↔ ω ↓ 1.
↭ Un graphe sans cycles est dit acyclique.

Un graphe acyclique Un graphe avec cycle

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 26 / 38

Graphes connexes

↭ Dans ce qui suit, soit G un graphe non dirigé.

↭ G est dit connexe si pour toute paire de sommets u, v , il
existe un chemin entre u et v .

Un graphe connexe Un graphe non connexe

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 27 / 38

Arbre

↭ Soit G un graphe non dirigé. Si G est connexe et acyclique, G

est dit un arbre.
↭ Parmi les graphes ci-dessous, seul G1 est un arbre. G2 est
connexe mais contient un cycle, et G3 est non connexe (et
contient un cycle).

G1 G2 G3

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 28 / 38

Arbre couvrant minimal

↭ Soit G un graphe pondéré, connexe. Un arbre couvrant de G

est un graphe T qui a
↭ les mêmes sommets que G
↭ et un sous-ensemble des arêtes de G ,
tel que T est un arbre.
↭ Un arbre couvrant minimal (ou arbre couvrant de poids
minimal) de G est un arbre couvrant T tel que la somme des
poids des arêtes de T est minimale.

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 29 / 38

Arbre couvrant minimal - exemple

Donner un arbre couvrant minimal du graphe ci-dessous :

1.5 5
3
1
0.5
0 4
2

1
4
1

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 30 / 38

Arbre couvrant minimal

1.5 5
1.5 5
1.5 5
3 3 3
1 1 1
0.5 0.5 0.5
0 4 0 4 0 4
2 2

2 2 2

1 1
4 4
1 1 1

Un arbre couvrant de Un arbre couvrant de Un arbre couvrant

poids 8 poids 9 minimal de poids 6

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 31 / 38

Arbre couvrant minimal

↭ Pour un graphe G non dirigé et pondéré, le problème de

trouver un arbre couvrant minimal de G a un grand nombre
d’applications 7 .
↭ il existe des algorithmes 8 qui trouvent un arbre couvrant
minimal d’un graphe à n sommets et m arêtes en temps
O(m log2 (n)).

7. [Link] spanning tree#Applications

8. [Link] de Prim,
[Link] de Kruskal
Leonard Hardiman, Ghid Maatouk ICS - Cours 12 32 / 38
Arbre couvrant minimal avec BFS/DFS

↭ Soit G un graphe connexe. Si G est non pondéré, tous les

arbres couvrants sont de même poids. En particulier, tout
arbre couvrant est minimal.
↭ Dans ce cas, BFS et DFS produisent un arbre couvrant
minimal, qui reflète dans chaque cas le parcours de chaque
algorithme.

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 33 / 38

Arbre couvrant avec BFS

from collections import deque

def BFS_arbre (G , s ):

a_parcourir = deque ( [s ])
vu = {u : False for u in G}
vu [ s ] = True
T = {u : [] for u in G}
while a_parcourir :
sommet = a_parcourir . popleft ()
for u in G [ sommet ]:
if not vu [ u] :
a_parcourir . append ( u )
vu [ u] = True
T [ sommet ]. append ( u )
T [u ]. append ( sommet )
return T

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 34 / 38

Arbre couvrant avec DFS

Arbres couvrants

Obtenu avec un parcours en largeur Obtenu avec un parcours en

profondeur

Leonard Hardiman, Ghid Maatouk ICS - Cours 12 38 / 38

Vous aimerez peut-être aussi

Introduction à Matlab : Vecteurs et Matrices
Pas encore d'évaluation
Introduction à Matlab : Vecteurs et Matrices
32 pages
Notions de base sur MATLAB TP n°1
Pas encore d'évaluation
Notions de base sur MATLAB TP n°1
37 pages
Notions de base sur MATLAB TP n°1
Pas encore d'évaluation
Notions de base sur MATLAB TP n°1
37 pages
Chapitre Cours Introduction Python
Pas encore d'évaluation
Chapitre Cours Introduction Python
7 pages
Saisie et affichage de vecteurs en Python
Pas encore d'évaluation
Saisie et affichage de vecteurs en Python
1 page
Concepts de base du langage C
Pas encore d'évaluation
Concepts de base du langage C
30 pages
Indentation et Boucles en Python
Pas encore d'évaluation
Indentation et Boucles en Python
18 pages
Programmation Python : Structures et Boucles
Pas encore d'évaluation
Programmation Python : Structures et Boucles
16 pages
Introduction aux conditions en Python
Pas encore d'évaluation
Introduction aux conditions en Python
17 pages
Boucles et Fonctions en Python 2021
Pas encore d'évaluation
Boucles et Fonctions en Python 2021
17 pages
Guide des Boucles et Types de Données Python
Pas encore d'évaluation
Guide des Boucles et Types de Données Python
1 page
Chapitre2 - Programmation Python - F
Pas encore d'évaluation
Chapitre2 - Programmation Python - F
11 pages
Note Programmation Graphique Python Tkinter 031511
Pas encore d'évaluation
Note Programmation Graphique Python Tkinter 031511
26 pages
Programmation impérative en Pascal
Pas encore d'évaluation
Programmation impérative en Pascal
2 pages
Chap5 Tests P2
Pas encore d'évaluation
Chap5 Tests P2
8 pages
Contrôle du flux d'instructions Python
Pas encore d'évaluation
Contrôle du flux d'instructions Python
18 pages
Structures de contrôle en Python
Pas encore d'évaluation
Structures de contrôle en Python
29 pages
Boucle S
Pas encore d'évaluation
Boucle S
23 pages
Conditions et structures en Python
Pas encore d'évaluation
Conditions et structures en Python
16 pages
Introduction aux bases de Python
Pas encore d'évaluation
Introduction aux bases de Python
7 pages
Structures répétitives en Python
Pas encore d'évaluation
Structures répétitives en Python
23 pages
Instruction Conditionnelle en Python
Pas encore d'évaluation
Instruction Conditionnelle en Python
1 page
Structures de contrôle en Python
Pas encore d'évaluation
Structures de contrôle en Python
25 pages
Installation et Bases de Python
Pas encore d'évaluation
Installation et Bases de Python
6 pages
Structures de contrôle itératives en Python
Pas encore d'évaluation
Structures de contrôle itératives en Python
4 pages
Histoire et concepts clés de Python
Pas encore d'évaluation
Histoire et concepts clés de Python
15 pages
Révision
Pas encore d'évaluation
Révision
4 pages
L'Instruction Non Borné Tant Que
Pas encore d'évaluation
L'Instruction Non Borné Tant Que
3 pages
Conditions et Gestion des Erreurs en Python
Pas encore d'évaluation
Conditions et Gestion des Erreurs en Python
10 pages
Structures de contrôle en Python
Pas encore d'évaluation
Structures de contrôle en Python
6 pages
Structures répétitives en Python
Pas encore d'évaluation
Structures répétitives en Python
13 pages
Bases de la programmation en Python
Pas encore d'évaluation
Bases de la programmation en Python
4 pages
Initiation A La Programmation
Pas encore d'évaluation
Initiation A La Programmation
36 pages
Chp 2 Python-Partie1
Pas encore d'évaluation
Chp 2 Python-Partie1
14 pages
Controle Et Repetitions
Pas encore d'évaluation
Controle Et Repetitions
10 pages
Structures conditionnelles et boucles en Python
Pas encore d'évaluation
Structures conditionnelles et boucles en Python
20 pages
Structures itératives en Python
Pas encore d'évaluation
Structures itératives en Python
9 pages
PythonM1PS CHP3
Pas encore d'évaluation
PythonM1PS CHP3
12 pages
Programmation Python : Opérateurs Conditionnels
Pas encore d'évaluation
Programmation Python : Opérateurs Conditionnels
7 pages
Introduction à Python 3 pour débutants
Pas encore d'évaluation
Introduction à Python 3 pour débutants
113 pages
Structures de contrôle en algorithmique
Pas encore d'évaluation
Structures de contrôle en algorithmique
15 pages
Structures de contrôle en Python
Pas encore d'évaluation
Structures de contrôle en Python
44 pages
Introduction aux boucles et conditions en Python
Pas encore d'évaluation
Introduction aux boucles et conditions en Python
10 pages
Instructions de branchement et boucles en C
Pas encore d'évaluation
Instructions de branchement et boucles en C
25 pages
Structures de contrôle en Python
Pas encore d'évaluation
Structures de contrôle en Python
21 pages
Introduction À La Programmation Avec Python
Pas encore d'évaluation
Introduction À La Programmation Avec Python
2 pages
Boucles et structures itératives en Python
Pas encore d'évaluation
Boucles et structures itératives en Python
1 page
Structures de contrôle en Python
Pas encore d'évaluation
Structures de contrôle en Python
11 pages
Boucles et structures en Python
Pas encore d'évaluation
Boucles et structures en Python
20 pages
Expose Complet Preprocesseur C
Pas encore d'évaluation
Expose Complet Preprocesseur C
4 pages
Compiler un programme multi-fichiers C
Pas encore d'évaluation
Compiler un programme multi-fichiers C
5 pages
TP1 : Expressions régulières avec LEX
Pas encore d'évaluation
TP1 : Expressions régulières avec LEX
1 page
Guide de Programmation avec Sage
Pas encore d'évaluation
Guide de Programmation avec Sage
8 pages
Introduction à Python et ses structures
Pas encore d'évaluation
Introduction à Python et ses structures
36 pages
Introduction à la programmation Python
Pas encore d'évaluation
Introduction à la programmation Python
48 pages
Les Sous Programmes2022 2023 3eme Sciences
Pas encore d'évaluation
Les Sous Programmes2022 2023 3eme Sciences
13 pages
Structures Répétitives en Algorithmique
Pas encore d'évaluation
Structures Répétitives en Algorithmique
9 pages
Projet Python Complet et Guide
Pas encore d'évaluation
Projet Python Complet et Guide
17 pages
AffectationVsEgalité&Remarques 1ere
Pas encore d'évaluation
AffectationVsEgalité&Remarques 1ere
1 page
Analyse Algo 1erepartie
Pas encore d'évaluation
Analyse Algo 1erepartie
5 pages
Propriétés physiques des sols
Pas encore d'évaluation
Propriétés physiques des sols
4 pages
Calcul des pièces en traction simple
Pas encore d'évaluation
Calcul des pièces en traction simple
7 pages
Classification des rayonnements non ionisants
Pas encore d'évaluation
Classification des rayonnements non ionisants
6 pages
Exercices sur la Notation Scientifique
Pas encore d'évaluation
Exercices sur la Notation Scientifique
7 pages
Brise-roche hydraulique HB 4100
Pas encore d'évaluation
Brise-roche hydraulique HB 4100
3 pages
DELEUZE. Différence Et Répétition (Avant-Propos)
Pas encore d'évaluation
DELEUZE. Différence Et Répétition (Avant-Propos)
9 pages
Notions et méthodes de métrologie
Pas encore d'évaluation
Notions et méthodes de métrologie
16 pages
Expertise technique des bâtiments à Tunis
100% (1)
Expertise technique des bâtiments à Tunis
46 pages
Mobile Banking au Congo : Innovation et Confiance
Pas encore d'évaluation
Mobile Banking au Congo : Innovation et Confiance
3 pages
Tableau de conversion de fractions
Pas encore d'évaluation
Tableau de conversion de fractions
1 page
Installation Office ProPlus 2024 Preview
Pas encore d'évaluation
Installation Office ProPlus 2024 Preview
3 pages
Cahier Des Charges Pour L'acquisition Des Equipements
Pas encore d'évaluation
Cahier Des Charges Pour L'acquisition Des Equipements
40 pages
FR Avis Technique Sikaplan Sgma Sous Lestage Et Jardins 5 152447
Pas encore d'évaluation
FR Avis Technique Sikaplan Sgma Sous Lestage Et Jardins 5 152447
43 pages
Manuel d'utilisation moteur DEUTZ TCD 2012
Pas encore d'évaluation
Manuel d'utilisation moteur DEUTZ TCD 2012
84 pages
Montée d'air pour réservoir d'ammoniac
Pas encore d'évaluation
Montée d'air pour réservoir d'ammoniac
12 pages
Importance des Zones Humides pour l'Humanité
Pas encore d'évaluation
Importance des Zones Humides pour l'Humanité
25 pages
Modélisation du froissage rayonnant
Pas encore d'évaluation
Modélisation du froissage rayonnant
11 pages
Création et Modification des Permissions SIAF
Pas encore d'évaluation
Création et Modification des Permissions SIAF
3 pages
TD2 : Logique combinatoire en électronique
100% (1)
TD2 : Logique combinatoire en électronique
3 pages
Types et schémas d'interrupteurs électriques
Pas encore d'évaluation
Types et schémas d'interrupteurs électriques
19 pages
Manuel d'utilisation OLV-10 Concentrateur d'oxygène
Pas encore d'évaluation
Manuel d'utilisation OLV-10 Concentrateur d'oxygène
29 pages
Méthode de Simpson : Intégration et Erreurs
Pas encore d'évaluation
Méthode de Simpson : Intégration et Erreurs
11 pages
Classification de l'affectivité et éthique médicale
Pas encore d'évaluation
Classification de l'affectivité et éthique médicale
3 pages
Incidences de la RE 2020 sur la construction
Pas encore d'évaluation
Incidences de la RE 2020 sur la construction
21 pages
Statistiques JIRAMA 2008 : Ventes et Abonnés
Pas encore d'évaluation
Statistiques JIRAMA 2008 : Ventes et Abonnés
114 pages
Corrigés de Physique-Chimie 1ère
Pas encore d'évaluation
Corrigés de Physique-Chimie 1ère
1 page
DÉCODEUR DES HOMMES - Ebook Nel Jamila
Pas encore d'évaluation
DÉCODEUR DES HOMMES - Ebook Nel Jamila
222 pages
Méthode des éléments finis en 1D
Pas encore d'évaluation
Méthode des éléments finis en 1D
25 pages
Fiche Emotion Aid
Pas encore d'évaluation
Fiche Emotion Aid
2 pages