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é.

À 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 :
- 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.
 

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