Remerciez-le!

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

Algorithmique Avancée Cours I: Rappel Complexité Hadda CHERROUN Dépt. d’informa

Algorithmique Avancée Cours I: Rappel Complexité Hadda CHERROUN Dépt. d’informatique, Université Amar Telidji Laghouat hadda_cherroun@mail.lagh-univ.dz Septembre 2020 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Plan 1 Vocabulaire et Déﬁnitions 2 Complexité théorique 3 Variantes complexité H. CHERROUN Algorithmique Avancée 2/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Analyse d’un l’algorithme ? 1 Correction : Vériﬁer sa correction vis-a-vis du problème c.à.d qu’il donne bien la solution attendue 2 Complexité s’assurer que le temps d’exécution et l’espace mémoire qu’il demande sont compatibles avec les performances demandés. H. CHERROUN Algorithmique Avancée 3/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Analyse d’un l’algorithme ? 1 Correction : Vériﬁer sa correction vis-a-vis du problème c.à.d qu’il donne bien la solution attendue 2 Complexité s’assurer que le temps d’exécution et l’espace mémoire qu’il demande sont compatibles avec les performances demandés. Intérêt de commencer par ces analyses Préciser les actions à entreprendre, sans être encombrer des détails, trop précis, de l’implémentation en machine. H. CHERROUN Algorithmique Avancée 3/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Problème ? On désigne par Problème une Question comportant un ou plusieurs paramètres Exemple Tri d’un tableau de n éléments Calcul de la somme des éléments d’une matrice de n lignes et m colonnes Quel est le plus court chemin entre deux sommets données d’un graphe ? Quel est le maximum d’une liste L de t éléments? H. CHERROUN Algorithmique Avancée 4/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Taille d’un problème La Taille d’un problème est une ou plusieurs variables exprimées en fonction des paramètres du problème Exemple Problème du tri d’un tableau de n éléments = ⇒la taille c’est n Somme des éléments d’une matrice = ⇒taille c’est le couple (n,m) Le Problème du plus court chemin entre deux sommets données d’un graphe. = ⇒Taille le couple (n,m) n le nombre de sommets et m le nombre d’arcs H. CHERROUN Algorithmique Avancée 5/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Instance d’un problème soit P un problème une instance de P serait alors caractérisée par un ensemble de données concret E = e1, . . . , en Exemple Problème du tri d’un tableau T de n éléments = ⇒une Instance I serait le problème avec ces données n = 8 et T = [12, 15, 14, 0, 3, 0, 89, 150] Somme des éléments d’une matrice A = ⇒un exemple d’instance le couple (n = 3,m = 4) A =   1 2 3 2 1 20 12 3 51 2 13 44   H. CHERROUN Algorithmique Avancée 6/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Complexité On cherche estimé ou comprendre le comportement de notre algorithme en fonction des variations de la taille du problème. H. CHERROUN Algorithmique Avancée 7/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Complexité Pratique Vise à une analyse ﬁne des algorithmes au niveau de chaque instruction. Il s’agit d’une estimation grossière car une estimation ﬁne nécessite des informations sur la machine ciblée H. CHERROUN Algorithmique Avancée 8/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Complexité théorique Vise au contraire à donner une idée du comportement général d’un algorithme. On fait appel aux fonctions mathématique pour cette complexité: On dit que l’algorithme a un comportement de l’ordre d’une certaine fonction f. H. CHERROUN Algorithmique Avancée 9/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité la notation O La notation Ω-Equivalent- La notation Θ La notation O On dit que deux fonctions f et g sont de même ordre, noté f = O(g) se lit f est en grand O (Big O) de g ssi ∃c ≥0, ∃n0 ∈R∗+, ∀n > n0 telque |f(n)| ≤c.|g(n)| . Signiﬁcation Pour toutes les grandes entrées (i.e., n > n0), on est assuré que l’algorithme ne prend pas plus de c.g(n) étapes. On parle alors d’une Borne supérieure. Utilité Ceci nous renseigne que f, qui représente le comportement de notre algorithme, est bornée par le dessus par g asymptotiquement à un facteur près. H. CHERROUN Algorithmique Avancée 10/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité la notation O La notation Ω-Equivalent- La notation Θ La notation Ω On dit que deux fonctions f et g sont de même ordre, noté f = Ω(g) se lit f est en Ω(Oméga) de g ssi ∃c ≥0, ∃n0 ∈R∗+, ∀n > n0 telque |f(n)| ≥c.|g(n)| Signiﬁcation Pour toutes les grandes entrées (i.e., n > n0), on est assuré que l’algorithme ne prend pas moins de c.g(n) étapes. On parle alors d’une Borne Inférieure. Utilité Ceci nous renseigne que f, qui représente le comportement de notre algorithme, est bornée par le dessous par g asymptotiquement à un facteur près. H. CHERROUN Algorithmique Avancée 11/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité la notation O La notation Ω-Equivalent- La notation Θ La notation θ On dit que deux fonctions f et g sont de même ordre, noté f = θ(g) se lit f est en θ (Thêta) de g ssi ∃c1, c2 ≥0, ∃n0 ∈R∗+, ∀n > n0 telque c1.|g(n)| ≤|f(n)| ≤c2.|g(n) . Signiﬁcation Pour toutes les grandes entrées (i.e., n > n0), on est assuré que l’algorithme ne prend pas moins de c1.g(n) étapes. et ne prend pas plus de c2.g(n). On parle alors d’une Borne Inférieure et supérieure. la notation θ est aussi utilisée lorsque O(f) = θ(f) Utilité Ceci nous renseigne que f, qui représente le comportement de notre algorithme, est dominée par (ou soumise ) à g asymptotiquement à un facteur près. H. CHERROUN Algorithmique Avancée 12/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité la notation O La notation Ω-Equivalent- La notation Θ Explication schématique H. CHERROUN Algorithmique Avancée 13/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité la notation O La notation Ω-Equivalent- La notation Θ Règles de calcul de complexité Règle 1 : Les constantes et les coefﬁcients n’ont pas d’importance Si un problème T(n) est O(d.f(n)) avec (d > 0) alors T(n) est O(f(n)) Exemple T(n) est en O(2000n2 c’est équivaut > O(n2) en terme de comportement Algorithmique Règle 2 : Les termes d’ordre inférieur n’ont pas d’importance Si T(n) = aknk + ak−1nk−1 + . . . + a1n + a0 alors T(n) est O(nk) Exemple T(n) = n2 + 100n ≃O(n2) H. CHERROUN Algorithmique Avancée 14/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité la notation O La notation Ω-Equivalent- La notation Θ Comportements fréquents Les comportements les plus fréquents avec n la taille du problème : Ordre de grandeur Appellation Exemple O(1) constant Dépiler 1 élément d’une pile O(log n) logarithmique Recherche dichotomique O(n) linéaire Recherche d’un élément dans un tableau O(n ln n) Quasi-logarithmique Tri fusion O(n2) quadratique Tri par Insertion O(n3) cubique multiplication matricielle O(nk) polynomial avec k constante O(2n) exponentiel Exploration s’un arbre binaire complet de profondeur n O(n!) Factoriel H. CHERROUN Algorithmique Avancée 15/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Complexité en temps amorti Analyse Amortie L ’analyse amortie consiste à estimer une borne supérieure sur le coût total T(n) requis par une séquence de n opérations. Quelques opérations, parmi cette séquence, peuvent avoir un coût énorme et d’autres, un coût moindre. L ’algorithme génère un coût T(n) pour les n opérations. Le coût amorti pour chaque opération est T(n)/n. Il existe 3 techniques pour déterminer la complexité amortie. Méthode par agrégation Méthode comptable Méthode du potentiel (plus de détail au chapitre suivant). H. CHERROUN Algorithmique Avancée 16/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Complexité en temps amorti Exemple : Analyse Amortie soit T la structure de données de type tableau. Si l’on considère les opérations suivantes L ’opération o1 : Recherche(T,x)d′unlmentxdansT= ⇒O(n) L ’opération o2 :Tri des éléments du tableau o2 : Tri(T) = ⇒O(n2) L ’opération o3 : Accès à un élément du tableau o3 : T[i] = ⇒O(1) L ’opération o4 :Saisie des éléments du tableau o4 : Saisie(T[i]) = ⇒O(n) Sur cet ensemble de 4 opérations {o1, o2, o3, o4} pour T seule le tri est couteux. Le cout amorti est calculé en fonction de la fréquence d’appel à ces opérations. On compte sur le fait que l appel à tri se fait plus rare par rapport au nombre d’accès H. CHERROUN Algorithmique Avancée 17/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Complexité en temps amorti Analyse Amortie vs. Complexité moyenne L ’analyse amortie est différente de l’analyse en moyenne : Dans l’analyse en moyenne, on cherche à exploiter le fait que le pire cas est peu probable en faisant des hypothèses sur la distribution des entrées ou sur les choix aléatoires effectués dans l’algorithme ; Dans l’analyse amortie, on cherche à exploiter le fait que le pire cas des l’algorithmes ne peuvent pas se produire plusieurs fois consécutivement, ou de manière trop rapprochée, quelle que soit l’entrée. H. CHERROUN Algorithmique Avancée 18/ 19 Vocabulaire et Déﬁnitions Complexité théorique Variantes complexité Complexité en temps amorti Références D. Beauquier, J. Berstel, and P . Chrétienne. Éléments d’algorithmique. Masson, 1992. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. uploads/Management/ algo-avance-rappels-complexite.pdf