PrérequisMathématiques et algorithmique (S1-S2-S3)
ValidationCC+examen
Enseignant
Horaires hebdomadaires 2 h CM , 3 h TD

Syllabus

Le cours est une introduction aux objets discrets en mathématiques et à la théorie des graphes.

Sommaire

Après de rapides rappels sur les ensembles (y compris les fonctions et les relations) et leur cardinal, on s'intéressera à la théorie des graphes et à ses fondements. On étudiera plusieurs algorithmes et techniques de preuves sur les graphes (études de cas simples, généralisations, preuves par induction). Dans une dernière partie, on introduira les fonctions génératrices et certaines de leurs applications.

Bibliographie

Invitation to Discrete Mathematics, Jiri Matousek and Jaroslav Nesetril