Structures de données et algorithmes 2
Cursus master ingénierie (CMI)Parcours Cursus master ingénierie (CMI) - Informatique, image, réalité virtuelle, interactions et jeux
Description
Cette UE présente de nombreuses structures de données classiques :
- Tables : avec adressage calculé, associatif, indexé, partagé et haché;
- Arbres et forêts : binaires, généraux, préfixés, (auto-)équilibrés, e.g., AVL et B-arbres;
- Graphes : non orientés, orientés, acycliques, etc.
Au niveau algorithmique, il s’agira principalement d’étudier les algorithmes de parcours classiques (en profondeur et en largeur), la dérécursivation et les algorithmes de tri (interne ou externe). Les algorithmes de tri en particulier seront utilisés pour illustrer et approfondir les notions d’optimalité et de complexité introduites en SDA1. Sur les graphes, seuls quelques exemples seront traités : la fermeture transitive avec l’algorithme de Warshall et le calcul d’une forêt de recouvrement dans le cas orienté (algorithme de Tarjan).
Dès lors que la notion de type abstrait des structures étudiées aura été formellement introduite et définie (par exemple avec la méthode de spécification algébrique initiée en SDA1), la seconde étape consistera à rigoureusement spécifier les algorithmes manipulant ces structures. Cette spécification sera essentiellement réalisée sous une forme équationnelle équivalente à une approche fonctionnelle mais, sur certains exemples, on raffinera la spécification pour produire des algorithmes itératifs traduits ensuite dans un pseudo-langage impératif. Enfin, il s’agira d’aller au bout de la démarche avec des implantations concrètes en programmation impérative, par exemple en C.
Compétences visées
À l'issue de cette UE un étudiant saura d'une manière générale spécifier, programmer et implanter de façon efficace des algorithmes et des structures de données les plus pertinentes pour résoudre des problèmes concrets, ou, en détaillant
- maîtriser et manipuler une variété de structures de données classiques ;
- utiliser et comparer les principaux algorithmes manipulant ces structures de données;
- choisir les structures de données les plus adaptées aux problèmes à résoudre;
- évaluer la complexité en temps et en espace des solutions retenues.
Bibliographie
Bibliographie :
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Algorithmique. Dunod, 2010. ou
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (en anglais), PHI Learning, 2010.
- J-F. Dufourd, D. Bechmann, Y. Bertrand, Spécifications algébriques, Algorithmique et Programmation. InterEditions, Octobre 1995.
- R. Sedgewick. Algorithmes en langage C. Dunod, 2005.