Notes de Cours Algorithmes et Structures de Données usto lmd s3-S4
télécharger 98.4 Kb.
|
Notes de Cours Algorithmes et Structures de Données USTO LMD S3-S4 Algorithmique et structures de données CHAPITRE I NOTIONS D’ALGORITHME ET DE COMPLEXITE
Intuitivement un algorithme est : « n’importe quelle procédure de calcul non ambiguë pouvant prendre une ou plusieurs valeurs en entrée et produisant une ou plusieurs valeurs en sortie ». C’est un outil pour la résolution d’un problème bien spécifié dont l’énoncé spécifie la relation entre les entrées et les sorties. L’algorithme doit décrire donc le schéma permettant l’obtention des sorties à partir des entrées. Il y a lieu de citer d’autres définitions classiques d’un algorithme : a- « la spécification d’un schéma de calcul, sous forme d’une suite d’opérations élémentaires obéissant à un enchaînement déterminé ». (Encyclopedia Universalis) b- « une procédure générale permettant de résoudre un problème : appliqué à n’importe quelle instance du problème, l’algorithme produit sûrement une solution en un nombre de pas fini ». c- « une suite finie d’instructions non ambiguës pouvant être exécutées de façon automatique ». Parmi les exemples classiques d’algorithmes, on cite : - Calcul du produit de deux matrices - Calcul de la solution d’un système d’équations linéaire - Calcul du PGCD (algorithme d’Euclide) - Calcul du plus court chemin (algorithme de Dijkstra) - Changement de base d’écriture d’un nombre - Tri d’une liste - Recherche d’un mot dans un dictionnaire - Recherche sur le Web - Compression des données Exemple d’un algorithme de tri Formellement, le problème de tri peut être défini comme suit : Entrée: Une suite de n nombres {a1,a2,…,an}. Sortie : Une permutation (ordonnancement) {a’1,a’2,…,a’n} telle que a’1 ≤ a’2 ≤ … ≤ a’n. Par exemple, la séquence {1,18,5,4,33} doit être transformée en {1,4,5,18,33} par un algorithme de tri. La séquence d’entrée est appelée instance du problème de tri. Un algorithme est dit correct si, pour n’importe quelle instance d’entrée doit s’arrêter avec une sortie correcte. On dit que l’algorithme résout correctement le problème. I.1. Description d’un algorithme Il y a trois façons de décrire un algorithme :
Exemple : recherche séquentielle d’un élément dans une liste non triée. Il s’agit de comparer successivement tous les éléments de la liste avec l’élément recherché jusqu’à rencontrer celui-ci ou bien arriver à la fin de la liste.
Note : Il y a différents formalismes possibles. Exemple : Recherche séquentielle dans un tableau // Entrée : n données se trouvant dans un tableau T. // La donnée recherchée notée clé. On utilise une variable booléenne // notée trouvé et un entier i. i 1; trouvé faux; Tant que ((non trouvé) et (i <= n)) Si (T[i] = clé) alors trouvé vrai; Sinon i i+1; Fin boucle renvoyer trouvé
Exemple : Tri par insertion (En Java) public void insertionSort() { int in, out; for(out=1; out { long temp = a[out]; in = out; while(in>0 && a[in-1]>=temp) { a[in] = a[in-1]; --in; } a[in] = temp; } } Remarques :
I.2. Implémentation d’un algorithme L’implémentation d’un algorithme consiste à le traduire dans un langage de programmation et ceci dans le but de l’exécuter sur ordinateur. L’implémentation nécessite le choix de la représentation des données ou la structure de données. La résolution d’un problème peut être souvent effectuée par plusieurs algorithmes et pour chaque algorithme il existe plusieurs structures de données. L’algorithme ainsi que la structure de donnée associée à son implémentation est caractérisé par :
Le langage C est un langage évolué, conçu en 1970 par Dennis RITCHIE (Bell AT&T), capable de traiter de manière standard des informations de bas niveau très proche de la structure matérielle des ordinateurs. Le langage C et sa version orientée objet C++ sont à l’origine de nombreux langages récents tels que JAVA. 1) Structure générale
Exemple : Tri à bulles
Remarque : printf/scanf (C) cout/cin (C++) (utiliser #include 2) Déclaration des variables * Les types de données Entiers : int (char, bool) Modificateurs : short, long, unsigned, signed, long long Réels : float (double , long double) Chaînes de caractères : char nom[20]; ou char *nom; Structures : struct Personne { Ou typedef struct { char nom[20]; == int age; } Personne; } PERS[100]; Personne PERS[100]; * Déclaration int a, b, c; short i=0; // Une variable peut être initialisée lors de sa déclaration float r; Remarques :
Exemple : float x; int d =(int)(x); 3) Opérateurs (Par ordre décroissant de priorité) * Arithmétiques : Plus unaire + Moins unaire – Incrément ++ Décrément – – Multiplication * Division / Modulo % Addition + Soustraction – Affectation = += *= /= – = %= * Logiques : Non ! Comparaisons = = ! = < <= > >= Ou | | Et && Remarques : * L’opérateur ? permet d’exécuter l’équivalent d’une instruction if else; Ex : (a==b) ? printf(a est égal à b) : printf(a est différent de b); * L’affectation retourne la valeur affectée ce qui permet d’écrire par exemple a = b = 5 ; 4) Instructions fondamentales Une instruction atomique est toujours terminée par point virgule (;). Un bloc est une suite de déclarations et d’instructions encadrée par des accolades {………}. Voici la syntaxe des principales instructions de contrôle : * if (expression) instruction1; else instruction2; * switch (expression) { case expre_cste : instructions; ... default : instructions; } * while (expression) instructions * do { instructions } while (expression); * for (init;arret;increment) instructions Remarque : - break provoque la sortie immédiate d’une boucle ou de l’instruction switch. - continue passe directement à l’itération suivante de la boucle. 5) Les pointeurs Un pointeur est une adresse permettant de désigner un objet (une variable ou une fonction) en mémoire centrale. Exemple de manipulation de listes chaînées
On abordera essentiellement dans ce chapitre la complexité temporelle ou en temps. III.1. Généralités a) Définition L’étude de la complexité des algorithmes a pour objectif l’estimation du coût d’un algorithme (assorti d’une structure de donnée). Cette mesure permet donc la comparaison de deux algorithmes sans avoir à les programmer. Si l’on prend en compte pour l’estimation de la complexité les ressources de la machine telles que la fréquence d’horloge, le nombre de processeurs, le temps d’accès disque etc., on se rend compte immédiatement de la complication voir l’impossibilité d’une telle tâche. Pour cela, on se contente souvent d’estimer la relation entre la taille des données et le temps d’exécution, et ceci indépendamment de l’architecture utilisée. Il s’agit d’un modèle simplifié qui tient compte des ressources technologiques ainsi que leurs coûts associés. On prendra comme référence un modèle de machine à accès aléatoire et à processeur unique où les opérations sont exécutées l’une après l’autre sans opérations simultanées. On définit la complexité (temporelle) d’un algorithme comme étant la mesure du nombre d’opérations élémentaires qu’il effectue sur un jeu de données. La complexité est exprimée comme une fonction de la taille du jeu de données. L’analyse de la complexité consiste généralement à mesurer asymptotiquement le temps requis pour l’exécution de l’algorithme sur une machine selon un modèle de calcul. Cette mesure permet juste d’avoir une idée imprécise mais très utile sur le temps d’exécution de l’algorithme en question. Elle nous permet, entre autres, d’estimer la taille des instances pouvant être traitées sur une machine donnée en un temps raisonnable. Cependant, l’analyse de la complexité peut s’avérer très difficile même pour des algorithmes relativement simples nécessitant parfois des outils mathématiques très poussés. D’une façon formelle, on peut aussi définir la complexité d’un algorithme a comme étant tout ordre de grandeur du nombre d’opérations élémentaires effectuées pendant le déroulement de a. Les notions d’opérations élémentaires et d’ordre de grandeurs ainsi que les notations les plus utilisées seront définis au fur et à mesure. b) Opérations élémentaires On appelle opérations élémentaires les opérations suivantes :
Exemple : L’instruction « c a + b ; » nécessite les quatre opérations élémentaires suivantes :
c) Remarques
III.2. Evaluation des coûts Suivant le type d’instruction, la complexité est évaluée comme suit : a) Séquence A : J; K; TA(N) = TJ(N) + TK(N) b) Alternative A : Si C Alors J Sinon K TA(N) = TC(N) + max{TJ(N) , TK(N)} : Pire cas (Worst case) TA(N) = TC(N) + min{TJ(N) , TK(N)} : Meilleur cas (Best case) c) Boucles A : nb B TA(N) = nb . TB(N) d) Récursivité Etablir la formule de récurrence et en déduire la complexité. III.3. Mise en œuvre a) Exemple d’illustration : Le Tri par insertion Considérons l’algorithme de tri par insertion permettant de trier un tableau A de taille N. Considérons le modèle de complexité qui associe à chaque ligne i (du code) son coût (ou temps d’exécution) Ci. L’analyse peut se faire donc comme suit : void tri_inserer (int A[50] , int N) // coût Nombre de fois { // ========================== int j, temp, i; for (j=2 ; j<=N ; j++) // coût C1 ........ N { temp = A[j]; // coût C2 ........ N-1 i = j-1; // coût C3 ........ N-1 while (i>0 && A[i]>temp) // coût C4 ........ 2+3+...+N { A[i+1]=A[i]; // coût C5 ........ 1+2+...N-1 i=i-1; // coût C6 ........ 1+2+...N-1 } A[i+1]=temp; // coût C7 ........ N-1 } } b) Rappel des principales suites
 La complexité de l’algorithme de tri par insertion est donc : T(N) =  Et puisqu’on s’intéresse aux valeurs de N très grandes (comportement asymptotique de la complexité), nous pouvons noter la complexité en utilisant les ordres de grandeurs (voir rappel ci-après) comme suit : T(N) = O(N2) Note : T(N) représente la complexité dans le pire des cas car on n’a pas tenu compte dans notre calcul de la valeur de l’expression logique de la condition (A[i] > temp) qui détermine le nombre d’exécutions de la boucle interne. L’algorithme de tri par insertion peut donc prendre moins de temps pour des tableaux ayant une structure particulière et par conséquent, la complexité est une variable aléatoire. C’est pourquoi on parle de complexité en moyenne d’un algorithme qu’on peut calculer comme étant l’espérance de cette variable aléatoire. c) Généralités sur les ordres de grandeurs - Notation (thêta) : soit g une fonction positive d’une variable entière n. (g(n)) désigne l’ensemble des fonctions positives de la variable n, pour lesquelles il existe deux constantes c1, c2 et un entier n0, satisfaisant la relation : 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) n≥n0 Par abus de notation on écrit f(n) = (g(n)) pour exprimer que f (g(n)) (malgré que (g(n)) est un ensemble et f est un élément de celui-ci). Exemple : Soit g(n) = n2 et f(n) = 50n2+10n. Il s’agit de trouver c1, c2 et n0 tels que : c1 n2 ≤ 50n2+10n c1 ≤ 50, 50n2+10n ≤ c2 n2 c2 ≥50. donc on a bien f(n) = (g(n)) = (n2) La figure suivante montre les graphes de trois fonctions f1, f2 et f3. On peut facilement vérifier que f2 = (f1(N)) et aussi f3 = (f1(N)). On peut interpréter la relation f(n) = (g(n)) comme suit : pour n assez grand, la fonction f est bornée à la fois supérieurement et inférieurement par la fonction g, c'est-à-dire que les fonctions f et g sont égales, à une constante prét.  - Notation O (grand o) : Lorsque la fonction f est bornée uniquement supérieurement par la fonction g on utilise la notation O. O(g(n)) désigne donc l’ensemble des fonctions positives de la variable n, pour lesquelles il existe une constante c et un entier n0, satisfaisant la relation : 0 ≤ f(n) ≤ c g(n) n≥n0 La relation f(n) = O(g(n)) indique que la fonction f est bornée supérieurement par la fonction g pour des valeurs suffisamment grandes de l’argument n. Donc f(n) = (g(n)) implique que f(n) = O(g(n)) (par abus de notation). Formellement, on peut écrire (g(n)) O(g(n)). Exemple : 100n2 + 10n = O(n2) mais on peut aussi écrire 100n = O(n2) ! Car ceci est équivalent à dire que 100n est asymptotiquement bornée supérieurement par n2. - Notation Ω (grand oméga) : Ω(g(n)) désigne l’ensemble des fonctions positives de la variable n, pour lesquelles il existe une constante c et un entier n0, satisfaisant la relation : 0 ≤ c g(n) ≤ f(n) n≥n0 La relation f(n) = Ω(g(n)) indique que la fonction f est bornée inférieurement par la fonction g pour des valeurs suffisamment grandes de l’argument n. Par conséquent, f(n) = (g(n)) implique que f(n) = Ω(g(n)) (par abus de notation). Formellement, on peut écrire : (g(n)) Ω(g(n)). Le théorème suivant découle immédiatement des définitions données : Théorème : f(n) = (g(n)) si et seulement si : f(n) = Ω(g(n)) et f(n) = O(g(n)) Les trois notations précédentes peuvent être récapitulées par le schéma suivant : Ө Borne Supérieure et Inférieure Large O Borne Supérieure Large Ω Borne Inférieure rge Quelques propriétés de la notation O
d) Autre méthode d’analyse de complexité La complexité d’un algorithme peut être dans certains cas facilement trouvée si on arrive à analyser et comprendre l’algorithme et repérer ses opérations fondamentales. Ainsi pour le tri par insertion, on peut s’intéresser aux comparaisons comme suit : Le nombre de comparaisons exécutées à l’itération i est au plus i. Le nombre total de comparaisons est donc :  e) Exercices - Etudier la complexité meilleur et pire cas de l’algorithme de recherche séquentielle puis dichotomique. - Analyser la complexité d’un algorithme récursif. III.4. Complexité polynomiale et exponentielle Un algorithme est considéré pratique, relativement à une classe de problèmes, s’il est capable de résoudre n’importe qu’elle instance (dans le pire des cas) ou en moyenne (complexité moyenne) en temps polynomial c'est-à-dire, sa complexité est O(Nk), où k est un entier quelconque. En réalité une complexité est dite polynomiale si elle peut être bornée par un polynome, on retrouve donc : O(1) (Complexité constante) O(log(N)) (Complexité logarithmique) O(N) O(N) (Complexité linéaire) O(NlogN) (Complexité quasi-linéaire) O(N²) (Complexité quadratique) O(N3) (Complexité cubique) … D’autre part une complexité est dite exponentielle (O(kN) en général) si elle ne peut pas être bornée par un polynome, on retrouve par exemple : O(NlogN) (Complexité sous exponentielle) O(2N), O(3N) (Complexité exponentielle) O(N!) (Complexité factorielle) O(NN) … III.5. Etude Comparative : Tri par insertion vs Tri par sélection III.6. Différentes formes de complexité Il est évident que la complexité d’un algorithme peut ne pas être la même pour deux jeux de données différents. Ceci peut avoir des conséquences sur le choix du meilleur algorithme pour un problème donné. En pratique, on s’intéresse aux formes suivantes de la complexité : III.6.1. Complexité dans le pire des cas (Worst case) Il s’agit de considérer le plus grand nombre d’opérations élémentaires effectuées sur l’ensemble de toutes les instances du problème ; on cherche une borne supérieure qui est atteinte même pour des instances ayant une très faible, voire zéro, probabilité. Cette forme de complexité est plus simple à calculer mais peut conduire à un choix erroné d’un algorithme. III.6.2. Complexité dans le meilleur des cas (Best case) Il s’agit, cette fois ci, de considérer le plus petit nombre d’opérations élémentaires ; c'est-à-dire on cherche un minorant de la complexité au lieu d’un majorant. Cette forme de complexité peut être considérée comme complément de la complexité dans le pire des cas mais n’offre aucune garantie à l’utilisateur. III.6.3. Complexité en moyenne (Average case) Il s’agit de calculer la moyenne (espérance mathématique) des nombres d’opérations élémentaires effectuées sur la totalité des instances. Ce calcul est généralement très difficile et souvent même délicat à mettre en œuvre car il faut connaître la probabilité de chacun des jeux de données pour pouvoir calculer la complexité en moyenne. Cette forme d’analyse fait actuellement l’objet de nombreux travaux de recherche et permet d’expliquer, d’une part le comportement de certains algorithmes en pratique ; et d’autre part, le choix d’algorithmes pour des problèmes ayant des tailles considérables tels que les problèmes d’apprentissage en intelligence artificielle. |
similaire:
 | «la spécification d’un schéma de calcul, sous forme d’une suite d’opérations élémentaires obéissant à un enchaînement déterminé».... |  | |
| | ||
| | ||
| «parlantes» sont transférées à la base de données du cloud. Cette méthode basée sur les concepts du fog computing (informatique géodistribuée)... | | |
| «L’art des Structures». Ce livre de 175 pages est disponible dans une édition reliée et au format électronique. Chacun des 6 vainqueurs... | | «communisme de la pensée» et du travail collectif. La collaboration est active, et peu-à-peu se forge une mythologie des groupes |