De la combinatoire aux graphes

De la combinatoire aux graphesCode de l'UE : HLIN201

Présentation

La première partie de ce module commence par de rapides rappels des mathématiques de base nécessaires à l'informatique fondamentale
et vus lors de modules du premier semestre : ensembles, relations, applications, preuves par récurrence et induction.
Nous approfondirons ensuite la notion de cardinalité des ensembles et les relations binaires (relations d'ordre et d'équivalence).
Nous verrons les grands principes de dénombrement (arrangement, permutation, principe des tiroirs, ...).
Nous traiterons des ensembles définis par induction et des preuves par induction structurelle associées.
La deuxième partie introduit la notion de graphe (version orientée et non orientée) et les définitions de base associées : degrés, connexité,
cheminement, arbres. Nous énoncerons plusieurs propriétés de graphes. Nous nous servirons des graphes comme supports aux principes
vus lors de la première partie, notamment en s'attachant à la démonstration de propriétés sur les graphes.

Objectifs

Maîtrise des mathématiques de base nécessaires à l'informatique fondamentale
Premières notions de graphes
Faire des démonstrations/soutenir un raisonnement

Pré-requis recommandés

Maîtrise des notions d'ensembles, de relations, d'applications.

Volume horaire

  • CM : 19.5
  • TD : 30
  • TP : 0

Syllabus

Mathématiques pour l’informatique avec exercices - A. Arnold et I. Guessarian - 4e édition - Edisciences -
EAN13 : 9782100492305

Diplômes intégrant cette UE

En bref

Crédits ECTS 7.5

Langue d'enseignement
fr

Contact(s)

Contact(s) administratif(s)

Severine BERARD (severine.berard @ umontpellier.fr)