L'unité d'enseignement « Éléments de structures discrètes pour l'algorithmique » est une UE de niveau (200) approfondissement relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines en alternance. Elle est placée sous la responsabilité de David, alain.

Description

Ce cours est consacré d'une part, à l'acquisition d'outils permettant une écriture raisonnée des algorithmes et, d'autre part, à l'étude des principaux types de données et algorithmes fondamentaux.

Dans un premier temps nous présenterons des éléments mathématiques utiles pour l'informatique : systèmes de numération, calcul booléen, calcul propositionnel, récurrence et récursivité, introduction à l'évaluation des algorithmes.

L'apprentissage d'une écriture raisonnée des algorithmes se fera à travers les approches récursive et itérative de la programmation.

Nous étudierons enfin les structures de données linéaires et arborescentes et les algorithmes élémentaires sur les graphes et les automates.

Préalables et buts pédagogiques

Bibliographie

• J. Vélu, Méthodes mathématiques pour l'informatique, Dunod, Paris, 2005.

• A. Arnold, I. Guessarian, Mathématiques pour l'informatique, Avec exercices corrigés, Dunod, 2005.

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction à l'algorithmique, Dunod, 2002.

• D. Beauquier, J. Berstel, Ph. Chrétienne, Éléments d'Algorithmique, Masson, Paris, 1997.

Contenu indicatif par semaine

1. Systèmes de numération

2. Calcul booléen

3. Calcul propositionnel

4. Récurrence et récursivité

5. Programmation récursive

6. Programmation itérative

7. Introduction à l'évaluation des algorithmes

8. Structures de données linéaires

9. Structures de données arborescentes

10. Graphes : définitions et représentations

11. Cheminement dans les graphes

12. Automates finis