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. Ce cours introduit à l'analyse de la complexité théorique des algorithmes . L'intérêt du cours réside dans l'énorme potentiel de modélisation constitué par les graphes.

Contenu

Graphes connexes, eulériens et bipartis Plus court chemin Arbres et connectivite Graphes hamiltoniens Mariages, couplages et couvertures Coloriages d'arêtes Cliques, ensembles indépendants et l'impossible désordre Coloriages de sommets Graphes planaires Flots et coupes P, N P et N P-complétude Grands et très grands graphes

Méthode d'évaluation

L'évaluation repose sur un travail personnel en lien avec la théorie des graphes pour lequel chaque étudiant remet un travail écrit qu'il défend lors d'une présentation orale. Cette présentation est suivie de quelques questions théoriques et quelques questions sur des exercices similaires à ceux réalisés en TDs, qui permettent de tester la compréhension des différents concepts abordés et de moduler la note finale.

Sources, références et supports éventuels

Syllabus et slides disponible sur Webcampus

Langue d'instruction

Formation Programme d’études Bloc Crédits Obligatoire
Master 60 en sciences informatiques (horaire décalé) Standard 0 4
Master 60 en sciences informatiques (horaire décalé) Standard 1 4