Remerciez-le!

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

Complexité algorithmique Complexité des algorithmes récursifs Algorithme de la

Complexité algorithmique Complexité des algorithmes récursifs Algorithme de la programmation dynamique 1 1- Complexité algorithmique 2 Introduction 3 Comment choisir parmi les différentes approches pour résoudre un problème? Exemples: Liste chaînée ou tableau? algorithme de tri par insertion de tri rapide? …, etc 4 Pour comparer des solutions, • Exactitude des programmes • Simplicité des programmes • Convergence et stabilité des programmes • Efficacité des programmes 5 •L’efficacité des algorithmes 6 • Définition: Un algorithme est un ensemble d’instructions permettant de transformer un ensemble de données en un ensemble de résultats et ce, en un nombre fini étapes. • Pour atteindre cet objectif, un algorithme utilise deux ressources d’une machine: le temps et l’espace mémoire 7 • Temps: 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. • L’espace: 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. 8 Facteurs affectant le temps d’exécution 9 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. 10 Exemple 1: x=3; la longueur des données dans ce cas est limitée à une seule variable. Exemple 2: sum = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) sum++; En revanche, dans ce cas, elle est fonction du paramètre n 11 Pire cas, meilleur cas et cas moyen 12 Pire cas, meilleur cas et cas moyen Toutes les entrées d’une taille 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. Deux solutions s’offrent à nous: 13 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é soit déclaré inexistant. 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: 14 15 Procédure Recherche(T : Tab ; x : Entier) Variables i : Entier Début i0 Répéter ii + 1 Jusqu’à (T[i] = x) ou (i > n) Si (T[i] = x) Alors Ecrire(”Indice = ”,i) Sinon Ecrire(”Elément introuvable…”) FinSi Fin int recherche(int *tab, int C){ int i; i = 0; while (i<n && tab[i] != C ) i = i+1; if (tab[i] == C ) return(i); else return(0); } /* fin de la fonction */ 16 17 Procédure Rechdicho(T : Tab , x : entier) Variables premier, milieu, dernier : Entier trouve : Booléen Début Premier 1 dernier n Trouve Faux Répéter Milieu (premier + dernier) div 2 Si (x < T[milieu]) Alors dernier milieu – 1 Sinon Si (x > T[milieu]) Alors Premier milieu + 1 Sinon Trouve Vrai FinSi FinSi Jusqu’à (trouve = Vrai) ou (premier > dernier) Si (trouve = Vrai) Alors Ecrire(”Indice = ”,milieu) Sinon Ecrire(”Elément introuvable…”) FinSi Fin int recherche(int *tab, int C){ int dernier, premier, milieu; bool trouve; premier = 0; dernier = n-1; trouve = false; while (dernier >=premier && !trouve) { milieu = (premier + dernier) / 2; if (C == tab[milieu]) trouve = true; else if (C < tab[milieu]) dernier = milieu -1; else premier = milieu + 1; if (!trouve) return(0); return(milieu) } /* fin de la fonction */ 18 Comparaison de solutions Deux méthodes peuvent être utilisées: • Méthode empirique • Méthode mathématique 19 a- 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. 20 Problème! Ces résultats dépendent • la machine utilisée; • jeu d’instructions utilisées • l’habileté du programmeur • jeu de données générées • compilateur choisi • l’environnement dans lequel est exécuté les deux algorithmes • .... etc. 21 b- 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 seconde, mais à faire le décompte des instructions de base exécutées par ces deux algorithmes. 22 • 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. 23 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 24 int recherche(int *tab, int C){ int i; i = 0; while (i<n && tab[i] != C ) i = i+1; if (i == n) return(0); else return(i); } /* fin de la fonction */ 25 • Il est clair que ce décompte dépend non seulement de la valeur C mais 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 la cas moyen 26 • 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 cas le plus défavorable en fonction du paramètre n (ici le nombre d’éléments dans le tableau). 27 28 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 connaît la probabilité Pi de réalisation de la valeur t(i), alors par définition, on a: ) ( ... ) 1 ( ) ( 1 n t p t p n T n moy    Il est clair que pour certains algorithmes, il n’y a pas lieu de distinguer entre ces trois mesures de complexité. 29 Remarque Revenons à l’exemple Affectation notée par e Test noté par t Addition notée par a 30 int recherche(int *tab, int C){ int i; i = 0; while (i<n && tab[i] != C ) i = i+1; if (i == n) return(0); else return(i); } /* fin de la fonction */ 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) = e + 3t Une seule affectation et 3 tests (deux dans la boucle et un autre à l’extérieur de la boucle) 31 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, tous les éléments. Tmax(n) = 1e + n(2t+1e+ 1a)+ 1t + 1t = (n+1)e + na + (2n+2)t 32 Cas moyen: Comme les complexités favorable et défavorable sont respectivement (e + 3t) et (n+1)e + na + (2n+2)t, la complexité dans le cas moyen va se situer entre ces deux valeurs. Son calcul se fait comme suit: On suppose que la probabilité de présence de C dans le tableau A est de ½. De plus, dans le cas où cet élément C existe dans le tableau, on suppose 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: t(i) = (i+1)e + ia + (2i+2)t 33 Rappel 34 Par conséquent, dans le cas où C existe, la complexité moyenne de notre algorithme est : t n a n e n n X t i ia e i n n X moy n i moy ) 4 ( ) 1 ( 2 1 ) 1 3 ( 2 1 ) ( ) 2 2 ( ) 1 ( 1 ) ( 0             35 ) ( ... ) 1 ( ) ( 1 n t p t p n T n moy    Par analogie, si l’élément C n’existe pas dans le tableau, la complexité de notre algorithme est tmax(n). Par conséquent: t n a n e n n T n T n uploads/Industriel/ complexite-algorithmique-complexite-des-algorithmes-recursifs-algorithme-de-la-programmation-dynamique.pdf