Structures de données IFT-2000 Abder Alikacem Analyse d’algorithmes Semaine 1 Département...

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