Matière
Structures de données et algorithmes 1
Description
Cet enseignement vise à déployer une démarche rigoureuse de résolution de problèmes informatique afin de tendre ensuite vers du code certifié. La démarche proposée consiste à définir la notion de type abstrait avec une méthode de spécification dans laquelle on précise une signature contenant des types et des fonctions et les relations exigées entre ces différentes fonctions. On introduit le formalisme de spécifications en relation avec la programmation. Cette méthodologie est utilisée pour décrire des types de données de base et 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é. Enfin, les qualités de complétude, de consistance et de non-redondance d'une spécification ainsi que la validité d'une implantation relativement à une spécification seront présentées.
Compétences requises
Algorithmique et Programmation 2 en L1 S2
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 simples ;
-
S’appuyer sur la spécification pour programmer des types linéaires : piles, files, listes ;
-
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 ;
- Démontrer les qualités d’une spécification au travers de propriétés déductives ou de théorèmes inductifs.
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.