Remerciez-le!

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

Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoi

Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Analyse de la complexité des algorithmes Benchikhi Loubna Ecole Nationale des Sciences Appliquées de Marrakech Université Cadi Ayyad l.benchikhi@uca.ma October 4, 2018 Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Plan I 1 Algorithme 2 Critères de résolution d’un problème 3 Temps de calcul VS Espace mémoire 4 Complexité en temps de calcul 5 Evaluation de T(n) pour les structures algorithmiques 6 Complexiteé asymptotique 7 Notation grand-O 8 Notation Grand-Omega 9 La notation Theta 10 Notes Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Plan II 11 Applications Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Déﬁnition 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 ﬁni étapes. Pour atteindre cet objectif, un algorithme utilise deux ressources d’une machine: le temps l’espace mémoire Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications L’eﬃcacité en terme d’exécution : Un algorithme sera dit plus eﬃcace qu’un autre si pour la même donnée il s’exécute en un laps de temps plus court. L’eﬃcacité en espace mémoire : Un algorithme sera dit plus eﬃcace en espace mémoire qu’un autre si pour la même donnée il utilise moins d’espace mémoire. Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications La ﬁabilité de l’algorithme qui est le degreé d’absence de bugs : un algorithme sera jugé plus ﬁable ou plus stable qu’un autre s’il présente moins de bugs. La robustesse de l’algorithme : un algorithme sera plus robuste qu’un autre s’il résiste mieux aux erreurs de manipulations des utilisateurs plus au moins attentionnés notamment dans sa composante entrées/sorties Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications L’optimisation de l’eﬃcacité en terme d’exécution va à l’encontre de l’optimisation en espace. Il n’y a pas de méthode ou d’échelle de mesure permettant d’évaluer la ﬁabilité ou la robustesse d’un algorithme. Par contre, il existe des méthodes rationnelles et rigoureuses pour évaluer l’eﬃcacité en espace et en temps d’un algorithme ⇒Analyse de la « complexité des algorithmes » Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Le temps d’exécution : la complexité en temps L’espace mémoire requis : la complexité en espace Si par exemple vous avez besoin d’allouer en moyenne n Kilo-octets de mémoire pour un algorithme dont l’entrée est de taille n, la complexité mémoire est de l’ordre de n. Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications ⇒Aujourd’hui, la complexité en temps est le point essentiel. Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Attention Dans certains domaines de l’informatique on s’intéressera à d’autres caractéristiques, parfois mesurables elles aussi en terme de complexité, des algorithmes. Par exemple, un programmeur pour calculatrice ou système embarqué pourra s’interroger sur la consommation électrique de son algorithme, aﬁn d’économiser la batterie. Dans le cas général, on s’intéressera uniquement aux complexités en temps et en mémoire, et même principalement à la complexité en temps. Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Si je donne à mon programme une entrée de taille n, quel est l’ordre de grandeur, en fonction de n, du nombre d’opérations qu’il va eﬀectuer ? Elle repose sur le fait que les programmes qui résolvent un problème dépendent des conditions du problème : si les conditions changent, ils peuvent s’eﬀectuer en plus ou moins de temps. La complexité permet de quantiﬁer, mettre une formule mathématique, la relation entre les conditions de départ et le temps eﬀectué par l’algorithme. Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Compter les opérations Il faut en fait choisir soi-même quelques petites opérations que l’algorithme eﬀectue souvent, et que l’on veut utiliser comme opérations de base pour mesurer la complexité Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Compter les opérations Exemple de l’omelette Pour faire une omelette, on peut considérer que les trois opérations de base sont : Casser un oeuf Battre l’oeuf Faire cuire l’oeuf battu Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Compter les opérations Exemple de l’omelette On peut donc pour chaque recette compter le nombre d’oeufs cassés, cuits et battus, et avoir ainsi une idée de la complexité de la recette, Pour N oeufs, on eﬀectue 3N opérations. Par contre l’ajout de sel, poivre ou herbes est très rapide, et n’a pas besoin d’être pris en compte dans l’analyse de la complexité Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications La complexité en temps d’un algorithme se mesure essentiellement en calculant le nombre d’opérations élémentaires pour traiter une donnée de taille n Notations : On note n : taille des données T (n) : nombre d’opérations élémentaires Conﬁgurations caractéristiques : meilleur cas pire des cas cas moyen Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Complexité au meilleur cas C’est le plus petit nombre d’opérations qu’aura à exécuter l’algorithme sur un jeu de données de taille ﬁxée (ici n). C’est une borne inférieure de la complexité de l’algorithme sur un jeu de données de taille n Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation Theta Notes Applications Complexité au pire cas C’est le plus grand nombre d’opérations qu’aura à exécuter l’algorithme sur un jeu de données de taille ﬁxée (ici n). Avantage : il s’agit d’un maximum et l’algorithme ﬁnira donc toujours avant d’avoir eﬀectuer Tmax(n) opérations. Inconvénient : cette complexité peut ne pas reﬂéter le comportement usuel de l’algorithme, le pire cas pouvant ne se produire que très rarement, mais il n’est pas rare que le cas moyen soit aussi mauvais que le pire cas. Benchikhi Loubna Algorithmique Avancée et Compléxité Algorithme Critères de résolution d’un problème Temps de calcul VS Espace mémoire Complexité en temps de calcul Evaluation de T(n) pour les structures algorithmiques Complexiteé asymptotique Notation grand-O Notation Grand-Omega La notation uploads/Ingenierie_Lourd/ chapitre1-2-10-2018.pdf