le cours
Contents
1. Structures de donn es Le plan du cours Bibliographie Universit Blaise Pascal Bibliographie Universit Blaise Pascal Chapitre 1 Niveaux de description Olivier Raynaud Universit Blaise Pascal Chap 1 Niveaux de description Base conceptuelle d un ordinateur MICROORDINATEUR Extrait de Tis CLAVIER SOURIS ECRANS DISQUES CD DVD GRAVEUR IMPRIMANTES VIDEO MODEM RE SEAU Olivier Raynaud Universit Blaise Pascal Chap 1 Niveaux de description La m moire 2S EE E L Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Interpr tation Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Unit centrale et registre Olivier Raynaud Universit Blaise Pascal Chap 1 Niveaux de description Espace de stockage Nous contenan Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Variable Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Exemple variable compos e E E E Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description La r unitarisation Universit Blaise Pascal Chap 1 Niveaux de description Caract ristique d un langage Universit Blaise Pascal Chap 1 Niveaux de description Syntaxe et s mantique du langage Olivier Raynaud U2. Repr sentation des arbres binaires Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Principe d induction structurelle Universit Blaise Pascal 23 Chap 3 Type r cursifs et sch ma d induction Application du principe d induction Olivier Raynaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Arbres binaires complets ou presque Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Notion de chemin Olivier Ravnaud Universit Blaise Pascal 24 Chap 3 Type r cursifs et sch ma d induction Application du principe d induction Olivier Raynaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Les arbres complets d arit k Universit Blaise Pascal 25 Chap 3 Type r cursifs et sch ma d induction Application du principe d induction Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Les arbres binaires de recherche Universit Blaise Pascal 26 Chap 3 Type r cursifs et sch ma d induction Exemple Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma
3. Blaise Pascal 35 Chap 4 Type de donn es abstrait Impl mentation Olivier Raynaud Universit Blaise Pascal Chap 4 Type de donn es abstrait Comparaison d impl mentation Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait T D A Gestion de partition Universit Blaise Pascal 36 Chap 4 Type de donn es abstrait Gestion de partition Impl mentation L E E Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait Gestion de partition Impl mentation Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait Gestion de partition Impl mentation Olivier Ravnaud Universit Blaise Pascal 37 Chap 4 Type de donn es abstrait Pour r sumer E a Olivier Raynaud Universit Blaise Pascal Chapitre 5 Table de hachage Olivier Raynaud Universit Blaise Pascal Chap 5 Table de hachage Principe Olivier Ravnaud Universit Blaise Pascal 38 Chap 5 Table de hachage Table adressage direct El E Olivier Ravnaud Universit Blaise Pascal Chap 5 Table de hachage Table de hachage Olivier Ravnaud Universit Blaise Pascal Chap 5 Table de hachage R solution par cha nage Olivier Ravnaud Universit Blaise Pascal 39 Chap 5 Table de hachage Construction Olivier Raynaud Universit Blaise Pascal Cha
4. Blaise Pascal Chap 6 Complexit Temps d ex cution Extrait de GJ00 Olivier Ravnaud Universit Blaise Pascal 49 Chap 6 Complexit Extrait de GJ00 Projection Olivier Raynaud Universit Blaise Pascal Chap 6 Complexit Pour aller plus loin E L_ Olivier Ravnaud Universit Blaise Pascal Clermont Question Que faire fasse un probl me intraitable Chap 6 Complexit Pour aller plus loin E E Olivier Ravnaud Universit Blaise Pascal Question A quelle classe de complexit appartient un probl me donn 50 Chap 6 Complexit Pour r sumer E E a Olivier Ravnaud Universit Blaise Pascal Chapitre 7 Applications Olivier Raynaud Universit Blaise Pascal Chap 7 Application Applications E E Olivier Ravnaud Universit Blaise Pascal 51 Chap 7 Application Compression de donn es El es Olivier Raynaud je Universit Blaise Pascal Chap 7 Application Evaluation de la compression D finition Le quotient de compression est le degr de r duction des donn es et est gal au quotient Taille Originale Taille compress D finition Le taux de compression exprime en pourcentage l inverse du quotient de compression taux de compression 1 quotient de compression Olivier Ravnaud Universit Blaise Pascal Chap 7 Application Question Contexte Les
5. si p re i 0 alors retourner nil sinon retourner codage lp re i l nouvelleListe p rel i gt 0 fin Olivier Ravnaud Universit Blaise Pascal 55 Olivier Raynaud Universit Blaise Pascal Chap 7 Application Tran E Olivier Ravnaud Universit Blaise Pascal 56
6. d induction Cellules isol es Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Les listes cha n es Universit Blaise Pascal 19 Chap 3 Type r cursifs et sch ma d induction Les op rations l mentaires Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Les listes cha n es circulaires Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Sch ma inductif de construction 20 Chap 3 Type r cursifs et sch ma d induction La notion de classe Olivier Raynaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Les arbres Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Parcours Olivier Ravnaud Universit Blaise Pascal 21 Chap 3 Type r cursifs et sch ma d induction Quelques d finitions Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction t de sous classe Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction La classe des arbres binaires E m Olivier Ravnaud Universit Blaise Pascal 22 Chap 3 Type r cursifs et sch ma d induction Parcours en profondeur Olivier Raynaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction
7. pr fixe complet 3 Il existe une version dite statique et une version dite adaptative j Olivier Ravnaud Universit Blaise Pascal Chap 7 Application Construction et repr sentation Olivier Ravnaud Universit Blaise Pascal 54 Chap 7 Application Impl mentation On appellera code le produit cart sien sur les quatre champs cha ne liste d entiers taille entier p re tableau d entiers fr quence tableau d entier Les op rations e __nouveauCode s __code arbre e __code codage i code compression Olivier Raynaud Universit Blaise Pascal Clermont Ferrand Chap 7 Application M thode code arbre Algorithme code arbre Donn es self code R sultat le tableau p rel est m j Variables maFile filePriorit x y entier D but pour i taille faire maFile ins rer i frequenceli pour i taille 1 2 taille 1 faire x maFile minimum maFile maFile extraire y maFile minimum maFile lt maFile extraire frequenceli lt frequence x frequencel y p re x i p re y i maFile lt maFile ins rer i frequenceli in Universit Blaise Pascal Olivier Ravnaud Chap 7 Application M thode code codage Algorithme code codage Donn es self code i entier R sultat codage liste de bool ens D but
8. Chap 6 Complexit Exercices Question 1 valuer les poids relatifs de chacun des termes du polyn me 3x2 10x 5 Question 2 valuer les poids relatifs de chacun des termes de la fonction de complexit kx Ak Olivier Raynaud Universit Blaise Pascal Chap 6 Complexit Ordre de grandeur E m Olivier Ravnaud Universit Blaise Pascal Chap 6 Complexit Ordre de grandeur Question quelle peut tre l influence du codage et du mod le de machine pour l valuation de la complexit d un algorithme Olivier Ravnand Universit Blaise Pascal 47 Chap 6 Complexit Exemple de codage E E S Olivier Ravnaud Universit Blaise Pascal Chap 6 Complexit Comparaison de codage Olivier Ravna Ravnaud Universit Blaise Pascal Chap 6 Complexit Impact du mod le de machine simul e Olivier Ravna md 48 Chap 6 Complexit Algorithme polynomial D finition Un algorithme polynomial est un algorithme dont la complexit est en O p n avec p une fonction polynomiale quelconque Olivier Raynaud Universit Blaise Pascal Chap 6 Complexit Algorithme exponentiel D finition Un algorithme esten temps exponentiel si et seulement si il n est pas polynomial D finition Un probl me est dit intraitable s il est si difficile qu aucun algorithme polynomial puisse le r soudre Olivier Ravnaud Universit
9. cution d un algorithme donn E E Olivier Ravnaud Universit Blaise Pascal Chap 6 Complexit Op ration l mentaire D finition Une op ration l mentaire est une op ration qui s effectue en temps constant sur tous les calculateurs usuels Olivier Ravnaud Universit Blaise Pascal Chap 6 Complexit Fonction de complexit D finition La fonction de complexit temporelle d un algorithme exprime le temps requis par l algorithme pour calculer la solution correspondant une instance en fonction de la taille de celle ci Olivier Ravnaud Universit Blaise Pascal 45 Chap 6 Complexit Hypoth ses de simplification Pour valuer le nombres d op rations l mentaires on s appuie sur les param tres de description de la donn e Olivier Raynaud Universit Blaise Pascal Chap 6 Complexit Crit res d valuation Analyse dans le pire des cas t n maximum des temps d ex cution de l algorithme pour toutes les instances de taille n Analyse moyenne tmoy n moyenne des temps d ex cution de l algorithme pour toutes les instances de taille n Olivier Ravnaud Universit Blaise Pascal Chap 6 Complexit Ordre de grandeur Ordre de grandeur On dit qu une fonction f n est en O g n s il existe une constance c positive et non nulle telle que If n l_ lt c g n n20 Olivier Ravnaud Universit Blaise Pascal 46
10. d induction D finition par sch ma d induction E Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Quelques questions Olivier Ravnaud Universit Blaise Pascal 27 Chap 3 Type r cursifs et sch ma d induction Les tas Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Impl mentation par un tableau E Olivier Ravnaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma d induction Les tas relation de filiation E E Olivier Ravnaud Universit Blaise Pascal 28 Chap 3 Type r cursifs et sch ma d induction Pour r sumer El El Olivier Raynaud Universit Blaise Pascal Chapitre 4 Les types de donn es abstraits Olivier Raynaud Universit Blaise Pascal Chap 4 Type de donn es abstrait D finition Olivier Ravnaud Universit Blaise Pascal 29 Chap 4 Type de donn es abstrait Contraintes d impl mentation Olivier Raynaud Universit Blaise Pascal Chap 4 Type de donn es abstrait T D A Ensemble dynamique Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait T D A Dictionnaire Universit Blaise Pascal 30 Chap 4 Type de donn es abstrait Dictionnaire Impl mentation Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait T D A Pi
11. de description Pour r sumer Universit Blaise Pascal 10 Chapitre 2 Concepts de valeur et de type Olivier Raynaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Valeurs Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Classification g m Olivier Ravnaud Universit Blaise Pascal 11 Chap 2 Concept de type et de valeur En C Olivier Raynaud Universit Blaise Pascal Chap 2 Concept de type et de valeur et Types Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Types primitifs compos s Olivier Ravnaud Universit Blaise Pascal 12 Chap 2 Concept de type et de valeur Produit cart sien Olivier Raynaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Union disjointe Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur En Pascal E m Olivier Ravnaud Universit Blaise Pascal 13 Chap 2 Concept de type et de valeur En C E E E Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Les fonctions ou mapping Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Les tableaux comme mapping Olivier Ravnaud Universit Blaise Pascal 14 Chap 2 Concept de type et de valeur En Pascal E E E Olivi
12. er Raynaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Les fonctions comme mapping Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur En Pascal 2 E E Olivier Ravnaud Universit Blaise Pascal 15 Chap 2 Concept de type et de valeur Les types r cursifs Olivier Raynaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Exemple des listes Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Olivier Ravnaud Universit Blaise Pascal 16 Chap 2 Concept de type et de valeur Exemple de type r cursif ML E E Olivier Raynaud Universit Blaise Pascal Chap 2 Concept de type et de valeur pe r cursif vs Pointeur E E El Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur En C Olivier Ravnaud Universit Blaise Pascal 17 Chap 2 Concept de type et de valeur Les syst mes de type E E E Olivier Raynaud Universit Blaise Pascal Chap 2 Concept de type et de valeur V rification de type E E L Olivier Ravnaud Universit Blaise Pascal Chap 2 Concept de type et de valeur Pour r sumer E l E Olivier Ravnaud Universit Blaise Pascal 18 Chapitre 3 Types r cursifs et sch ma d induction Olivier Raynaud Universit Blaise Pascal Chap 3 Type r cursifs et sch ma
13. le Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait piles applications Olivier Ravnaud Universit Blaise Pascal 31 Chap 4 Type de donn es abstrait Les piles Impl mentation Olivier Raynaud Universit Blaise Pascal Chap 4 Type de donn es abstrait T D A File Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait Les files applications E E Olivier Ravnaud Universit Blaise Pascal 32 Chap 4 Type de donn es abstrait Les files Impl mentation Universit Blaise Pascal Chap 4 Type de donn es abstrait Les files Impl mentation Universit Blaise Pascal Chap 4 Type de donn es abstrait Comparaison d impl mentation Universit Blaise Pascal 33 Chap 4 Type de donn es abstrait T D A Files de priorit Olivier Raynaud Universit Blaise Pascal Chap 4 Type de donn es abstrait File de priorit Impl mentation Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait T D A Famille d ensembles Universit Blaise Pascal 34 Chap 4 Type de donn es abstrait Impl mentation et complexit Olivier Raynaud Universit Blaise Pascal Chap 4 Type de donn es abstrait Olivier Ravnaud Universit Blaise Pascal Chap 4 Type de donn es abstrait L arbre lexicographique Olivier Ravnaud Universit
14. m thodes actuelles pour compresser du texte admettent des taux de compression de 50 pour des images statiques le taux est de 80 et pour des images de films le gain est de l ordre de 95 Olivier Ravnaud Universit Blaise Pascal 52 Chap 7 Application Les m thodes a Olivier Raynaud Universit Blaise Pascal Chap 7 Application Code pr fixe E L Olivier Ravnaud Universit Blaise Pascal Clermont D finition Un ensemble P de mots non vides est un code pr fixe si aucun des mots de P n est pr fixe propre d un autre mot de P Chap 7 Application Code pr fixe complet E E Olivier Ravnaud Universit Blaise Pascal D finition Un ensemble P de mots non vides est un code pr fixe complet si tout mot est pr fixe d un produit de mots de P 53 Chap 7 Application Probl matique EX ss Olivier Raynaud Probl me Codage arborescent Entr e un texte coder Sortie un code pr fixe complet Relation le code pr fixe complet qui minimise la taille du texte cod Universit Blaise Pascal Chap 7 Application Algorithme de Huffman Ils agit d un algorithme statistique qui affecte chaque caract re d un texte en clair un code sous forme binaire 1 La longueur du code d une lettre est fonction de la fr quence d apparition de la lettre 2 Le d codage est rendu facile par le choix d un code
15. niversit Blaise Pascal Chap 1 Niveaux de description Le Langage machine Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Le langage d assemblage E E Universit Blaise Pascal Chap 1 Niveaux de description Un morceau d A D N E E E Olivier Raynaud Universit Blaise Pascal Chap 1 Niveaux de description L assembleur Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Les langages de compilation E Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Les trois niveaux de description L E E Olivier Raynaud Universit Blaise Pascal Chap 1 Niveaux de description Les compilateurs Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description L amor age Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Les interpr teurs E E Olivier Raynaud Universit Blaise Pascal Chap 1 Niveaux de description Historique Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Langage de description d BH E m Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux de description Math matique fonction calculable Olivier Raynaud Universit Blaise Pascal Chap 1 Niveaux de description La th se de Alonso Church Olivier Ravnaud Universit Blaise Pascal Chap 1 Niveaux
16. p 5 Table de hachage M thode la division Olivier Ravnaud Universit Blaise Pascal Chap 5 Table de hachage Hachage universel Olivier Ravnaud Universit Blaise Pascal 40 Chap 5 Table de hachage Hachage universel Olivier Raynaud Universit Blaise Pascal Chap 5 Table de hachage Adressage ouvert Olivier Ravnaud Universit Blaise Pascal Chap 5 Table de hachage Num ro de sondage Universit Blaise Pascal 41 Chap 5 Table de hachage Hachage uniforme Olivier Raynaud Universit Blaise Pascal Chap 5 Table de hachage Sondage lin aire Olivier Ravnaud Universit Blaise Pascal Chap 5 Table de hachage Sondage quadratique Universit Blaise Pascal 42 Chap 5 Table de hachage Sondage par double hachage Olivier Raynaud Universit Blaise Pascal Chap 5 Table de hachage Pour r sumer E E E Olivier Ravnaud Universit Blaise Pascal Chapitre 6 Complexit Olivier Raynaud Universit Blaise Pascal 43 Chap 6 Complexit Qu est ce qu un probl me Olivier Raynaud Universit Blaise Pascal Chap 6 Complexit Un algorithme Olivier Ravnaud Universit Blaise Pascal Chap 6 Complexit Evaluation d algorithmes Olivier Ravnaud Universit Blaise Pascal 44 Chap 6 Complexit Evaluation des temps d ex cution Probl matique Comment valuer le temps d ex
Download Pdf Manuals
Related Search