Upload
aurelie-legay
View
104
Download
1
Embed Size (px)
Citation preview
Structures de données
IFT-2000
Abder AlikacemAbder Alikacem
Analyse d’algorithmesSemaine 1
Département d’informatique et de génie logiciel
! +
Édition Septembre 2009
Plan
Introduction Efficacité des algorithmes Analyse algorithmique Notation O (big-oh) Instruction Baromètre Comparaison entre les classes de complexité
Efficacité des algorithmes
Habituellement on mesure l’efficacité d’un algorithme par sa vitesse.
• C’est-à-dire la durée que met l’algorithme à produire ses résultats.
On veut savoir combien de temps cela prend de résoudre une instance de taille n du problème P:
• données(n) + Algorithme(P) ==> résultat(n).• temps mis ? (en microsecondes, cycles d’horloge, nombre
d’instructions exécutées, etc..)On prend en compte la taille n des données:
•en bits, entiers, nombres d’enregistrements...
Parfois, on considère aussi la mémoire nécessaire.
Efficacité des algorithmes
Approche empirique: mesure de performances.• essayer l’algorithme sur différents jeux de données bien
choisis.Avantages:
• résultats réalistes. Inconvénients:
• coûteux et long• dépend du processeur, de l’OS et de la charge • dépend de l’implémentation• pas toujours généralisable.
Efficacité des algorithmes
Approche algorithmique:• estimer le nombre de pas de l’algorithme en fonction de la taille
des données.• On aura recours à l’analyse d’algorithmes, basée sur la branche des
mathématiques qui s’appelle l’analyse fonctionnelle, pour déterminer ce nombre de pas de façon beaucoup plus fiable.
Avantages: • résultats généraux: on ne dépend pas du processeur, de l’OS ou de l’implémentation
• Estimation rapide et peu coûteux • évite de se fourvoyer.
Inconvénients:• prédictions parfois approximatives.
Dans notre cours, on va s’intéresser à l’approche algorithmique pour la détermination de l’efficacité d’un algorithme. Relevez qu’on parle souvent de complexité d’un algorithme lorsqu’on s’intéresse à son efficacité.
Analyse algorithmique
Analyse détaillée :• Avantage :Très précise• Désavantage : Long à calculer
Solution: Analyse asymptotique du comportement de l’algorithme lorsque le(s) paramètre(s) de l’algorithme tendent vers l’infini:
• Avantage: Parfois facile à calculer• Désavantage: Parfois moins précis
Mesure indépendante de l'implémentation : Temps d'exécution d'un algorithme = fonction(taille du problème)
Notation O (big-oh)
On Cherche une fonction simple qui dépend de la taille n de l’instance en entrée dans un algorithme qui résout un problème donnée et qui décrit la borne supérieure de la complexité de l’algorithme.
Dans notre cours, on s’intéressera uniquement à cette notation et l’appliquer uniquement aux cas les plus simples. La théorie complète pour l’analyse d’algorithmes est le sujet d’un cours entier.
Pour déterminer la complexité d’un algorithme dans la notation
O(), on doit d’abord identifier des opérations de base (instructions baromètres), puis trouver la fonction f(n) qui compte le combien de fois cette instruction baromètre est effectuée dans l’algorithme.
Nous verrons dans un exemple qui suit comment déduire la
complexité d’un algorithme dans la notation O() à partir de la fonction f(n).
Opération baromètre
Une opération baromètre est une opération élémentaire qui, à une constante près, est effectuée au moins aussi souvent que n’importe quelle autre opération élémentaire de l’algorithme.
Il est généralement assez simple d’identifier une opération baromètre pour un algorithme car la nature du problème qu’il tente de résoudre
nous suggère souvent l’opération contribuant le plus au temps d’exécution
Exemples:• Pour les algorithmes de tri (par comparaison), l’opération de base
est la comparaison de deux valeurs (ou de deux clés)• Pour la multiplication de matrices, l’opération de base est la
multiplication de deux nombres• Et plusieurs autres exemples à venir dans le cours …
Exemple
void triSelection(int tab[MAXTAB], int n){
int PositionMin, temp, i, j;
for (i = n-1; i > 0; i--){
PositionMin = i;for (j = 0; j < i; j++){
if (tab[j] < tab[PositionMin]){
PositionMin = j;}
}temp = tab[i];tab[i] = tab[PositionMin];tab[PositionMin] = temp;
}}
void triSelection(int tab[MAXTAB], int n){
int PositionMin, temp, i, j;
for (i = n-1; i > 0; i--){
PositionMin = i; //b1for (j = 0; j < i; j++){
if (tab[j] < tab[PositionMin]){
PositionMin = j;}
}temp = tab[i];tab[i] = tab[PositionMin];tab[PositionMin] = temp;
}}
// i * a
//b2
Possible baromètre
Exemple
Exemple (suite)
for (i = n-1; i>0; i--)
{Coût b1 /* PositionMin = i */
Coût i*a; /* pour exécuter la boucle interne*/
Coût b2; /* pour l'échange de tab[i] et tab[PositionMin] */
}
Exemple (suite)Exemple (suite)
1
1
( ) ( )n
i
f n ai b
b = b1 + b2
1 1
1 1
( )n n
i i
f n a i b
( 1)( ) ( 1)
2
n nf n a n b
2( ) 2 2
a af n b n bn
Comportement de la fonction f(n) = an2 + bn + c quand n est très grand (n )
a = 0.0001724, b = 0.0004, c = 0.1
n f(n) an2 % du n2
125 2.8 2.7 94.7
250 11.0 10.8 98.2
500 43.4 43.1 99.3
1000 172.9 172.4 99.7
2000 690.5 689.6 99.9
Exemple (suite)
Notation O(g(n)) (big-oh)
Pour un nombre n assez grand f(n) an2
Temps d'exécution de l’algorithme est donné parf(n) = an2 + bn + c
g(n) = n2
On dit que l'algorithme est en O(n2)
Notation O(g(n)) (big-oh)
L’analyse est donc simplifiée selon les règles suivantes:• Les constantes sont éliminées• Seul le monôme avec le degré le plus élevé est conservé
Exemple: f(n) = 3n2+5n+4 est en O(n2)
0 10 20 30 40 50 600
500
1000
1500
2000
2500
3000
3500
4000
n (taille des données)
f(n) vs n2
f(n)
n2
f(n)
f(n)
1
log n
n2n2n
Notation O(g(n)) (big-oh)
Il y a différentes classes de fonctions qu’on peut exprimer dans la notation O() : O(1), O(n), O(n2), O(n3), O(log n), …
n
Comparaison entres les classes
O(1). Constant ou borné parfait.O(log(n)). Logarithmique excellentO(n). Linéaire très bonO(n log(n) ) bon.O(na) polynomial acceptableO(an) exponentiel inacceptableO(n!) factoriel beurk.
Exemple (suite)
1
1
( ) ( )n
i
f n ai b
b = b1 + b2
1 1
1 1
( )n n
i i
f n a i b
( 1)
( ) ( 1)2
n nf n a n b
2( ) 2 2
a af n b n bn
L’algorithme est en O(n2)
Exemple (suite et fin)
L’algorithme est en O(n2)
void triSelection(int tab[MAXTAB], int n){
int PositionMin, temp, i, j;
for (i = n-1; i > 0; i--){
PositionMin = i; for (j = 0; j < i; j++){
if (tab[j] < tab[PositionMin]){
PositionMin = j;}
}temp = tab[i];tab[i] = tab[PositionMin];tab[PositionMin] = temp;
}}
Le bon baromètre
int minimumOn2(int tableau[],int taille){ int i,j; for(i=0;i<taille;i++) { j=0; while(j<taille && tableau[i]<=tableau[j] ) {
j++; } if(j == taille) return tableau[i]; } return tableau[i];}
int minimumOn(int tableau[],int taille){ int i,min = tableau[0]; for(i=0;i<taille;i++) {
if( tableau[i]<min) min = tableau[i]; } return min;}
Algorithme #1
Algorithme #2
Exemple 2: chercher le minimum dans un tableau d’entiers
Autres exemples sur les boucles
void f(int N){
int i;for(i=0;i<n;i++) cout <<‘’Allo\n’’;
}
Cet algorithme est en O(n)
void f(int N){
int i,j;for(i=0;i<n;i++)
for(j=0;j<n;j++)cout << i << j << endl;
}
Cet algorithme-ci est dans O(n²)
Autres exemples sur les boucles
void f(int N) {
int i,j;for(i=0;i<n;i++)
for(j=0;j<n;j++)cout << i << j << endl;
for(i=0;i<n;i++)cout << i << endl;
}
Cet algorithme est en O(n²)
void f(int N){
int i;for(i=0;i<10000;i++)
cout<<’’Allo\n’’;}
Puisque son temps d’exécution ne dépend pas de n, même si la boucle est très longue, l’algorithme est en O(1). En effet, lorsque le temps d’exécution d’un algorithme ne dépend même pas du nombre d’éléments, ce temps est alors constant et il est dans O(1).
Autres exemples sur les boucles
void f(int N){
int i;for(i=0;i<5340*n;i++)
cout <<‘’Allo\n’’;}
Puisque qu’il faut faire abstraction de toute constante multiplicative, cet algorithme est en O(n).
void f(int N){
int i;for(i=0;i<n;i++)
for(j=0;j<i;j++)cout <<‘’Allo\n’’;
} On a donc:
L’algorithme est en O(n²)
1 1 1
0 0 0
( 1)( ) 1
2
² ²( ) ( ²)
2 2 2
n i n
i j i
n nf n i
n n n nO n
Annexe mathématique
• Les séries simplifiées• Rappel sur les logarithmes• Règles de simplification dans la notation O()
En plus, voir document RappelsMath.pdf sur le site Web du cours.
Analyse d’algorithmes
1- En choisissant l’opération d’affectation comme baromètre, déterminez la fonction f(n) qui exprime le temps de calcul pour l’algorithmes suivant.
2- Déduisez sa complexité dans la notation du O().
i 0 Tant Que i < n début i i + 1 fin
a)
Analyse d’algorithmes
Mêmes questions pour l’algorithme suivant.
i 1 Tant Que i < ndébut j 1 Tant que j < n
début j j + 1
fini i + 1
fin
b)
Analyse d’algorithmesMêmes questions..
i 1Tant Que i < ndébut
j 1Tant Que j < idébut
j j + 1fin
i i +1fin
c)
Analyse d’algorithmes
Mêmes questions pour l’algorithme suivant.
s 0 i 1 Tant Que i ≤ n début s s - 1 j 1
Tant Que j ≤ i début
s s + 2 j j+1 fin i i + 1
fin fin
d)
Analyse d’algorithmes
i nTant Que i > 0début
i i/2fin
i 1Tant Que i <ndébut i 2*ifin
Mêmes questions pour les 3 algorithmes suivants:
f)
g)
i nTant Que i > 0début
i i - 2fin
e)
Analyse d’algorithmes
Mêmes questions.
i 1Tant Que i ≤ ndébut
j 1Tant Que j < idébut
j j*2fini i+1
fin
h)
i 1Tant Que i <ndébut i 2*ifin
Laboratoire de la semaine
Soit a1, a2, ..., an, une séquence d’entiers possiblement négatifs.
On veut trouver le couple (i,j) tel que la somme des ak, k=i, ..., j est maximale, avec 1≤ i ≤ j ≤ n
a1 a2 a3 a4 ... an-3 an-2 an-1 an
« Maximum Subsequence Sum Problem »
Laboratoire de la semaine
Il s’agit d’évaluer en termes de notation asymptotique quelques solutions proposées à cette problématique. Il s’agit également de comparer le temps d’exécution de ces solutions pour, d’abord, confirmer la complexité de chacune d’elles et, ensuite, de constater l’énorme différence en temps de calcul qui peut exister entre une solution naïve et une solution plus élaborée.
« Maximum Subsequence Sum Problem »
Fichiers fournis• ModeleTranchesMax.h (définitions de types + inclusions de librairies C++• TrancheMax.h (prototypes des fonctions à implanter)• Algorithmes.cpp (à compléter par l’implémentation des fonctions demandées)• Main.cpp (le programme principal: appel des fonctions implémentant les algorithmes proposés pour déterminer la tranche max dans un tableau d’entiers, mesure du temps d’exécution de chaque algorithme pour des fins de comparaison).
Laboratoire de la semaine
Tous les fichiers fournis dans ce laboratoire ont été documentés avec les balises de Doxygen. Afin de vous familiariser avec, nous vous demandons de compiler tous les fichiers avec cet outil afin de générer la documentation attendue. Nous vous fournissions le fichier de configuration sdd.doxyfile pour cette fin.
Vous trouverez un tutoriel pour utiliser Doxygen (avec le Doxywizard ou bien dans Eclipse si vous utilisez cet IDE) dans la section Travaux Examen/Travaux Pratiques/Doxygen sur le site Web du cours).
Utilisation de Doxygen (génération de documentations automatisée)
L'interface...
/**
* \brief
*
* \pre
* \pre
*
* \post
* \post
*
* \exception
* \exception
*/
Implémentation...
/**
* \fn
*
* \param[in]
* \param[out]
*
* \return
Section Documentations/Normes de programmation:
•Resume.h (à propos des commentaires Doxygen)
Résumé des balises de Doxygen
Laboratoire de la semaine
Éléments du C++ à découvrir lors de ce laboratoire
• Les entrées/sorties• #include <iostream> // Librairie pour les entrées/sorties• using namespace std;
• ne jamais mettre cette instruction dans les fichiers .h• cin (stdin), cout (stdout), • << (printf du C), >> (scanf du C), endl (saut de ligne)
• Les structs: différence entre le C et le C++ struct SousSequence { int debut; /*!< Indice de début de la sous-séquence dans Sequence*/ int fin; /*!< Indice de fin*/ int somme; /*!< La somme (max) de la sous-séquence*/ };
En C++, le typedef est inutile…
Laboratoire de la semaine
Éléments du C++ à découvrir lors de ce laboratoire
• Gestion des exceptions
• #include <stdexcept> • Le mécanisme try…catch..throw…(voir fichier Main.cpp)
int main(){
... try {
... affiche(trancheMax3(seq, tailleSeq)); ...
} catch (invalid_argument& ia) { cerr << "Invalid argument: " << ia.what() << endl;
} ... return 0;}
Laboratoire de la semaine
Éléments du C++ à découvrir lors de ce laboratoire
• Gestion des exceptions
• Gestion des exceptions dans une fonction…(fichier Algorithmes.cpp)
SousSequence trancheMax1(Sequence a, int taille){ … if (taille<=0) throw invalid_argument("TrancheMax1: argument invalide\n"); …
}
La classe invalid_argument fait partie de <stdexcept>
Éléments du C++ à voir courant la semaine
•Du C au C++•Les entrées/sorties (important pour cette semaine)•L'espace de nommage•Les types vector et string
Voir Section « C++ primer » dans le semainier sur le site Web