Graphes et langages (M2201) (MATH221_INFO)

Volume horaire

Présentation

Aborder des concepts et des outils centraux des mathématiques de l'informatique.

Objectifs

• Graphes orientés et non orientés, concepts et outils
• Problèmes usuels (cheminements, affectation, flots, etc.) et exemples d'algorithmes de résolution
• Langages, expressions rationnelles (regular expressions), automates finis, opérations usuelles sur les langages
• Coloration de graphes

Compétences acquises

Modéliser à l'aide de graphes et d'automates.

Pré-requis

M1201 : Mathématiques discrètes

M1202 : Algèbre linéaire

Informations complémentaires

Modalités de mise en oeuvre :

• illustration par les bases de données, la gestion et les langages de programmation ;
• recherche par expression rationnelle.

Prolongements possibles :

• complexité des algorithmes ;
• planarité.

Diplômes intégrant ce cours

• DUT Informatique