Graphes et Languages (MATH531_IDU)
Présentation
Ce cours vise à acquérir les connaissances sur la théorie des graphes et leurs applications afin d'être capable d'utiliser cet outil informatique pour modéliser des problèmes de représentation de données et les manipuler. Ce cours vise également, en s'appuyant sur la théorie des graphes, à acquérir les connaissances sur la théorie des langages afin d'être capable de concevoir un langage pour une application cible.
Objectifs
À l'issue du cours, l'étudiant sera capable :
- de choisir une structure arborescente - générique, N-aire - adaptée à une problématique donnée,
- de concevoir et d'implémenter des algorithmes itératifs et récursifs dédiés aux arborescences N-aires,
- de concevoir et implémenter des algorithmes itératifs et récursifs dédiés aux arborescences génériques,
- de choisir une structure de graphe adaptée à une problématique donnée,
- d'implémenter des algorithmes classiques dédiés aux parcours de graphes,
- de concevoir et implémenter un langage rationnel,
- de concevoir et implémenter un langage basé sur un lexique et une grammaire.
Heures d'enseignement
| Cours Magistral | 12h | |
| Travaux Dirigés | 12h | |
| Travaux Pratiques | 16h |
Pré-requis obligatoires
INFO501 (Base de la programmation Python)
Plan du cours
- Arbres et arborescences
- Structures de données (séquentielles et récursives)
- Primitives sur les arbres
- Algorithmiques de parcours d'arbres (profondeur/largeur, préfixe/infixe/postfixe...)
- Arbres binaires (de recherche, rouge/noir...)
- Graphes
- Structures de données (matricielle et ensembliste)
- Primitives sur les graphes
- Algorithmiques de parcours de graphe (plus court chemin, arbre recouvrant, flots...)
- Théorie des langages
- Langage rationnel
- Automates à états finis
- Lexique et grammaire
TP1 Tri de données : Arbre binaire de recherche (ABR)
TP2 Ordonnancement de tâches : Graphes orientés acycliques (DAG)
TP3 Voyageur de commerce
TP4 Parler l'Idule (langue des IDU) : conception d'un langage
Contacts
