Acquis d'apprentissage

Développer l'aptitude mathématique dans le cadre de l'algorithmique liée à la théorie des graphes et dans la modélisation du comportement dynamique de systèmes discrets. L'intérêt du cours réside dans l'énorme potentiel de modélisation constitué par les graphes.

Le cours présentera divers problèmes liés à la vie réelle - comme l'algorithme de recherche de Google, la recherche du plus court chemin pour un système GPS, l'assignation de tâches à un groupe de personnes ou de machines, la programmation d'une IA jouant aux échecs, etc. - et développera à chaque fois les concepts et théories mathématiques derrière ces problèmes ainsi que les algorithmes pour les résoudre.
 

Contenu

Graphes connexes, eulériens et bipartis, Plus court chemin, Arbres et connectivite, Intelligence artificielle en théorie des jeux, Graphes hamiltoniens, Mariages, couplages et couvertures, Coloriages d'arêtes et Théorie de Ramsey, Cliques et ensembles indépendants, Coloriages de sommets, Graphes planaires, NP-complétude, Grands et très grands graphes,...

 
 

Méthodes d'enseignement

Cours magistral et scéances d'exercices.

 
 

Méthode d'évaluation

Un examen uniquement écrit portant à la fois sur la théorie et sur des exercices, dont le contenu est le suivant :

- Partie théorie (50%) : présentation et explication des concepts, théorèmes ou algorithmes présentés au cours, restitution de démonstrations.

- Partie exercices (50%) : exercices d'application du même genre que ceux proposés en séances de travaux dirigés.

L'entièreté de l'examen sera à cours fermé. L'examen est strictement individuel, aucune aide extérieure ni l'utilisation de matériel électronique n'est autorisée.

 

 

Sources, références et supports éventuels

Syllabus (en construction) disponible sur Webcampus.

 
 

Langue d'instruction