Cours002 Info3 L2MPC

LICENCE 2 : Mathématiques-Informatique, Physyque et Chimie
Algorithme et Programmation
(Cours 2)
BOUITYVOUBOU Henri Mesmin Noël
Département de Mathématiques et Informatique

Université des Sciences et Techniques de Masuku
[email protected]
January 16, 2023

UE : INFORMATIQUE 3
UE : INFORMATIQUE 3
Modules : INFORMATIQUE 3
Volume horaire (60H) : CM 16H – TD 18H – TP 26H
Coefficients : 3
Crédits : 6
Semestres : 3
Pré-requis : Notion de programmation en C++
Responsable : Dr. Ing. OKALAS OSSAMI Dieudonné
Chargé de TD et TP : M. BOUITYVOUBOU Henri Mesmin Noel

OBJECTIFS DU MODULE
OBJECTIFS DU MODULE
AXE 1 : Algorithme
I Algorithmes de tri lents et/ou rapides ;
I Evaluation des algorithmes(complexité).
AXE 2 : Programmation
I Tri et Recherche par dichotomie ;
I Structure, Pointeurs et Classes
PLAN DU COURS
PLAN DU COURS
1. Complexité
1.1 Ressources
1.1.1 Spatiales (mémoires)
1.1.2 Temporelles (temps d’exécution)
1.2 Méthode de calcul
1.2.1 Exemple
PLAN DU COURS
Planning et semainier
Cours Titre Type

1 Définitions
Algorithme,Algorithmique,Tri,Recherche,Complexité
2 Evaluation d’un Algorithme
Complexité EXP
3 Structure d’un Algorithme
Algorithmes TD1
4 Algorithmes de tri et de recherche
Tri à bulles, Tri par sélection, Tri par insertion TP1
Recherche par dichotomie TP2
5 Programmation en C++
Structures, Pointeurs et Classes TP 3
Table: Semestre 3 - L2MPC - INFORMATIQUE 3
Introduction
Introduction :
Quand les scientifiques ont voulu énoncer formellement et

rigoureusement ce qu’est l’efficacité d’un algorithme ou au
contraire sa complexité, ils se sont rendu compte que la
comparaison des algorithmes entre eux était nécessaire et que les
outils pour le faire à l’époque1 étaient primitifs.
Complexité
Complexité :
La complexité d’un algorithme est une mésure de la quantité de
ressources nécessaires pour résoudre un problème donné.
1. Il existe deux types de ressources :
1.1 Temporelles (temps d’exécution)
1.2 Spatiales (mémoires)
Dans le cadre de ce cours on regardera juste la complexité
temporelle. Autrement dit :
I Le temps nécessaire pour résoudre un problème;
I ou bien, le nombre d’étapes de calcul élémentaires.
C’est-à-dire, connaı̂tre exactement le nombre d’instructions
élémentaires qui composent un algorithme donné.
I En règle générale, la complexité d’un algorithme, est le min
des complexités des Algorithmes pour résoudre ledit problème.
Complexité
Méthode de calcul
Méthode de calcul
Comment déterminer la complexité d’un Algorithme ?
1. on compte le nombre d’instructions élémentaires,
2. on tient compte d’un paramètre C(n) qui est donné en entrée
de l’algorithme.
3. de plus, quand on fait le calcul, on s’interesse beaucoup plus
aux valeurs asymptotiques de n, que l’on note O(n).
I C(n+1) = C(n) : O(1) complexité constante
I C(n+1) = C(n) + 1 : O(n) complexité linéaire
I C(2n) = C(n) + 1 : O(log2 (n)) complexité logarithmique
I C(n+1) = C(n) + n : O(n2 ) complexité polynomiale
I C(n+1) = 2*C(n) : O(2n ) complexité exponentielle
Complexité
Illustration
Exemple 1 : Recherche d’un élément dans une liste L

--------------------------------------------------------
Algorithme R1 : recherche d’un élément dans une liste L
CR1(n) : 1 + (1+1+n)*n = n*n + 2*n + 1
--------------------------------------------------------
R1(x,L) :
DEBUT
i = 1
TANTQUE (i > Taille(L)) FAIRE
SI (x == L(i))
AFFICHER("VRAI")
SINON
i = i+1
FINSI
FINTANTQUE
FIN
Complexité
Illustration
Exemple 2 : Recherche d’un élément dans une liste L

--------------------------------------------------------
CR2(n) : (2 + 1)*n = 2*n + n = 3*n
--------------------------------------------------------
R2(x,L) :
DEBUT
t = Taille(L)
POUR i ALLANT DE 1 A t FAIRE
SI (x == L(i))
AFFICHER("VRAI")
FINSI
FINPOUR
AFFICHER("FAUX")
FIN
Complexité
Illustration
TD 2 : Calculez la complexité de R3, en considérant que la

liste L est triée.
--------------------------------------------------------
--------------------------------------------------------
R3(x,L) :
DEBUT
SI L est vide ALORS AFFICHER("FAUX")
SI L=={p} ALORS
SI p==x ALORS AFFICHER("VRAI")
SI p différent de x ALORS AFFICHER("FAUX")
FINSI
L1,L2 = L/2
SI x <= max(L1) ALORS R3(x,L1)
SINON R3(x,L2)
FIN
QUESTIONS
QUESTIONS
Des Questions ?

Cours002 Info3 L2MPC

Transféré par

Droits d'auteur :

Formats disponibles

Cours002 Info3 L2MPC

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours002 Info3 L2MPC

Transféré par

Droits d'auteur :

Formats disponibles

LICENCE 2 : Mathématiques-Informatique, Physyque et Chimie

Département de Mathématiques et Informatique

January 16, 2023

Volume horaire (60H) : CM 16H – TD 18H – TP 26H

Pré-requis : Notion de programmation en C++

Responsable : Dr. Ing. OKALAS OSSAMI Dieudonné

Chargé de TD et TP : M. BOUITYVOUBOU Henri Mesmin Noel

Cours Titre Type

Quand les scientifiques ont voulu énoncer formellement et

Exemple 1 : Recherche d’un élément dans une liste L

Exemple 2 : Recherche d’un élément dans une liste L

TD 2 : Calculez la complexité de R3, en considérant que la

Vous aimerez peut-être aussi