Graphes (INFO601_INFO)

Les graphes sont au cœur de nombreuses applications informatiques. Il suffit de citer leurs mises en œuvre dans les graphes de connaissances sur lesquels reposent les moteurs de recherche sur internet, les encyclopédies en ligne et les sites de commerce électronique. Il est donc indispensable de connaître les fondements de la théorie des graphes et les principaux algorithmes de parcours. Le cours commence par quelques notions théoriques sur les graphes (connexité, isomorphismes, chemins et cycles, etc.) avant d'en aborder les aspects algorithmiques : représentation en mémoire, algorithmes de parcours et de calcul d'arbres couvrants. Finalement, on considère différents problèmes d'optimisation sur les graphes (plus court chemin). Le cours se terminera sur une introduction aux graphes de connaissances et la prise en compte des relations dans les parcours de graphes. Les « property graphs » seront également cités.

TD/TP : Modélisation à l'aide de graphes, implémentation et utilisation des algorithmes vus en cours. Les TP sont réalisés dans le langage au choix de l’étudiant : Java, Python, C++…