Filière :MP/TSI

Algorithmique et programmation 2
Introduction aux Bases de Données

Présenté par :
Mr. YASSINE KHARCHACHI

Année Universitaire: 2020/2021

CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Partie 1 :
Algorithmique et programmation 2

2
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

La Complexité

3
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Introduction
Exercice
Ecrire en python une fonction qui prend en
argument une chaine de caractères et
détermine si le caractère 'a' est présent
dans la chaîne (on retourne soit True soit
False).

4
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Analysons plusieurs solutions

 Première solution
def fct1(chaine) :
k=0
N = len(chaine)
result = False
while (result == False and k < N)
if chaine[k] == 'a' :
result = True
k=k+1
return result

5
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Deuxième solution :
def fct2(chaine) :
for i in range(len(chaine))
if chaine[i] == 'a' :
return True
return False

6
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Troisième solution :
def fct3(chaine) :
n = chaine.count('a')
return bool(n)
Quatrième solution :
def fct4(chaine) :
return ('a' in chaine)

7
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Quelques questions :
que remarquez vous concernant cet exercice ?
Le code le plus court ! Est-il meilleur ?
Comment peut-on designer le meilleur code
parmi ces quatre solutions ?

8
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Définition de la complexité
La complexité d'un problème mathématiques
P est une mesure de la quantité de ressources
nécessaires à la résolution du problème P.
Cette mesure est basée sur une estimation du
nombre d'opérations de base effectuées par
l'algorithme en fonction de la taille des
données en entrée de l'algorithme.

9
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Généralement, pour le même problème P, on

peut trouver plusieurs algorithmes (Alg1; Alg2;
::; Algn).
L'objectif de la complexité est d‘évaluer le
coût d'exécution de chaque algorithme afin de
choisir le meilleur.

10
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Types de complexité

En fonction des ressources utilisées pour

évaluer la complexité d'un algorithme, on
sera amène a distinguer deux types de
complexité : complexité temporelle et
complexité spatiale.

11
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

 Complexité temporelle (en temps)

La complexité temporelle d'un algorithme est
le nombre d'opérations élémentaires
(affectations, comparaisons, opérations
arithmétiques) effectuées par un algorithme.
Complexité spatiale (en espace)
La complexité en mémoire donne le nombre
d'emplacements mémoires occupés lors de
l'exécution d'un programme.

12
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

La notation O
Définition
Soit T(n) une fonction qui désigne le temps de calcul
d'un algorithme A.
On dit que T(n) est en grand O de f(n) : T(n) = O(f (n)) si
et seulement si :Ǝ(n0; c) telle que T(n) <= c f (n) pour
tout n >= n0

13
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Exemples
Exemple 1 :
si T(n) = 3n + 6 alors T(n) = O(n)
Démonstration :
En effet, pour n >= 2, on a 3n + 6 <= 9n ; la quantité
3n + 6 est donc bornée, à partir d'un certain rang,
par le produit de n et d'une constante.

14
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Exemple 2 :
si T(n) = n2 + 3n alors T(n) = O(n2)
Démonstration :
En effet, pour n >= 3, on a n2 + 3n <= 2n2 ; la
quantité n2 + 3n est donc bornée, à partir
d'un certain rang, par le produit de n2 et
d'une constante.

15
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Classes de complexité les plus usuelles

16
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Le cout des instructions élémentaires

 Opération élémentaire
On appelle opération de base, ou opération élémentaire, toute :
 Affectation
 Test de comparaison :==; <;<=;>=; ! =
 Opération de lecture (input) et écriture (print)
 Opération arithmétique :+;-;* ; /;%
 Opération d'incrémentation :a=a+1,(pas 1) a=a+n (pas n)
 Opération de décrémentation :a=a-1,(pas 1) a=a-n (pas n)

17
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Exemple 1 : Que vaut le coût de l'algorithme A

somme = n + 1 #instr1
somme = somme * n #instr2
somme = somme/2#instr3

Cout(A)= coût(inst1)+ coût(instr2)+ coût(instr3)

18
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Le coût des instructions composées

Opération composée
On appelle opération composée, toute
instruction contenant :
 L'exécution d'une instruction conditionnelle : Si P
est une instruction conditionnelle du type:
if b alors Q1 else Q2
le nombre d'opérations est :
Coût(P) <= Coût (test) + max(Coût(Q1), Coût(Q2))

19
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

 L'exécution d'une boucle : le temps d'une

boucle est égal a la multiplication de nombre
d’itérations par la somme du Coût de chaque
instruction xi du corps de la boucle ;
Coût(boucle for) = Σ Coût(xi)
Coût(boucle while) =Σ (Coût(comparaison) + coût(xi))

20
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

 Exemple 2 : Que vaut le coût de l'algorithme B

if i%2==0 :
n=i//2
else :
i=i+1
n=i//2
Coût(B)=Coût(i%2 == 0)+ max(Coût(n = i//2),Coût(i = i + 1; n = i//2)
 Exemple 3 : Que vaut le coût de l'algorithme C
while i <= n :
somme=somme+i
i=i+1
Coût(C)=Coût (i <= n)+Coût (somme = somme + i)+Coût (i = i + 1)
=n+n+n=3n

21
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

L'appel d'une fonction : Lorsqu'une fonction

ou une procédure est appelée, le coût de cette
fonction ou procédure est le nombre total
d'opérations élémentaires engendrées par
l'appel de cette fonction.

22
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Calculer La complexité
Déterminer les opérations élémentaires
(OE) à prendre en considération : coût
T(OE).
 Calculer le nombre d'instructions
effectuées par les opérations composées
(OC) : coût T(OC).
 Préciser les instructions a négliger.
 Le coût de l'algorithme T(Alg) est :
T(Alg) = T(OE) + T(OC)

23
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

La complexité du produit matriciel ?

def ProduitMatriciel(A,B) :
prod = [[0]*len(A) for i in range(len(A))]
for i in range(len(A)) :
for j in range(len(B[0])) :
s=0
for k in range(len(B)) :
s= s + A[i][k] * B[k][j]
prod[i].append(s)
return prod

24
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

produit matriciel
 On suppose que A et B sont deux matrices carrées
d'ordre n (len(A) = len(B) = n)
 Coût pour calculer une valeur de s est 2 (produit et
affectation)
 Le nombre d'itération de la boucle sur k pour j fixé
égal à n
 Le nombre d'itération de la boucle sur j pour i fixé
égal à n
 Le nombre total d'opérations est 2+n(n(2+n(2))
 Complexité : O(n3)

25
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

La complexité De la Recherche dichotomique ?

def RechDichotomique(T,x) :
g,d=0,len(T)-1
while g<=d :
m=(g+d)//2
if T[m]==x :
return True
if T[m]<x :
g=m+1
else :
d=m-1
return False

26
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

La complexité De la Recherche dichotomique ?

la complexité de chaque itération de while O(1)

 Nombre de fois maximum d’exécution de la
boucle while est m (c-a-d la complexité est m)
 Au pire, on divise l'intervalle de recherche par 2
à chaque étape.
Donc : 2m-1 <= n <= 2m
on déduit que m <= log2(n) + 1
Complexité : O(log2(n))

27
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI

Différentes nuances de complexité

Il est fréquent que la complexité en temps soit

améliorée au prix d'une augmentation de la
complexité en espace, et vice-versa.
La complexité dépend notamment :
 de la puissance de la machine sur laquelle
l'algorithme est exécute,
 du langage et interpréteur (ou compilateur) utilise
pour coder l'algorithme,
 du style du programmeur.

28
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

La complexité de:

Tri à bulles
Tri par sélection
Tri par insertion
Tri rapide
Tri par fusion

29
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Différentes nuances de complexité

Pour des données de même taille, un
algorithme n'effectue pas nécessairement le
même nombre d'opérations élémentaires.
Pour cela, on distingue 3 types de
complexité :
 Complexité au pire des cas.
 Complexité dans le meilleur des cas.

30
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Complexité au pire des cas

La complexité au pire est le plus grand
nombre d'opérations qu'aura à exécuter
l'algorithme sur un jeu de données de taille
fixée à n.
Tmax (n) = max{C(d)} avec (dϵDn)
avec Dn l'ensemble des données de taille n
C(n) est le coût d'exécution de l'algorithme
sur la donnée de taille n.

31
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Complexité au pire des cas

 Exemple : Recherche d'un élément dans un tableau
def RE(T,x) :
for i in T :
if i == x :
return True
return False
On note n la longueur du tableau T (n=len(T)).
Dans le pire des cas : quand l’élément recherché (x) est le
dernier (dans la case n-1) ou est absent.
Donc la complexité dans le pire est Cmax (n) = n

32
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Complexité dans le meilleur des cas

La complexité au meilleur est le plus petit nombre

d'opérations qu'aura à exécuter l'algorithme sur un
jeu de données de taille fixée. C'est une borne
inferieure de la complexité de l'algorithme sur un
jeu de données de taille n.
Tmin(n) = min {C(d)} avec (dϵDn)
Exemple : Recherche d'un élément dans un tableau
Dans le meilleur des cas : quand l‘élément recherché
(x) se trouve en 1ere position.
Donc la complexité dans le meilleur des cas est
Cmin(n) = 1
33
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri

34
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
I- Tri à bulles :
Principe :
Comparaison 2 à 2 des éléments adjacents
et échange s'ils ne sont pas ordonnés. Le
programme s'arrête lorsqu'on parcours la liste
sans faire d'échange
Comme les bulles, les plus grands éléments
remontent en fin de liste

35
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
I- Tri à bulles :
def triBulles (ls):
echange= True
while echange==True :
echange=False
for i in range(0,len(ls)-1) :
if(ls[i]>ls[i+1]):
val=ls[i]
ls[i]=ls[i+1]
ls[i+1]=val
echange=True
return ls

36
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
II- Tri par sélection :
Principe :
 Recherche du plus petit élt du tableau et échange avec
le premier élt
 Recherche du plus petit élt du tableau entre les
positions 2 et n-1 et échange avec le second élt
 ...
 Recherche du plus petit élt entre les positions n-2 et n-
1 et échange avec l'élt en position n-2

37
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
II- Tri par sélection :
def triSelection (ls):
for i in range(0,len(ls)) :
indice = i
for j in range(i+1,len(ls)) :
if ls[j] < ls[indice] :
indice = j
if indice != i :
val=ls[indice]
ls[indice] = ls[i]
ls[i] = val
return ls

38
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
III- Tri par insertion :
Principe :

Il consiste à insérer successivement

chaque élément a[i] dans la portion
du tableau a[0:i] déjà triée

39
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
III- Tri par insertion :
def tri_Insertion(T) :
n=len(T)
for i in range(1,n):
x=T[i]
j=i
while j>0 and T[j-1]>x :
T[j]=T[j-1]
j=j-1
T[j]=x
return T
40
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
IV- Tri rapide :
Principe :
L’algorithme de tri rapide, "quick sort", est un algorithme
fondé sur la méthode de conception diviser pour régner;
Son principe consiste à séparer l’ensemble des éléments en
deux parties.
Pour effectuer la séparation, une valeur pivot est choisie au
hasard. Les valeurs sont réparties en deux ensembles
suivant qu’elles sont plus grandes ou plus petites que le
pivot. Ensuite, les deux ensembles sont triés séparément,
suivant la même méthode.

41
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
IV- Tri rapide :
Exemple :
Soit la liste :
L = [ 4, 23, 3, 42, 2, 14, 45, 18, 38, 16 ]
Prenons comme pivot la dernière valeur
pivot = 16
Nous obtenons donc :
L1 = [4, 14, 3, 2]
L2 = [23, 45, 18, 38, 42]
A cette étape voici l'arrangement de L :
L = L1 + pivot + L2 = [4, 14, 3, 2, 16, 23, 45, 18, 38, 42]

42
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri

En appliquant la même démarche au deux sous-listes : L1 (pivot=2)

et L2 (pivot=42)
[4, 14, 3, 2, 16, 23, 45, 18, 38, 42]
nous obtenons :

L11=[ ] liste vide L21=[23, 38, 18]

L12=[3, 4, 14] L22=[45]
L1=L11 + pivot + L12 = (2,3, 4, 14) L2=L21 + pivot + L22 = (23, 38, 18, 42, 45)

43
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri

Etapes tri rapide sur [a..b] :

1. Partition [a..b] renvoie pivot & [a..b] =

[x .. pivot']+[pivot]+[pivot'' .. y]
2. Tri Rapide sur [pivot'' .. y]
3. Tri Rapide sur [x .. pivot']

44
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
Fonction partitionner :
def partitionner(T,premier,dernier) :
p=T[dernier]
j=premier
for i in range(premier,dernier) :
if T[i]<p :
T[i],T[j]=T[j],T[i]
j=j+1
T[dernier],T[j]=T[j],T[dernier]
return j

45
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
Fonction triRapide :
def triRapide(T,premier,dernier) :
if premier < dernier :
pivot=partitionner(T,premier,dernier)
triRapide(T,premier,pivot-1)
triRapide(T,pivot+1,dernier)

46
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
V- Tri par fusion :
Principe :
Le tri fusion est un algorithme de tri basé sur la technique
algorithmique diviser pour régner. L'opération principale
de l'algorithme est la fusion, qui consiste à réunir deux
listes triées en une seule.

47
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
Principe :
Le principe de cet algorithme tend à adopter une
formulation récursive :

 On découpe les données à trier en deux parties plus ou

moins égales
 On trie les 2 sous-parties ainsi déterminées
 On fusionne les deux sous-parties pour retrouver les
données de départ

48
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
Implémentation :
L'implémentation de cet algorithme repose
essentiellement en 2 fonctions :

 Fusion :Permet de fusionner deux listes triées de

telle sorte que la liste résultante la soit aussi.
 triFusion : Une fonction récursive qui assure le
découpage de la liste et l'appel de la fonction de
fusion.

49
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
Fonction fusion :
def fusion(L1, L2):
res = []
ind1, ind2 = 0, 0
while ind1 < len(L1) and ind2 < len(L2):
if L1[ind1] <= L2[ind2]:
res.append(L1[ind1])
ind1 += 1
else:
res.append(L2[ind2])
ind2 += 1
50
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
Fonction fusion :
if ind1!=len(L1):
res+=L1[ind1:]
if ind2!=len(L2):
res+=L2[ind2:]
return res

51
Prof: Yassine KHARCHACHI
CPGE TETOUAN Filière : MP/TSI Année Scolaire: 2020/2021

Méthodes de tri
Fonction triFusion :
def triFusion(ls):
if len(ls) <= 1:
return ls
moitie = len(ls) // 2
return fusion( triFusion(ls[:moitie]), triFusion(ls[moitie:]))

52
Prof: Yassine KHARCHACHI