Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Analyse des algorithmes et Complexité Algorithmique 2 La question abordée: Co

1 Analyse des algorithmes et Complexité Algorithmique 2 La question abordée: Comment choisir parmi les différentes approches (méthodes) pour résoudre un problème? 3 • Définition: Un algorithme est un ensemble d’actions permettant de transformer un ensemble de données en un ensemble de résultats, en un nombre fini d’étapes. • Pour atteindre cet objectif, un algorithme utilise deux ressources d’une machine: le temps et l’espace mémoire. 4 Analyse d’un algorithme • Il existe souvent plusieurs algorithmes pour résoudre un problème. – ex. Tris, … • On veut donc choisir l’algorithme le plus efficace: – Au point de vue de la vitesse d’exécution – De la quantité de mémoire de travail utilisée • Un autre point peut entrer en ligne de compte : la simplicité de l’algorithme. 5 • Définition 1: la complexité temporelle d’un algorithme est le temps mis par ce dernier pour transformer les données du problème considéré en un ensemble de résultats. 6 • Définition 2: la complexité spatiale d’un algorithme est l’espace utilisé par ce dernier pour transformer les données du problème considéré en un ensemble de résultats. 7 Comparaison de solutions Pour comparer des solutions entre-elles, deux méthodes peuvent être utilisées: • Étude empirique: (exécuter le programme) • Analyse mathématique Cette comparaison se fera, en ce qui nous concerne, relativement à deux ressources critiques: temps, espace mémoire,... Nous allons nous concentrer beaucoup plus sur le temps d’exécution 8 Facteurs affectant le temps d’exécution: 1. machine, 2. langage, 3. programmeur, 4. compilateur, 5. algorithme et structure de données. Le temps d’exécution dépend de la longueur de l’entrée. Ce temps est une fonction T(n) où n est la longueur des données d’entrée. 9 Exemples (suite) Exemple: x:=3; la longueur des données dans ce cas est limitée à une seule variable. Exemple : S:= 0; Pour i:=0 à n Faire Pour j:=0 à n Faire S:=S+1; Fait; Fait; En revanche, dans ce cas, elle est fonction du paramètre n 10 • La longueur des données d’entrée, définissant le problème considéré, est définie comme étant l’espace qu’elle occupe en mémoire. 11 Pire cas, meilleur cas et cas moyen Toutes les entrées d’une longueur donnée ne nécessitent pas nécessairement le même temps d’exécution. Exemple: soit à rechercher un élément C dans un tableau de n élément triés dans un ordre croissant. Considérons les solutions suivantes: 1. Recherche séquentielle dans un tableau de taille n. Commencer au début du tableau et considérer chaque élément jusqu’à ce que l’élément cherché soit trouvé. 12 2. Recherche dichotomique: tient compte du fait que les éléments du tableau soient déjà triés. Information ignorée par l’algorithme de la recherche séquentielle. • Ces deux algorithmes sont présentés comme suit: 13 Fonction recherche1(Entrée tab: Tableau[n] entier; C: entier): Entier; Debut Var i : Entier; b: Booléen; i := 1; b:=Faux; Tantque (i<=n Et non b) Faire Si tab[i] = C Alors b:=Vrai; Sinon i:=i+1; Fsi; Fait; Si (non b) Alors Recherche1:= -1; Sinon Recherche1:= i; Fsi; Fin; /* fin de la fonction */ 14 Fonction recherche2(Entrée tab: Tableau[n] entier; C: entier): Entier; Début Var sup, inf, milieu: Entier; trouve: Booléen; inf := 1; sup :=n; trouve := faux; Tantque (sup >=inf et non trouve) Faire milieu = [(inf + sup) / 2]; Si (C = tab[milieu]) Alors trouve :=Vrai; Sinon Si (C < tab[milieu]) Alors sup := milieu -1; Sinon inf := milieu + 1; Fsi; Fsi; Fait; Si (non trouve) Alors Recherche2:=-1; Sinon Recherche2:= milieu; Fsi; Fin; /* fin de la fonction */ 15 La méthode empirique • Elle consiste à coder et exécuter deux (ou plus) algorithmes sur une batterie de données générées d’une manière aléatoire; • À chaque exécution, le temps d’exécution de chacun des algorithmes est mesuré. • Ensuite, une étude statistique est entreprise pour choisir le meilleur d’entre-eux à la lumière des résultats obtenus. 16 Problème! Ces résultats dépendent • de la machine utilisée; • du jeu d’instructions utilisées • de l’habileté du programmeur • du jeu de données générées • du compilateur choisi • de l’environnement dans lequel est exécuté les deux algorithmes (partagé ou non) • .... etc. 17 Méthode mathématique • Pour pallier à ces problèmes, une notion de complexité plus simple mais efficace a été proposée par les informaticiens. • Ainsi, pour mesurer cette complexité, la méthode mathématique, consiste non pas à la mesurer en unité de temps (par exemple les secondes), mais à faire le décompte des actions (instructions) de base exécutées par ces deux algorithmes. 18 • Cette manière de procéder est justifiée par le fait que la complexité d’un algorithme est en grande partie induite par l’exécution des instructions qui le composent. Cependant, pour avoir une idée plus précise de la performance d’un algorithme, il convient de signaler que la méthode expérimentale et mathématique sont en fait complémentaires. 19 Comment choisir entre plusieurs solutions? 1. décompte des instructions • Reconsidérons la solution 1 (recherche séquentielle) et faisons le décompte des instructions. Limitons-nous aux instructions suivantes: • Affectation notée par e • Test noté par t • Addition notée par a 20 • Il est clair que ce décompte dépend non seulement de la valeur C mais aussi de celles des éléments du tableau. • Par conséquent, il y a lieu de distinguer trois mesures de complexité: • 1. dans le meilleur cas • 2. dans le pire cas • 3. dans le cas moyen 21 • Meilleur cas: notée par tmin(n) représentant la complexité de l’algorithme dans le meilleur des cas en fonction du paramètre n (ici le nombre d’éléments dans le tableau). • Pire cas: notée par tmax(n) représentant la complexité de l’algorithme dans le pire cas en fonction du paramètre n (ici le nombre d’éléments dans le tableau). • Cas Moyen: notée par tmoy(n) représentant la complexité de l’algorithme dans le cas moyen en fonction du paramètre n (ici le nombre d’éléments dans le tableau). C’est-à-dire la moyenne de toutes les complexités, t(i), pouvant apparaître pour tout ensemble de données de taille n (t(i) représente donc la complexité de l’algorithme dans le cas où C se trouve en position i du tableau). Dans le cas où l’on apparaître la probabilité Pi de réalisation de la valeur t(i), alors par définition, on a: tmoy(n) = p1 t(1) + p2 t(2) + p3 t(3) + ... +pn t(n) 22 • Il est clair que pour certains algorithmes, il n’y a pas lieu de distinguer entre ces trois mesures de complexité. Cela n’a pas vraiment de sens. 23 Meilleur cas pour la recherche séquentielle: Le cas favorable se présente quand la valeur C se trouve au début du tableau tmin(n) = 24 Pire cas: Le cas défavorable se présente quand la valeur C ne se trouve pas du tout dans le tableau. Dans ce cas, l’algorithme aura à examiner, en vain, tous les éléments. tmax(n) = 25 Cas moyen: Comme les complexités favorable et défavorable sont respectivement (e + 3t) et = (n+1)e + na + (2n+3)t, la complexité dans le cas moyen va se situer entre ces deux valeurs. Son calcul se fait comme suit: Pour plus de simplicité, on suppose que C existe dans le tableau. On suppose aussi que sa probabilité de présence dans l’une des positions de ce tableau est de 1/n. Si C est dans la position i du tableau, la complexité t(i) de l’algorithme est: 26 Analyse d’un Algorithme • Analyse détaillée d’un algorithme: – Avantage :Très précise – Désavantage : Long à calculer • Solution: Analyser asymptotiquement le comportement de l’algorithme lorsque le(s) paramètre(s) de l’algorithme tendent vers l’infini: – Avantage: Facile à calculer – Désavantage: Moins précis 27 Complexité asymptotique • Le décompte d’instructions peut s’avérer fastidieux à effectuer si on tient compte d’autres instructions telles que: – accès à un tableau, – E/S, opérations logiques, – appels de fonctions,.. etc. • De plus, même en se limitant à une seule opération, dans certains cas, ce décompte peut engendrer des expressions que seule une approximation peut conduire à une solution. • Par ailleurs, même si les opérations élémentaires ont des temps d’exécution constants sur une machine donnée, ils sont différents néanmoins d’une machine à une autre. 28 Par conséquent: • Pour ne retenir que les caractéristiques essentielles d’une complexité, et rendre ainsi son calcul simple (mais indicatif!), il est légitime d’ignorer toute constante pouvant apparaître lors du décompte du nombre de fois qu’une instruction est exécutée. • Le résultat obtenu à l’aide de ces simplifications représente ce qu’on appelle la complexité asymptotique de l’algorithme considéré. 29 La complexité asymptotique d’un algorithme décrit le comportement de celui-ci quand la taille n des données du problème traité devient de plus en plus grande, plutôt qu’une mesure exacte du temps d’exécution. 30 • Une notation mathématique, permettant de représenter cette façon de procéder, est décrite dans ce qui suit: 31 Notation O • Détermine une borne supérieure • Définition formelle : f(n) = O(g(n)) s’il existe deux constantes positives n0 et c tel que f(n) <= cg(n) pour tout n>n0 f(n) = O(g(n)) n temps cg(n) f(n) n0 32 Notation O La notation grand-O uploads/Management/ chap-01-complexite-algo.pdf