Cours 2021-2022

Théorie des graphes et réseaux de Petri [IHDCM321]

  • 4 crédits
  • 30h+15h
  • 2e quadrimestre
Langue d'enseignement: Français

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

Disciplines

Théorie des graphes

Mode 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'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté d'informatique
rue Grandgagnage 21
5000 NAMUR
T. 081725252
F. 081724967
secretariat.info@unamur.be

Cycle

Etudes de 2ème cycle