Vous êtes ici :

UFR de mathématique et d'informatique

Information importante

La page que vous consultez correspond à l'offre de formation 2023-2024.

Trouvez votre formation pour l'année universitaire 2024-2025

Structures de données et algorithmes 2

  • Cours (CM) 20h
  • Cours intégrés (CI) -
  • Travaux dirigés (TD) 22h
  • Travaux pratiques (TP) 12h
  • Travail étudiant (TE) -

Langue de l'enseignement : Français

Niveau de l'enseignement : B2-Avancé - Utilisateur indépendant

Description du contenu de l'enseignement

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 à acquérir

À 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, lectures recommandées

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.
 

Pré-requis obligatoires

À 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 1 (L1.S1) & 2 (L1.S2) et SDA1 (L2.S3)
 

Contact

UFR de mathématique et d'informatique

7, rue René Descartes
67084 STRASBOURG CEDEX
0368850200

Formulaire de contact

Responsable

Pascal Merindol


Cursus master ingénierie (CMI)

Partenaires

Logo du CNRS
Logo Établissement associé de l'Université de Strasbourg
Logo du réseau Epicur
Logo de EUCOR, Le Campus européen
Logo de l'Inserm Grand Est
Logo de l'Inria

Labels

Logo du label Bienvenue en France
Logo du programme HRS4R
Logo du programme France 2030
Logo de Service Public+

Réseaux

Logo de France Universités
Logo de la Ligue européenne des universités de recherche (LERU)
Logo du réseau Udice
Logo de l'Université franco-allemande