1. Objectifs du cours

Ce cours couvre les thèmes suivants de mathématiques discrètes : principes de dénombrement et analyse combinatoire ; théorie des graphes et des arbres ; fonctions génératrices ; introduction aux langages formels. Des thèmes sous- jacents à ces thèmes principaux sont aussi abordés : preuve par récurrence, suites définies par récurrence, ordre et préordre en sont des exemples. 

Les méthodes formelles utilisées en informatique s'appuient essentiellement sur des concepts mathématiques, comme la théorie des ensembles, la logique, les mathématiques combinatoires ou encore la théorie des graphes (dont l'application à un réseau de communication permet d'introduire des notions très complexes comme, par exemple, les répartitions de charge et de trafic sur Internet).

C’est un rappel des notions indispensables en logique et en algorithmique : théorie des ensembles, relations, fonctions, combinatoire, théorie des graphes et algèbre de boole. Chaque notion est illustrée d'un exemple concret, appliqué à l'informatique ou à l'électronique. 

2. Objectifs spécifiques Les sujets étudiés dans le cours: 

A- Dénombrement 

• Notions de base 

• Permutations et combinaisons 

• Principe d'inclusion-exclusion 

B -Relations de récurrence 

• Notions de base et applications 

• Relations linéaires 

C -Fonctions génératrices 

• Définition et propriétés élémentaires 

• Applications 

D-Graphes 

• Notion de base 

• Isomorphismes 

• Connexité 

• Arbres 

• Chaînes eulériennes et hamiltoniennes 

• Graphes planaires 

• Coloriage de graphes

3. Prérequis

CONDITIONS PRÉALABLES : MAT 130 ou supérieur ou équivalents ou placement par test