Notes de cours
Notes de coursLes transparents de C. Carrez sont issus de l'ouvrage: "Structures de données en Java, C++ et Ada95" C. Carrez, Masson 1997.
Ce chapitre décrit les caractéristiques des principaux supports de mémorisation des informations, c'est-à-dire, essentiellement la mémoire centrale, les disques et les bandes magnétiques. Version pdf (772ko)
Nous introduisons la notion d'algorithme comme ensemble de règles opératoires pour résoudre un problème en un nombre fini d'opérations. Ce nombre, induisant le temps d'exécution de l'algorithme, doit avoir une valeur "raisonnable". L'étude de la complexité d'un algorithme permet de connaître l'évolution de son efficacité suivant la taille des données à traiter. Version pdf (69 ko)
Les types abstraits seront à la base de la présentation des structures de données. Ils permettent de distinguer la syntaxe (signature), la sémantique et l'implantation. Ils servent de guide à la conception des structures, qui sont ensuite traduites en programme lors de l'implantation. Une démonstration permet de montrer un tel type abstrait en tant que boîte noire. Nous évoquons ensuite quelques notions à prendre en compte au cours de l'implantation dans un langage de programmation. Version pdf (113 ko)
Les structures séquentielles, ou listes, sont les structures les plus simples et les plus employées en informatique. Elles permettent de structurer une collection sous la forme d'une suite, qui peut être parcourue du début à la fin. Elles permettent de faire un traitement une fois et une seule sur tous les éléments de la collection, dans l'ordre où ils ont été rangés dans la liste.
Partie 1 - structures séquentielles contigues (Version pdf 228 ko)
Partie 2 - structures séquentielles chaînées (Version pdf 334 ko)
Les structures arborescentes, ou arbres sont les structures de données les plus importantes en informatique. Ayant une couverture plus large d'applications, elles sont néanmoins encore assez simples dans leur manipulation. Elles permettent une meilleure efficacité des algorithmes qui les utilisent par la possibilité qu'elles offrent d'accéder à un élément de la collection plus rapidement que dans les structures séquentielles.
Structures arborescentes (Version pdf 254 ko)
L'étude des algorithmes de tri est surtout l'occasion de montrer qu'un même problème peut avoir plusieurs solutions dont l'efficacité peut être très différente lorsque la taille des données est importante. Pour chacun des tris présentés, une démonstration est disponible.
Nous montrons tout d'abord comment définir un algorithme de tri avec le minimum de contrainte sur l'algorithme effectif. Par affinement, on peut ensuite préciser quelques méthodes simples. Version pdf (104 ko)
Nous abordons ici deux algorithmes efficaces, le tri par tas et le tri rapide. Version pdf (82 ko)
Nous comparons ici les données de complexités et les mesures effectuées sur les programmes effectifs. Nous complétons cette étude en évoquant les paramètres influant sur le temps d'exécution des algorithmes de même complexité. Version pdf (38 ko)
La recherche d'informations est un problème classique de l'informatique. Cette partie étudie la mise en oeuvre des structures de base pour résoudre ce problème.
La première idée est d'utiliser une liste pour structurer les informations, mais une telle solution n'est pas très efficace pour un grand nombre d'informations. Une démonstration de la recherche dans une liste contiguë est disponible.La structure en tas peut aussi être une solution pour des problèmes spécifiques (recherche du plus petit). Version pdf (53 ko)
L'utilisation des structures arborescentes sont un autre moyen d'aborder la recherche. Les arbres binaires de recherche sont introduits ainsi que les opérations qui leur sont attachées (recherche, adjonction et suppression). Nous mettons en évidence la complexité moyenne logarithmique de ces opérations, ce qui est un avantage certain sur les structures séquentielles. Cependant nous n'évitons pas d'avoir une complexité linéaire dans le pire des cas. Version pdf (168 ko)
Pour éviter de rencontrer le cas le pire, il faut équilibrer l'arbre de recherche en permanence. Les arbres AVL permettent de montrer comment des opérations de rotation simples et ponctuelles peuvent transformer complètement un arbre de façon à limiter les déséquilibres, et obtenir des opérations de complexité au pire d'ordre logarithmique. Une démonstration est également disponible. Version pdf (121 ko)
Les arbres balancés sont une certaine forme de généralisation des arbres AVL qui permet de prendre en compte une caractéristique du disque: la taille des blocs transférés. Leur application immédiate est la structure de fichier séquentiel indexé. Une démonstration est également disponible. Version pdf (154 ko)
On ne peut parler de recherche sans aborder la notion de hachage. Nous en présentons les principes, ainsi que l'une des méthodes de résolution des collisions, adaptée à la mémorisation sur disque. Version pdf (65 ko)
En conclusion du cours, nous présentons une étude de cas, l'analyse d'un fichier client. Cette étude est l'occasion de passer en revue les différentes structures étudiées dans le cours, en vue de trouver une solution efficace au problème posé. Version pdf (81 ko)