Fondements de l’informatique - Structures de données et algorithmes

18h C / 6h TD / 18h EL / EE / 4 crédits ECTS

Claude Bocage (Gif), Frédéric Boulanger (Gif), Fabrice Popineau (Metz), Joanna Tomasik-Barth (Gif), Bernard Vivinis (Rennes)

Ce module poursuit deux objectifs : d'une part, introduire les concepts théoriques sous-jacents à la définition de structures de données et conception d'algorithmes, d'autre part, présenter les structures de données traditionnelles, leurs définitions abstraites et implémentations diverses. Des algorithmes classiques seront, à cette occasion, présentés. Ce module permettra, par ailleurs, de compléter la présentation du langage support de cours préalablement introduit lors du module «Modèles et langages de programmation».

Fondements de l'informatique

Types abstraits : spécification formelle algébrique, algèbre {S, ...}, profil, axiomes. Preuve de programme : validité, vérification a priori, invariant de boucle. Complexité des algorithmes : évaluation du temps de traitement, faisabilité. Complexité des problèmes : polynomiaux, NP-complets, exponentiels.

Structures de données et algorithmes

Définitions abstraites et implémentations des listes (dont les piles et files), des arbres, des graphes. Algorithmes de parcours d'arbres: en pré-ordre (profondeur), en ordre, en post-ordre, en largeur. Algorithmes sur les graphes : coloriage, recherche de chemin le plus court, calcul de flot. Algorithmes de classement : par insertion, par fusion, par tas (arbre binaire), tri rapide. Algorithmes de recherche et adressage dispersé. Back-tracking.

Bibliographie :

J-F. Dufourd, D. Bechmann, Y. Bertrand, «Spécification algébrique, algorithmique et programmation», Ed. Interéditions
M. Gondran, M. Minoux, «Graphes et algorithmes», 3e édition, Ed. Eyrolles
A. Aho, J. Ullman, «Concepts fondamentaux de l’informatique», Ed. Dunod.
C. Froidevaux, M-C. Gaudel, M. Soria, «Types de données et algorithmes», Ed. Ediscience International