Remerciez-le!

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

2.1 Analyse d’algorithmes ANALYSE D’ALGORITHMES • Révision mathématique rapide

2.1 Analyse d’algorithmes ANALYSE D’ALGORITHMES • Révision mathématique rapide • Temps d’exécution • Pseudo-code • Analyse d’algorithmes • Notation asymptotique • Analyse asymptotique n = 4 Algorithme Entrée T(n) Sortie 2.2 Analyse d’algorithmes Cas moyen vs. Pire des cas: Temps d’exécution d’un algorithme • Un algorithme peut être plus performant avec certains ensembles de données qu’avec d’autres, • Trouver le cas moyen peut s’avérer difficile, alors les algorithmes sont mesurés typiquement selon la complexité temporelle du pire des cas. • De plus, pour certain domaines d’application (par ex. contrôle aérien, chirurgie, gestion de réseau) connaître la complexité temporelle du pire des cas est d’importance cruciale. Entrée Temps 1 ms 2 ms 3 ms 4 ms 5 ms A B C D E F G pire des cas meilleur des cas }cas moyen? 2.3 Analyse d’algorithmes Mesurer le temps d’exécution • Comment devrions-nous mesurer le temps d’exécution d’un algorithme? • Étude expérimentale: - Écrivez un programme qui réalise l’algorithme. - Exécutez le programme avec des ensembles de données de taille et de contenu variés. - Utilisez une méthode (System.currentTimeMillis()) pour mesurer précisément le temps d’exécution. - Les mesures résultantes devraient ressembler à: 50 100 0 t (ms) n 10 20 30 40 50 60 2.4 Analyse d’algorithmes Au-delà des études expérimentales • Les études expérimentales ont quelques restrictions: - Il est nécessaire de réaliser et de tester l’algorithme afin de déterminer son temps d’exécution. - Les essais peuvent être faits seulement sur un ensemble limité d’entrées, et ils peuvent ne pas être indicatifs du temps d’exécution d’autres entrées non considérées. - Afin de comparer deux algorithmes, les mêmes environnements matériel et logiciel devraient être utilisés. • Nous développerons maintenant une méthodologie générale pour analyser le temps d’exécution d’algorithmes qui: - Utilise une description de haut niveau de l’algorithme au lieu de tester sa réalisation. - Considère toutes les entrées possibles. - Permet d’évaluer l’efficacité d’un algorithme indépendamment des environnements matériels et logiciels. 2.5 Analyse d’algorithmes Pseudo-code • Le pseudo-code est une description d’algorithme qui est plus structurée que la prose ordinaire mais moins formelle qu’un langage de programmation. • Exemple: trouver l’élément maximal d’un vecteur (array). Algorithm arrayMax(A, n): Entrée: Un vecteur A contenant n entiers. Sortie: L’élément maximal de A. currentMax ← A[0] for i ← 1 to n −1 do if currentMax < A[i] then currentMax ← A[i] return currentMax • Le pseudo-code est notre notation de choix pour la description d’algorithmes. • Cependant, le pseudo-code cache plusieurs problèmes liés à la conception de programmes. 2.6 Analyse d’algorithmes Qu’est-ce que le pseudo-code? • Un mélange de langage naturel et de concepts de programmation de haut niveau qui décrit les idées générales derrière la réalisation générique d’une structure de données ou d’un algorithme. - Expressions: utilisez des symboles mathématiques standards pour décrire des expressions booléennes et numériques - utilisez ← pour des affectations (“=” en Java) - utilisez = pour la relation d’égalité (“==” en Java) - Déclaration de méthodes: - Algorithm nom(param1, param2) - Éléments de programmation: - décision: if ... then ... [else ... ] - boucle while: while ... do - boucle repeat: repeat ... until ... - boucle for: for ... do - indexage de vecteur: A[i] - Méthodes: - appel: object method(args) - retour: return value 2.7 Analyse d’algorithmes Analyse d’algorithmes • Opérations primitives: opérations de bas niveau qui sont largement indépendantes du langage de programmation et qui peuvent être identifiées en pseudo-code, par exemple: - Appel et retour d’une méthode - effectuer une opération arithmétique (addition) - comparer deux nombres, etc. • En inspectant le pseudo-code, nous pouvons compter le nombre d’opérations primitives exécutées par un algorithme. • Exemple: Algorithm arrayMax(A, n): Entrée: Un vecteur A contenant n entiers. Sortie: L’élément maximal de A. currentMax ← A[0] for i ← 1 to n −1 do if currentMax < A[i] then currentMax ← A[i] return currentMax 2.8 Analyse d’algorithmes Notation asymptotique • But: simplifier l’analyse en se débarrassant de l’information superflue. - comme “arrondir” 1 000 001 ≈ 1 000 000 - nous désirons indiquer formellement que 3n2 ≈ n2 • La notation “Grand-O” soit les fonctions f(n) et g(n), nous disons que f(n) est O(g(n)) si et seulement si il y a des constantes positives c et n0 tel que f(n) ≤ c g(n) pour n ≥ n0 f(n) = 2n + 6 g(n) = n 20 21 22 23 24 25 26 27 20 21 22 23 24 25 26 27 c g(n) = 4n n 2.9 Analyse d’algorithmes Un autre exemple • n2 n’est pas O(n) • nous ne pouvons pas trouver c et n0 tel que n2 ≤ c n for n ≥ n0 f(n) = n2 g(n) = n 20 21 22 23 24 25 26 27 20 21 22 23 24 25 26 27 n c g(n) 2.10 Analyse d’algorithmes Notation asymptotique (suite) • Note: Même si il est correct de dire “7n - 3 est O(n3)”, une meilleure formulation est “7n - 3 est O(n)”, c’est-à-dire, nous devrions faire l’approximation la plus juste possible. • Règle simple: laissez tomber les termes d’ordre inférieur de même que les facteurs - 7n - 3 est O(n) - 8n2log n + 5n2 + n est O(n2log n) • Classes spéciales d’algorithmes: - logarithmique: O(log n) - linéaire O(n) - quadratique O(n2) - polynomial O(nk), k ≥ 1 - exponentiel O(an), n > 1 • “Parenté” de Grand-O −Ω(f(n)): Grand-Oméga −Θ(f(n)): Grand-Thêta 2.11 Analyse d’algorithmes Analyse asymptotique et temps d’exécution • Utilisez la notation Grand-O pour indiquer le nombre d’opérations primitives exécutées en fonction de la taille d’entrée. • Par exemple, nous disons que l’algorithme arrayMax a un temps d’exécution O(n). • En comparant les temps d’exécution asymptotiques - un algorithme d’ordre O(n) est meilleur qu’un autre d’ordre O(n2) - de la même façon, O(log n) est meilleur que O(n) - hiérarchie de fonctions: - log n << n-2 << n << n log n << n2 << n3 << 2n • Attention! - Méfiez-vous des facteurs constants très grands. Un algorithme au temps d’exécution 1 000 000 n est quand même O(n) et peut être moins efficace sur votre ensemble de données qu’un autre au temps d’exécution 2n2, qui est O(n2). 2.12 Analyse d’algorithmes Exemple d’analyse asymptotique • Un algorithme pour calculer les moyennes préfixes: Algorithm prefixAverages1(X): Entrée: Un vecteur de nombres X à n éléments. Sortie: Un vecteur de nombres A à n éléments tel que A[i] est la moyenne des éléments X[0], ... , X[i]. Soit A un vecteur de n nombres. for i ← 0 to n - 1 do a ← 0 for j ← 0 to i do a ← a + X[j] A[i] ← a/(i + 1) return array A • Analyse ... 2.13 Analyse d’algorithmes Révision mathématique rapide • Progression arithmétique: - Un exemple - deux représentations visuelles i 1 2 3 … n + + + + = i 1 = n ∑ n2 n + 2 - - - - - - - - - - - - - - - = 1 n/2 0 1 2 n 3 2 n+1 ... 1 2 n 0 1 2 n 3 3 ... 2.14 Analyse d’algorithmes Un autre exemple • Un meilleur algorithme pour calculer les moyennes préfixes: Algorithm prefixAverages2(X): Entrée: Un vecteur de nombres X à n éléments. Sortie: Un vecteur de nombres A à n éléments tel que A[i] est la moyenne des éléments X[0], ... , X[i]. Soit A un vecteur de n nombres. s ← 0 for i ← 0 to n - 1 do s ← s + X[i] A[i] ← s/(i + 1) return array A • Analyse ... 2.15 Analyse d’algorithmes Mathématiques à réviser • Logarithmes et exposants - propriétés des logarithmes: logb(xy) = logbx + logby logb(x/y) = logbx - logby logbxα = αlogbx logxa logxb - propriétés des exposants: a(b+c) = abac abc = (ab)c ab/ac = a(b-c) b = a bc = a logba = logab c*logab 2.16 Analyse d’algorithmes Mathématiques à réviser (suite) • Plancher (Floor) x = le plus grand entier ≤ x • Plafond (Ceiling) x = le plus petit entier ≥ x • Sommations - définition générale: - où f est une fonction, s est l’index de départ, et t est l’index d’arrivée • Progression géométrique: f(i) = ai - soit un entier n ≥ 0 et un nombre réel 0 < a ≠ 1 - les progressions géométriques ont une croissance exponentielle. f i ( ) i s = t ∑ f s ( ) f s 1 + ( ) f s 2 + ( ) … f t ( ) + + + + = ai 1 a a2 … an 1 an 1 + – 1 a – - - - - - - - - - - - - - - - - - - - - - = + + + + = i 0 = n ∑ 2.17 Analyse d’algorithmes Sujets avancés: techniques de justification simples • Par exemple - Trouvez un uploads/Management/ csi2514-4x-conception-et-analyse-des-algorithmes.pdf