Remerciez-le!

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

1 UMLV  Université de Marne-la-Vallée STRUCTURES DE DONNÉES Maxime CROCHEMORE

1 UMLV  Université de Marne-la-Vallée STRUCTURES DE DONNÉES Maxime CROCHEMORE http://www-igm.univ-mlv.fr/~mac/ 2 UMLV  Plan du cours • Structures de données • Algorithmes, preuve, complexité • Récursivité • Types abstraits, listes, ensembles • Classements • Recherches • Algorithmique • Graphes et leurs traitements • Algorithmes sur les langages et automates • Traitement des chaînes de caractères 3 UMLV  Algorithmique Conception de méthodes pour la résolution de problèmes Description des données Description des méthodes Preuve de bon fonctionnement Complexité des méthodes Efficacité : temps de calcul, espace nécessaire, ... Complexité intrinsèque, optimalité Solutions approchées Réalisation - implémentation Organisation des objets Opérations élémentaires 4 UMLV  Modèle Mathématique Types de données abstraits Structures de données Algorithme informel ou abstrait Algorithme formalisé Super-Pascal Programme Pascal, C, Java, ... 5 UMLV  Algorithme Al Khowarizmi, Bagdad IXè siècle. Encyclopedia Universalis : « Spécification d’un schéma de calcul sous forme d’une suite finie d’opérations élémentaires obéissant à un enchaînement déterminé. » DONNÉES RÉSULTATS, ACTIONS Composition d ’un nombre fini d’opérations dont chacune est : • définie de façon rigoureuse et non ambiguë • effective sur les données adéquates (exécution en temps fini) 6 UMLV  Bibliographie Beauquier, Berstel, Chrétienne Éléments d’algorithmique, Masson, 1993. Sedgewick Algorithmes en C, InterÉditions, 1992. Aho, Hopcroft, Ullman Structures de données et algorithmes, InterÉditions, 1987. Cormen, Leiserson, Rivest Algorithmes, Dunod, 1994. 7 UMLV  Spécification d ’un algorithme : ce que fait l’algorithme cahier des charges du problème à résoudre Expression d ’un algorithme : comment il le fait texte dans un langage de type Pascal / C Implémentation d ’un algorithme : traduction du texte précédent dans un langage de programmation réel Bien distinguer ! 8 UMLV  Éléments de méthodologie • Programmation structurée • Modularité • Programmation fonctionnelle • Récursivité • Types abstraits de données • Objets • Réutilisabilité du code 9 UMLV  Exemple : classement Suite s = (7, 3, 9, 4, 3, 5) Suite classée c = (3, 3, 4, 5, 7, 9) (en ordre croissant) Spécification suite suite classée Méthode informelle (Bulles) tant que il existe i tel que si > si +1 faire échanger (si, si +1) Opérations élémentaires comparaisons transpositions d’éléments consécutifs 10 UMLV  Preuve Inversion : (i,j) tels que i < j et si > sj Inv(s) = nombre d’inversions dans la suite s Inv(7, 3, 9, 4, 3, 5) = 8 s = (s1, …, si-1, si, si+1, si+2, …, sn) échange de si et si+1 s’ = (s1, …, si-1, si+1, si, si+2, …, sn) Note : si si > si+1, alors Inv(s’) = Inv(s) - 1 c suite classée Inv(c) = 0 11 UMLV  Formalisation Algorithme Bulles1 répéter { i : = 1 ; tant que i < n et si ≤si+1 faire i := i + 1 ; si i < n alors {échanger (si, si+1) ; inversion := vrai ; } sinon inversion := faux ; } tant que inversion = vrai ; 12 UMLV  Temps de calcul Complexité en temps T(algo, d) = temps d'exécution de l'algorithme algo appliqué aux données d Éléments de calcul de la complexité en temps T(opération élémentaire) = constant T( si C alors I sinon J) ≤T(C) + max(T(I), T(J)) T( pour i ←e1 à e2 faire I i ) = T(e1) + T(e2) + Σ T(Ii) Temps de calcul de procédures récursives → solution d’équations de récurrence 13 Temps de calcul (suite) T(algo, d) dépend en général de d. Complexité au pire TMAX (algo, n) = max {T(algo, d) ; d de taille n} Complexité au mieux TMIN (algo, n) = min {T(algo, d) ; d de taille n} Complexité en moyenne TMOY (algo, n) = ∑ p(d).T(algo, d) d de taille n p(d) = probabilité d'avoir la donnée d TMIN (algo, n) ≤TMOY (algo, n) ≤TMAX(algo, n) UMLV  14 Algorithme Bulles2 { pour j := n-1 à 1 pas -1 faire pour i := 1 à j faire si si > si+1 alors échanger(si, si+1) ; } Temps d ’exécution TMAX (Bulles2, n) j donné →temps ≤k.j + k' TMAX (Bulles2, n) ≤ ∑(k.j + k') + k'' j ≤ + k'.(n-1) + k'' Nb comparaisons = Nombre d'échanges ≤ 2 1) ( . − n n k 2 1) ( − n n UMLV  2 1) ( − n n 15 Comparaisons de complexités Ordres de grandeur asymptotique "grand O" T(n) = O(f(n)) ssi ∃c > 0 ∃N > 0 ∀n > N T(n) ≤c.f(n) "grand oméga" T(n) = Ω(f(n)) ssi ∃c > 0 ∃N > 0 ∀n > N T(n) ≥c.f(n) "grand théta" T(n) = Θ(f(n)) ssi T(n) = O(f(n)) et T(n) = Ω(f(n)) Exemple (complexités au pire) T(BULLES2,n) = O(n2) = Ω(n2) T(BULLES1,n) = O(n3) = Ω(n3) UMLV  16 UMLV  Ordres de grandeur (exemples) 1, log n, n, n.log n, n2, n3, 2n n T(n) 1 Log n n 2 n 2n 17 UMLV  Évolution du temps Évolution de la taille quand la taille est quand le temps est 10 fois plus grande 10 fois plus grand 1 t ∞ log2n t + 3,32 n10 n 10 x t 10 x n n log2n (10 + ε) x t (10 - ε) x t n2 100 x t 3,16 x n n3 1000 x t 2,15 x n 2n t 10 n + 3,32 18 UMLV  Optimalité E (P) = ensemble des algorithmes qui résolvent un problème P au moyen de certaines opérations élémentaires. A ∈E (P) est optimal en temps (par rapport à E (P)) ssi ∀B ∈ E (P) ∀ donnée d T(B,d) ≥T(A,d) A ∈ E (P) est asymptotiquement optimal ssi T(A,n) = O(T(B,n)) Exemple ( complexité au pire) BULLES 2 est asymptotiquement optimal parmi les algorithmes de classement qui utilisent les opérations élémentaires : comparaisons, transpositions d’éléments consécutifs. Preuve : Inv((n,n-1, …,1)) = = O (n2) n n ( ) −1 2 19 UMLV  Remarques 1. Temps de conception ne doit pas être >> temps d ’exécution. 2. La complexité de la description nuit à la mise à jour d ’un algorithme. 3. Les constantes de proportionnalité peuvent être importantes si les données sont réduites. 4. Réduire le temps peut conduire à augmenter l’espace nécessaire 5. Pour les algorithmes numériques, la précision et la stabilité des valeurs sont des critères importants. 20 UMLV  P G C D Spécification Calculer pgcd(n,m), plus grand diviseur commun aux entiers ≥0, n et m. Algorithme 1 (n≥m) pour i : = m à 1 pas -1 faire si i divise n et m alors retour (i) pgcd (21,9) = 3 [21 = 3x7, 9 = 3x3] 7 étapes Algorithme d ’Euclide (300 avant J-C) division entière n = q.m + r, 0 ≤ r < m propriété : pgcd (n,m) = pgcd (m,r) pgcd(n,m) = si m = o alors n sinon pgcd(m, n mod m) Preuve : si n<m première étape = échange, sinon propriété arithmétique Terminaison : m décroît à chaque étape (strictement) pgcd(9,21) = pgcd(21,9) = pgcd(9,3) = pgcd(3,0) = 3 3 étapes 21 UMLV  Complexité Algorithme 1 T(Algo1, (n,m)) = O(min(m,n)) moins de 2.min(n,m) divisions entières Algorithme d’Euclide Théorème de Lamé (1845) : (n≥m) Si l ’algorithme d ’Euclide nécessite k étapes pour calculer pgcd (n,m) on a n≥m≥Fibk [Fib0 = 0, Fib1 = 1, Fibk = Fibk-1 + Fibk-2, pour k>1] pgcd(21,13) = pgcd(13,8) = pgcd(8,5) = pgcd(5,3) = pgcd(3,2) = pgcd(2,1) = pgcd(1,0) = 1 T(Euclide, (n,m)) = O(log min(n,m)) 22 UMLV  Version récursive function PGCD(n,m: integer): integer; {n>=0, m>=0} begin if m = 0 then return (n) else return (PGCD(m, n mod m)); end; Version itérative : function PGCD(n,m: integer): integer; {n>=0, m>=0} var temp; begin while m > 0 do begin temp := m; m := n mod m; n := temp; end; return (n); end; 23 UMLV  Version récursive : int PGCD(int n, int m){ /* n>=0, m>=0 */ if (m == o) return (n); else return ( PGCD(m, n % m)); } Version itérative : int PGCD(int n, int m){ /* n>=0, m>=0 */ int temp; while (m > o){ temp = m; m = n % m; n = temp; } return (n); } 24 Récursivité terminale fonction F(x) ; début si C(x) alors {I; retour (y); } sinon {J; retour (F(z)); } fin. SEUL APPEL RÉCURSIF Élimination (par copier-coller) : fonction F(x) ; début tant que non C(x) faire {J; x := z; } {I; retour (y); } fin. UMLV  25 Factorielle fonction FAC(n) ; fonction FAC'(n, m) début début si n=0 alors retour (1) si n=0 alors retour (m) sinon retour (n* FAC(n-1)) ; sinon retour (FAC'(n-1, n*m)) ; fin. fin. RÉCURSIVE RÉCURSIVITÉ TERMINALE fonction FAC(n) ; fonction FAC'(n, m) ; début début m: = 1 ; tant que n > 0 faire tant que n > 0 faire { m : = n* m ; n : = n-1 ; } { m := n* m ; n := n-1 ; } retour (m) ; uploads/s3/ chap-1 2 .pdf