Remerciez-le!

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

Cours Complexité Algorithmique Dr. Mouna Jouini Mail: jouini.mouna@yahoo.fr A.U

Cours Complexité Algorithmique Dr. Mouna Jouini Mail: jouini.mouna@yahoo.fr A.U. 2020-2021 1 Plan du cours Chap-1: Eléments de base de la complexité algorithmique Chap-2: Complexité & optimalité Chap-3: Complexité des classes 2 Objectifs du cours Maîtriser la démarche «diviser pour régner» Savoir estimer la complexité d’un algorithme itératif ou récursif pouvant conduire à des récurrences linéaires d’ordre 1, d’ordre 2 et des récurrences de type « diviser régner » Connaître les différents algorithmes et estimer leur complexité 3 Chapitre 1 –Eléments de base de la complexité algorithméque 4 Introduction Un algorithme = une suite ordonnée d'instruction écrites pour la résolution d'un problème donné. Algorithme = une suite d’actions que devra effectuer un automate pour arriver à partir d’un état initial, en un temps fini, à un résultat Une structure de données indique la manière d'organisation des données dans la mémoire. 5 Le choix d'une structure de données adéquate dépend généralement du problème à résoudre. Deux types de structures de données : Statiques: Les données peuvent être manipulées dans la mémoire dans un espace statique alloué dès le début de résolution du problème. Ex : les tableaux Dynamiques: On peut allouer de la mémoire pour y stocker des données au fur et à mesure des besoins de la résolution du problème. Ex: liste chainée, pile, file, … Introduction 6 Qu’est-ce qu’un problème? Commençons par donner quelques exemples de problèmes : déterminer si un nombre naturel n est pair ou impair; calculer le PGCD de deux nombres naturels m et n; étant donné un graph G et deux sommets m et n de ce graphe, déterminer s’il existe un chemin menant de m à n dans ce graphe; Introduction 7 Problèmes de décision? Un problème est dit de décision si la réponse aux instances du problème est soit oui soit non. Exemples : Déterminer si oui ou non un nombre entier n est pair est un problème de décision; Par contre déterminer la longueur minimale du circuit qui passe par tous les sommets d’un graphe n’est pas un problème de décision, mais un problème d’optimisation. Introduction 8 Caractéristiques d’un algorithme Simplicité et intelligibilité de l’algorithme Efficacité de l’algorithme Temps d’exécution Quantité d’espace disque occupée par les variables Quantité de trafic généré sur un réseau Quantité de données déplacées sur le disque Temps d’exécution versus place mémoire occupée 9 Pour résoudre un problème donné, on veut un algorithme correct Trouver une solution exacte ou approchée efficace Analyser la complexité d’un algorithme Caractéristiques d’un algorithme 10 Pour résoudre un problème: Connaitre les notions de calculabilité et de décidabilité. Le problème est il classique (tri, recherche dans des graphes, programmation linéaire,…). Appliquer des schémas d’algorithme (diviser pour régner, programmation dynamique,…). Résolution d’un problème 11 Une propriété mathématique est dite décidable s'il existe un procédé mécanique qui détermine, au bout d'un temps fini, si elle est vraie ou fausse dans n'importe quel contexte possible. L'indécidabilité c'est l'impossibilité absolue et définitivement démontrée de résoudre par un procédé général de calcul un problème donné. Dire que le problème est indécidable est plus fort que dire que l'on ne sait pas résoudre le problème, ce qui marquerait simplement notre ignorance. Décidabilité et indécidabilité (1) 12 Notons que la notion de décidabilité doit être rapprochée de celle de calculabilité. En effet, à toute propriété mathématique, il est toujours possible d'associer une fonction numérique (et récip) En effet: une propriété mathématique P(a) est une fonction vers un ensemble à deux valeurs, {vrai, faux} ou, ce qui est équivalent {0, 1}. De façon symétrique, à toute fonction y = f(x), on peut associer une propriété P(x, y) vraie si y = f(x) et fausse sinon. Décidabilité et indécidabilité (2) 13 En conséquence, le problème de la décision, càd la recherche d'une procédure qui indique dans chaque contexte, et au bout d'un temps fini, si une propriété est vraie ou fausse, est équivalent à la construction d'un algorithme qui calcule pour chaque fonction f et pour chaque argument x de f, la valeur y telle que y = f(x). Autrement dit, le problème de la décision est équivalent au problème du calcul. Décidabilité et indécidabilité (3) 14 Problème A Soient m et n deux entiers donnés > 1. m est-il un multiple de n ? On sait qu'il est vrai que: 12 est un multiple de 2 et qu'il est faux que : 16 est un multiple de 5. On sait même bien plus que cela, on sait comment s'y prendre pour déterminer pour tout n et tout m quand il est vrai que "m est un multiple de n» et quand il est faux que : "m est un multiple de n« . Exemple (1) 15 Problème A Il suffit en effet de : faire la division de m par n, regarder le reste obtenu, r, si r = 0 alors il est VRAI que "m est un multiple de n’’ sinon il est FAUX que "n est un multiple de m" Exemple (2) 16 Problème A C'est un procédé absolument sûr, qui fonctionne en un temps fini pour tous les jeux de données possibles et conduit toujours à la bonne réponse. il montre que le problème A est décidable. Exemple (3) 17 Problème B Un problème indécidable de géométrie élémentaire. Soient F1 F2 ... Fn une liste de formes polygonales. Peut-on paver le plan, sans recouvrement ni espace vide avec des exemplaires de F1 F2... Fn ? Il a été démontré que ce problème est indécidable, il n'existe aucun algorithme permettant par un calcul fini à partir des données (la liste des formes géométriques) d'établir si OUI ou NON il est possible de paver le plan avec des exemplaires des formes géométriques considérées. Exemple (4) 18 Maintenant que l’on sait ce qui peut être calculé il y a une autre limite: l’espace et le temps. Parmi les problèmes que l’on peut résoudre, il y a en a certains qui sont plus faciles que d’autres: Ex1: pour trier une liste, il y a des algorithmes en O(n log n). C’est considéré comme un problème facile (surtout avec les machines d’aujourd’hui). Ex2: Pour résoudre le problème du voyageur de commerce, on ne connait pas d’algorithmes non exponentiels : il y a environ n! chemins possibles. Si n = 15 alors 15! = 1307674368000 Donc il est très difficile. Complexité 19 Un paradigme est une méthode générique qui s'applique dans plusieurs situations algorithmiques. L'induction: Ce paradigme donne lieu à des processus itératifs. Diviser pour régner: tous les algorithmes récursifs. Trouver un ordre "optimal" sur les opérations à effectuer Exemples : •les parcours en profondeur dans les graphes, •les utilisations des ordres lexicographiques. Quelques paradigmes pour un algorithme efficace 20 Utiliser une structure de données ad hoc: pour résoudre efficacement les opérations de base de l'algorithme. Exemples : arborescences binaires ordonnées de recherche, arborescences bicolorées,… Utiliser un procédé stochastique (à base de tirages aléatoires). Les algorithmes randomisés ou probabilistes sont souvent très simples à mettre en oeuvre et donnent le bon résultat. Quelques paradigmes pour un algorithme efficace 21 Exemple : Calcul de la valeur d’un polynôme Soit P(X) un polynôme de degré n P(X) = anXn + an-1Xn-1 + ... + a1X + a0 Où, n : entier naturel an, an-1, ..., a1, a0 : les coefficients du polynôme 1ère variante : début P=0 Pour i de 0 à n faire P= P+ ai*Xi finpour fin Coût de l’algorithme : -(n+1) additions -(n+1) multiplications -(n+1) puissances 22 2ème variante : debut Inter=1 P =0 Pour i de 0 à N faire P= P+ Inter *ai Inter = Inter * X finpour Fin Coût de l’algorithme : -(n+1) additions -2(n+1) multiplications Exemple : Calcul de la valeur d’un polynôme 23 3ème variante : Schéma de Horner P(x) = (….(((anx+an-1)x+an-2)x+an-3)…..)x+a0 début P = an Pour i de n-1 à 0 (pas = –1) faire P = P*X + ai Fin pour Fin Nécessité d’estimer le coût d’un algorithme avant de l’écrire et l’implémenter Coût de l’algorithme: -n additions -n multiplications Exemple : Calcul de la valeur d’un polynôme 24 Chapitre 2 – Complexité et optimalité 25 Plan Complexité temporelle et spatiale Calcul du coût d’un algorithme Approximation des complexités 26 La complexité algorithmique permet de mesurer les performances d'un algorithme afin de le comparer avec d'autres algorithmes résolvant le même problème. L’idée est de quantifier les deux grandeurs physiques (temps d’exécution, place mémoire) dans le but de comparer différents algorithmes qui résolvent le même problème, indépendamment: des détails d’implémentation. de la machine, du langage de programmation, compilateur Introduction 27 Introduction La complexité algorithmique cherche à analyser le comportement des algorithmes (son temps d'exécution et/ou la place mémoire occupée) en fonction de la taille des données d'entrée. La complexité algorithmique permet de dire si : Un algorithme A est meilleur qu’un algorithme B. Un algorithme A est optimal. Un algorithme ne doit pas être utilisé. 28 Définition Critères d’évaluation d’un programme Est-ce que le programme satisfait les spécifications de la tâche ? Est-ce qu’il fonctionne correctement ? Est-il bien documenté ? (commentaires, guide d’utilisation) Est-ce que le code uploads/Geographie/ cours-complexite-algo-3lfiag-2020-2021-drmounajouini.pdf