Notions préliminaires :
-
Rappel succinct des propriétés et caractéristiques essentielles des supports de mémorisation, tels que la mémoire centrale, les disques et les bandes.
-
Notion de complexité des algorithmes : mesure d'efficacité en fonction de la taille du problème.
Les structures de données :
-
Les structures séquentielles et les structures arborescentes.
-
Principaux algorithmes liés à ces structures.
-
Différentes techniques d'implantation de ces structures : avantages et inconvénients.
L'utilisation des structures :
-
Principaux algorithmes de tri. Généralités et méthodes simples. Méthodes efficaces. Mesures et comparaisons entre ces algorithmes.
-
Principes de la recherche d'informations. Recherche séquentielle dans une liste quelconque. Recherche dichotomique dans une liste ordonnée pour laquelle on dispose de l'accès par le rang. Gestion d'un tas : solution efficace pour rechercher le plus petit élément d'un ensemble.
-
Utilisation de structures arborescentes pour la recherche. Les arbres binaires de recherche : recherche, adjonction et suppression. Évaluation de la complexité logarithmique en moyenne de ces opérations, et comparaison avec les structures séquentielles. Évaluation de la complexité au pire linéaire : amélioration par rééquilibrage donnant les arbres AVL. Analyse des opérations simples de rotation ponctuelle pour conserver l'équilibre.
-
Généralisation des arbres AVL aux arbres balancés pour prendre en compte une caractéristique des disques : la taille des blocs transférés. Application aux fichiers séquentiels indexés.
-
Recherche utilisant la notion de hachage : principes et méthodes de résolution des collisions.
Remarque : Implantations proposées au moyen de paquetages Ada génériques disponibles en machine (ou modules Java ou C++), pour que les élèves puissent les utiliser lors de travaux pratiques personnels, et apprennent ainsi les notions fondamentales de réutilisation du logiciel.
|
