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 1

  • 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 unité d'enseignement vise à définir la notion de type abstrait avec une méthode de spécification algébrique dans laquelle on précise une signature contenant des types et des fonctions (encapsulation) et les relations exigées entre ces différentes fonctions (spécification équationnelle). On introduit le formalisme des spécifications algébriques en relation avec le concept de modèle (programmation par contrat). Cet outillage théorique est utilisé pour décrire des types de données de base comme les couples, par exemple, puis les types linéaires simples classiques que sont les piles, les files et les listes. Pour chaque type abstrait, les différentes possibilités d'implantation en langage C sont discutées et comparées suivant des critères d'efficacité en temps et en espace. C'est ainsi qu'on étudie des styles d'implantations statiques/fonctionnelles sans effets de bord et des styles d'implantations dynamiques avec des passages d'arguments par adresse. On donne aussi les premiers éléments qui permettent de comprendre la notion de complexité algorithmique et son utilité.

Compétences à acquérir

À l'issue de cette UE un étudiant devrait avoir les compétences suivantes :
- il possédera une certaine capacité à abstraire lui permettant d'analyser un problème ;
- il saura spécifier le problème et sa solution en utilisant des types abstraits simples ;
- il saura utiliser les types linéaires simples : piles, files, listes et ensemble ;
- il saura implanter ces spécifications de plusieurs manières possibles en langage C
et en choisir une qui permette de répondre de manière efficace au problème posé ;
- il saura calculer la complexité en temps et en espace dans quelques cas simples.

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

Les deux UEs d'algorithmique dispensées en L1, avec une bonne connaissance du langage C

Contact

UFR de mathématique et d'informatique

7, rue René Descartes
67084 STRASBOURG CEDEX
0368850200

Formulaire de contact


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