Graphes et langages (MATH531_IDU)

Volume horaire

CM : 12h / TD : 12h / TP : 16h

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.

This course will introduce you to some of the key features of the language and theory of graphs. The main themes discussed are:

  • Properties of Tree, rooted tree and binary tree
  • Properties of directed and undirected graphs
  • Modelling of practical problems
  • Algorithms for the exploration of tree or graphs

Objectifs

Ce cours vise à rendre l'élève apte à :

Niveau

A l'issue de ce cours l'élève sera capable de :

modéliser des informations sous forme d'arbre afin de les manipuler de la manière la plus efficace possible

Maîtrise

de choisir une structure arborescente - générique, N-aire - adaptée à une problématique donnée.

de concevoir et 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

représenter des données sous forme de graphe et les manipuler de manière efficace.

Maîtrise

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

concevoir un langage adapté aux besoins

Maîtrise

de concevoir et implémenter un langage rationnel

de concevoir et implémenter un langage basé sur un lexique et une grammaire

Pré-requis

aucun

Plan du cours

  1. Arbres et arborescences
    1. Structures de données (séquentielles et récursives)
    2. Primitives sur les arbres
    3. Algorithmiques de parcours d'arbres (profondeur/largeur, préfixe/infixe/postfixe...)
    4. Arbres binaires (de recherche, rouge/noir...)
  2. Graphes
    1. Structures de données (matricielle et ensembliste)
    2. Primitives sur les graphes
    3. Algorithmiques de parcours de graphe (plus court chemin, arbre recouvrant, flots...)
  3. Théorie des langages
    1. Langage rationnel
    2. Automates à états finis
    3. Lexique et grammaire

Diplômes intégrant ce cours

En bref

Langue d'enseignement
Français

Contact(s)

UFR, Écoles, Instituts

Lieu(x)

  • Annecy-le-Vieux (74)