Structures de données et algorithmes 2

Description

Cette UE présente les structures de données relationnelles 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 (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 requises

À l'entrée de cette UE, un étudiant devrait savoir manipuler, analyser et comparer des structures de données simples (i.e. linéaires, e.g., listes, files, etc) et concevoir des algorithmes basiques de leur spécification à leur implémentation pour résoudre efficacement des problèmes concrets.

En pratique il s’agit des compétences développées en AlgoProg (L1.S1 et L1.S2) et SDA1 (L2.S3) 

Compétences visées

• Capacité à abstraire et analyser un problème à résoudre algorithmiquement ;

• Spécifier le problème et sa solution en utilisant des types abstraits ;

• S’appuyer sur la spécification pour programmer des types : tables, graphes et arbres;

• Programmer ces spécifications de plusieurs manières possibles en langage C et être capable d’en choisir une qui permette de répondre de manière efficace au problème posé ;

• Calculer la complexité en temps et en espace dans quelques cas simples ;

Discipline(s)

• Informatique

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.
 

Contact